数据结构课程设计(图指针的指针)

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-next;while(c != null)deleteedge(g,c-ver-d,vertex);c=c-next;q-next