數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)書源代碼

1、實(shí)驗(yàn)一 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)一、實(shí)驗(yàn)?zāi)康模?掌握線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。2熟練地利用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)實(shí)現(xiàn)線性表的基本操作。3能熟練地掌握鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中算法的實(shí)現(xiàn)。二、實(shí)驗(yàn)內(nèi)容：1用頭插法或尾插法建立帶頭結(jié)點(diǎn)的單鏈表。2 實(shí)現(xiàn)單鏈表上的插入、刪除、查找、修改、計(jì)數(shù)、輸出等基本操作 。三、 實(shí)驗(yàn)要求：1. 根據(jù)實(shí)驗(yàn)內(nèi)容編寫程序，上機(jī)調(diào)試、得出正確的運(yùn)行程序。2. 寫出實(shí)驗(yàn)報(bào)告（包括源程序和運(yùn)行結(jié)果） 。四、實(shí)驗(yàn)學(xué)時(shí)： 2 學(xué)時(shí)五、實(shí)驗(yàn)步驟：1進(jìn)入編程環(huán)境，建立一新文件；2. 參考以下相關(guān)內(nèi)容，編寫程序，觀察并分析輸出結(jié)果。 定義單鏈表的數(shù)據(jù)類型，然后將頭插法和尾插法、插入、刪除、查找、修改、計(jì)數(shù)、 輸出

2、等基本操作都定義成子函數(shù)的形式， 最后在主函數(shù)中調(diào)用它， 并將每一種操作前后的結(jié) 果輸出，以查看每一種操作的效果。 部分參考程序/ 單鏈表的建立 （頭插法 ），插入，刪除，查找、修改、計(jì)數(shù)、輸出#include#define elemtype intstruct link elemtype data ； / 元素類型link *next ； / 指針類型，存放下一個(gè)元素地址;/ 頭插法建立帶頭結(jié)點(diǎn)的單鏈表link *hcreat（） link s,p;elemtype i;couti ；p=new link ；p-next=NULL ；while（i） / 當(dāng)輸入的數(shù)據(jù)不為 0 時(shí)，循環(huán)建單鏈

3、表s=new link ； s-data=i ； s-next=p-next ； p-next=s ； cini ； return p ； / 輸出單鏈表 void print(1ink *head)1ink *p ； p=head-next ； while(p-next!=NULL) coutdata ”；/ 輸出表中非最后一個(gè)元素p=p-next ； coutdata ； / 輸出表中最后一個(gè)元素 coutnext ；while(p!=NULL)&(p-data!=x)p=p-next ；return p ；/ 在 head 為頭指針的單鏈表中，刪除值為 x 的結(jié)點(diǎn)void deletel

4、(1ink *head，elemtype x)1ink *p ， *q ；q=head ；p=head-next ；while(p!=NULL)&(p-data!=x)q=p ；p=p-next ； If(p=NULL) coutnext=p -next ；delete(p) ；y 的結(jié)點(diǎn)/ 在頭指針 head 所指的單鏈表中，在值為 x 的結(jié)點(diǎn)之后插入值為 void insert(1ink *head ， elemtype x ， elemtype y) link *p , *s ; s=new link ； s-data=y ；if(head-next=NULL) / 鏈表為空 head-

5、next=s ； s-next=NULL ：p=Locate(head ， x) ； / 調(diào)用查找算法if(p=NULL)coutnext=p-next ； p-next=s ；/ 將單鏈表 p 中所有值為 x 的元素修改成 yvoid change(1ink *p,elemtype x,elemtype y)link *q ； q=p-next ； while(q!=NULL) if(q-data=x) q-data=y ； q=q-next ；void count(1ink *h) / 統(tǒng)計(jì)單鏈表中結(jié)點(diǎn)個(gè)數(shù)1ink *p ； int n=0 ；p=h-next ； while(p!=NUL

6、L) n+ ； p=p-next ； return n;void main() int n ； elemtype x ， y； link *p ， *q ； p=hcreat() ； / 頭插法建立鏈表 print(p) ； / 輸出剛建立的單鏈表 couty ； deletel(p ， y)； print(p) ； / 輸出刪除后的結(jié)果 coutx ； couty ； insert(p ，x ，y)； print(p) ； / 輸出插入后的結(jié)果 coutxy ； change(p ，x，y) ； print(p) ； coutx ； q=Locate(p ，x) ； if(q=NULL)co

