《數(shù)據(jù)結(jié)構(gòu)》課程實(shí)驗(yàn)指導(dǎo)書

1、數(shù)學(xué)與計(jì)算機(jī)學(xué)院數(shù)據(jù)結(jié)構(gòu)課程實(shí)驗(yàn)指導(dǎo)書適用專業(yè): 計(jì)算機(jī)科學(xué)與技術(shù)目 錄第二部分 實(shí)驗(yàn)指導(dǎo)3實(shí)驗(yàn)一 線性表的插入和刪除3實(shí)驗(yàn)二 線性結(jié)構(gòu)（二）棧和隊(duì)列13實(shí)驗(yàn)三 查找算法18實(shí)驗(yàn)四 排序算法25實(shí)驗(yàn)五 二叉樹的操作27實(shí)驗(yàn)六 圖的操作31第一部分 緒論本指導(dǎo)書是根據(jù)數(shù)據(jù)結(jié)構(gòu)課程實(shí)驗(yàn)教學(xué)大綱編寫的，適用于計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)。一、 本課程實(shí)驗(yàn)的作用與任務(wù)（楷體小三號(hào)）該課程實(shí)驗(yàn)的作用與任務(wù)是讓同學(xué)們掌握計(jì)算機(jī)加工的數(shù)據(jù)結(jié)構(gòu)的特性，以便為應(yīng)用涉及的數(shù)據(jù)選擇適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及其相應(yīng)的算法。數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)不但需要有扎實(shí)的理論學(xué)習(xí)過程，合理和有效的實(shí)驗(yàn)也是必不可少的。通過數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)課程的教學(xué)和

2、實(shí)際操作，需要學(xué)生總體上把握以下三個(gè)方面：其一就是讓學(xué)生學(xué)會(huì)分析研究計(jì)算機(jī)加工的數(shù)據(jù)對(duì)象的特性，以便為數(shù)據(jù)選擇適當(dāng)?shù)奈锢斫Y(jié)構(gòu)和邏輯結(jié)構(gòu)；其二，根據(jù)結(jié)構(gòu)，選擇適當(dāng)?shù)乃惴?，并初步掌握算法的時(shí)間分析和空間分析；其三，學(xué)習(xí)復(fù)雜的程序設(shè)計(jì)。二、 本課程實(shí)驗(yàn)的基礎(chǔ)知識(shí)依據(jù)理論課的講授情況，本書的實(shí)驗(yàn)安排以表（包括有序表、鏈表等），樹，圖三個(gè)主要的數(shù)據(jù)結(jié)構(gòu)為重點(diǎn)。 本書的第一個(gè)實(shí)驗(yàn)是表的實(shí)驗(yàn)，有序表、鏈表為重中之重，必須掌握。第五個(gè)實(shí)驗(yàn)為樹的實(shí)驗(yàn)，樹也是數(shù)據(jù)結(jié)構(gòu)課中的一個(gè)重點(diǎn)，要認(rèn)真掌握。應(yīng)當(dāng)以二叉樹的建立和遍歷為重點(diǎn)。圖論是近年來興起的新興學(xué)科，第六個(gè)實(shí)驗(yàn)為圖的實(shí)驗(yàn)：鄰接表的建立與圖的遍歷。建立鄰接表，應(yīng)

3、當(dāng)與鏈表的實(shí)驗(yàn)相比較，并且應(yīng)當(dāng)站在數(shù)據(jù)結(jié)構(gòu)的角度來考慮兩個(gè)實(shí)驗(yàn)的區(qū)別、聯(lián)系。圖的遍歷，可以和二叉樹的遍歷相比較。第三個(gè)和第四個(gè)的實(shí)驗(yàn)是查找和排序的實(shí)驗(yàn)。就算法而言，排序就是使關(guān)鍵字有序；就數(shù)據(jù)結(jié)構(gòu)而論，排序還應(yīng)關(guān)注數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)，即排序的對(duì)象是記錄，只有這樣理解，才能真正的理解數(shù)據(jù)結(jié)構(gòu)這門課。三、本課程實(shí)驗(yàn)教學(xué)項(xiàng)目及其教學(xué)要求序號(hào)實(shí)驗(yàn)項(xiàng)目名稱學(xué)時(shí)教學(xué)目標(biāo)、要求1線性結(jié)構(gòu)（線性表的插入和刪除4掌握用turbo c上機(jī)調(diào)試線性表的基本方法；掌握線性表的基本操作，插入、刪除、查找，以及線性表合并等運(yùn)算在順序存儲(chǔ)結(jié)構(gòu)和鏈接存儲(chǔ)結(jié)構(gòu)上的運(yùn)算。掌握握單鏈表的基本操作：插入、刪除、查找等運(yùn)算*2線

