《数据结构课程设计(图指针的指针).doc》由会员分享，可在线阅读，更多相关《数据结构课程设计(图指针的指针).doc（17页珍藏版）》请在三一办公上搜索。
1、课 程 设 计课程：数据结构题目：图11（邻接表）班级：信管08级姓名：XXXXXX学号：XXXXXXXX设计时间：2010年01月10日2010年05月10日成绩：指导教师：XXXXXXXX 一、题目题目图11结构邻接表表示顶点链的头指针回传方式指针的指针操作图的基本操作二、概要设计1. 存储结构typedef struct vnode /顶点结构 char d; /顶点信息struct lnode *h; /邻接表表头struct vnode *next; /指向下一个顶点char ch; /遍历过程中访问标记*Net;struct lnode /邻接表结点结构 struct vnode
2、*a; /出端 struct lnode *next; /指向下一个邻接点;图的邻接表存储(顶点链)：h 顶点 入端地址 入端地址 2 .设计要点(1) Net ins_V(Net *G,char v) /插入顶点 (2) Net ins_E(Net *G,char u,char v,float c) /插入边(3) Net DeleteEdge(Net *G,char Vertex1, char Vertex2)/删除边(4) Net DeleteVertex(Net *G,char Vertex)/删除顶点(5) void out1(Net *G) /输出(6) void out2(Net
3、 *G) /输出(7) Net creat1(Net *G) /创建图(8) Net creat2(Net *G) /创建图(9) Net DFS(Net *G,char Vertex)/广度优先遍历(10) Net BFSM(Net *G,vnode &_ver)/深度优先遍历(11) Net DFSL(Net*G)/深度优先遍历以邻接表存储的图G3 存储要点(1) 创建图Net creat1(Net *G) /创建Net p=new vnode;（2） 插入顶点：Net ins_V(Net G,char v)：通过扫描图的顶点链表，找到链表的尾部，在尾部添加一个顶点。（3）插入边：Net
4、ins_E(Net G,char u,char v)：找到边顶点的地址，在相应的顶点下，将地址添加到链表中，一般追加到链表的尾部。四 源程序#includeusing namespace std;typedef struct vnode /顶点结构 char d; /顶点信息struct lnode *h; /邻接表表头struct vnode *next; /指向下一个顶点char ch; /遍历过程中访问标记*Net;struct lnode /邻接表结点结构 struct vnode *a; /出端地址 struct lnode *next; /指向下一个邻接点;struct QNode
5、 / 图的广度优先遍历，用到队列，再次定义队列 vnode * Ver;QNode * Next;struct LQNodeQNode * front;QNode * rear;class Queuepublic :Queue();Queue();bool EmptyQueue();void AddQueueNodeVertex(QNode * NV);vnode * DeleteQueueNodeVertex();private:LQNode *LQ;Queue:Queue()this-LQ=NULL;Queue:Queue() bool Queue:EmptyQueue()if(this-
6、LQ=NULL)return 1;elsereturn 0;void Queue:AddQueueNodeVertex(QNode * NV)QNode * P;P=new QNode;P-Ver=(*NV)-Ver;P-Next=NULL;if(this-LQ = NULL)this-LQ=new LQNode;this-LQ-front=P;this-LQ-rear=P;elsethis-LQ-rear-Next=P;this-LQ-rear=P;vnode * Queue:DeleteQueueNodeVertex()if(this-EmptyQueue()cout对空！LQ-front
7、 = this-LQ-rear)vnode * Q;Q=this-LQ-front-Ver;delete this-LQ-front;delete this-LQ;this-LQ=NULL;return Q;elsevnode * Q;QNode * P=this-LQ-front;this-LQ-front=this-LQ-front-Next;Q=P-Ver;delete P;return Q;Net ins_V(Net *G,char v) /插入顶点 Net _G = *G;if(*G = NULL)Net p=new vnode;p-next=*G;*G=p;(*G)-h=0;(*G
8、)-d=v;(*G)-ch = 0;elsewhile(_G-d != v & _G-next != NULL)_G=_G-next;if(_G-next = NULL)Net p=new vnode;p-next=*G;*G=p;(*G)-h=0;(*G)-d=v;(*G)-ch = 0;elsecoutd!=u)p=p-next;while(q&q-d!=v)q=q-next;r=new lnode;r-next=p-h;r-a=q;p-h=r;return *G;void out1(Net *G) /输出Net p=*G;lnode *q;while(p)cout顶点dh;if(q)co
9、uta-dnext;while(q)couta-dnext;coutnext;void out2(Net *G) /输出Net p=*G;lnode *q;while(p)cout顶点dh;if(q)couta-dnext;while(q)couta-dnext;coutnext;Net creat1(Net *G) /创建图*G=ins_V(G,d);*G=ins_V(G,c);*G=ins_V(G,b); *G=ins_V(G,a);*G=ins_E(G,a,b,8);*G=ins_E(G,a,c,7);*G=ins_E(G,b,c,6);*G=ins_E(G,c,d,5);*G=ins_
10、E(G,d,a,6);return *G;Net creat2(Net *G) /创建图*G=ins_V(G,p);*G=ins_V(G,l);*G=ins_V(G,q); *G=ins_V(G,n); *G=ins_V(G,m);*G=ins_E(G,m,n,6);*G=ins_E(G,m,q,8);*G=ins_E(G,n,q,9);*G=ins_E(G,q,l,6);*G=ins_E(G,l,p,5); *G=ins_E(G,p,m,4);return *G;void Visit(char Vertex)coutVertexnext != NULL & NE-a != &ver2)NE=
11、NE-next;if(NE-a = &ver2)return 1;elsereturn 0;Net DFS(Net *G,char Vertex)/ ver1 指向当前接点所在vnode * ver1=NULL;vnode * ver= *G;while(ver-d !=Vertex & ver-next !=NULL)ver=ver-next;if(ver-next = NULL & ver-d !=Vertex)cout输入顶点数据错误，程序退出！h = NULL)M=NULL;elseNE=ver1-h;/ M 指向邻接点链表的头结点M=new node;M-Ver=NE-a;M-nex
12、t=NULL;N=M;while(NE-next != NULL)node * L=new node;L-Ver=NE-next-a;L-next=NULL;N-next=L;N=L;NE=NE-next;ver=*G;while(ver != NULL)if(ver != ver1)if(JudgementInDegree(*ver,*ver1)node * LL=new node;LL-Ver=ver;LL-next=NULL;if(N=NULL)N=LL;M=N;elseN-next=LL;ver=ver-next;node * k;k=M;ver1-ch=1;Visit(ver1-d)
13、;for(k=M;k!=NULL;k=k-next)if(k-Ver-ch=0)DFS(G,k-Ver-d);return *G;Net BFSM(Net *G,vnode &_ver)vnode * _g = *G;do_g-ch = 0;_g = _g-next;while(_g != NULL);Queue Que;vnode * H;Visit(_ver.d);_ver.ch=1;QNode * P=new QNode;P-Ver=&_ver;Que.AddQueueNodeVertex(&P);while(Que.EmptyQueue() != 1)H=Que.DeleteQueue
14、NodeVertex();QNode * M=NULL;QNode * N=NULL;vnode * ver;lnode * NE=NULL;if(H-h = NULL)M=NULL;elseNE=H-h;/ M 指向邻接点链表的头结点M=new QNode;M-Ver=NE-a;M-Next=NULL;N=M;while(NE-next != NULL)/*N-Vnext=NE-Enext-Edge;N=NE-Enext-Edge;NE=NE-Enext;*/QNode * L=new QNode;L-Ver=NE-next-a;L-Next=NULL;N-Next=L;N=L;NE=NE-
15、next;ver=*G;while(ver != NULL)if(ver != H)if(JudgementInDegree(*ver,*H)QNode * LL=new QNode;LL-Ver=ver;LL-Next=NULL;if(N=NULL)N=LL;M=N;elseN-Next=LL;ver=ver-next;QNode * A;/QNode * B;A=M;while(A != NULL)if(A-Ver-ch = 0)Visit(A-Ver-d);A-Ver-ch=1;Que.AddQueueNodeVertex(&A);A=A-Next;return *G;Net Delet
16、eEdge(Net *G,char Vertex1, char Vertex2)vnode * NA=NULL;vnode * NB=NULL;lnode * EA=NULL;lnode * EB=NULL;/ NA指向当前Vertex1接点NA=*G;while(NA-d != Vertex1)NA=NA-next;/ 起始接点的边集EA=NA-h;/ 第一个接点是目标接点if(EA-a-d = Vertex2)/ 第一种情况为边集next为空if(EA-next = NULL)delete EA;NA-h=NULL;/ 第二种情况为边集next不为空elseNA-h=EA-next;del
17、ete EA;/ 第一个接点不是目标接点else/ EA 是目标接点/ EB 是前驱接点EB=EA;while(EA-a-d != Vertex2)EB=EA;EA=EA-next;if(EA-a-d = Vertex2)if(EA-next = NULL)EB-next=NULL;delete EA;elseif(EA-next != NULL)EB-next=EA-next;delete EA;return *G;Net DeleteVertex(Net *G,char Vertex)/ ver1 指向当前接点所在vnode * ver1=NULL;vnode * ver=*G;vnode
18、 * Q=ver;while(ver-d !=Vertex & ver-d !=NULL)Q=ver;ver=ver-next;if(ver-next = NULL & ver-d !=Vertex)cout输入顶点数据错误，程序退出！h = NULL)M=NULL;elseNE=ver1-h;/ M 指向邻接点链表的头结点M=new node;M-Ver=NE-a;M-next=NULL;N=M;while(NE-next != NULL)/*N-Vnext=NE-Enext-Edge;N=NE-Enext-Edge;NE=NE-Enext;*/node * L=new node;L-Ver
19、=NE-next-a;L-next=NULL;N-next=L;N=L;NE=NE-next;K=N;ver=*G;while(ver != NULL)if(ver != ver1)if(JudgementInDegree(*ver,*ver1)node * LL=new node;LL-Ver=ver;LL-next=NULL;if(N=NULL)N=LL;C=N;elseN-next=LL;C=LL;N=LL;ver=ver-next;node * A=NULL;node * B=NULL;A=M;while(A != K)DeleteEdge(G,Vertex,A-Ver-d);A=A-
20、next;while(C != NULL)DeleteEdge(G,C-Ver-d,Vertex);C=C-next;Q-next=ver1-next;if(ver1 = *G)*G=ver1-next;delete ver1;return *G;void main()char v1;char v2;char v3;Net G1=0; /struct vnode *Gcout图1的输出如下：endl;G1=creat1(&G1); out1(&G1);Net G2=0;coutendl图2的输出如下：endl; G2=creat2(&G2); out2(&G2); coutnn图1的深度优先遍
21、历结果：endl;DFS(&G1,a);coutnn图1的广度优先遍历结果：endl;BFSM(&G1,*G1);coutv3;DeleteVertex(&G1,v3);out1(&G1);coutv1;cinv2;DeleteEdge(&G1,v1,v2);out1(&G1);getchar();/*db c*/图1的输出如下：顶点a 出端: c b顶点b 出端: c顶点c 出端: d顶点d 出端: a图2的输出如下：顶点m 出端:q n顶点n 出端:q顶点q 出端:l顶点l 出端:p顶点p 出端:m图1的深度优先遍历结果：a c d b图1的广度优先遍历结果：a c b d请输入删除的点：六 总结通过这次的课程设计让我知道理论与实际之间的差距，我们平时不能太沉溺于理论之中而忽视实践的重要性，因此我们以后在学习时应该将理论与实践相结合，那样我们才能更好的去学好学精，去更好的去理解数据结构这门学科。
