數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告

1、精選優(yōu)質(zhì)文檔-傾情為你奉上數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 專業(yè)：xxxxxxx 學(xué)號(hào)：xxxxxxxxx 姓名：xxxxxxxx 指導(dǎo)老師：xxxxxxxxx 日期：2011-12-29 目錄一、 實(shí)驗(yàn)要求將整個(gè)系統(tǒng)采用菜單控制，一級(jí)菜單為各章的名稱，二級(jí)菜單為每章的算法。整個(gè)系統(tǒng)應(yīng)包括數(shù)據(jù)結(jié)構(gòu)的典型算法30個(gè)以上。了解每個(gè)算法的設(shè)計(jì)思想，能夠熟練的分析各個(gè)算法的執(zhí)行過(guò)程。二、實(shí)驗(yàn)內(nèi)容2.1實(shí)驗(yàn)一（線性表的順序存儲(chǔ)）掌握線性表的順序存儲(chǔ)結(jié)構(gòu)；能熟練利用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)線性表的基本操作；能熟練掌握線性表創(chuàng)建、插入、刪除、查找和顯示線性表中元素等基本操作。2.1.1實(shí)驗(yàn)一內(nèi)容建立含有不少于3個(gè)元素的順序表，

2、并將結(jié)果在屏幕上輸出；對(duì)剛建立的順序表實(shí)現(xiàn)插入、刪除、查找，并將結(jié)果在屏幕上輸出；設(shè)計(jì)一個(gè)選擇式菜單。2.1.2實(shí)驗(yàn)一算法描述#include "iostream.h"const int maxsize1=10; /maxlen表示線性表允許的最大長(zhǎng)度#define elemtype1 intstruct sequenlist elemtype1 amaxsize1;/表示線性表（a1，a2，.,an）int len;/len表示線性表的實(shí)際長(zhǎng)度 ;int length(sequenlist L)/求順序表的長(zhǎng)度length(L) return L.len;/插入運(yùn)算Ins

3、ert(&L,x,i), 線性表L的第 i 個(gè)位置上插入一個(gè)值為 x 的新元素void Insert(sequenlist &L,elemtype1 x,int i) int j;if(L.len>=maxsize1-1) cout<<"overflow"<<endl;else if (i<1)|(i>L.len+1) cout<<"position is not correct!"<<endl;else for(j=L.len;j>=i;j-)L.aj+1=L.aj

4、;/元素后移L.ai=x;/插入元素L.len+;/表長(zhǎng)度增加/刪除運(yùn)算Delete(&L,i),線性表L中刪除序號(hào)為i的數(shù)據(jù)元素void Delete(sequenlist &L,int i) int j; if(i<1)|(i>L.len) cout<<"tttt輸入的i不合法!"<<endl; else for(j=i+1;j<=L.len;j+) L.aj-1=L.aj;/元素前移 L.len-;/表長(zhǎng)度減1 void setnull(sequenlist &L) /置空表setnull(&L

5、) L.len=0;/*定位算法Locate(L,x),表L中查找值為的數(shù)據(jù)元素，其結(jié)果返回在L中首次出現(xiàn)的值為的那個(gè)元素的序號(hào)或地址，稱為查找成功; 否則，在L中未找到值為的數(shù)據(jù)元素，返回一特殊值表示查找失敗。 */int Locate(sequenlist L, elemtype1 x) int j=1; while(j<=L.len)&&(L.aj!=x) j+; if(j<=L.len) return j; else return 0;/取元素Get(L,i),返回線性表L中序號(hào)為i的數(shù)據(jù)值elemtype1 Get(sequenlist L,int i)

6、if(i<1)|(i>L.len) return NULL; else return L.ai;void print(sequenlist L) /打印線性表 int i; for (i=1;i<=L.len;i+) cout<<L.ai<<" " cout<<endl;void main1() sequenlist L; int i,j,k; elemtype1 x;setnull(L); cout<<"nn" cout<<"ttt 線性表子系統(tǒng)n"cou

7、t<<"tt*n"cout<<"tt* 1-插入元素*n"cout<<"tt* 2-刪除元素*n"cout<<"tt* 3-查找數(shù)據(jù)*n"cout<<"tt* 4-顯示線性表*n"cout<<"tt* 0-返回*n"cout<<"tt*n"do cout<<"tt 請(qǐng)選擇菜單項(xiàng)04："cin>>k;switch(k) case 1

