java邻接表代码实现,java图的邻接表

请编写一个完整的程序，建立有向图的邻接表存储结构，要求：

给你一个邻接表的完整程序：

目前创新互联已为近1000家的企业提供了网站建设、域名、网络空间、网站托管运营、企业网站设计、天水网站维护等服务，公司将坚持客户导向、应用为本的策略，正道将秉承"和谐、参与、激情"的文化，与客户和合作伙伴齐心协力一起成长，共同发展。

#include iostream.h

struct node

{

int data;

node *next;

};

class list

{

public:

list(){head=NULL;};

void MakeEmpty();

int Length();

void Insert(int x,int i);//将x插入到第i个结点（不含头结点）的之后

void Insertlist(int a,int b);//将节点b插入a之前

int Delete(int x);

int Remove(int i);

int Find(int x);

void Display();

private:

node *head;

};

void list::Display()

{

node *current=head;

while (current!=NULL)

{

coutcurrent-data" ";

current=current-next;

}

coutendl;

}

void list::MakeEmpty()

{

head=NULL;

}

int list::Length()

{int n=1;

node *q=head;

if(q==NULL)

n=1;

else

while(q!=NULL)

{

n++;

q=q-next;

}

return n;

}

int list::Find(int x)//在链表中查找数值为x的结点，成功返回1，否则返回0

{

node *p=head;

while(p!=NULLp-data!=x)

p=p-next;

if(p-data==x)

return 1;

else

return 0;

}

void list::Insert (int x,int i)//将x插入到第i个结点（不含头结点）的之后；

{

node *p;//p中放第i个结点

node *q;//q中放i后的结点

node *h;//h中存要插入的结点

h=new node;

h-data =x;

p=head;

if(p-next !=NULL) //链表不是只有一个结点或者空链表时候

{

int n=1;

while(p-next !=NULL)

{

n++;

p=p-next ;

}// 得到链表的结点的个数

p=head;//使p重新等于链首

if(i==n)//i=n时，直接加在最后面就行了

{

while(p-next !=NULL)

p=p-next;

p-next=h;

h-next =NULL;

}

else if(ini1)//先找到第i个结点，用p存第i个结点，用q存i后的结点，用h存要插入的结点

{

for(int j=1;ji;j++)

p=p-next;//找到第i个结点，用p存第i个结点

q=p-next;//q存i后的结点

p-next=h;

h-next=q;

}

else

cout"超出链表结点个数的范围"endl;

}

else

cout"这个链表是空链表或者结点位置在首位"endl;

}

void list::Insertlist(int a,int b)//将b插入到结点为a之前

{

node *p,*q,*s;//p所指向的结点为a,s所指为要插入的数b,q所指向的是a前的结点

s=new node;

s-data=b;

p=head;

if(head==NULL)//空链表的时候

{

head=s;

s-next=NULL;

}

else

if(p-data==a)//a在链首时候

{

s-next=p;

head=s;

}

else

{

while(p-data!=ap-next!=NULL)//使p指向结点a,q指向a之前的结点

{

q=p;

p=p-next;

}

if(p-data==a)//若有结点a时候

{

q-next=s;

s-next=p;

}

else//没有a的时候

{

p-next=s;

s-next=NULL;

}

}

}

int list::Delete(int x)//删除链表中值为x的结点，成功返回1，否则返回0；

{

node *p,*q;

p=head;

if(p==NULL)

return 0;

if(p-data==x)

{

head=p-next;

delete p;

return 1;

}

else

{

while(p-data!=xp-next!=NULL)

{ q=p;

p=p-next;

}

if(p-data==x)

{

q-next =p-next;

delete p;

return 1;

}

else

return 0;

}

}

int list::Remove(int i)

{

node *p,*q;

p=head;

if(p!=NULL)

{ int n=1;

while(p-next !=NULL)

{

n++;

p=p-next ;

}//得到链表结点的个数

p=head;

if(i==n)//i结点在结尾的时候

{

while(p-next!=NULL)

{

q=p;

p=p-next;

}

q-next=NULL;

delete p;

return 1;

}

else if(ini1)//i结点在中间的时候

{

for(int j=1;ji;j++)

{

q=p;//q中放i前的结点

p=p-next ;//p中放第i个结点

}

q-next=p-next;

delete p;

return 1;

}

else if(i==1)//i结点在首位的时候

{

q=p-next;

head=q;

delete p;

return 1;

}

else

return 0;

}

else

return 0;

}

