數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)(圖指針的指針)

1、課 程 設(shè) 計(jì)課程：數(shù)據(jù)結(jié)構(gòu)題目：圖11（鄰接表）班級(jí)：信管08級(jí)姓名：xxxxxx學(xué)號(hào)：xxxxxxxx設(shè)計(jì)時(shí)間：2010年01月10日2010年05月10日成績(jī)：指導(dǎo)教師：xxxxxxxx 一、題目題目圖11結(jié)構(gòu)鄰接表表示頂點(diǎn)鏈的頭指針回傳方式指針的指針操作圖的基本操作二、概要設(shè)計(jì)1. 存儲(chǔ)結(jié)構(gòu)typedef struct vnode /頂點(diǎn)結(jié)構(gòu) char d; /頂點(diǎn)信息struct lnode *h; /鄰接表表頭struct vnode *next; /指向下一個(gè)頂點(diǎn)char ch; /遍歷過(guò)程中訪(fǎng)問(wèn)標(biāo)記*net;struct lnode /鄰接表結(jié)點(diǎn)結(jié)構(gòu) struct vnode

2、*a; /出端 struct lnode *next; /指向下一個(gè)鄰接點(diǎn);圖的鄰接表存儲(chǔ)(頂點(diǎn)鏈)：h 頂點(diǎn) 入端地址 入端地址 2 .設(shè)計(jì)要點(diǎn)(1) net ins_v(net *g,char v) /插入頂點(diǎn) (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)/刪除頂點(diǎn)(5) void out1(net *g) /輸出(6) void out2(net

3、 *g) /輸出(7) net creat1(net *g) /創(chuàng)建圖(8) net creat2(net *g) /創(chuàng)建圖(9) net dfs(net *g,char vertex)/廣度優(yōu)先遍歷(10) net bfsm(net *g,vnode &_ver)/深度優(yōu)先遍歷(11) net dfsl(net*g)/深度優(yōu)先遍歷以鄰接表存儲(chǔ)的圖g3 存儲(chǔ)要點(diǎn)(1) 創(chuàng)建圖net creat1(net *g) /創(chuàng)建net p=new vnode;（2） 插入頂點(diǎn)：net ins_v(net g,char v)：通過(guò)掃描圖的頂點(diǎn)鏈表，找到鏈表的尾部，在尾部添加一個(gè)頂點(diǎn)。（3）插入邊：net

4、ins_e(net g,char u,char v)：找到邊頂點(diǎn)的地址，在相應(yīng)的頂點(diǎn)下，將地址添加到鏈表中，一般追加到鏈表的尾部。四 源程序#includeusing namespace std;typedef struct vnode /頂點(diǎn)結(jié)構(gòu) char d; /頂點(diǎn)信息struct lnode *h; /鄰接表表頭struct vnode *next; /指向下一個(gè)頂點(diǎn)char ch; /遍歷過(guò)程中訪(fǎng)問(wèn)標(biāo)記*net;struct lnode /鄰接表結(jié)點(diǎn)結(jié)構(gòu) struct vnode *a; /出端地址 struct lnode *next; /指向下一個(gè)鄰接點(diǎn);struct qnode

5、 / 圖的廣度優(yōu)先遍歷，用到隊(duì)列，再次定義隊(duì)列 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對(duì)空！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) /插入頂點(diǎn) 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頂點(diǎn)dh;if(q)co

9、uta-dnext;while(q)couta-dnext;coutnext;void out2(net *g) /輸出net p=*g;lnode *q;while(p)cout頂點(diǎn)dh;if(q)couta-dnext;while(q)couta-dnext;coutnext;net creat1(net *g) /創(chuàng)建圖*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) /創(chuàng)建圖*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 指向當(dāng)前接點(diǎn)所在vnode * ver1=null;vnode * ver= *g;while(ver-d !=vertex & ver-next !=null)ver=ver-next;if(ver-next = null & ver-d !=vertex)cout輸入頂點(diǎn)數(shù)據(jù)錯(cuò)誤，程序退出！h = null)m=null;elsene=ver1-h;/ m 指向鄰接點(diǎn)鏈表的頭結(jié)點(diǎn)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 指向鄰接點(diǎn)鏈表的頭結(jié)點(diǎn)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指向當(dāng)前vertex1接點(diǎn)na=*g;while(na-d != vertex1)na=na-next;/ 起始接點(diǎn)的邊集ea=na-h;/ 第一個(gè)接點(diǎn)是目標(biāo)接點(diǎn)if(ea-a-d = vertex2)/ 第一種情況為邊集next為空if(ea-next = null)delete ea;na-h=null;/ 第二種情況為邊集next不為空elsena-h=ea-next;del

17、ete ea;/ 第一個(gè)接點(diǎn)不是目標(biāo)接點(diǎn)else/ ea 是目標(biāo)接點(diǎn)/ eb 是前驅(qū)接點(diǎn)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 指向當(dāng)前接點(diǎn)所在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輸入頂點(diǎn)數(shù)據(jù)錯(cuò)誤，程序退出！h = null)m=null;elsene=ver1-h;/ m 指向鄰接點(diǎn)鏈表的頭結(jié)點(diǎn)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