8、: /在線性表第i位置處插入值為X的元素cout<<"n 請(qǐng)輸入插入的位置i:"cin>>i;cout<<" 請(qǐng)輸入數(shù)據(jù)X:"cin>>x;Insert(L,x,i);cout<<"插入后線性表的順序存儲(chǔ)為:"print(L); break;case 2: /刪除線性表中值為X的元素 cout<<"n 請(qǐng)輸入要?jiǎng)h除元素的位置i:"cin>>i;cout<<"刪除前線性表為:"print(L); Del

9、ete(L,i);cout<<"刪除后線性表為:"print(L); break;case 3: /查找線性表中元素值為x的位置cout<<"n 請(qǐng)輸入要查找的數(shù)值X:"cin>>x; cout<<"n線性表的順序存儲(chǔ)為："j=Locate(L,x) ;cout<<endl;if (j !=0 ) print(L);cout<<"線性表中值為X所在的位置是："<<j;elsecout<<"tt線性表中無(wú)此元素!

10、n"cout<<endl;break;case 4: /輸出線性表 cout<<"n線性表為：" print(L); while(k!=0);2.2實(shí)驗(yàn)二（線性表的鏈?zhǔn)酱鎯?chǔ)）掌握線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)；能熟練利用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)實(shí)現(xiàn)線性表的基本操作；能熟練掌握鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中算法的實(shí)現(xiàn)。2.2.1實(shí)驗(yàn)二內(nèi)容用頭插法或尾插法建立帶頭結(jié)點(diǎn)的單鏈表，并在屏幕上輸出顯示此鏈表；實(shí)現(xiàn)單鏈表上的插入、刪除、修改、查找、計(jì)數(shù)等操作，并將結(jié)果在屏幕上輸出；設(shè)計(jì)一個(gè)選擇式菜單。2.2.2實(shí)驗(yàn)二算法描述#define elemtype int#include &quo

11、t;iostream.h"#include "stdlib.h"class link public:elemtype data; link *next; void Insert(link *head,elemtype x1,elemtype y); void dele(link *head , elemtype x1); link *Locate(link *head,elemtype x1) ; link *hcreat(int x1) ; void print(link *h); ;/建立單鏈表link *link:hcreat(int n ) link *s

12、,*p;int i;p=new link;p->next=NULL;for(i=1;i<=n;i+) s=new link; cin>>s->data; s->next=p->next; p->next=s;return p;/按值查詢link *link:Locate(link *head , elemtype x1) link *p; p=head->next; while(p!=NULL)&&(p->data!=x1) p=p->next; return p;/在頭指針head所指帶頭結(jié)點(diǎn)的單鏈表中，在值為

13、y的結(jié)點(diǎn)之后插入值為x1的結(jié)點(diǎn)void link:Insert(link *head , elemtype x1 , elemtype y) link *p,*s; s=new link; s->data=x1; if(head->next=NULL) /鏈表為空 head->next=s; s->next=NULL; p=Locate(head,y); /調(diào)用查找算法 if(p=NULL) cout<<"插入位置非法"<<endl; else s->next=p->next; p->next=s; /刪除值

14、為x1的結(jié)點(diǎn)void link:dele(link *head , elemtype x1) link *p,*q; q=head; p=head->next; while(p!=NULL)&&(p->data!=x1) q=p; p=p->next; if(p=NULL) cout<<"要?jiǎng)h除的結(jié)點(diǎn)不存在"<<endl; else q->next=p->next; delete(p);/打印單鏈表void link:print(link *h) link *p=h->next;while(p) c

15、out<<p->data<<"->"p=p->next;cout<<"NULL"<<endl;void main2() link *head=new link; link *p=new link;int k; elemtype x1,y;cout<<"nnnn"cout<<"tt 單鏈表的子系統(tǒng) n"cout<<"tt*n"cout<<"tt* 1查詢?cè)?*n"

16、cout<<"tt* 2刪除元素 *n"cout<<"tt* 3插入元素 *n"cout<<"tt* 4打印鏈表 *n"cout<<"tt* 0返回主菜單 *n"cout<<"tt*n" cout<<"請(qǐng)輸入鏈表元素："head=head->hcreat(5); do cout<<"請(qǐng)選擇菜單項(xiàng)0-4: "cin>>k; switch(k)case 1:c