7、utx ”不在表中，找不到 !” endl ； else coutx ”在表中，已找到 !” endl ； n=count(p) ； cout ”鏈表中結(jié)點(diǎn)個(gè)數(shù)為： ” nendl ： / 單鏈表的建立 (尾插法 )、插入、刪除、查找、修改、計(jì)數(shù)、輸出 #include#define elemtype intstruct link elemtype data ； / 元素類型link *next ； / 指針類型，存放下 - 個(gè)元素地址；/ 尾插法建立帶頭結(jié)點(diǎn)的單鏈表link *rcreat()link *s ， *p ， *r ； elemtype i ； couti; p=r=new li

8、nk ； p-next=NULL ； while(i)s=new link ； s-data=i ； r-next=s ； r=s ； cini ； r-next=NULL ； return p ； / 輸出單鏈表void print(1ink *head)link *p ； p=head-next ； while(p-next!=NULL)coutdata” ; / 輸出表中非最后一個(gè)元素p=p-next ；)coutdata ； / 輸出表中最后一個(gè)元素 coutendl ；x 個(gè)結(jié)點(diǎn)link *Locate(1ink *head, int x) /在單鏈表中查找第link *p ；p=h

9、ead ；int j=0 ；while(p!=NULL)&(jnext; j+； return p ；void delete I(1ink *head ， elemtype x)/ 在 head 為頭指針的單鏈表中，刪除值為 x 的結(jié)點(diǎn)link *p, *q ； q=head ； p=head-next ； while(p!=NULL)&(p-data!=x)q=p ；要?jiǎng)h除的結(jié)點(diǎn)不存在p=p-next ； ) if(p=NULL)coutnext=p-next delete(p) ； void insert(1ink *head， int x,elemtype y)y 的結(jié)點(diǎn)/ 在頭指針 h

10、ead 所指單鏈表中，在第 x 個(gè)結(jié)點(diǎn)之后插入值為 link *p ， *s ； s=new link ； s-data=y ；if(head-next=NULL)/ 鏈表為空 head-next=s ； s-next=NULL ：p=Locate(head ，x) ；/ 調(diào)用查找算法if(p=NULL) coutnext=p-next ； p-next=s ；void change(1ink *p,elemtype x ， elemtype y)/將單鏈表P中所有值為x的元素改成值為y link *q ；q=p-next ；while(q!=NULL)if(q-data=x)q-data=y

11、 ；q=q-next ；void count(1ink *h)/ 統(tǒng)計(jì)單鏈表中結(jié)點(diǎn)個(gè)數(shù)(1ink *p ； int n=0 ； p=h-next ； while(p!=NULL)n+ ； p=p-next ； retum n;void main() int n;link p,q;p=rcreat() ； / 尾插法建立鏈表print(p) ； / 輸出剛建立的單鏈表couty ；deletel(p ， y) ；print(p) ； / 輸出刪除后的結(jié)果coutx ；couty ；insert(p ，x ，y)；print(p) ； / 輸出插入后的結(jié)果coutxy ；change(p ，x ，

12、y)；print(p) ；coutx ；q=Locate(p ,x) ；if(q=NULL)coutx”不在表中 ,找不到 ! ” endl ；else coutx ”在表中，已找到 !” endl ； n=count(p) ；cout ”鏈表中結(jié)點(diǎn)個(gè)數(shù)為： ” nendl;六、選作實(shí)驗(yàn)試設(shè)計(jì)一元多項(xiàng)式相加(鏈?zhǔn)酱鎯?chǔ))的加法運(yùn)算。A(X) =7+3X+9X 8+5X 9B ( X ) =8X+22X 7-9X 81 建立一元多項(xiàng)式；2 輸出相應(yīng)的一元多項(xiàng)式；3 相加操作的實(shí)現(xiàn)。實(shí)驗(yàn)二 循環(huán)鏈表的操作一、實(shí)驗(yàn)?zāi)康模和ㄟ^本實(shí)驗(yàn)中循環(huán)鏈表和雙向鏈表的使用，使學(xué)生進(jìn)一步熟練掌握鏈表的操作方式。二、實(shí)驗(yàn)

