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

實(shí)驗(yàn)一 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)一、 實(shí)驗(yàn)?zāi)康模?1掌握線性表的鏈?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ù)、輸出等基本操作都定義成子函數(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)建單鏈表 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(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)；/在頭指針head所指的單鏈表中，在值為x的結(jié)點(diǎn)之后插入值為y的結(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-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!=NULL)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)coutx”不在表中，找不到!”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 link； 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； link *Locate(1ink *head，int x) 在單鏈表中查找第x個(gè)結(jié)點(diǎn) link *p； p=head； 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； p=p-next；) if(p=NULL)coutnext=p-next；delete(p)； void insert(1ink *head，int x,elemtype y)/在頭指針head所指單鏈表中，在第x個(gè)結(jié)點(diǎn)之后插入值為y的結(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的元素改成值為ylink *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!=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，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+9X8+5X9 B（X）=8X+22X7-9X8 1建立一元多項(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)內(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)系，使得線性表(al，a2，a3，an)成為(an，a3，a2，a1)。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)鏈表，從頭到尾掃描單鏈表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)鏈表 頭文件h1h的內(nèi)容 #define NULL 0 #include #include typedef struct node int num； struct node *next；linklist；以下是主程序#include”h1h”輸出循環(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； 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(”輸出建立的單循環(huán)鏈表：n”)； output(head)； printf(”現(xiàn)在進(jìn)行逆置! n”)； head=invert(head)； printf(”輸出進(jìn)行逆置運(yùn)算后的單循環(huán)鏈表的結(jié)點(diǎn)信息! n”)； output(head)； /雙向鏈表參考程序 /以下是頭文件hhh的內(nèi)容 #include #include typedef struct dupnode int data； struct dupnode *next,*prior；dulinklist；/以下是主程序的內(nèi)容#include”hhh”/create函數(shù)用來構(gòu)建雙向鏈表dulinklist *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 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，int x)dulinklist *p，*s；int j；p=head；j=0；whi1e(p-next!=head)&(jnext；j+；If(j=i-1)s(dulinklist*)malloc(sizeof(dulinklist)；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(dulinklist *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)；else printf(”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”)；printf(”%dn”,p-data)；p=p-next； void main()dulinklist *head；int flag=l，i，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 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)算均是按序號(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)三 樹形結(jié)構(gòu)一、 實(shí)驗(yàn)?zāi)康模?1掌握二叉樹的數(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)容，編寫程序，觀察并分析輸出結(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ù)將交換前后的三種遍歷效果，分別輸出。以下為部分參考程序：/遞歸實(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；while(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(rear2=1)front+； /出隊(duì)cinch；return root：void preorder(bitree *root) /先序遍歷bitree *p；p=root；if(p!=NULL)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()； /建立二叉鏈表cout”先序遍歷的結(jié)果”endl； preorder(root)；coutendl； cout”中序遍歷的結(jié)果”endl；inorder(root)；coutendl：cout”后序遍歷的結(jié)果”endl；postorder(root)；cout0) while(p!=NULL) coutdatalchild； p=stop-； /退棧p=p-rchild； void inorderl(bitree*root) /中序遍歷bitree*p，*s100； int 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； do while(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-rchild； elsecoutdata0)；/ /建立二叉鏈表參考前述程序/按照層次遍歷二叉鏈表#includetypedef char elemtype；struct bitree elemtype 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=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”先序遍歷的結(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”后序遍歷的結(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 struct int vertex； struct st_arc *firstarc；vernode； typedef vernode adjlistmaxnode； void del_arc(vernode g，int v，int w) /刪除從頂點(diǎn)v到頂點(diǎn)w的邊 arcnode *rl,*r2； rl=gvfrrstarc；r2=rl；while(r1!=null&r1-adjvex!=w)r2=rl;rl=rl-nextarc；if (rl=null)printf(”no edge v-w”)；return；elseif(r1=r2) /當(dāng)只有一個(gè)邊結(jié)點(diǎn)時(shí)gv.firstarc=r1-nextarc；else r2-nextarc=r1-nextarc； /有多個(gè)邊結(jié)點(diǎn)時(shí)rl=gw.firstarc；r2=rl；while(r1!=null&r1-adjvex!=v) /在以v為頭結(jié)點(diǎn)的鏈表中，刪除相應(yīng)的 /邊結(jié)點(diǎn)r2=rl；rlrl-nextarc；if (rl=null)printf(”no edge v-w.”)；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(”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=(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)造有向圖鏈接表與無向圖鏈接表的算法區(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_arc int 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； /存放與頂點(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，再