17、out<<"請(qǐng)輸入要查詢的元素："cin>>x1; cout<<"元素所在的位置："<<p<<endl; head->Locate(head,x1);break;case 2:cout<<"請(qǐng)輸入要?jiǎng)h除的元素："cin>>x1; head->dele(head ,x1);break;case 3:cout<<"請(qǐng)輸入插入新元素的位置："cin>>y; cout<<"請(qǐng)輸入插入

18、的新元素："cin>>x1; head->Insert(head,x1,y);break;case 4:cout<<"鏈表為："head->print(head);break;while(k);2.3實(shí)驗(yàn)三（棧的應(yīng)用）掌握棧的數(shù)據(jù)類型描述及棧的特點(diǎn)；掌握棧的順序和鏈?zhǔn)絻煞N存儲(chǔ)結(jié)構(gòu)的特點(diǎn)及算法描述；掌握棧的5種基本運(yùn)算及算法在兩種不同存儲(chǔ)結(jié)構(gòu)上的實(shí)現(xiàn)。2.3.1實(shí)驗(yàn)三內(nèi)容編寫(xiě)鏈?zhǔn)綏＿M(jìn)棧、出棧、顯示棧中全部元素的程序；將一個(gè)正整數(shù)n轉(zhuǎn)換成R進(jìn)制，要求用順序棧的來(lái)實(shí)現(xiàn)；用switch語(yǔ)句設(shè)計(jì)一個(gè)選擇式菜單，以菜單方式執(zhí)行上述操作。2.

19、3.2實(shí)驗(yàn)三算法描述#include "iostream.h"#include "stdlib.h"const int maxsize3=10000; /定義棧的最大容量為maxlentypedef int elemtype3; class seqstack public:elemtype3 stackmaxsize3; /將棧中元素定義為elemtype類型 int top; /指向棧頂位置的指針void inistack(seqstack &s); /將棧s置為一個(gè)空棧（不含任何元素）void push(seqstack &s , e

20、lemtype3 x) ; /將元素x插入到棧s中，也稱為“入棧”、“插入”、“壓入”void pop(seqstack &s) ; /刪除棧s中的棧頂元素，也稱為“退棧”、“刪除”、“彈出”elemtype3 gettop(seqstack s) ; /取棧s中棧的頂元素bool empty(seqstack s) ; /判棧s是否為空void print(seqstack s);/初始化棧算法void seqstack:inistack(seqstack &s ) s.top=0; /進(jìn)棧算法void seqstack:push(seqstack &s, elemt

21、ype3 x) if (s.top=maxsize3-1) cout<<"overflow" else s.top+; s.stacks.top=x;/出棧算法void seqstack:pop(seqstack &s ) if (s.top=0) cout<<"underflow" else s.top-; /取棧頂元素算法elemtype3 seqstack:gettop(seqstack s ) if (s.top=0) cout<<"underflow"return 0;else r

22、eturn s.stacks.top;/判斷?？账惴╞ool seqstack:empty(seqstack s) if (s.top=0) return 1;else return false ;/打印棧算法void seqstack:print(seqstack s) for(int i=1;i<=s.top;i+)cout<<s.stacki<<" " cout<<endl;void main3() seqstack s;int k;bool t;elemtype3 x,y;s.inistack(s);cout<<

23、"tt 順序棧的操作 n"cout<<"tt*n" cout<<"tt* 1-進(jìn)棧 *n"cout<<"tt* 2-出棧 *n"cout<<"tt* 3-取棧頂元素 *n"cout<<"tt* 4-判棧空 *n"cout<<"tt* 5-輸出棧 *n"cout<<"tt* 0-退出 *n"cout<<"tt*n" doco

24、ut<<"tt 請(qǐng)選擇（0-5）："cin>>k;switch(k)case 1:cout<<"請(qǐng)輸入進(jìn)棧的值="cin>>x;s.push(s,x);break;case 2:s.pop(s);break;case 3:y=s.gettop(s);cout<<"棧頂?shù)闹?"<<y<<endl;break;case 4:t=s.empty(s); if(t) cout<<"棧為空！n" else cout<<