13、內(nèi)容：本次實(shí)驗(yàn)可以從以下兩個(gè)實(shí)驗(yàn)中任選一個(gè)：1 建立一個(gè)單循環(huán)鏈表并實(shí)現(xiàn)單循環(huán)鏈表上的逆置。 所謂鏈表的逆置運(yùn)算 （或稱為逆轉(zhuǎn)運(yùn)算 ）是指在不增加新結(jié)點(diǎn)的前提下，依次改變數(shù)據(jù) 元素的邏輯關(guān)系，使得線性表（ai, a2, a3，an）成為（an，a3, a2, ai）。2. 構(gòu)建一個(gè)雙向鏈表，實(shí)現(xiàn)插入、查找和刪除操作。三、 實(shí)驗(yàn)要求：1. 根據(jù)實(shí)驗(yàn)內(nèi)容編寫程序，上機(jī)調(diào)試、得出正確的運(yùn)行程序。2. 寫出實(shí)驗(yàn)報(bào)告（包括源程序和運(yùn)行結(jié)果） 。四、實(shí)驗(yàn)學(xué)時(shí)： 2 學(xué)時(shí)五、實(shí)驗(yàn)步驟：1 進(jìn)入編程環(huán)境，建立一新文件；2. 參考以下相關(guān)內(nèi)容，編寫程序，觀察并分析輸出結(jié)果。 建立一個(gè)帶頭結(jié)點(diǎn)的單循環(huán)鏈表，從頭到

14、尾掃描單鏈表L,把p作為活動(dòng)指針，沿著鏈表向前移動(dòng)， q 作為 p 前趨結(jié)點(diǎn)， r 作為 q 的前趨結(jié)點(diǎn)。其中， q 的 next 值為 r ；r 的 初值置為 head 。 雙向鏈表的構(gòu)造與單鏈表相同，至于它的插入與刪除運(yùn)算比單鏈表復(fù)雜，插入運(yùn)算 需要 4 步操作，刪除運(yùn)算需要 2 步操作，注意語句的次序，不要任意交換位置，以免不能 正確插入或刪除結(jié)點(diǎn)。 部分參考程序/ 循環(huán)鏈表/頭文件hi . h的內(nèi)容#define NULL 0#include#includetypedef struct nodeint num ；struct node *next；linklist ；/以下是主程序#i

