數(shù)據(jù)結(jié)構(gòu)上機(jī)實(shí)驗(yàn)源代碼

1、數(shù)據(jù)結(jié)構(gòu)上機(jī)實(shí)驗(yàn)源代碼棧的應(yīng)用十進(jìn)制數(shù)轉(zhuǎn)換為八進(jìn)制數(shù)，逆序輸出所輸入的數(shù)實(shí)驗(yàn)代碼：/stack.h,頭文件classstackpublic:stack();boolempty()const;boolfull()const;error_codegettop(elementtype&x)const;error_codepush(constelementtypex);error_codepop();private:intcount;elementtypedatamaxlen;stack:stack()count=0;boolstack:empty()constreturncount=0;boolst

2、ack:full()constreturncount=maxlen;error_codestack:gettop(elementtype&x)constif(empty()returnunderflow;elsex=datacount-l;returnsuccess;errorcodestack:push(constelementtypex)if(full()returnoverflow;datacount=x;count+;returnsuccess;errorcodestack:pop()if(empty()returnunderflow;count；returnsuccess;主程序#i

3、ncludeenumerror_codeoverflow,underflowsuccess;typedefintelementtype;constintmaxlen=20;#include,stack.hMvoidread_write()逆序輸出所輸入的數(shù)stacks;inti;intn,x;coutHpleaseinputnumintn:;cinn;for(i=l;i二n;i+)coutHpleaseinputanum:;cinx;s.push(x);while(!s.empty()s.gettop(x);coutxspop();coutendl;voidDec_to_Ocx(intn)十進(jìn)

4、制轉(zhuǎn)換為八進(jìn)制stacksi;intmod,x;while(n!=0)mod=n%8;sl.push(mod);n二n/B;coutHtheocxofthedecis:;while(!sl.empty()sl.gettop(x);coutx;sl.pop();coutendl;voidmain()intn;/read_write();coutHpleaseinputadec:;cinn;Dec_to_Ocx(n);隊(duì)列的應(yīng)用打印n行楊輝三角實(shí)驗(yàn)代碼：/queue.hclassqueuepublic:queue()count=0;front=rear=0;boolempty()returncou

5、nt=0;boolfull()returncount=maxlenl;error_codeget_front(elementtype&x)if(empty()returnunderflow;x=data(front+l)%maxlen;returnsuccess;error_codeappend(constelementtypex)if(full()returnoverflow;rear=(rear+l)%maxlen;datarear=x;count+;returnsuccess;error_codeserve()if(empty()returnunderflow;front=(front+

6、l)%maxlen;count-;returnsuccess;privatesntcount;intfront;intrear;intdatamaxlen;；主程序#includeenumerror_codeoverfIow,underflow,success;typedefintelementtype;constintmaxlen二20;打印前n行的楊輝三角#include,打印前n行的楊輝三角voidout_number(intn)intsl，s2;inti;intj;intk;queueq;for(i=l;i=(n-l)*2;i+)coutcoutlendl;q.append(l);fo

7、r(i=2;i二n;i+)sl=0;for(k=l;k=(n-i)*2;k+)coutfor(j=l;j=i-l;j+)q.get_front(s2);q.serve();coutsl+s2Hq.append(sl+s2);sl=s2;coutlMencll;q.append(l);voidmain()intn;coutpleaseinputn:;cinn;out_number(n);單鏈表實(shí)驗(yàn)實(shí)驗(yàn)?zāi)康模簩?shí)驗(yàn)?zāi)康睦斫饩€性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。熟練掌握動(dòng)態(tài)鏈表結(jié)構(gòu)及有關(guān)算法的設(shè)計(jì)。根據(jù)具體問(wèn)題的需要，設(shè)計(jì)出合理的表示數(shù)據(jù)的鏈表結(jié)構(gòu)，并設(shè)計(jì)相關(guān)算法。實(shí)驗(yàn)任務(wù)說(shuō)明1：本次實(shí)驗(yàn)中的鏈表結(jié)構(gòu)均為帶頭結(jié)點(diǎn)的單

8、鏈表。說(shuō)明2：為使實(shí)驗(yàn)程序簡(jiǎn)潔直觀，卞面的部分實(shí)驗(yàn)程序中將所需要的函數(shù)以調(diào)用庫(kù)函數(shù)的形式給出，并假設(shè)將庫(kù)函數(shù)放在程序文件“l(fā)inklist.h”中，同時(shí)假設(shè)該庫(kù)函數(shù)文件中定義了鏈表結(jié)構(gòu)中的指針類型為link,結(jié)點(diǎn)類型為node,并定義了部分常用運(yùn)算。例如構(gòu)建鏈表、以某種方式顯示鏈表、從文件中讀入一個(gè)鏈表、跟蹤訪問(wèn)鏈表結(jié)點(diǎn)等。各運(yùn)算的名稱較為直觀，并有相應(yīng)的注釋，因而易于理解和實(shí)現(xiàn)。讀者在上機(jī)實(shí)驗(yàn)時(shí)，需要自己設(shè)計(jì)出所涉及到的庫(kù)函數(shù)，或者將函數(shù)放在實(shí)驗(yàn)程序中，以方便實(shí)驗(yàn)程序的調(diào)試。如時(shí)間緊的話，也可到作者的網(wǎng)站下載以供參考(不完全相同)。編寫(xiě)算法實(shí)現(xiàn)下列問(wèn)題的求解。求鏈表中第i個(gè)結(jié)點(diǎn)的指針(函數(shù))

9、，若不存在，則返回NULL。實(shí)驗(yàn)測(cè)試數(shù)據(jù)基本要求：第一組數(shù)據(jù)：鏈表長(zhǎng)度n10,i分別為5,n,0,n+1,n+2第二組數(shù)據(jù)：鏈表長(zhǎng)度n=0,i分別為0,2在第i個(gè)結(jié)點(diǎn)前插入值為x的結(jié)點(diǎn)。實(shí)驗(yàn)測(cè)試數(shù)據(jù)基本要求：第一組數(shù)據(jù)：鏈表長(zhǎng)度n10,x=100,i分別為5,n,n+l,0,l,n+2第二組數(shù)據(jù)：鏈表長(zhǎng)度n=0,x=100,i=5刪除鏈表中第i個(gè)元素結(jié)點(diǎn)。實(shí)驗(yàn)測(cè)試數(shù)據(jù)基本要求：第一組數(shù)據(jù)：鏈表長(zhǎng)度n10,i分別為5,n,l,n+l,0第二組數(shù)據(jù)：鏈表長(zhǎng)度n=0,i=5在一個(gè)遞增有序的鏈表L中插入一個(gè)值為x的元素，并保持其遞増有序特性。實(shí)驗(yàn)測(cè)試數(shù)據(jù)基本要求：鏈表元素為(10,20,30,40,5

10、0,60,70,80,90)00),x分別為25,85,110和8將單鏈表L中的奇數(shù)項(xiàng)和偶數(shù)項(xiàng)結(jié)點(diǎn)分解開(kāi)，并分別連成一個(gè)帶頭結(jié)點(diǎn)的單鏈表，然后再將這兩個(gè)新鏈表同時(shí)輸出在屏幕上，并保留原鏈表的顯示結(jié)果，以便對(duì)照求解結(jié)果。實(shí)驗(yàn)測(cè)試數(shù)據(jù)基本要求：第一組數(shù)據(jù)：鏈表元素為(1,2,3,4,5,6,7,8,9,10,20,30,40,50,60)第二組數(shù)據(jù)：鏈表元素為(10,20,30,40,50,60,70,80,90,100)求兩個(gè)遞增有序鏈表L1和L2中的公共元素，并以同樣方式連接成鏈表L3。實(shí)驗(yàn)測(cè)試數(shù)據(jù)基本要求：第一組第一個(gè)鏈表元素為(1,3,6,10,15,16,17,18,19,20)第二個(gè)鏈

11、表元素為(1,2,3,4,5,6,7,8,9,10,18,20,30)第二組第一個(gè)鏈表元素為(1,3,6,10,15,16,17,18,19,20)第二個(gè)鏈表元素為(2,4,5,7,8,9,12,22)第三組第一個(gè)鏈表元素為()第二個(gè)鏈表元素為(1,2,3,4,5,6,7,8,9,10)實(shí)驗(yàn)代碼：/linklist.henumerror_codearrange_errocnull,success;typedefstructnodeelementtypedata;structnode才next;node;classlistprivate:node*head;intcount;public:lis

12、t()鏈表的初始化head=newnode;head-next=NULL;count=0;intlength()求鏈表的長(zhǎng)度returncount;取鏈表中第i個(gè)節(jié)卻的扌取鏈表中第i個(gè)節(jié)卻的扌*node*locate(constinti)node*p=head;intj=0;if(ilength()returnNULL;while(p!=NULL)訐(j=i)returnp;p=p-next;j+；returnNULL;*在第i節(jié)點(diǎn)之前插入數(shù)為error_codeinsert(constinti,constelementtypex)node*p=head;intj=0;while(j!=i-l

13、&p!=NULL)p=p-next;j+；if(icount+l)coutdata=x;snext=p-next;pnext=s;count+;cout插入成功!endl;returnsuccess;刪除第i個(gè)節(jié)點(diǎn)error_codedelete_element(constinti)node*p=head;intj=0;while(j!=i-l&p!=NULL)p=p-next;j+;if(ilength()cout此元素不存ffiendl;returnarrange_error;node*u=p-next;pnext=u-next;count-;deleteu;cout,刪除成功tcendl

14、;returnsuccess;/*若原鏈表遞增，插入一個(gè)元素保持其遞增的順序*/error_codeinsertl(constelementtypex)node*p=head-next;if(head-next-datax)nodeSunewnode;u-data=x;unext=head-next;head-next=u;returnsuccess;while(p-next!=NULL)if(p-next-datax)node*u=newnode;u-data=x;unext=p-next;pnext=u;returnsuccess;p=p-next;node*u=newnode;u-dat

15、a=x;unext二NULL;pnext=u;returnsuccess;取鏈表頭結(jié)點(diǎn)的地址node*gethead()returnhead;輸出鏈表中的所有元素error_codeprint()node*p=head-next;while(p!=NULL)coutp-dataHp=p-next;coutendl;returnsuccess;error_codedepart()lista;listb;node*pa=a.gethead();node*pb=b.gethead();node*p=head-next;while(p!=NULL)if(p-data)%2=l)node*u=newno

16、de;u-data=p-data;pa-next=u;pa=u;pa-next=NULL;if(p-data)%2=0)node承u二newnode;u-data=p-data;pbnext=u;pb=u;pb-next=NULL;p=p-next;cout“鏈表所有的奇數(shù)項(xiàng)為：“endl;print();coutH鏈表所有的偶數(shù)項(xiàng)為：next;pb=b.gethead()-next;rc=c.gethead();while(pa!=NULL&pb!二NULL)if(pa-datadata)pa=pa-next;elseif(pa-datapb-data)pb=pb-next;elseu=ne

17、wnode;u-data=pa-data;onext=u;rc=u;count+;pa=pa-next;pb=pb-next;rc-next=NULL;cout兩鏈表中的公共元素為：endl;c.print();/主程序#includetypedefintelementtype;#include,linklist.h,voidmain()lista;listb;listc;intm;intn;intj;inti;intchoice;elementtypetemp;docoutnO,實(shí)驗(yàn)結(jié)束endl;coutl,實(shí)驗(yàn)要求lendl;cout2,實(shí)驗(yàn)要求2endl;cout3,實(shí)驗(yàn)要求3endl;

18、cout4,實(shí)驗(yàn)要求4endl;cout5,實(shí)驗(yàn)要求5endl;coutn6,實(shí)驗(yàn)要去6Hendl;coutchoice;switch(choice)case0:cout實(shí)驗(yàn)結(jié)束endl;break;case1:/*實(shí)驗(yàn)要求case1:/*實(shí)驗(yàn)要求1cout請(qǐng)輸入a鏈表的長(zhǎng)度:endl;cinm;for(j=l;jtemp;a.insert。,temp);coutiW輸入i的值endl;cini;if(a.locate(i)!=NULL)cout鏈表第idataendl;elsecout,NULL,endl;coutiW輸入i的值endl;cini;if(a.locate(i)!=NULL)c

19、out鏈表第idataendl;elsecoutn;for(j=0;jdataendl;elsecout“鏈表第n+j”個(gè)元素的值為:NULLHendl;break;case2:/實(shí)驗(yàn)要求2case2:/cout%青輸入a鏈表的長(zhǎng)度:uendl;cinm;for(j=l;jtemp;a.insert。,temp);cout謂輸入x的值:Mendl;cintemp;for(j=l;j=3;j+)cout請(qǐng)輸入插入點(diǎn)的位置：endl;cini;a.insert(i,temp);cout謂輸入n的值endl;cinn;for(j=0;j3;j+)a.insert(n+j,temp);break;ca

20、se3:/*實(shí)驗(yàn)要求3case3:/*cout%青輸入a鏈表的長(zhǎng)度:endl;for(j=l;j=m;j+)coutniw輸入元素的值”temp;a.insert。,temp);intnl;cout“請(qǐng)輸入要?jiǎng)h除的元素的位置“endl;cini;a.delete_element(i);cout請(qǐng)輸入n的值endl;cinn;a.delete_element(n);nl=n+l;cout“請(qǐng)輸入要?jiǎng)h除的元素的位置“endl;cini;a.delete_element(i);cout刪除n+l位置的元素endl;a.delete_element(nl);cout“請(qǐng)輸入要?jiǎng)h除的元素的位置“endl

21、;cini;a.delete_element(i);break;case4:/*實(shí)驗(yàn)要求4coutH請(qǐng)輸入a鏈表的長(zhǎng)度：“endl;cinm;for(j=l;j=m;j+)cout請(qǐng)輸入元素的值temp;a.insert(j,temp);coutM表未插入前的，其中的只有：Hendl;a.print();for(j=l;j=4;j+)cout請(qǐng)輸入要插入的元素x的值：temp;a.insertl(temp);cout插入后鏈表中的值為：nendl;a.print();break;case5：/*實(shí)驗(yàn)要求5cout請(qǐng)輸入a鏈表的長(zhǎng)度:uendl;cinm;for(j=l;jtemp;a.inse

22、rt。,temp);a.depart();break;cout請(qǐng)輸入a鏈表的長(zhǎng)度:uendl;cinm;for(j=l;jtemp;a.insert(j,temp);coutH請(qǐng)輸入鏈表的長(zhǎng)度:Hendl;cinm;for(j=l;jtemp;b.insert(j,temp);erset(b,c);cout鏈表中的元素有：next=Head;Head-prior=Head;count=0;DLinkList:DLinkList()/析構(gòu)函數(shù),釋放鏈表所占空間Node*p,*q;while(q-next!=Head)q=q-next;/定位q到尾結(jié)點(diǎn)？while(Head!=Head-

23、next)從頭結(jié)點(diǎn)開(kāi)始，依次釋放結(jié)點(diǎn)p=Head;Head=Head-next;qnext=Head;Head-prior=q;deletep;count；Head=NULL;/頭結(jié)點(diǎn)指向空voidDLinkList:CreateList(intn)尾插法(正序)創(chuàng)建具有n個(gè)元素的雙循環(huán)鏈表Node*p,*s;設(shè)置工作指針。p指向尾結(jié)點(diǎn)p=Head;cout請(qǐng)依次輸An個(gè)元素值:endl;for(inti=l;idata;/輸入新建數(shù)據(jù)元素值s-next=p-next;/新結(jié)點(diǎn)鏈入表尾pnext=s;s-prior=p;Head-prior=s;P=s；count+;voidDLinkList

24、:ListDisplay()顯示鏈表Node*p;p=Head-next;inti=l;while(p!=Head)couti,t,1;coutp-dataendl;p=p-next;i+；voidDLinkList:symmetry()Node*p,*s;inti;p=Head-next;s=Head-prior;for(i=l;idata!=s-data)cout鏈表不對(duì)Hendl;break;p=p-next;s=s-prior;if(i=count/2+l)cout鏈表對(duì)稱endl;主程序#include/coutzcintypedefintT;#includedLinklisthvo

25、idmain()主函數(shù)inti;DLinkListL;/intchoice;do/顯示主菜單coutl-創(chuàng)建雙循環(huán)鏈表n;cout2-判斷鏈表是否對(duì)稱n“;cout3-顯示鏈表n;cout4-退出n;coutHEnterchoice:1;cinchoice;switch(choice)case1:/創(chuàng)建鏈表cout請(qǐng)輸入要?jiǎng)?chuàng)建的鏈表中元素個(gè)數(shù):“;cini;將創(chuàng)建的鏈表中數(shù)據(jù)元素的個(gè)數(shù)coutendl;L.CreateList(i);break;case2:/判斷鏈表是否為空L.symmetry();break;case3:/顯示表L.ListDisplay();coutendl;break;

26、case4:/退出cout結(jié)束運(yùn)行”endl;break;default:/coutHlnvalidchoicen;break;while(choice!=4);結(jié)束二叉樹(shù)的試驗(yàn)試驗(yàn)要求:二叉樹(shù)的構(gòu)建,二叉樹(shù)的前序，中序，后序遍歷算法,查找替換樹(shù)中的節(jié)點(diǎn)，交換一棵樹(shù)的左右子樹(shù)試驗(yàn)代碼：#includeenumerror_codesuccess;typedefcharelementtype;typedefstructbnodeelementtypedata;structbnode*lchild,*rchild;bnode,*bitree;classbitreprivate:bnode*root;

27、voidcreate(bitree&T);inthigh(bnode*T);voidpreorder(bnode*T);/先序遍歷voidinorder(bnode*T);中序遍歷voidpostorder(bnode*T);后序遍歷public:bnode*getroot()returnroot;voidcreate()create(root);inthigh()returnhigh(root);voidpreorder()preorder(root);/先序遍歷voidinorder()inorder(root);/中序遍歷voidpostorder()postorder(root);/后

28、序遍歷voidsearch(bnode*T,char&num,bitree&m);查找voidjhuan(bnode*T,char&num,char&temp);/替換voidjbitree(bnode*Tchar&num);/交換一個(gè)節(jié)點(diǎn)的左右子樹(shù);voidbitre:jbitree(bnode*7；char&num)交換一個(gè)節(jié)點(diǎn)的左右子樹(shù)if(T!二NULL)if(T-data=二num)bnode*temp;temp=T-lchild;T-lchild=T-rchild;prchild=temp;jbitree(lchilcLnum);jbitree(T-rchild,num);void

29、bitre:jhuan(bnode*T,char&num,char&temp)替換樹(shù)中的元素if(T!二NULL)if(T-data=num)T-data=temp;coutn交換成功Hendl;jhuan(lchildum,temp);jhuan(Trchild,numztemp);voidbitre:search(bnode*l；char&num,bitree&m)查找元素并返回該元素的地址if仃!=NULL)if(T-data=num)m=T;search(lchild,num,m);search(rchild,nurrLm);intmax(intm,intn)求最人值return(m=

30、n)?m:n;intbitre:high(bnode*T)if(T=NULL)return0;elsereturnmax(high(T-lchild),high(T-rchild)+l;創(chuàng)建一顆二叉樹(shù)創(chuàng)建一顆二叉樹(shù)voidbitre:create(bitree&T)charx;cinx;if(x=,.1)T=NULL;elseT=newbnode;T-data=x;create(T-Ichild);create(T-rchild);voidbitre:preorder(bnode*T)if(T!二NULL)coutT-data;preorder(T-lchild);preorder(T-rch

31、ild);voidbitre:inorder(bnode*T)if(T!二NULL)inorder(T-lchild);coutT-data;inorder(Trchild);voidbitre:postorder(bnode*T)if(T!=NULL)postorderCPlchild);postorderCPrchild);coutT-data;voidmain()charch;chardh;bitret;bitreea;cout請(qǐng)按先序序列輸入二叉樹(shù)中元素的值endl;t.create();cout樹(shù)的先序序列為endl;t.preorder();coutendl;coutH樹(shù)的中序序列

32、為endl;t.inorder();coutendl;cout樹(shù)的后序序列為endl;t.postorder();coutendl;coutch;t.search(t.getroot(),ch,a);couta-dataendl;cout請(qǐng)先后輸入待交換的元素與交換的元素endl;cinch;cindh;t.jhuan(tgetroot()，ch,dh);cout請(qǐng)輸入待交換節(jié)點(diǎn)的元素值endl;cinch;t.jbitree(t.getroot()zch);t.preorder();coutendl;圖的試驗(yàn)試驗(yàn)要求：圖的構(gòu)建，實(shí)現(xiàn)圖的深度遍歷算法與廣度遍歷算法，以及圖的有關(guān)操作試驗(yàn)代碼：/

33、*單鏈隊(duì)歹U*/linkqueue.h#ifndefLINKNODE#defineLINKNODEtemplatestructLinkNodeTdata;LinkNode*next;；templateclassLinkedQueuefprotected:LinkNode*front;LinkNode*rear;intlength;public:LinkedQueue();LinkedQueue();voidClearQueue();boollsEmpty()const;intGetLength()const;LinkNode*GetHead()const;/返回對(duì)頭元素boolEnQueue(

34、T&elem);boolDeQueue(T&receive);boolQueueTraverse(bool(*Visit)(T&elem);templateLinkedQueue:LinkedQueue()front=newLinkNode;if(!front)return;rear=front;front-next=false;length=O;templateLinkedQueue:LinkedQueue()ClearQueue();deletefront;templatevoidLinkedQueue:ClearQueue()/從隊(duì)頭清到隊(duì)尾LinkNode*temp=front-nex

35、t;while(frontnext)front-next=temp-next;deletetemp;temp=front-next;rear=front;length=O;templateboolLinkedQueue:lsEmpty()constreturn(front=rear)?true:false;templateintLinkedQueue:GetLength()constreturnlength;templateLinkNode*LinkedQueue:GetHead()constreturnfront;templateboolLinkedQueue:EnQueue(T&elem)

36、LinkNode*temp=newLinkNode;if(!temp)returnfalse;temp-data=elem;temp-next=false;rear-next=temp;rear=temp;+length;returntrue;templateboolLinkedQueue:DeQueue(T&receive)if(front=rear)returnfalse;LinkNode*temp=front-next;指向隊(duì)頭元素receive=temp-data;front-next=temp-next;deletetemp;if(!frontnext)rear=front;leng

37、th;returntrue;templateboolLinkedQueue:QueueTraverse(bool(*Visit)仃&elem)/從隊(duì)頭到隊(duì)尾進(jìn)行一次遍歷LinkNode*temp=frontnext;while(temp)if(!Visit(temp-data)returnfalse;temp=temp-next;returntrue;#endif主程序/數(shù)組表示法#includeiostream#includestring#include,iomanipM#include”LinkQueue.husingnamespacestd;#defineMAX_VERTEX_NUM20

38、/最人頂點(diǎn)數(shù)constintinfinity=INT_MAX;structArcCellintadj;對(duì)無(wú)權(quán)圖有1,0表示是否相鄰，對(duì)帶權(quán)圖，則為權(quán)值類型char*info;/該弧的相關(guān)信息；templatestruct_MGraphTvexsMAX_VERTEX_NUM;/頂點(diǎn)表ArcCellarcsMAX_VERTEX_NUMMAX_VERTEX_NUM;/鄰接矩陣，即邊表intvexnum;頂點(diǎn)數(shù)intarcnum;/邊數(shù)intkind;/是以鄰接矩陣存儲(chǔ)的圖類型;templateclassMGraph_MGraphmgraph;boolvisitedMAX_VERTEX_NUM;pub

39、lic:intLocateVex(Tu);的位置TGetVex(intindex);index的頂點(diǎn)voidPutVex(Tv,Tvalue);接點(diǎn)的序號(hào)若無(wú)領(lǐng)接點(diǎn)則返回空intNextAdjVex(Tv,Tw);intFirstAdjVex(Tv);圖存在，圖中存在頂點(diǎn)u則返回該頂點(diǎn)在圖中圖存在，index是圖中某個(gè)頂點(diǎn)的序號(hào)則返回圖存在，v是，v是G中某個(gè)頂點(diǎn)返回v的第一個(gè)臨圖存在，v是圖中某個(gè)頂點(diǎn)則對(duì)v賦值value圖存在圖中某個(gè)頂點(diǎn)，w是V的鄰接點(diǎn)返回V的相對(duì)于w的下一個(gè)鄰接點(diǎn)的序號(hào)若w是v的最后一個(gè)鄰接點(diǎn)則返回空boolCreateUDG();voidDFS(intindex);bo

40、ol(*VisitFunc)(Tv);voidDisPlay();構(gòu)造無(wú)向圖從第index出發(fā)遞歸的深度優(yōu)先遍歷圖訪問(wèn)頂點(diǎn)V的方式輸出鄰接矩陣boolDFSTraverse(bool(*visit)(Tv);圖存在,對(duì)圖進(jìn)行深度優(yōu)先遍歷boolBFSTraverse(bool(*visit)(Tv);圖存在，對(duì)圖進(jìn)行廣度優(yōu)先遍歷；templateboolvisit(Tv)coutvreturntrue;templateTMGraph:GetVex(intindex)/okif(index=mgraph.vexnum)returnfalse;/越界返回空returnmgraph.vexsinde

41、x;templatevoidMGraph:PutVex(Tv,Tvalue)/okintindex=LocateVex(v);if(index0)return;mgraph.vexsindex=value;templateboolMGraph:CreatellDG()/ok構(gòu)造無(wú)向圖intiJ;Tvlzv2;coutmgraph.vexnummgrapharcnum;cout請(qǐng)輸入各個(gè)頂點(diǎn):for(i=O;imgraph.vexsi;for(i=O;imgraph.vexnum;i+)初始化鄰接矩陣for(j=O;jmgraph.vexnum;j+)mgraph.arcsij.adj=0;mg

42、=false;for(i=0;imgraph.arcnum;i+)構(gòu)造鄰接矩陣cout-請(qǐng)輸入一條邊依附的兩個(gè)頂點(diǎn):“；cinvlv2;intm=LocateVex(vl);intn=LocateVex(v2);mgraph.arcsmn.adj=1;/mgraph.arcsnm.adj=1;/mgraph.kind=2;returntrue;templateintMGraph:LocateVex(Tu)/okfor(inti=0;iMAX_VERTEX_NUM;i+)if(u=mgraph.vexsi)returni;returntemplateintMGra

43、ph:FirstAdjVex(Tv)/okinttemp=LocateVex(v);intj=0;if(mgraph.kind=l11mgraph.kind=3)j=infinity;for(inti=0;imgraph.vexnum;i+)if(mgraph.arcstempi.adj!=j)returni;return-1;/無(wú)鄰接點(diǎn)返回空templateintMGraph:NextAdjVex(Tv,Tw)/okintid_v=LocateVex(v);intid_w=LocateVex(w);intj=0;if(mgraph.kind=l11mgraph.kind=3)j=infini

44、ty;for(inti=id_w+l;imgraph.vexnum;i+)if(mgraph.arcsid_vi.adj!=j)returni;return-1;templatevoidMGraph:DisPlay()inti,j;chargraphkind7;chararckind3;switch(mgraph.kind)caseO:strcpy(graphkind/有向圖);strcpy(arckindz弧”)；break;casel:strcpy(graphkind有向網(wǎng)”)；strcpyfarckind/弧”)；break;case2:strcpy(graphkind/1無(wú)向圖”)；s

45、trcpyfarckind/1邊);break;case3:strcpy(graphkind/無(wú)向網(wǎng));strcpy(arckind/邊,)；break;,arckind的coutmgraph.vex,arckind的graphkindendl;輸出頂點(diǎn)cout頂點(diǎn)為；for(i=O;imgraph.vexnum;i+)coutmgraph.vexsi輸出權(quán)值的鄰接矩陣cout“權(quán)值的鄰接矩陣為:endl;for(i=O;imgraph.vexnum;i+)for(j=O;jmgraph.vexnum;j+)if(mgraph.arcsij.adj=infinity)coutsetw(5)8”t；elsecoutsetw(5)mgraph.arcsij.adj,t,;couten