4、性結(jié)構(gòu)（二）4掌握棧的基礎(chǔ)知識(shí)、結(jié)構(gòu)特點(diǎn)及應(yīng)用；掌握隊(duì)列的結(jié)構(gòu)特點(diǎn)和基本操作3查找算法3掌握查找表的定義和存貯；掌握查找常用方法及過程；實(shí)現(xiàn)順序查找、二分查找、二叉排序樹查找等算法。4排序算法3掌握常用的排序方法，并掌握用高級(jí)語言實(shí)現(xiàn)排序算法的方法；深刻理解排序的定義和各種排序方法的特點(diǎn)，并能加以靈活應(yīng)用；了解各種方法的排序過程及其依據(jù)的原則，并掌握各種排序方法的時(shí)間復(fù)雜度的分析方法。5二叉樹的操作4進(jìn)一步掌握指針變量、動(dòng)態(tài)變量的含義；掌握二叉樹的結(jié)構(gòu)特征，以及各種存儲(chǔ)結(jié)構(gòu)的特點(diǎn)及適用范圍；掌握用指針類型描述、訪問和處理二叉樹的運(yùn)算。6圖的操作4掌握?qǐng)D的基本存儲(chǔ)方法；掌握有關(guān)圖的操作算法并用高

5、級(jí)語言實(shí)現(xiàn)；熟練掌握?qǐng)D的兩種搜索路徑的遍歷方法。合計(jì)18注：有*號(hào)的表示是選開的實(shí)驗(yàn)，學(xué)生自由上機(jī)完成。第 38 頁第二部分 實(shí)驗(yàn)指導(dǎo)實(shí)驗(yàn)一 線性表的插入和刪除一、 實(shí)驗(yàn)?zāi)康?. 掌握用turbo c上機(jī)調(diào)試線性表的基本方法；2. 掌握線性表的基本操作，插入、刪除、查找，以及線性表合并等運(yùn)算在順序存儲(chǔ)結(jié)構(gòu)和鏈接存儲(chǔ)結(jié)構(gòu)上的運(yùn)算。3. 掌握握單鏈表的基本操作：插入、刪除、查找等運(yùn)算二、 實(shí)驗(yàn)要求1、順序表要用函數(shù)creatlist()隨機(jī)生成,用三個(gè)函數(shù)完成順序表的插入，刪除和按值查找。2、用四個(gè)函數(shù)實(shí)現(xiàn)單鏈表的建立、插入、刪除和查找。3、保存和打印出程序的運(yùn)行結(jié)果，并結(jié)合程序進(jìn)行分析。4、打印

6、出文件清單。三、 實(shí)驗(yàn)原理線性表是最常用的而且也是最簡(jiǎn)單的一種數(shù)據(jù)結(jié)構(gòu)，線性表是n個(gè)數(shù)據(jù)元素的有限序列。例如26個(gè)英文元素的字母表：（a，b，c，d，）。其數(shù)據(jù)結(jié)構(gòu)的描述為：linear_list=(d,r)其中：d=ai|ai屬于d0,i=1,2,3,r=n,n=|i=2,3,4,。本實(shí)驗(yàn)是以數(shù)組的形式把有序表存放在計(jì)算機(jī)內(nèi)存的一個(gè)連續(xù)的區(qū)域內(nèi)，這樣便有：loc(ai+1)=loc(ai)+m。其中m是存放每個(gè)元素所占的內(nèi)存字?jǐn)?shù)。loc(ai)=lo+m(i-1)。其中l(wèi)o是ai的地址，即首地址。四、 主要儀器及耗材計(jì)算機(jī)，turbo c 2.0 軟件。五、 實(shí)驗(yàn)內(nèi)容與步驟程序1：線性表基本

7、操作的實(shí)現(xiàn)這個(gè)程序中演示了順序表的創(chuàng)建、插入、刪除和查找，請(qǐng)修改并完成。 程序如下：#include #include /*順序表的定義：*/#define listsize 100typedef structint datalistsize;/*向量data用于存放表結(jié)點(diǎn)*/int length;/*當(dāng)前的表長(zhǎng)度*/seqlist;void main()void createlist(seqlist *l,int n);void printlist(seqlist *l,int n);int locatelist(seqlist *l,int x);void insertlist(seqli