25、"棧非空！n"break;case 5:cout<<"棧中的結(jié)果是："s.print(s);break;while(k!=0);2.4實(shí)驗(yàn)四（隊(duì)列的應(yīng)用）掌握隊(duì)列的數(shù)據(jù)類型描述及隊(duì)列的特點(diǎn)；掌握隊(duì)列的順序和鏈?zhǔn)絻煞N存儲(chǔ)結(jié)構(gòu)的特點(diǎn)及算法描述；掌握隊(duì)列的5種基本運(yùn)算及算法在兩種不同存儲(chǔ)結(jié)構(gòu)上的實(shí)現(xiàn)。2.4.1實(shí)驗(yàn)四內(nèi)容實(shí)現(xiàn)順序循環(huán)或鏈?zhǔn)疥?duì)列的進(jìn)隊(duì)列、出隊(duì)列、判斷隊(duì)列空否、顯示隊(duì)列中全部元素的運(yùn)算；設(shè)計(jì)一個(gè)選擇式菜單，以菜單方式選擇隊(duì)列的各種操作。2.4.2實(shí)驗(yàn)四算法描述#include "iostream.h"#include

26、 "stdlib.h"const int maxsize4= 10; /定義隊(duì)列的最大容量為maxlentypedef int elemtype4;class seqqueuepublic:elemtype4 queuemaxsize4; /將隊(duì)列中元素定為數(shù)組型，元素類型為elemtype4int front; /隊(duì)頭指針int rear; /隊(duì)尾指針void INIQUEUE4(seqqueue &Q);/將隊(duì)列Q設(shè)置成一個(gè)空隊(duì)列void ENQUEUE4(seqqueue &Q,elemtype4 x);/將元素X插入到隊(duì)尾中，也稱“進(jìn)隊(duì)”，“插入”v

27、oid DLQUEUE4(seqqueue &Q);/將隊(duì)列Q的隊(duì)頭元素刪除，也稱“退隊(duì)”、“刪除”elemtype4 GETHEAD4(seqqueue Q);/得到隊(duì)列Q的隊(duì)頭元素之值bool EMPTY4(seqqueue Q);/判斷隊(duì)列Q是否為空，若為空返回真，否則返回假void print4(seqqueue Q );/初始化void seqqueue:INIQUEUE4(seqqueue &Q )Q.front=Q.rear=maxsize4-1; /進(jìn)隊(duì)列void seqqueue:ENQUEUE4 (seqqueue &Q, elemtype4 x)

28、if (Q.rear+1)%maxsize4 = Q.front) cout<<"overflow" else Q.rear=(Q.rear+1)%maxsize4; Q.queueQ.rear=x;/出隊(duì)列void seqqueue:DLQUEUE4(seqqueue &Q ) if (Q.rear=Q.front) cout<<"underflow" else Q.front =(Q.front+1)%maxsize4;/取隊(duì)頭元素elemtype4 seqqueue:GETHEAD4(seqqueue Q ) if

29、(Q.rear=Q.front) cout<<"underflow"return NULL; else return Q.queue(Q.front+1)%maxsize4; /判隊(duì)列空否bool seqqueue:EMPTY4(seqqueue Q ) if (Q.rear=Q.front) return true; else return false;/打印隊(duì)列void seqqueue:print4(seqqueue Q) while(Q.front!=Q.rear)Q.front=(Q.front+1)%maxsize4; cout<<Q.q

30、ueueQ.front<<" "cout<<endl;void main4() seqqueue Q;int t,k;elemtype4 x,y;Q.INIQUEUE4(Q);cout<<"nnnn"cout<<"tt 隊(duì)列的子系統(tǒng) n"cout<<"tt*n"cout<<"tt* 1進(jìn)隊(duì)列 *n"cout<<"tt* 2出隊(duì)列 *n"cout<<"tt* 3取隊(duì)頭元素

31、*n"cout<<"tt* 4判隊(duì)列空 *n" cout<<"tt* 5打印隊(duì)列 *n"cout<<"tt* 0返回主菜單 *n"cout<<"tt*n" docout<<"請(qǐng)選擇（0-5）："cin>>k;switch(k)case 1:cout<<"請(qǐng)輸入進(jìn)隊(duì)列的值="cin>>x;Q.ENQUEUE4 (Q, x);break;case 2:Q.DLQUEUE4(Q