void main()

{

list A;

int data[10]={1,2,3,4,5,6,7,8,9,10};

A.Insertlist(0,data[0]);

for(int i=1;i10;i++)

A.Insertlist(0,data[i]);

A.Display();

menu:cout"1.遍历链表"'\t'"2.查找链表"'\t'"3.插入链表"endl;

cout"4.删除链表"'\t'"5.链表长度"'\t'"6.置空链表"endl;

int m;

do

{

cout"请输入你想要进行的操作（选择对应操作前面的序号）："endl;

cinm;

}while(m1||m6);//当输入的序号不在包括中，让他重新输入

switch(m)

{

case 1:

{

A.Display ();

goto menu;

};break;

case 2:

{

cout"请输入你想要找到的结点："endl;

int c;

cinc;//输入你想要找到的结点

if(A.Find (c)==1)

{

cout"可以找到"cendl;

A.Display ();//重新显示出链表A

}

else

{

cout"链表中不存在"cendl;

A.Display ();//重新显示出链表A

}

goto menu;

};break;

case 3:

{

cout"请选择你要插入的方式(选择前面的序号进行选择）"endl;

cout"1.将特定的结点加入到特定的结点前"'\t'"2.将特定的结点加到特定的位置后"endl;

int b1;

do

{

cout"请输入你想要插入的方式（选择前面的序号进行选择）："endl;

cinb1;

}while(b11||b12);//当输入的序号不在包括中，让他重新输入

if(b1==1)

{

cout"请输入你想要插入的数和想要插入的结点（为此结点之前插入）："endl;

int a1,a2;

cina1a2;

A.Insertlist (a1,a2);//将a1插入到结点为a2结点之前

cout"此时链表为："endl;

A.Display ();//重新显示出链表A

}

else

{

cout"请输入你想要插入的数和想要插入的位置（为此结点之后插入）："endl;

int a1,a2;

cina1a2;

A.Insert (a1,a2);//将a1插入到结点位置为a2的结点之后

cout"此时链表为："endl;

A.Display ();//重新显示出链表A

}

goto menu;

};break;

case 4:

{

cout"请选择你要删除的方式(选择前面的序号进行选择）"endl;

cout"1.删除特定的结点"'\t'"2.删除特定位置的结点"endl;

int b1;

do

{

cout"请输入你想要插入的方式（选择前面的序号进行选择）："endl;

cinb1;

}while(b11||b12);//当输入的序号不在包括中，让他重新输入

if(b1==1)

{

cout"请输入你想要删除的结点："endl;

int a;

cina;//输入你想要删除的结点

if(A.Delete (a)==1)

{

cout"成功删除"aendl;

cout"删除后的链表为："endl;

A.Display ();

}

else

{

cout"此链表为："endl;

A.Display ();//重新显示出链表A

cout"链表中不存在"aendl;

}

}

else

{

cout"请输入你想要删除的结点位置："endl;

int b;

cinb;//输入你想要删除的结点的位置

if(A.Remove(b)==1)

{

cout"成功删除第"b"个结点"endl;

cout"删除后的链表为："endl;

A.Display ();//重新显示出链表A

}

else

{

cout"当前链表的结点个数为："A.Length ()endl;

cout"您输入的结点位置越界"endl;

}

}

goto menu;

};break;

case 5:

{

cout"这个链表的结点数为:"A.Length ()endl;

goto menu;

};break;

case 6:

{

A.MakeEmpty ();

cout"这个链表已经被置空"endl;

goto menu;

};break;

}

}

评论(3)|1

sunnyfulin |六级采纳率46%

擅长：C/C++JAVA相关Windows数据结构及算法百度其它产品

按默认排序|按时间排序

其他1条回答

2012-04-23 17:41121446881|六级

我写了一个C语言的，只给你两个结构体和一个初始化函数：

#include "stdio.h"

#include "malloc.h"

struct adjacentnext//邻接表项结构体