8、st *l,int x,int i);void deletelist(seqlist *l,int i); seqlist l;int i,x;int n=10;/*the length of list*/l.length=0;clrscr();createlist(&l,n);/*creat the list*/printlist(&l,n);/*print the list*/printf(input the research element);scanf(%d,&x);i=locatelist(&l,x);printf(the research position is %dn,i);/*

9、順序表查找*/printf(input the position of insert:n);scanf(%d,&i);printf(input the value of insertn);scanf(%d,&x);insertlist(&l,x,i);/*順序表插入*/printlist(&l,n);/*打印順序表*/printf(input the position of deleten);scanf(%d,&i);deletelist(&l,i);/*順序表刪除*/printlist(&l,n);getch();/*打印順序表*/*順序表的建立：*/void createlist(seql

10、ist *l,int n)int i;printf(please input n numbersn);for(i=1;idatai);l-length=n;/*順序表的打?。?/void printlist(seqlist *l,int n)int i;printf(the sqlist isn);for(i=1;idatai);/*順序表的查找：*/int locatelist(seqlist *l,int x)int i;for(i=1;idatai)=x) return(i); else return(0);/*順序表的插入：*/void insertlist(seqlist *l,in

11、t x,int i)int j;for(j=l-length;j=i;j-)l-dataj+1=l-dataj;l-datai=x;l-length+;/*順序表的刪除：*/void deletelist(seqlist *l,int i) int j;for(j=i;jlength)-1;j+)l-dataj=l-dataj+1;程序2：?jiǎn)捂湵砘静僮鞯膶?shí)現(xiàn)這個(gè)程序中演示了單鏈表的創(chuàng)建、插入、刪除和查找。程序如下： #includetypedef struct node int data; struct node *next; node;/*/node *create()node *p,*h