15、nclude ”h1 h ” /輸出循環(huán)鏈表的信息 void output(linklist *head) linklist *p ； p=head-next ； while(p!=head)printf( ” d ”， p-num) ； p=p-next ；printf( ”n ” )；/ 建立單循環(huán)鏈表 Linklist *creat(int n) int k;linklist *head,*r,*p ； p=(linklist*)malloc(sizeof(linklist) head=p ； r=p ； p-next=p ； for(k=1 ； knum=k ； r-next=p ；

16、r=p ；p-next=head ； return(head) ； /逆置函數(shù)linklist *invert(linklist *head)Linklist *p ，*q，*r ； p=head-next ； q=head ； while(p!=head) r=q ； q=p ；p=p-next ； q-next=r ；head-next=q ； return(head) ；void main()int n ；Linklist *head ；printf( “輸入所建立的循環(huán)鏈表的結(jié)點(diǎn)個(gè)數(shù)： n ” )； scanf( “%d ”， n) ；head=creat(n) ；printf( ”輸

17、出建立的單循環(huán)鏈表： n ” )； output(head) ；printf( ”現(xiàn)在進(jìn)行逆置 ! n ” )； head=invert(head) ；! n ” ) ；printf( ”輸出進(jìn)行逆置運(yùn)算后的單循環(huán)鏈表的結(jié)點(diǎn)信息 output(head) ；/ 雙向鏈表參考程序/ 以下是頭文件 hh h 的內(nèi)容#include #includetypedef struct dupnodeint data ；struct dupnode *next,*prior ；dulinklist ；/ 以下是主程序的內(nèi)容#include ”hh h”/create 函數(shù)用來構(gòu)建雙向鏈表dulinklist

18、 *create()dulinklist *head,*p ， *r;int i， n； head=(dulinklist*)malloc(sizeof(dulinklist )；head-next=NULL ； head-prior=NULL ； r=head ；printf( “請(qǐng)輸入所建雙向鏈表中結(jié)點(diǎn)的個(gè)數(shù)： n ” )； scanf( “ d” , n) ；for(i=l ；idata) ； p-next=NULL ； r-next=p ； p-prior=r ； r=r-next ；return(head) ；/find 函數(shù)用來實(shí)現(xiàn)在雙向鏈表中按序號(hào)查找某個(gè)結(jié)點(diǎn)的功能。 void

19、find(dulinklist *h)int k,i ； dulinklist *p ； p=h ； i=0 ： printf( ”輸入要查找結(jié)點(diǎn)的序號(hào)： n ” )； scanf( ” %d ” ,&k) ； while(p!=NULL)&(inext ； i+ ：if(p)printf( ”所查到的結(jié)點(diǎn)的值為： n ” )； printf( ”%dn ” ,p-data) ；elseprintf( ”沒找到該結(jié)點(diǎn) ! n ” )；/insdulist 函數(shù)用來實(shí)現(xiàn)在雙向鏈表中按序號(hào)插入結(jié)點(diǎn)的功能 dulinklist *insdulist(dulinklist *head， int i ，

20、 int x)dulinklist *p ，*s ；int j ； p=head ； j=0 ； whi1e(p-next!=head)&(jnext ；j+ ；If(j=i-1)s = (duli nklist*)malloc(sizeof(duli nklist)；s-data=x ；s-prior=p ；s-next=p-next ；p-next-prior=s ；p-next=s ；elseprintf( ” errorn ”)；return head ；/deledulist 函數(shù)實(shí)現(xiàn)在雙向鏈表中按序號(hào)刪除某個(gè)結(jié)點(diǎn)的功能dulinklist *deledulist(dulinklis

21、t *head， int i)dulinklist *p ；int j ；p=head ；j=0while(p-next!=head)&(jnext ；j+ ；If(j=i)p-prior-next=p-next ；p-next-prior=p-prior ；free(p) ；elseprintf( ” error n ” )；return head ；/output 函數(shù)用來輸出整個(gè)雙向鏈表的結(jié)點(diǎn)值void output(dulinklist *h)dulinklist *p ；p=h-next ；while(p!=NULL)printf( ”輸出該雙向鏈表的結(jié)點(diǎn)，分別為： n ” )；pr

22、intf( ” %dn ” ,p-data) ；p=p-next ；void main() dulinklist *headint flag=li， k ， x；while(flag)/flag 作為判斷循環(huán)的標(biāo)志位 printf( ”1建立雙向鏈表n ” )；printf( ”2查找某個(gè)結(jié)點(diǎn)n ”)；printf( ”3插入一個(gè)結(jié)點(diǎn)n ”)；prtntf( ”4刪除一個(gè)結(jié)點(diǎn)n ” )；printf( ”5退出 n ”）；printf（ ”請(qǐng)輸入選擇： n “ ）； scanf（ ”%d ”， &i） ； switch（i） case 1 ：head=create0 ； break ；case

23、 2 ： find（head） ；break ；case 3 ： printf（ ”輸入待插的結(jié)點(diǎn)的序號(hào)及新插入結(jié)點(diǎn)的 data 值 . n ” ）; scanf（ ”%d%d ”， k，x）； head=insdulist（head，k，x） ；output（head） ； break ；case 4 ： printf（ ”輸入要?jiǎng)h除的結(jié)點(diǎn)的序號(hào) . n ” ）； scanf（ ”%d ，k） ； head=deledulist（head， k） ；output（head） ； break ；case 5: flag=0 ；/while 循環(huán)結(jié)束 此程序不論是插入、 查找還是刪除運(yùn)算均是按序

24、號(hào)的方式來處理， 當(dāng)然也可改為按結(jié)點(diǎn) 的值來作相應(yīng)的處理，試修改以上程序?qū)崿F(xiàn)按值操作的功能。六、選作實(shí)驗(yàn)利 用單循 環(huán)鏈表 存儲(chǔ) 結(jié)構(gòu)， 解決約 瑟夫（ Josephus ）環(huán)問 題。即： 將編號(hào) 是 1,2,n（n0）的n個(gè)人按照順時(shí)針方向圍坐一圈，每人持有一個(gè)正整數(shù)密碼。開始時(shí)任選 一個(gè)正整數(shù)作為報(bào)數(shù)上限值 m, 從某個(gè)人開始順時(shí)針方向自 1 開始順序報(bào)數(shù)，報(bào)到 m 時(shí)停 止報(bào)數(shù)，報(bào) m 的人出列， 將他的密碼作為新的 m 值，從他在順時(shí)針方向的下一個(gè)人開始重 新從 1 報(bào)數(shù)，如此下去，直到所有的人全部出列為止。令 n 最大值取 30。設(shè)計(jì)一個(gè)程序， 求出出列順序，并輸出結(jié)果。實(shí)驗(yàn)三 樹形

25、結(jié)構(gòu)一、實(shí)驗(yàn)?zāi)康模?掌握二叉樹的數(shù)據(jù)類型描述及二叉樹的特性。2 掌握二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) （二叉鏈表 ）的建立算法。3 掌握二叉鏈表上二叉樹的基本運(yùn)算的實(shí)現(xiàn)。二、實(shí)驗(yàn)內(nèi)容：從以下 1、2 和 3、4 中各選擇一項(xiàng)內(nèi)容1. 用遞歸實(shí)現(xiàn)二叉樹的先序、中序、后序 3 種遍歷。2. 用非遞歸實(shí)現(xiàn)二叉樹的先序、中序、后序 3 種遍歷。3. 實(shí)現(xiàn)二叉樹的層次遍歷。4. 將一棵二叉樹的所有左右子樹進(jìn)行交換。三、實(shí)驗(yàn)要求：1. 根據(jù)實(shí)驗(yàn)內(nèi)容編程，上機(jī)調(diào)試、得出正確的運(yùn)行程序。2. 寫出實(shí)驗(yàn)報(bào)告（包括源程序和運(yùn)行結(jié)果） 。四、實(shí)驗(yàn)學(xué)時(shí)： 4 學(xué)時(shí)五、實(shí)驗(yàn)步驟：1進(jìn)入編程環(huán)境，建立一新文件；2. 參考以下相關(guān)內(nèi)容

26、，編寫程序，觀察并分析輸出結(jié)果。 將建立二叉樹及先序、 中序、 后序 3 種遍歷算法都寫成子函數(shù)， 然后分別在主函數(shù) 中調(diào)用它，但在建立二又樹中，必須把二叉樹看成完全二叉樹的形式。若不是完全 二叉樹，則在輸入數(shù)據(jù)時(shí)，用虛結(jié)點(diǎn) （不存在 ）表示（本算法中，用“， ”號(hào)代替 ）。 用非遞歸法實(shí)現(xiàn)二叉樹的遍歷 非遞歸算法中，必須設(shè)置堆棧，可以直接用一維數(shù)組來代替棧，但必須另外設(shè)置棧 頂指針。 實(shí)現(xiàn)二叉樹的層次遍歷 用一個(gè)一維數(shù)組代替隊(duì)列，實(shí)現(xiàn)二叉樹的層次遍歷。 將一棵二叉樹的所有左右子樹進(jìn)行交換。 本算法只要增加一個(gè)實(shí)現(xiàn)二叉樹左右子樹交換的子函數(shù)即可。為了便于查看，在主 函數(shù)將交換前后的三種遍歷效果

27、，分別輸出。以下為部分參考程序：/ 遞歸實(shí)現(xiàn)二叉樹的 3 種遍歷#includetypedef char elemtype ； struct bitree定義二叉樹數(shù)據(jù)類型 elemtype data ； / 結(jié)點(diǎn)信息 bitree *lchild ， *rchild ； / 左右孩子 ;bitree *create() / 建立二叉鏈表 bitree *root, *s， *q100 ； /q 為隊(duì)列，最大空間為 100int front=l ， rear=0 ； / 隊(duì)列頭、尾指針 char ch ； root=NULL ；cout ”請(qǐng)輸入結(jié)點(diǎn)值 (，為虛結(jié)點(diǎn)， #結(jié)束 )：”ch ；w

28、hile(ch!= # )s=NULL ；if(ch!= , )s=new bitree ； s-data=ch ；s-lchild=NULL ； s-rchild=NULL ；rear+ ； qrear=s ； / 進(jìn)隊(duì) if(rear=1) root=s ； elseif(s!=NULL)&(qfront!=NULL)if(rear%2=0) qfront-lchild=s ； else qfront-rchid=s； if(rear 2=1)front+ ； / 出隊(duì)cinch ；return root ：bitree *p ；p=root ；if(p!=NULL)/ 中序遍歷/ 后序遍

29、歷coutdatalchild) ； preorder(p-rchild) ； void inorderl(bitree *root) bitree*p ； p=root ；if(p!=NULL)inorder(p-lchild) ；coutdatarchild) ； void postorder( bitree *root) bitree *p ； p=root ； if(p!=NULL)postorder(p-lchild) ；postorder(p-rchild) coutdata “”； void main()bitree *root ；root=create() ； / 建立二叉鏈表

30、 cout ”先序遍歷的結(jié)果” endl ； preorder(root) ； coutendl ； cout ”中序遍歷的結(jié)果” endl ； inorder(root) ； coutendl ：cout ”后序遍歷的結(jié)果” endl ； postorder(root) ； cout0) while(p!=NULL)3 種遍歷，部分遍歷程序如下 / 先序遍歷/s 為堆棧/top 為棧頂指針中序遍歷/ 后序遍歷coutdatalchild ；p=stop- ； / 退棧 p=p-rchild ；void inorderl(bitree*root) / bitree*p ， *s100 ；int

31、 top=0 ；p=root ； while(p!=NULL)Il(topO) while(p!=NULL)s+top=p ； p=p-lchild ； p=stop- ； coutdatarchild ；void postorderl( bitree *root) (bitree *p *sl100 ；int s2100 ， top=0 ，b ； p=root ；dowhile(p!=NULL)s1top=p ； s2top+=0 ； p=p-lchild ； )if(top0)(b=s2-top ；p=s1top ；if(b=0)sltop=p ； s2top+=l ； p=p-rchil

32、d ； elsecoutdata0) ；/ / 建立二叉鏈表參考前述程序/ 按照層次遍歷二叉鏈表 #include typedef char elemtype ； struct bitreeelemtype data ； / 結(jié)點(diǎn)信息 bitree *lchild ， *rchild ； / 左右孩子 ;/ 按層次遍歷二叉樹 (建立二叉鏈表同前 ) void lorder(bitree *t) bitree q100 ，*p ；/q 代表隊(duì)列int f,r; /f ，r 類似于隊(duì)列頭、尾指針 q1=t ； f=r=l ； cout ”按層次遍歷二叉樹的結(jié)果為：” ; while if=r) p

33、=qf ； f+ ； / 出隊(duì) coutdatalchild!=NULL) r+ ；qr=p-lchild ； / 入隊(duì)if p-rchild!=NULLl r+ ； qr=p-rchild; / 入隊(duì) coutlchild); leftOright(root-rchild);bitree *t=root-lchild; root-lchild=root-rchild; root-rchild=t;/ 主函數(shù)void main()bitree *root ；root=create() ； / 建立二叉鏈表coutendlendl ”左右子樹交換前的遍歷結(jié)果” endl ； cout ”先序遍歷