{

int element;

int quanvalue;

struct adjacentnext *next;

};

struct adjacenthead//邻接表头结构体

{

char flag;

int curvalue;

int element;

struct adjacenthead *previous;

struct adjacentnext *son;

};

//初始化图，用邻接表实现

struct adjacenthead *mapinitialnize(int mapsize)

{

struct adjacenthead *ahlists=NULL;

struct adjacentnext *newnode=NULL;

int i;

int x,y,z;

ahlists=malloc(sizeof(struct adjacenthead)*mapsize);

if(ahlists==NULL)

return NULL;

for(i=0;imapsize;i++)

{

ahlists[i].curvalue=0;

ahlists[i].flag=0;

ahlists[i].previous=NULL;

ahlists[i].son=NULL;

ahlists[i].element=i+1;

}

scanf("%d%d%d",x,y,z);//输入源结点，目的结点，以及源结点到目的结点的路权值

while(x!=0y!=0)//x,y至少有一个零就结束

{

newnode=malloc(sizeof(struct adjacentnext));

newnode-element=y;

newnode-quanvalue=z;

newnode-next=ahlists[x-1].son;

ahlists[x-1].son=newnode;

scanf("%d%d%d",x,y,z);

}

return ahlists;//返回邻接表头

}

新手求助，这是我找的Java邻接表的代码，第三行ArcNode next怎么理解，Java中不是没有指针吗？？？？？？

理解为一个ArcNode型的变量。其实java中任何一个非基本数据类型的变量名就相当于一个指针，只是一般不这么说罢了。

求代码，java实验，题目如图

import java.util.Scanner;

import java.util.Stack;

public class DFS

{

// 存储节点信息

private char[] vertices;

// 存储边信息（邻接矩阵）

private int[][] arcs;

// 图的节点数

private int vexnum;

// 记录节点是否已被遍历

private boolean[] visited;

// 初始化

public DFS(int n)

{

vexnum = n;

vertices = new char[n];

arcs = new int[n][n];

visited = new boolean[n];

for(int i = 0; i  vexnum; i++)

{

for(int j = 0; j  vexnum; j++)

{

arcs[i][j] = 0;

}

}

}

// 添加边(无向图)

public void addEdge(int i, int j)

{

// 边的头尾不能为同一节点

if(i == j)

return;

arcs[i - 1][j - 1] = 1;

arcs[j - 1][i - 1] = 1;

}

// 设置节点集

public void setVertices(char[] vertices)

{

this.vertices = vertices;

}

// 设置节点访问标记

public void setVisited(boolean[] visited)

{

this.visited = visited;

}

// 打印遍历节点

public void visit(int i)

{

System.out.print(vertices[i] + " ");

}

// 从第i个节点开始深度优先遍历

private void traverse(int i)

{

// 标记第i个节点已遍历

visited[i] = true;

// 打印当前遍历的节点

visit(i);

// 遍历邻接矩阵中第i个节点的直接联通关系

for(int j = 0; j  vexnum; j++)

{

// 目标节点与当前节点直接联通，并且该节点还没有被访问，递归

if(arcs[i][j] == 1  visited[j] == false)

{

traverse(j);

}

}

}

// 图的深度优先遍历（递归）

public void DFSTraverse(int start)

{

// 初始化节点遍历标记

for(int i = 0; i  vexnum; i++)

{

visited[i] = false;

}

// 从没有被遍历的节点开始深度遍历

for(int i = start - 1; i  vexnum; i++)

{

if(visited[i] == false)

{

// 若是连通图，只会执行一次

traverse(i);

}

}

}

// 图的深度优先遍历（非递归）

public void DFSTraverse2(int start)

{

// 初始化节点遍历标记

for(int i = 0; i  vexnum; i++)

{

visited[i] = false;

}

StackInteger s = new StackInteger();

for(int i = start - 1; i  vexnum; i++)

{

if(!visited[i])

{

// 连通子图起始节点

s.add(i);

do

{

// 出栈

int curr = s.pop();

// 如果该节点还没有被遍历，则遍历该节点并将子节点入栈

if(visited[curr] == false)

{

// 遍历并打印

visit(curr);

visited[curr] = true;

// 没遍历的子节点入栈

for(int j = vexnum - 1; j = 0; j--)

{

if(arcs[curr][j] == 1  visited[j] == false)

{

s.add(j);

}

}

}

} while(!s.isEmpty());

}

}

}

public static void main(String[] args)

{

Scanner sc = new Scanner(System.in);

int N, M, S;

while(true)

{

System.out.println("输入N M S，分别表示图G的结点数，边数，搜索的起点：");

String line = sc.nextLine();

if(!line.matches("^\\s*([1-9]\\d?|100)(\\s+([1-9]\\d?|100)){2}\\s*$"))

{

System.out.print("输入错误，");

continue;

}

String[] arr = line.trim().split("\\s+");

N = Integer.parseInt(arr[0]);

M = Integer.parseInt(arr[1]);

S = Integer.parseInt(arr[2]);

break;

}

DFS g = new DFS(N);

char[] vertices = new char[N];

for(int i = 0; i  N; i++)

{

vertices[i] = (i + 1 + "").charAt(0);

}

g.setVertices(vertices);

for(int m = 0; m  M; m++)

{

System.out.println("输入图G的第" + (m + 1) + "条边，格式为“i j”，其中i，j为结点编号（范围是1~N）");

String line = sc.nextLine();

if(!line.matches("^\\s*([1-9]\\d?|100)\\s+([1-9]\\d?|100)\\s*$"))

{

System.out.print("输入错误，");

m--;

continue;

}

String[] arr = line.trim().split("\\s+");

int i = Integer.parseInt(arr[0]);

int j = Integer.parseInt(arr[1]);

g.addEdge(i, j);

}

sc.close();

System.out.print("深度优先遍历（递归）：");

g.DFSTraverse(S);

System.out.println();

System.out.print("深度优先遍历（非递归）：");

g.DFSTraverse2(S);

}

}