12、ead;int x;head=(node *)malloc(sizeof(node);head-next=null;printf(input data,-1 to end!n);scanf(%d,&x);while(x!=-1) p=(node *)malloc(sizeof(node); p-data=x; p-next=head-next; head-next=p; scanf(%d,&x);return(head);/*/void output(node *head) node *p; p=head; printf(begin to dump the linklist.n); while

13、(p-next!=null) printf(-%d,p-next-data); p=p-next; printf(nthe linklist ended!n);/*/int listlen(node *head) int i=0; node *p=head; while(p-next!=null) i+; p=p-next; return(i);/*/int get(node *head,int i)int j=0;node *p=head;while(p-next&jnext;if(!p-next|ji) return(0);else return(p-data);/*/void del(n

14、ode *head,int i)node *p=head;int j=0;while(p-next&jnext;if(!p-next|ji-1) printf(the position is wrongn);elsep-next=p-next-next;/*/void ins(node *head,int i,int e)node *p=head,*q;int j=0;while(p-next&jnext;if(!p-next&ji-1) printf(wrong positionn );else q=(node *)malloc(sizeof(node); q-data=e; q-next=

15、p-next; p-next=q;/*/main() node *head; int length; int i,element; clrscr(); head=create(); output(head); length=listlen(head); printf(the length of the link is %dn,length); printf(input the order :n); scanf(%d,&i); element=get(head,i); printf(the element of the order is %dn,element); printf(input th

16、e del position n); scanf(%d,&i); del(head,i); output(head); printf(input the insert posion and element:n); scanf(%d%d,&i,&element); ins(head,i,element); output(head); getch();六、 實(shí)驗(yàn)注意事項(xiàng)1 在編程的時(shí)候，要注意指針的使用。七、 思考題1 有序表，有哪些顯著的特點(diǎn)和優(yōu)點(diǎn)？2 分析實(shí)驗(yàn)指導(dǎo)書上的程序，以數(shù)據(jù)結(jié)構(gòu)上的對(duì)有序表的類型定義來改寫程序。實(shí)驗(yàn)二 線性結(jié)構(gòu)（二）棧和隊(duì)列一、 實(shí)驗(yàn)?zāi)康?、理解棧的基本概念和特點(diǎn)；2、

17、理解順序棧和鏈棧存儲(chǔ)結(jié)構(gòu)的特點(diǎn)；3、掌握順序棧存儲(chǔ)結(jié)構(gòu)的構(gòu)造、取棧頂元素、入棧和出棧的基本操作算法；4、理解隊(duì)列的基本概念和特點(diǎn)；5、掌握順序隊(duì)列和鏈隊(duì)列存儲(chǔ)結(jié)構(gòu)的各自特點(diǎn)；6、掌握順序隊(duì)列存儲(chǔ)結(jié)構(gòu)的構(gòu)造、取隊(duì)頭元素、入隊(duì)和出隊(duì)基本操作算法。二、 實(shí)驗(yàn)要求1、 要求掌握本實(shí)驗(yàn)的各個(gè)算法和程序。2、 要求獨(dú)立完成并上機(jī)運(yùn)行本程序。三、 實(shí)驗(yàn)原理從數(shù)據(jù)結(jié)構(gòu)角度看，棧和隊(duì)列是兩種特殊的線性表。它們的邏輯結(jié)構(gòu)和線性表相同，只是其運(yùn)算規(guī)則較線性表有更多的限制，即棧和隊(duì)列是操作受限制的線性表，也可以將它們稱為限定性的線性表結(jié)構(gòu)。四、 主要儀器及耗材計(jì)算機(jī)，turbo c 2.0 軟件。五、實(shí)驗(yàn)內(nèi)容與步驟

18、實(shí)驗(yàn)21 順序棧的建立，入棧和出棧#define n 5#include int stackn+1;int top=-1;int pop(void);void push(int ch);void main(void)int i;int an=1,3,5,7,9;printf(data before inversing:);for(i=0;in;i+)printf(%d ,ai);printf(n);for(i=0;in;i+)push(ai);for(i=0;in;i+)ai=pop();printf(data after inversinging:);for(i=0;in;i+)printf

19、(%d ,ai);printf(n);int pop(void)return stacktop-;void push(int ch)stack+top=ch;實(shí)驗(yàn)22 順序隊(duì)列的建立，入隊(duì)和出隊(duì)#define n 5#includeint cqueuen;int cfront=-1;int crear=-1;void addcq(int data);int delcq(void);int iscempty(void);int iscfull(void);void main(void)int i;int an=1,3,5,7,9;printf(data input:);for(i=0;in;i+

20、)printf(%d ,ai);addcq(ai);addcq(11);printf(n);printf(data output:);for(i=0;in;i+)printf(%d ,delcq();printf(n);void addcq(int data)if(iscfull()printf(cqueue is full!n);elsecqueue+crear%n=data;int delcq(void)if(iscempty()printf(cqueue is empty!n);return 0;elsereturn cqueue+cfront%n;int iscfull(void)if

21、(cfront=(crear+1)%n)return 1;elsereturn 0;int iscempty(void)if(cfront=crear)return 1;elsereturn 0;六、 實(shí)驗(yàn)注意事項(xiàng)實(shí)驗(yàn)過程中注意隊(duì)列中判斷隊(duì)滿的條件。七、 思考題1. 如何建立一個(gè)循環(huán)隊(duì)列，如何實(shí)現(xiàn)循環(huán)隊(duì)列的基本的操作？實(shí)驗(yàn)三 查找算法一、 實(shí)驗(yàn)?zāi)康?. 理解查找表的概念；3. 理解關(guān)鍵字的概念；4. 熟練掌握順序查找算法；5. 熟練掌握折半查找算法。二、 實(shí)驗(yàn)要求1、定義學(xué)生信息查找表記錄結(jié)構(gòu)；2、學(xué)生信息查找程序的主控程序設(shè)計(jì)；3、學(xué)生信息查找的功能函數(shù)設(shè)計(jì)；3、保存和打印出程序的運(yùn)行結(jié)果，

22、并結(jié)合程序進(jìn)行分析。4、打印出文件清單。三、 實(shí)驗(yàn)原理查找和排序是數(shù)據(jù)處理中使用頻率極高的重要運(yùn)算，幾乎在任何一個(gè)計(jì)算機(jī)系統(tǒng)軟件和應(yīng)用軟件中都會(huì)涉及到。我們把同一數(shù)據(jù)類型的數(shù)據(jù)元素構(gòu)成的集合稱為查找表，把查找表中某個(gè)可以標(biāo)識(shí)一個(gè)數(shù)據(jù)元素的數(shù)據(jù)項(xiàng)的值稱為關(guān)鍵字。當(dāng)問題涉及的數(shù)據(jù)量大的時(shí)候，常常要求使用效率較高的查找方法，如折半查找法，這往往要求先對(duì)查找表中的記錄進(jìn)行排序。四、 主要儀器及耗材計(jì)算機(jī)，turbo c 2.0 軟件。五、實(shí)驗(yàn)內(nèi)容與步驟 實(shí)驗(yàn)21 已知學(xué)生的信息數(shù)據(jù)項(xiàng)包括：學(xué)號(hào)、姓名、性別和年齡。定義學(xué)生信息查找表的記錄結(jié)構(gòu)。在學(xué)生信息查找表中實(shí)現(xiàn)對(duì)關(guān)鍵字學(xué)號(hào)進(jìn)行順序查找和折半查找。#

23、include#include#includetypedef struct student int num; char name20; char sex; int age; stunode; /*定義學(xué)生記錄的結(jié)構(gòu)stunode stu5=10101,li ling,m,18,10102,zhang fun,m,19,10103,wang min,f,20,10107,li mei,f,19,10105,zhao yun,m,20;/*順序查找算法的定義*/ int seqsearch(stunode stu,int n,int key)int i=0;while(i=n)return -1;

24、else return i;/*冒泡排序*/void bubblesort(stunode stu,int n)int i,j;stunode temp;for(i=0;ii;j-) if(stuj.num stuj-1.num)temp.num =stuj.num;strcpy(,);temp.sex=stuj.sex;temp.age=stuj.age;stuj.num =stuj-1.num; strcpy(,);stuj.sex=stuj-1.sex;stuj.age=stuj.age; stuj-1.num

25、=temp.num; strcpy(,);stuj-1.sex=temp.sex;stuj-1.age=temp.age;/*折半查找*/int binsearch(stunode stu,int n,int key)int low=0,high=n-1,mid,count=0;while(low key)high=mid-1;elselow=mid+1;return -1;/*主控函數(shù)*/void main()stunode *p;int n=5;int key,sresult;printf(no. name sex agen);for(p=stu;p

26、num,p-name,p-sex,p-age);printf(1、順序查找：n);printf(請(qǐng)輸入要查詢的學(xué)生學(xué)號(hào)：n);scanf(%d,&key); sresult=seqsearch(stu,n,key); if(sresult0)printf(沒有學(xué)號(hào)為%d的學(xué)生n,key);elseprintf(n學(xué)號(hào)為%d的學(xué)生為：n,key); printf(%-8d%-18s%4c%4dn,stusresult.num,stusr,stusresult.sex,stusresult.age);printf(2、按任意健，開始冒泡排序：n);printf(n初始序列：n)

27、; printf(no. name sex agen);for(p=stu;pnum,p-name,p-sex,p-age);bubblesort(stu,n); printf(n冒泡排序后的結(jié)果序列為：n); printf(no. name sex agen);for(p=stu;pnum,p-name,p-sex,p-age);printf(3、二分查找：n);printf(請(qǐng)輸入要查詢的學(xué)生的學(xué)號(hào)：n);scanf(%d,&key);sresult=binsearch(stu,n,key);if(sresultdata); preorder(bt-lchild); preorder(bt

28、-rchild); else if(g=2) printf(空樹n); bitreptr *crt_bt() /*建立二叉樹*/ bitreptr *bt; char ch; if(f=1) printf(輸入根結(jié)點(diǎn)，#表示結(jié)束n); else printf(輸入結(jié)點(diǎn)，#表示結(jié)束n); scanf(n%c,&ch); f=f+1; if(ch=#) bt=null; else bt=(bitreptr *)malloc(len); bt-data=ch; printf(%c 左孩子,bt-data); bt-lchild=crt_bt(); printf(%c 右孩子,bt-data); bt

29、-rchild=crt_bt(); return(bt); main() f=1; g=1; bt=crt_bt(); preorder(bt); 六、 實(shí)驗(yàn)注意事項(xiàng)實(shí)驗(yàn)過程中注意遞歸的使用。七、 思考題1. 畫出給出的各類型的數(shù)據(jù)示意圖，理解為不同目的而建立的不同數(shù)據(jù)結(jié)構(gòu)意義。2. 改寫程序完成中、后序遍歷。3. 考慮用非遞歸算法完成二叉樹遍歷。4完成其他的函數(shù)所定義的功能。實(shí)驗(yàn)六 圖的操作一、 實(shí)驗(yàn)?zāi)康?掌握?qǐng)D的基本存儲(chǔ)方法；2掌握有關(guān)圖的操作算法并用高級(jí)語言實(shí)現(xiàn)；3熟練掌握?qǐng)D的兩種搜索路徑的遍歷方法。二、 實(shí)驗(yàn)要求1 認(rèn)真閱讀和掌握本實(shí)驗(yàn)的算法 。2 上機(jī)將本算法實(shí)現(xiàn)。3 保存和打印出程

30、序的運(yùn)行結(jié)果，并結(jié)合程序進(jìn)行分析。4 按照你對(duì)圖的操作需要，重新改寫主程序并運(yùn)行，打印出文件清單和運(yùn)行結(jié)果三、 實(shí)驗(yàn)原理圖，是一種比樹和表要復(fù)雜得多的數(shù)據(jù)結(jié)構(gòu)。在線性表中，數(shù)據(jù)元素之間只有線性關(guān)系，每一個(gè)數(shù)據(jù)元素只有一個(gè)直接前驅(qū)和直接后繼；在樹形結(jié)構(gòu)之中，數(shù)據(jù)元素之間有著明顯的層次關(guān)系，并且每上一層的數(shù)據(jù)元素可能和下一層的多個(gè)數(shù)據(jù)元素相關(guān)，但只能和上一層的一個(gè)數(shù)據(jù)元素相關(guān)；而在圖形結(jié)構(gòu)中，結(jié)點(diǎn)之間的關(guān)系可以是任意的。圖中的任意結(jié)點(diǎn)之間的兩個(gè)數(shù)據(jù)元素都可以相關(guān)。由此，圖的應(yīng)用極為廣泛，特別是近年來的迅速發(fā)展，已滲透到諸如語言學(xué)、邏輯學(xué)、物理學(xué)、化學(xué)、電訊工程、計(jì)算機(jī)科學(xué)以及數(shù)學(xué)的其它分支里。圖有

31、多種存儲(chǔ)方式，鄰接表是一鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。在鄰接表中，對(duì)圖中的每一個(gè)結(jié)點(diǎn)都建立一個(gè)單鏈表，第一個(gè)單鏈表表示依附于頂點(diǎn)vi的邊。每一個(gè)結(jié)點(diǎn)有三個(gè)域組成，其鄰接點(diǎn)域指示與頂點(diǎn)vi鄰接的點(diǎn)圖中的位置，鏈域指示下一條邊或弧的結(jié)點(diǎn)，數(shù)據(jù)域存儲(chǔ)和邊或弧的相關(guān)信息，如權(quán)值等。每個(gè)鏈表附設(shè)一表頭結(jié)點(diǎn)。如下圖所示：鄰接點(diǎn)域鏈域數(shù)據(jù)域數(shù)據(jù)域鏈域 表結(jié)點(diǎn) 頭結(jié)點(diǎn)四、 主要儀器及耗材計(jì)算機(jī)，turbo c 2.0軟件。五、 實(shí)驗(yàn)內(nèi)容與步驟以鄰接矩陣和鄰接表的方式存儲(chǔ)連通圖。然后分別用深度優(yōu)先算法遍歷鄰接矩陣方式存儲(chǔ)的圖和鄰接表方式存儲(chǔ)的圖。算法 如下：深度優(yōu)先遍歷的遞歸算法 （1）深度優(yōu)先遍歷算法 int visited

32、maxvertexnum； /訪問標(biāo)志向量是全局量void dfstraverse(algraph *g) /深度優(yōu)先遍歷以鄰接表表示的圖g，而以鄰接矩陣表示g時(shí)，算法完全與此相同int i；for(i=0;in;i+)visitedi=false； /標(biāo)志向量初始化for(i=0;in；i+)if(!visitedi) /vi未訪問過dfs(g，i)； /以vi為源點(diǎn)開始dfs搜索/dfstraverse（2）鄰接表表示的深度優(yōu)先搜索算法void dfs(algraph *g，int i) /以vi為出發(fā)點(diǎn)對(duì)鄰接表表示的圖g進(jìn)行深度優(yōu)先搜索edgenode *p；printf(visit v

33、ertex：c，g-adjlisti.vertex)；/訪問頂點(diǎn)vivisitedi=true； /標(biāo)記vi已訪問p=g-adjlisti.firstedge； /取vi邊表的頭指針while(p)/依次搜索vi的鄰接點(diǎn)vj，這里j=p-adjvexif (!visitedp-adjvex)/若vi尚未被訪問dfs(g，p-adjvex);/則以vj為出發(fā)點(diǎn)向縱深搜索p=p-next； /找vi的下一鄰接點(diǎn)/dfs#define maxvertexnum 5#define m 5#define null 0typedef struct node int adjvex;struct node *next;jd;typedef struct tnode int vexdata; jd *firstarc;td;typedef structtd agm;int n;alg