34、的結(jié)果” endl ；preorder(root) ； coutendl ； cout ”中序遍歷的結(jié)果” endl ； inorder(root) ； coutendl ： cout ”后序遍歷的結(jié)果” endl ； postorder(root) ； coutendl ；leftTOright(root) ； coutendlendl ”左右子樹交換后的遍歷結(jié)果” endl ； cout ”先序遍歷的結(jié)果” endl ； preorder(root) ； coutendl ； cout ”中序遍歷的結(jié)果” endl ； inorder(root) ； coutendl ； cout ”后序

35、遍歷的結(jié)果” endl ； postorder(root) ； coutarcsvw.adj=l ；return ；void del_arc(graph *g ， int v ，int w)g-arcvw.adj=0 ；retum;/ 內(nèi)容 1 參考程序#define maxnode 40#define null 0 #include typedef struct st_arc int adjvex ； int weight ； struct st_arc *nextrac ；arcnode ；typedef structint vertex ；struct st_arc *firstarc；

36、vernode ；typedef vernode adjlistmaxnode；void del_arc(vernode g ，int v ， int w) / 刪除從頂點(diǎn) v 到頂點(diǎn) w 的邊 arcnode * rl,*r 2 ； rl=gv frrstarc ；r2=rl ； while(r1!=null&r1-adjvex!=w) r2=rl;rl=rl-nextarcif (rl=null)printf( ” no edge v-w ”)；return ；elseif(r1=r2) / 當(dāng)只有一個(gè)邊結(jié)點(diǎn)時(shí)gv.firstarc=r1-nextarcelser2-nextarc=r1-