32、);break;case 3:y=Q.GETHEAD4(Q);cout<<"隊(duì)頭的值="<<y<<endl;break;case 4:t=Q.EMPTY4(Q); if(t) cout<<"隊(duì)列為空！n" else cout<<"隊(duì)列非空！n"break;case 5:cout<<"隊(duì)列中的結(jié)果是："Q.print4(Q);break;while(k);2.5實(shí)驗(yàn)五（二叉樹(shù)的遍歷和應(yīng)用）掌握二叉樹(shù)的數(shù)據(jù)類型描述及二叉樹(shù)的特性；掌握二叉樹(shù)的鏈?zhǔn)酱?/p>

33、儲(chǔ)結(jié)構(gòu)的建立算法；掌握二叉鏈表上二叉樹(shù)的基本運(yùn)算的實(shí)現(xiàn)。2.5.1實(shí)驗(yàn)五內(nèi)容用遞歸或非遞歸的方法建立一棵二叉樹(shù)；用遞歸實(shí)現(xiàn)二叉樹(shù)的先序、中序、后序三種遍歷；求二叉樹(shù)的高度；設(shè)計(jì)一個(gè)選擇式菜單，以菜單方式實(shí)現(xiàn)各種操作。2.5.2實(shí)驗(yàn)五算法描述#include<iostream.h>typedef char elemtype5;const int maxsize5=1024;struct bitreeelemtype5 data; /結(jié)點(diǎn)數(shù)據(jù)類型bitree *lchild,*rchild; /定義左、右孩子為指針型;bitree *create()bitree *T;elemtype

34、5 x;cin>>x;if (x='0') T=NULL;else T=new bitree;T->data=x;cout<<" 請(qǐng)輸入"<<T->data<<"結(jié)點(diǎn)的左孩子："T->lchild=create();cout<<" 請(qǐng)輸入"<<T->data<<"結(jié)點(diǎn)的右孩子："T->rchild=create();return T;void preorder(bitree *root)

35、/前根遍歷二叉樹(shù)的遞歸遍歷算法 bitree *p;p=root;if(p!=NULL) cout<<p->data<<" " preorder(p->lchild); preorder (p->rchild);/中根遍歷二叉樹(shù)的遞歸遍歷算法void inorder(bitree *root) bitree *p; p=root; if (p!=NULL) inorder(p->lchild); cout<<p->data<<" " inorder(p->rchild);

36、/后根遍歷二叉樹(shù)的遞歸遍歷算法void postorder( bitree *root) bitree *p;p=root;if (p!=NULL) postorder (p->lchild); postorder (p->rchild); cout<<p->data<<" "int treehigh(bitree *T) int lh,rh;if (T=NULL) return 0;elselh=treehigh(T->lchild );rh=treehigh(T->rchild );if (lh>rh) ret

37、urn lh+1;else return rh+1;void lorder (bitree * t)/按層次遍歷一棵二叉樹(shù) bitree *qmaxsize5,*p; / maxsize5為最大容量 int f,r; / f,r類似于頭尾指針q1=t; f=r=1;while (f<=r) p=qf; f+; /出隊(duì) cout<<p->data<<" " if(p ->lchild!=NULL) r+; qr=p->lchild; /入隊(duì) if (p->rchild!=NULL) r+; qr=p->rchild;

38、 /入隊(duì)void main5() bitree *T;int k; cout<<"nnnn" cout<<"ttt 樹(shù)的子系統(tǒng)n"cout<<"tt*n"cout<<"tt* 1-建二叉樹(shù) *n"cout<<"tt* 2-前序遍歷 *n"cout<<"tt* 3-中序遍歷 *n"cout<<"tt* 4-后序遍歷 *n"cout<<"tt* 5-求樹(shù)高

39、度 *n"cout<<"tt* 6-層次遍歷 *n"cout<<"tt* 0-返回 *n"cout<<"tt*n"do cout<<"tt 請(qǐng)選擇菜單項(xiàng)05："cin>>k;if (k=1)cout<<"n 請(qǐng)輸入此樹(shù)的根結(jié)點(diǎn):"T=create(); cout<<endl; /建立二叉樹(shù) else if (k=2) cout<<"n 此樹(shù)前序遍歷的順序:"preorde

40、r(T);cout<<endl;else if (k=3)cout<<("n 此樹(shù)中序遍歷的順序:");inorder(T);cout<<endl;else if (k=4) cout<<"n 此樹(shù)后序遍歷的順序:"postorder(T);cout<<endl;else if (k=5) /樹(shù)的高度 int h=treehigh(T); cout<<"n此樹(shù)的高度是："<<h; cout<<endl; else if (k=6) /按層次