java中如何把图用邻接表表示出来

package my.graph;

import java.util.ArrayList;

import java.util.Iterator;

import my.queue.*;

import my.stack.StackX;

/**

* 邻接表表示

* @author xiayi

*

*/

public class Graph {

private int MAX_VERTS = 20;

private Vertex vertexList[];

private boolean is = false;//是否为有向图

private int nVerts = 0;

private StackX stackX;

private Vertex dfs[];

private Vertex bfs[];

private Queue queue;

public Graph(){

vertexList = new Vertex[MAX_VERTS];

dfs = new Vertex[MAX_VERTS];

bfs = new Vertex[MAX_VERTS];

}

public Graph(int n){

vertexList = new Vertex[n];

dfs = new Vertex[n];

bfs = new Vertex[n];

}

public Graph(int n, boolean is){

this.is = is;

vertexList = new Vertex[n];

dfs = new Vertex[n];

bfs = new Vertex[n];

}

//////////////////////////////////////////////

public boolean isIs() {

return is;

}

public void setIs(boolean is) {

this.is = is;

}

public Vertex[] getVertexList() {

return vertexList;

}

public Vertex[] getDfs() {

return dfs;

}

public Vertex[] getBfs() {

return bfs;

}

////////////////////////////////////////////////////

/**

* 添加顶点

*/

public void addVertex(Vertex vertex){

vertex.setIndex(nVerts);

vertexList[nVerts] = vertex;

nVerts++;

}

/**

* 添加边

*/

public void addEdge(int start, int end){

vertexList.addAdj(vertexList);

if (!is) {vertexList.addAdj(vertexList);}

}

/**

* 返回节点个数

* @return

*/

public int getVertsCount(){

return vertexList.length;

}

/**

* 深度优先迭代器

* @return

*/

public Iterator dfsIterator(){

dfs();

return new DfsIterator();

}

/**

* 广度优先迭代器

* @return

*/

public Iterator bfsIterator(){

bfs();

return new BfsIterator();

}

////////////////////////////////////////////////////////

public void displayGraph(){

ArrayListVertex next = null;

for (int i = 0; i vertexList.length; i++) {

printVertx(vertexList[i]);

}

}

public void printVertx(Vertex vertex){

ArrayListVertex next = vertex.getAdj();

if(next == null){ System.out.println(vertex.toString()+" 无连接点");}

else{

System.out.print(vertex.toString()+"有邻接点:");

for (int i = 0; i next.size(); i++) {

System.out.print("顶点"+next.get(i).label+", ");

}

System.out.println();

}

}

///////////////////////////////////////////////////////////

public void dfs(){

stackX = new StackX(MAX_VERTS);

vertexList[0].isVisted = true;

dfs[0] = vertexList[0];

stackX.push(vertexList[0]);

int dfsIndex = 0;

Vertex vertex;

while(!stackX.isEmpty()){

vertex = getAdjVertex((Vertex)stackX.peek());

if(vertex == null){

stackX.pop();

}else{

vertex.isVisted = true;

dfs[++dfsIndex]=vertex;

stackX.push(vertex);

}

}

for (int i = 0; i getVertsCount(); i++) {

vertexList[i].isVisted = false;

}

}

public void bfs() {

queue = new Queue(MAX_VERTS);

vertexList[0].isVisted = true;

bfs[0] = vertexList[0];

queue.insert(vertexList[0]);

int bfsIndex = 0;

Vertex vertex;

while(!queue.isEmpty()){

Vertex vertex2 = (Vertex)queue.remove();

while((vertex = getAdjVertex(vertex2))!=null){

vertex.isVisted = true;

bfs[++bfsIndex] = vertex;

queue.insert(vertex);

}

}

for (int i = 0; i getVertsCount(); i++) {

vertexList[i].isVisted = false;

}

}

/**

* 得到一个邻接点

* @param vertex

* @return

*/

public Vertex getAdjVertex(Vertex vertex){

ArrayListVertex adjVertexs = vertex.getAdj();

for (int i = 0; i adjVertexs.size(); i++) {

if(!adjVertexs.get(i).isVisted){

return adjVertexs.get(i);

}

}

return null;

}

/////////////////////////////////////////////////////////////

private abstract class GraphIterator implements Iterator{

int count = 0;

public GraphIterator(){

}

public boolean hasNext() {

return count != getVertsCount()-1;

}

public Object next() {

// TODO Auto-generated method stub

return null;

}

public void remove() {

// TODO Auto-generated method stub

}

}

//深度优先迭代

private class DfsIterator extends GraphIterator{

public DfsIterator(){

super();

}

public Vertex next() {

return dfs[count++];

}

}

//广度优先迭代

private class BfsIterator extends GraphIterator{

public BfsIterator(){

super();

}

public Object next() {

return bfs[count++];

}

}

/////////////////////////////////////////////////////////

public static void main(String[] args) {

int nVerts = 10;

int c = 'A'-1;

Vertex vertex;

Graph myGraph = new Graph(nVerts, false);

for (int i = 0; i nVerts; i++) {

c++;

vertex = new Vertex((char)(c));

myGraph.addVertex(vertex);

}

myGraph.addEdge(0, 1);

myGraph.addEdge(0, 4);

myGraph.addEdge(1, 2);

myGraph.addEdge(2, 3);

myGraph.addEdge(4, 5);

myGraph.addEdge(4, 6);

myGraph.addEdge(5, 8);

myGraph.addEdge(6, 7);

myGraph.addEdge(7, 8);

myGraph.addEdge(8, 9);

System.out.println("深度优先迭代遍历：");

for (Iterator iterator = myGraph.dfsIterator(); iterator.hasNext();) {

vertex = (Vertex) iterator.next();

System.out.println(vertex.toString());

}

System.out.println("/n广度优先迭代遍历：");

for (Iterator iterator = myGraph.bfsIterator(); iterator.hasNext();) {

vertex = (Vertex) iterator.next();

System.out.println(vertex.toString());

}

}

}

class Vertex{

public char label;

public boolean isVisted;

public int index;

private ArrayListVertex next = null;

public Vertex(char lab) // constructor

{

label = lab;

isVisted = false;

}

//为节点添加邻接点

public void addAdj(Vertex ver){

if(next == null) next = new ArrayListVertex();

next.add(ver);

}

public ArrayListVertex getAdj(){

return next;

}

public void setIndex(int index){

this.index = index;

}

public String toString(){

return "顶点 "+label+",下标："+index+".";

}

}

代码来自：