37、nextarc rl=gw.firstarc ； r2=rl ；while(r1!=null&r1-adjvex!=v)應(yīng)的r2=rl ；rl = rl-n extarc ；if (rl= = null)printf( ”no edge v-w. ”)；/ 有多個(gè)邊結(jié)點(diǎn)時(shí)/ 在以 v 為頭結(jié)點(diǎn)的鏈表中，刪除相/ 邊結(jié)點(diǎn)return ；elseif(r1=r2) gw.firstarc=rl-nextarc ；elser2-nextarc=r1-nextarc ；void print(vernode g ， int n)/ 打印圖中各結(jié)點(diǎn)的結(jié)構(gòu)arcnode *q ；int i ；printf(

38、 ”adjacency list of the graph：n ”)；for(i=0 ；iadjvex) ；printf( ” %dt ”， q-weight) ；q=q-nextarc ；printf( ”n ” )；main()int i ，j，n，k ，w，v；arcnode * p ，*q；adjlist g ；printf( ” Input node ： ”)；/ 輸入圖中頂點(diǎn)個(gè)數(shù)scanf( ”%d ”，&n) ；for(k=0 ；kadjvex=j ；q-weight=w ；q-nextarc=gi.firstarc ； / 頭指針指向新的邊結(jié)點(diǎn) gi.firstarc=q ；p

39、=(arcnode*)malloc(sizeof(arcnode) ； p-nextarc=gi.firstarc ； gi.firstarc=q ；p=(arcnode*)malloc(sizeof(arcnode) ；p-adjvex=i ；p-weight=w ； p-nextarc=gj.firstarc ；gj.firstarc=p ；print(g ， n) ；printf( ” Delete edge V-w ：” )；scanf( ”%d%d ”， v ，&w) ；del_arc(g ，v ，w)；print(g ，n) ； 內(nèi)容 2 的知識(shí)要點(diǎn)： 構(gòu)造有向圖鏈接表與無向圖鏈接

40、表的算法區(qū)別是：無向圖兩結(jié)點(diǎn)無向?qū)ε迹?因而鄰接表有一定的對(duì)偶性； 有向圖兩結(jié)點(diǎn)間有向無對(duì)偶關(guān)系， 因而建立鄰接表時(shí)應(yīng)根據(jù)輸入的頂點(diǎn)及邊的有向關(guān)系建立 （當(dāng)箭頭方向離開結(jié)點(diǎn)為有關(guān)，當(dāng)箭頭方向指向結(jié)點(diǎn)為無關(guān) )/ 內(nèi)容 2 的參考程序/ 有向圖鏈表的存儲(chǔ)結(jié)構(gòu)為：typedef struct st_arcint aajvex ； / 存放依附于該邊的另一頂點(diǎn)在一維數(shù)組中的序號(hào)int weight ； / 存放和該邊有關(guān)的信息，如權(quán)值等struct st_arc *nextarc ； / 依附于該頂點(diǎn)的下一個(gè)邊結(jié)點(diǎn)的指針arcnode ；typedef structint vertex ； / 存放

41、與頂點(diǎn)有關(guān)的信息struct st_arc*firstarc ；vernode ； / 存儲(chǔ)頂點(diǎn)信息typedef vernode adjlistmaxnode ；/ 參考程序見內(nèi)容 1 內(nèi)容 3 的知識(shí)要點(diǎn)：深度優(yōu)先搜索遍歷圖的算法：首先訪問指定的起始頂點(diǎn) v0 ，從 vo 出發(fā)，訪 問 vo 的一個(gè)未被訪問過的鄰接頂點(diǎn) w1 ，再?gòu)?w1 出發(fā)，訪問 w1 的一個(gè)未被訪 問的頂點(diǎn) w2 ，然后從 w2 出發(fā)，訪問 w2 的一個(gè)未被訪問的鄰接頂點(diǎn) w3 ，依此 類推，直到一個(gè)所有鄰接點(diǎn)都被訪問過為止。圖采用鄰接表作存儲(chǔ)結(jié)構(gòu)，圖的深度優(yōu)先遍歷次序?yàn)?T-一參考程序運(yùn)行過程中，深度優(yōu)先遍歷時(shí)指針 p 的移動(dòng)方向示意如圖下所示， 圖中pl、p2、p3、p4、p5和p6為深度優(yōu)先遍歷圖的各結(jié)點(diǎn)時(shí)，指針p的移動(dòng)次序。p5/內(nèi)容3的參考程序#defi ne maxnode 40#defi ne null 0#includevsddio . htypedef struct st_arc/定義結(jié)構(gòu)體 int adivex ；int weigh ；struct st_arc *n extarc arcnode ;typedef structint vertex ；struct st_arc *firstarc ;vernode ;typedef vernode