41、遍歷一棵二叉樹(shù) cout<<"n 此樹(shù)層次遍歷的順序:"lorder (T);cout<<endl; else if (k=0) break;while(k!=0);2.6實(shí)驗(yàn)六（圖的鄰接矩陣和遍歷）掌握?qǐng)D的基本概念和鄰接矩陣的存儲(chǔ)結(jié)構(gòu)；掌握?qǐng)D的鄰接矩陣存儲(chǔ)結(jié)構(gòu)的算法實(shí)現(xiàn)；掌握?qǐng)D在鄰接矩陣存儲(chǔ)結(jié)構(gòu)上遍歷算法的實(shí)現(xiàn)。2.6.1實(shí)驗(yàn)六內(nèi)容對(duì)給定的圖，建立圖的鄰接矩陣；實(shí)現(xiàn)該圖的深度優(yōu)先搜索遍歷；實(shí)現(xiàn)該圖的廣度優(yōu)先搜索遍歷；設(shè)計(jì)一個(gè)選擇式菜單，以菜單方式實(shí)現(xiàn)各種操作。2.6.2實(shí)驗(yàn)六算法描述#include<iostream.h>#includ

42、e"iomanip.h"typedef int elemtype6;const int N=20; / 圖中頂點(diǎn)數(shù) const int E6=100 ; / 圖中邊數(shù)struct graphelemtype6vN+1; / 存放頂點(diǎn)信息v1,v2,.vn，不使用v0存儲(chǔ)空間int arcsN+1N+1; / 鄰接矩陣;struct graph g;int visitedN+1;int n1,e; /實(shí)際圖的頂點(diǎn)數(shù)和邊數(shù)void creatadj()/建立無(wú)向圖的鄰接矩陣 int i, j,k ;for (k=1; k<=n1; k+)g.vk=k; /輸入頂點(diǎn)信息 f

43、or (i=1; i<=n1; i+ )for (j=1; j<=n1; j+)g.arcsij=0;cout<<"輸入"<<e<<"條無(wú)向邊n"for (k=1; k<=e; k+)cout<<"輸入"<<k<<"條無(wú)向邊的頂點(diǎn)對(duì)："cin>>i>>j; /輸入一條邊(i,j) g.arcsij=1;g.arcsji=1;void dfs (int i) / 從頂點(diǎn)i 出發(fā)深度遍歷int j; cou

44、t<<g.vi<<" " /輸出訪問(wèn)頂點(diǎn)visitedi=1; /全局?jǐn)?shù)組訪問(wèn)標(biāo)記置1表示已經(jīng)訪問(wèn)for(j=1; j<=n1; j+)if (g.arcsi j=1)&&(!visitedj) dfs(j); void bfs( int i) /從頂點(diǎn)i出發(fā)廣度遍歷int qN+1 ; /Q為隊(duì)列int f,r,j ; / f,r分別為隊(duì)列頭，尾指針f=r=0 ; /設(shè)置空隊(duì)列cout<<g.vi<<" " / 輸出訪問(wèn)頂點(diǎn)visitedi=1 ; /全局?jǐn)?shù)組標(biāo)記置1表示已經(jīng)訪問(wèn)r+

45、; qr=i ; /入隊(duì)列while (f<r) f+; i=qf ; /出隊(duì)列for (j=1; j<=n1; j+)if (g.arcsij=1)&&(!visitedj)cout<<g.vj<<" "visitedj=1 ;r+; qr=j ; void print()int i,j;cout<<endl<<" "for (i=1; i<=n1; i+) cout<<setw(5)<<g.vi;cout<<endl;for (i=1

46、; i<=n1; i+) for (cout<<i,j=1; j<=n1;j+) cout<<setw(5)<<g.arcsij; cout<<endl;void main6() int i,k;cout<<"nnnn"cout<<"tt 圖的鄰接矩陣子系統(tǒng)n"cout<<"tt*n"cout<<"tt* 1-更 新 圖 *n"cout<<"tt* 2-深度遍歷 *n"cout

47、<<"tt* 3-廣度遍歷 *n"cout<<"tt* 0-返回 *n"cout<<"tt*n"do cout<<"tt 請(qǐng)選擇菜單項(xiàng)03："cin>>k;switch(k) case 1:cout<<"n請(qǐng)輸入圖的頂點(diǎn)的個(gè)數(shù)n= "cin>>n1;cout<<"請(qǐng)輸入圖的邊個(gè)數(shù)e= "cin>>e;creatadj();cout<<"圖的鄰接矩陣

48、如下n"print();break;case 2:for (i=0; i<=n1; i+) /標(biāo)志向量初始化visited i=0; cout<<"n請(qǐng)輸入從圖的哪個(gè)頂點(diǎn)(1-"<<n1<<")開(kāi)始深度遍歷:"cin>>i;cout<<"深度遍歷的結(jié)果為："dfs(i);cout<<endl;break;case 3:for (i=0; i<=n1; i+) /標(biāo)志向量初始化visited i=0; cout<<"n請(qǐng)輸

49、入從圖的哪個(gè)頂點(diǎn)(1-"<<n1<<")開(kāi)始廣度遍歷:"cin>>i;cout<<"廣度遍歷的結(jié)果為："bfs(i);cout<<endl;break; while (k!=0);2.7實(shí)驗(yàn)七（圖的鄰接表和遍歷）掌握?qǐng)D的基本概念和鄰接表的存儲(chǔ)結(jié)構(gòu)；掌握?qǐng)D的鄰接表存儲(chǔ)結(jié)構(gòu)的算法實(shí)現(xiàn)；掌握?qǐng)D在鄰接表存儲(chǔ)結(jié)構(gòu)上遍歷算法的實(shí)現(xiàn)。2.7.1實(shí)驗(yàn)七的內(nèi)容對(duì)給定的圖，建立圖的鄰接表；實(shí)現(xiàn)該圖的深度優(yōu)先搜索遍歷；實(shí)現(xiàn)該圖的廣度優(yōu)先搜索遍歷；設(shè)計(jì)一個(gè)選擇式菜單，以菜單方式實(shí)現(xiàn)各種操作。2.7.2實(shí)驗(yàn)七算

50、法描述#include"iostream.h"typedef int elemtype7;const int m =20; /表示圖中最大頂點(diǎn)數(shù)const int E= 100; / 圖中最大邊數(shù)struct link7 /定義鏈表類型elemtype7 data ;link7 *next ;link7 am+1;int n7; /實(shí)際圖的頂點(diǎn)數(shù)int e7; /實(shí)際圖的邊數(shù)int visited7m+1;void creatlink7( ) /建立無(wú)向的鄰接表int i,j,k ; link7 *s ;for(i=1; i<=n7;i+) /建立鄰接表頭結(jié)點(diǎn) ai.

51、data=i ; ai.next=NULL;cout<<"輸入"<<e7<<"條無(wú)向邊n"for(k=1; k<=e7;k+)cout<<"輸入"<<k<<"條無(wú)向邊的頂點(diǎn)對(duì)："cin>>i>>j ; /輸入一條邊 (i,j)s=new link7; /申請(qǐng)一個(gè)動(dòng)態(tài)存儲(chǔ)單元s->data=j ;s->next=ai.next;ai.next=s;s=new link7; s->data=i ;s-

52、>next=aj.next;aj.next=s;void dfsl(int i) /鄰接表實(shí)現(xiàn)圖的深度優(yōu)先搜索link7 *p; cout<<ai.data<<" " ; /輸出訪問(wèn)頂點(diǎn)visited7i=1; /全局?jǐn)?shù)組訪問(wèn)標(biāo)記置為1表示已訪問(wèn)p=ai.next;while (p!=NULL)if (!visited7p->data) dfsl(p->data);p=p->next;void bfsl(int i) /鄰接表實(shí)現(xiàn)圖的廣度優(yōu)先搜索int qm+1 ; /定義隊(duì)列int f,r; link7 *p ; /P為搜索

53、指針f=r=0; cout<<ai.data<<" " ;visited7i=1; r+; qr=i; /進(jìn)隊(duì)while (f<r)f+; i=qf; /出隊(duì) p=ai.next;while (p!=NULL) if(!visited7p->data)cout<<ap->data.data<<" "visited7p->data=1;r+;qr=p->data; p=p->next;void print7() link7 *p; for(int i=1;i<=n7;i+) p=ai.next;cout<<i<<":"while(p)cout<<p-&