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

1、課程設(shè)計(jì)說明書設(shè)計(jì)題目： 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 專業(yè)： 電子信息科學(xué)與技術(shù) 班級(jí)： 2008級(jí)1班 設(shè)計(jì)人： 山 東 科 技 大 學(xué)年 月 日課程設(shè)計(jì)任務(wù)書學(xué)院： 專業(yè)： 班級(jí)： 姓名： 一、 課程設(shè)計(jì)題目： 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 二、 課程設(shè)計(jì)主要參考資料：（1） （2） （3） 三、課程設(shè)計(jì)應(yīng)解決的主要問題：（1）約瑟夫環(huán)問題 （2 迷宮問題 （2）三元組表示的稀疏矩陣的轉(zhuǎn)置、加法和乘法實(shí)現(xiàn) （3）前綴算術(shù)表達(dá)式轉(zhuǎn)換及表達(dá)式計(jì)算 （4）有向無環(huán)圖每個(gè)頂點(diǎn)出發(fā)的最短路徑及其長度； （5）2-路歸并排序 四、課程設(shè)計(jì)相關(guān)附件（如圖紙、軟件等）：五、任務(wù)發(fā)出日期： 課程設(shè)計(jì)完成日期： 指導(dǎo)教師簽字： 系

2、主任簽字： 指導(dǎo)教師對(duì)課程設(shè)計(jì)的評(píng)語指導(dǎo)教師簽字： 年 月 日設(shè)計(jì)1 約瑟夫環(huán)問題一、需求分析一、具體目標(biāo)包括： 1實(shí)現(xiàn)單循環(huán)鏈表的初始化 2理解約瑟夫環(huán)的定義，用循環(huán)找到每次報(bào)數(shù)人的序號(hào) 3. 從單循環(huán)鏈表中刪除節(jié)點(diǎn)，并判斷鏈表空與非空的臨界條件。二、單向循環(huán)鏈表的抽象數(shù)據(jù)類型定義為： adt circlelist 數(shù)據(jù)對(duì)象：dai | aielemset,i=1,2,n,n0 數(shù)據(jù)關(guān)系：r=, | ai-1,aid,i=2,n 基本操作：link initlist（int n）操作結(jié)果：構(gòu)造一個(gè)含有n個(gè)元素的單向循環(huán)鏈表。三、問題描述設(shè)編號(hào)為1，2，n(n0)個(gè)人按順時(shí)針方向圍坐一圈，每人

3、持有一個(gè) 正整數(shù)密碼。開始時(shí)任意給出一個(gè)報(bào)數(shù)上限值m，從第一人開始順時(shí)針方向自1 起順序報(bào)數(shù)，報(bào)到m時(shí)停止報(bào)數(shù)，報(bào)m的人出列，將他的密碼作為新的m值，從他在順指針方向上的下一個(gè)人起重新自1起順序報(bào)數(shù)；下去，直到所有人全部出列為止。要求設(shè)計(jì)一個(gè)程序模擬此過程。四、基本要求利用單向循環(huán)鏈表存儲(chǔ)結(jié)構(gòu)模擬此過程，按照出列的順序印出個(gè)人的編號(hào)。二、概要設(shè)計(jì)一、本程序分三個(gè)模塊 1）主模塊 void main() 初始化； 接受命令； 處理命令； 2）單向循環(huán)表單元模塊，實(shí)現(xiàn)單向循環(huán)鏈表的抽象數(shù)據(jù)類型功能； 3）節(jié)點(diǎn)結(jié)構(gòu)單元模塊，定義單向循環(huán)鏈表的節(jié)點(diǎn)結(jié)構(gòu)。三、詳細(xì)設(shè)計(jì)1、構(gòu)建一個(gè)單循環(huán)鏈表算法流程圖1結(jié)

4、束p-next=lp=qp-next=qhead=qi=1p指向申請(qǐng)空間i=np指向申請(qǐng)空間2主模塊實(shí)現(xiàn)算法從頭結(jié)點(diǎn)開始，根據(jù)報(bào)數(shù)上限找到下一個(gè)出列人的序號(hào)，并讀出該人的密碼作為新的報(bào)數(shù)上限，從此節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)開始進(jìn)行新的查找。通過指針依次刪除出列人相應(yīng)的節(jié)點(diǎn)，直到該鏈表中無節(jié)點(diǎn)，退出循環(huán)。輸入報(bào)數(shù)上限jnm=1?inexti=i+1=1q=l-next輸出q的numbermnext-number刪除q節(jié)點(diǎn)初始化一個(gè)單循環(huán)鏈表四、運(yùn)行結(jié)果及分析測(cè)試用例1：（一般數(shù)據(jù)）五、總結(jié)本次實(shí)驗(yàn)主要考察了對(duì)單循環(huán)鏈表的應(yīng)用。附：主要源代碼typedef struct lnode int data2;st

5、ruct lnode *next;lnode, *linklist;void creatlist(linklist l,int n)int i;linklist p, q=l;printf(請(qǐng)輸入報(bào)數(shù)密碼以及學(xué)生序號(hào)，并用逗號(hào)隔開:n);for(i=n;i0;i-) p=(linklist)malloc(sizeof(lnode);scanf(%d,%d,&p-data0,&p-data1);p-next=l; q-next=p; q=p;p-next=l-next;printf(學(xué)生依次出圈序號(hào)為：);printf(n*n);void main(void)int i=1,j,n; linkl

6、ist l,p,q; printf(請(qǐng)輸入學(xué)生數(shù)目n=); scanf(%d,&j);l=(linklist)malloc(sizeof(lnode); l-next=l; creatlist(l,n); p=l-next;q=l-next; while(j=3) if(p-data0)=1)while(p-next)!=q) p=p-next;p-next=q-next;printf(%d ,q-data1);j-;free(q);q=p-next; p=q;elsewhile(idata0) q=q-next; i+;while(p-next)!=q) p=p-next;p-next=q-

7、next;printf(%d ,q-data1);j-;free(q);q=p-next;p=q;i=1; if(p-data0%2) printf(%d ,p-data1); printf(%d ,p-next-data1); else printf(%d ,p-next-data1);printf(%d ,p-data1);printf(n*n); printf(n排序完畢n);設(shè)計(jì)2 迷宮問題一、需求分析一、具體目標(biāo)：1、生成一個(gè)m x n的迷宮，0和1分別表示迷宮中的通路和障礙。2、存在回路時(shí)，找出回路；3、不重復(fù)走過的路。二、棧的抽象數(shù)據(jù)類型的定義：adt stack 數(shù)據(jù)對(duì)象：d

8、ai|ai elemset,i=1,2,.,n,n0 數(shù)據(jù)關(guān)系：r1 | ai-1, aid, i=2,.,n 基本操作：initstack(sqstack *s)push(sqstack *s,snodeetype e)pop(sqstack *s,snodeetype *e)stackempty(sqstack *s) adt stack三、問題描述：迷宮時(shí)一些互相連通的交叉路口的集合，給定一個(gè)迷宮入口，一個(gè)迷宮出口，當(dāng)從入口到出口存在通路時(shí)輸出其中的一條通路，當(dāng)從入口到出口不存在通路時(shí)輸出無通路存在。二、概要設(shè)計(jì)1、主模塊void main () 構(gòu)造一個(gè)空棧，實(shí)現(xiàn)其初始化、插入、刪除操

9、作； 輸入迷宮入口位置； 判斷是否有回路； 輸出出口位置或“沒有找到！”2、主要模塊主模塊main()構(gòu)造空棧實(shí)現(xiàn)基本操作輸出出口位置或“沒有找到”輸入入口的位置并判斷是否有出口三、詳細(xì)設(shè)計(jì)流程圖：int *e1s-top=s-basee-di=s-top-di;e-ord=s-top-ord;e-seat.x=s-top-seat.x;e-seat.y=s-top-seat.y;e1=s-top;s-top=s-top-next;return error;free(e1)return ok2、主函數(shù)：流程圖：i=1; j=1i=njbase=(selemtype /構(gòu)造一個(gè)空棧s*)mall

10、oc(sizeof(selemtype);s-base-ord=0;if(!s-base)exit(overflow); /存儲(chǔ)分配失敗s-top=s-base;return ok; /initstackvoid push(sqstack *s,selemtype *e) /插入元素e為新的棧頂元素e-next=s-top; s-top=e;/pushstatus pop(sqstack *s,selemtype *e) /若棧不空，則刪除s的棧頂元素，用e返回其值，并返回ok,否則返回errorselemtype *e1;if(s-top =s-base) return error;e-di

11、=s-top-di;e-ord=s-top-ord;e-seat.x=s-top-seat.x;e-seat.y=s-top-seat.y;e1=s-top;s-top=s-top-next; free(e1);return ok;status stackempty(sqstack *s) /判斷棧s是否為空，若不空返回true,否者返回falseif(s-top=s-base) return true;else return false;void nextpos(posttype seat,int di,posttype curpose)switch(di)case 1:curpose-x=

12、seat-x;curpose-y=(seat-y)+1;break;case 2:curpose-x=seat-x+1;curpose-y=seat-y;break;case 3:curpose-x=seat-x;curpose-y=seat-y-1;break;case 4:curpose-x=seat-x-1;curpose-y=seat-y;break;status mazepath(sqstack *s,int masenn,posttype start,posttype end) /若迷宮mase中存在從入口start到出口end的通道，則求得一條放在棧中（從棧底到棧頂），并返回tr

13、ue，否則返回false;selemtype *e;posttype curpos=start;int curstep=1; initstack(s);doif(masecurpos-xcurpos-y=0) /當(dāng)前位置可以通過，即未曾走過的道路masecurpos-xcurpos-y=2; /留下痕跡e=(selemtype *)malloc(sizeof(selemtype);if(!e)exit(overflow);/存儲(chǔ)分配失敗e-ord=curstep;/e-seat=(posttype )malloc(sizeof(struct post);e-seat.x=curpos-x; e

14、-seat.y=curpos-y; e-di=1;push(s,e);/加入路徑if(curpos-x=end-x & curpos-y=end-y )return true; nextpos(&s-top-seat,1,curpos);curstep+;else /當(dāng)前位置不通if(!stackempty(s)while(s-top-di=4 & !stackempty(s) e=(selemtype )malloc(sizeof(selemtype);if(!e) exit(overflow);/存儲(chǔ)分配失敗pop(s,e);curstep-;free(e);if(s-top-ditop-

15、di+;nextpos(&s-top-seat,s-top-di,curpos);/設(shè)定當(dāng)前位置是該新方向上的相鄰塊while(!stackempty(s);return false;void imase(int masenn,posttype start,posttype end,int *n1,int *m1)int n,m,x,y,i,j;printf(迷宮行列數(shù)為：（用逗號(hào)隔開）（沒有外墻小于90）:);do scanf(%d,%d,&n,&m); while(n=0 & m=0);*n1=n;*m1=m;for(i=0;i=m+1;i+)mase0i=1;masen+1i=1;for

16、(j=0;jn | ym | x-1 | yx,&start-y);printf(輸入結(jié)束坐標(biāo)：);scanf(%d,%d,&end-x,&end-y);while(!(start-xyx0 & start-y0 & end-xyx0 & end-y0);void main()sqstack s; elemtype e;int masenn=0，i,j,n,m;struct post start, end;imase(mase,&start,&end,&n,&m);if(mazepath(&s,mase,&start,&end)while(!stackempty(&s)pop(&s,&e);m

17、asee.seat.xe.seat.y=4;for(i=1;i=n;i+)for(j=1;j=m;j+)if(maseij=2) maseij=0;if(maseij=0) printf( );else if(maseij=1)printf( + );else printf( - );printf(n);else printf(沒找到！);設(shè)計(jì)3 三元組表示的矩陣的操作實(shí)現(xiàn)一、需求分析一、抽象數(shù)據(jù)類型adt sparsematrix 數(shù)據(jù)對(duì)象： daj1,j2, .,ji, .,jn| ji =0,.,bi -1, i=1,2,.,n 數(shù)據(jù)關(guān)系： row|1=i=m,1=j=n-1 col|1

18、=i=m-1,1=j=n adt array 2、基本操作：（1）status logicmatrix(smatrix m,smatrix n,smatrix *q)操作結(jié)果：求矩陣邏輯乘積q=m*n （2）status summatrix(smatrix m,smatrix n,smatrix *q)操作結(jié)果：m+n=q二、概要設(shè)計(jì)1、用三元組順序表存儲(chǔ)表示，求稀疏矩陣的轉(zhuǎn)置矩陣2、求兩個(gè)矩陣的和及乘積3、求稀疏矩陣的自反閉包、對(duì)稱閉包和傳遞閉包三、詳細(xì)設(shè)計(jì)文字性描述：本設(shè)計(jì)本人能力有限，用序偶輸入的，根據(jù)自反、對(duì)稱和可傳遞閉包定義，在矩陣操作上，稍微改動(dòng)一下，但是也能基本實(shí)現(xiàn)，自反和對(duì)稱閉

19、包運(yùn)算，另外，可傳遞閉包用遞歸實(shí)現(xiàn)，只是循環(huán)次數(shù)是矩陣的行數(shù)四、運(yùn)行結(jié)果及分析五、總結(jié) 主要應(yīng)用三元組處理矩陣，利用矩陣的加法和乘法求自反閉包、對(duì)稱閉包和傳遞閉包附：主要源代碼typedef struct int i,j, e;triple;typedef struct triple datamax+1;int mu,nu,tu;tsmatrix;void zifanbibao(int amaxmax,int mu,int nu)int i,j,cmaxmax; for(i=1;i=mu;i+)for(j=1;j=nu;j+) if(i=j) printf(1 );cij=1;else cij

20、=aij;printf(%d ,aij); printf(n); printf(自反閉包關(guān)系輸出為：n);for(i=1;i=mu;i+)for(j=1;j=nu;j+) if(cij)printf( ,i,j);void duichenbibao(int amaxmax,int mu,int nu) int i,j, cmaxmax; for(i=1;i=mu;i+)for(j=1;j=nu;j+) cij=aij|aji;printf(%d ,cij);printf(n); printf(對(duì)稱閉包關(guān)系輸出為：n); for(i=1;i=mu;i+)for(j=1;j=nu;j+) if(c

21、ij)printf( ,i,j); void kechuandibibao(int amaxmax,int mu,int nu)inti,j,k,t,t cmaxmax=0,0,0,0,0,0,0,0,0;for(t=1;t=mu;t+) for(i=1;i=mu;i+)for(j=1;j=nu;j+)for(k=1;k=nu;k+) cij=cij|(aik*akj);for(i=1;i=mu;i+)for(j=1;j=nu;j+) printf(%d ,cij); printf(n); printf(可傳遞閉包關(guān)系輸出為：n); for(i=1;i=mu;i+)for(j=1;j=nu;j

22、+) if(cij)printf( ,i,j);void main() int i,j, mu,nu,tu=0, amaxmax;printf(請(qǐng)輸入矩陣n); printf(行數(shù)為：);scanf(%d,&mu);printf(列數(shù)為：);scanf(%d,&nu);printf(數(shù)據(jù)為:n);for(i=1;i=mu;i+)for(j=1;j=nu;j+)scanf(%dn,&aij); if(aij!=0) tu+; printf(你輸入的數(shù)據(jù)為：n);for(i=1;i=mu;i+)for(j=1;j=nu;j+)printf(%d ,aij); printf(n);printf(求得

23、自反閉包為：n); zifanbibao(a,mu,nu); printf(n求得對(duì)稱閉包為：n); duichenbibao(a,mu,nu);printf(n求得可傳遞閉包為：n);kechuandibibao(a,mu,nu);設(shè)計(jì)4前綴表達(dá)式一、需求分析1、具體目標(biāo)包括：（1）構(gòu)造一個(gè)隊(duì)列，實(shí)現(xiàn)對(duì)隊(duì)列元素的插入，刪除操作（2）構(gòu)造一個(gè)棧，實(shí)現(xiàn)對(duì)棧的元素的插入和刪除操作，判斷棧為空的條件（3）利用二叉樹的遍歷的順序?qū)崿F(xiàn)把以前綴形式輸入的算術(shù)表達(dá)式轉(zhuǎn)換為中綴和后綴表達(dá)式2、棧的抽象數(shù)據(jù)類型的定義：adt stack 數(shù)據(jù)對(duì)象： d ai|ai elemset,i=1,2,.,n,n0 數(shù)據(jù)

24、關(guān)系： r1 | ai-1, aid, i=2,.,n 基本操作：initstack(sqstack *s)push(sqstack *s,snodeetype e)pop(sqstack *s,snodeetype *e)stackempty(sqstack *s) adt stack3、問題描述算術(shù)表達(dá)式與二叉樹之間存在著對(duì)應(yīng)關(guān)系，編寫把以前綴形式輸入的合法算術(shù)表達(dá)式轉(zhuǎn)換為中綴表達(dá)式，再轉(zhuǎn)換為后綴表達(dá)式，并求表達(dá)式的值要求。(1) 把前綴表達(dá)式轉(zhuǎn)換為中綴表達(dá)式；(2) 輸出中綴表達(dá)式；(3) 把中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式；(4) 利用棧結(jié)構(gòu)實(shí)現(xiàn)后綴表達(dá)式的求值；二、概要設(shè)計(jì)1、主模塊 vo

25、id main() 新建棧，隊(duì)列，樹，并實(shí)現(xiàn)初始化； 接受命令； 處理命令；2、主要模塊主模塊 main()隊(duì)列初始化輸入算術(shù)表達(dá)式輸出算術(shù)表達(dá)式三、詳細(xì)設(shè)計(jì)1、tree creatbitree(bitree t)/按前綴形式輸入算術(shù)表達(dá)式/構(gòu)造二叉鏈表表示的二叉樹tchar ch; scanf(%c,&ch); switch(ch) case +: ; case -: ; case *: ; case /: if(!(t=(bitnode *)malloc(sizeof(bitnode) exit(overflow); t-data=ch; t-lchild=(bitnode *)mallo

26、c(sizeof(bitnode); t-rchild=(bitnode *)malloc(sizeof(bitnode); t-lchild=creatbitree(t-lchild); t-rchild=creatbitree(t-rchild); break; default: if(!(t=(bitnode *)malloc(sizeof(bitnode) exit(overflow); t-data=ch; t-lchild=null; t-rchild=null;return t;流程圖1scanf(“%c”,&ch)case+case*case-case/!(t=(bitnode

27、*)malloc(sizeof(bitnode)exitt-data=ch;t-lchild=(bitnode*)malloc(sizeof(bitnode);t-rchild=(bitnode*)malloc(sizeof(bitnode);t-lchild=creatbitree(t-lchild)t-rchild=creatbitree(t-rchild);default!(t=(bitnode*)malloc(sizeof(bitnode)t-data=ch;t-lchild=null;t-rchild=null;return ok四、運(yùn)行結(jié)果及分析附主要源代碼：typedef str

28、uct bitnode /樹telemtype data; struct bitnode *lchild,*rchild;bitnode,*bitree;typedef struct node /棧snodeetype data; struct node *next;selemtype;typedef struct stack selemtype *base; selemtype *top;sqstack;typedef struct qnode /隊(duì)列qelemtype data; struct qnode *next;qnode,*queueptr;typedef struct queue

29、ptr front; /隊(duì)頭指針 queueptr rear; /隊(duì)尾指針linkqueue;status initqueue(linkqueue *q)/構(gòu)造一個(gè)空隊(duì)列qif(!(q-rear=(queueptr)malloc(sizeof(qnode)exit(overflow); q-front=q-rear;q-front-next=null;return ok;status enqueue(linkqueue *q,qelemtype e)/插入以e為q的新的隊(duì)尾元素 queueptr p; if(!(p=(queueptr)malloc(sizeof(qnode) exit(ove

30、rflow); p-data=e; p-next=null; q-rear-next=p; q-rear=p; return ok;status dequeue(linkqueue *q,qelemtype *e)/刪除q的隊(duì)頭元素，用e返回其值 queueptr p; p=q-front-next; *e=p-data; q-front-next=p-next; if(q-rear=p) q-rear=q-front; free(p); return ok;status initstack(sqstack *s) /構(gòu)造一個(gè)空棧ss-base=(selemtype *)malloc(size

31、of(selemtype);if(!s-base)exit(overflow); /存儲(chǔ)分配失敗s-top=s-base;return ok; /initstackvoid push(sqstack *s,snodeetype e) /插入元素e為新的棧頂元素selemtype *e1;e1=(selemtype *)malloc(sizeof(selemtype);e1-next=s-top;e1-data=e;s-top=e1;/pushstatus pop(sqstack *s,snodeetype *e) /若棧不空，則刪除s的棧頂元素，用e返回其值，并返回ok,否則返回errorse

32、lemtype *e1;if(s-top =s-base)return error;*e=s-top-data;e1=s-top;s-top=s-top-next;free(e1);return ok; status stackempty(sqstack *s) /判斷棧s是否為空，若不空返回true,否者返回falseif(s-top=s-base)return true;else return false;bitree creatbitree(bitree t)/按前綴形式輸入算術(shù)表達(dá)式/構(gòu)造二叉鏈表表示的二叉樹tchar ch; scanf(%c,&ch); switch(ch) cas

33、e +: ; case -: ; case *: ; case /: if(!(t=(bitnode *)malloc(sizeof(bitnode) exit(overflow); t-data=ch; t-lchild=(bitnode *)malloc(sizeof(bitnode); t-rchild=(bitnode *)malloc(sizeof(bitnode); t-lchild=creatbitree(t-lchild); t-rchild=creatbitree(t-rchild); break; default: if(!(t=(bitnode *)malloc(size

34、of(bitnode) exit(overflow); t-data=ch; t-lchild=null; t-rchild=null; return t;status inordert(bitree t) if(t) /中序遍歷二叉樹inordert(t-lchild);printf(%c,t-data);inordert(t-rchild);return ok;status afterordert(bitree t,linkqueue *q) char e; /后序遍歷二叉樹if(t)afterordert(t-lchild,q);afterordert(t-rchild,q);print

35、f(%c,t-data);e=t-data;enqueue(q,e);return ok;status jisuan(snodeetype *e1,snodeetype e2,char ch)switch(ch)case +: *e1=*e1+e2;break; case -: *e1=e2-*e1;break; case *: *e1=*e1*e2;break; case /:*e1=e2/(*e1);break;return ok;status oper(linkqueue *q)sqstack *s;char ch;int sag=1;snodeetype e1,e2,e;if(!(s=

36、(sqstack *)malloc(sizeof(sqstack) exit(overflow);while(q-front!=q-rear)dequeue(q,&ch);switch(ch)case +: ;case -: ;case *: ;case /:pop(s,&e1);pop(s,&e2); jisuan(&e1,e2,ch); push(s,e1);break;default:if(sag=1)printf(有幾個(gè)變量？按行輸入)為變量賦值：);sag=0;scanf(%f,&e); push(s,e);pop(s,&e1);printf(結(jié)果為：%3fn,e1);return

37、ok;void main()bitnode *t; linkqueue *q; q=(linkqueue *)malloc(sizeof(linkqueue);initqueue(q); t=(bitnode *)malloc(sizeof(bitnode);t-lchild=null; t-rchild=null; printf(按前綴形式輸入算術(shù)表達(dá)式n);printf(請(qǐng)輸入前綴表達(dá)式:);t-lchild=creatbitree(t-lchild);printf(中序表達(dá)式：); inordert(t-lchild);printf(n);printf(后序表達(dá)式：);afterorde

38、rt(t-lchild,q);printf(n);oper(q);設(shè)計(jì)5 有向無環(huán)圖每個(gè)頂點(diǎn)出發(fā)的最長路徑及其長度一、需求分析1、生成一個(gè)有向無環(huán)圖2、用鄰接表存儲(chǔ)3、從有向無環(huán)圖的每個(gè)頂點(diǎn)出發(fā)求其最長路徑和它的長度。二、概要設(shè)計(jì)一、抽象數(shù)據(jù)類型adt graph 數(shù)據(jù)對(duì)象: v是具有相同特性的數(shù)據(jù)元素的集合，稱為頂點(diǎn)集； 數(shù)據(jù)關(guān)系：r=vr,vr| v,wv 且 p(v,w)表示從 v 到 w 的一條弧，并稱 v 為弧尾，w 為弧頭。謂詞 p(v,w) 定義了弧 的意義或信息。基本操作：creatgraph(&g, v, vr): 操作結(jié)果： 按定義(v, vr) 構(gòu)造圖insertvex(

39、&g, v); 操作結(jié)果：在圖g中增添新頂點(diǎn)v。deletevex(&g, v);操作結(jié)果： 刪除g中頂點(diǎn)v及其相關(guān)的弧。dfstraverse(g, v, visit(); 操作結(jié)果：從頂點(diǎn)v起深度優(yōu)先遍歷圖g，并對(duì)每個(gè)頂點(diǎn)調(diào)用函數(shù)visit一次且僅一次三、詳細(xì)設(shè)計(jì)采用鄰接表的存儲(chǔ)表示，構(gòu)造一個(gè)有向圖：return ok給p申請(qǐng)一個(gè)空間；p-adjvex=j;p-nextarc=g-verticesi.firstarc;g-verticesi.firstarc=p;p-info=wk+;i=locatevex(g,v1)j=locate(g,v2)輸入各個(gè)頂點(diǎn)的值karcnum輸入各個(gè)弧尾，

40、弧頭權(quán)重int i ,j,k,w ;char v1,v2;arcnode *ptopologicalorder：int indegree ,i,j,k;sqstack *s;arcnode *p;對(duì)各個(gè)頂點(diǎn)求入度；建入度頂點(diǎn)棧ivexnumi+indegreei=0push(s,i)棧不為空pop(s,&j);push(t,j);+count;p!=nullp=p-nextarc；k=p-adjvex;-indegreek=0push(s,k);vej+p-infovekvek=vej+p-info;p!=null vli=veg-vexnum-1ivexnuint vemax_vertex_

41、num=0int vlmax_vertex_num=0;int i,j,ee,dut,k,el;char tag;sqstack *t;arcnode *p; i+;k=p-adjvex;dut=p-info;vlk-dutvlj vlj=vlk-dut;jvexnump!=nullp=p-next;p=k=p-adjvex;dut=p-info;ee=vej;el=vlk-dut;tag=(ee=el)?*: e=el return ok輸出數(shù)據(jù)和路徑+jp=p-nextarc四、運(yùn)行結(jié)果：五、總結(jié)利用棧的結(jié)果，求有向無環(huán)圖的關(guān)鍵路徑。附：主要源代碼typedef struct arcnod

42、e int adjvex; /改弧所指向的定點(diǎn) struct arcnode *nextarc;/指向下一條弧的指針 infotype info; /權(quán)重arcnode;typedef struct vnode vertextype data; /頂點(diǎn)信息 arcnode *firstarc; /指向第一條依附于改頂點(diǎn)的弧的指針vnode,adjlistmax_vertex_num;typedef struct adjlist vertices; int vexnum,arcnum;/圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)algraph;typedef struct node /棧snodeetype data

43、; struct node *next;selemtype;typedef struct stackselemtype *base; selemtype *top;sqstack;status initstack(sqstack *s) /構(gòu)造一個(gè)空棧ss-base=(selemtype *)malloc(sizeof(selemtype);if(!s-base)exit(overflow); /存儲(chǔ)分配失敗s-top=s-base;return ok; /initstackvoid push(sqstack *s,snodeetype e) selemtype *e1;e1=(selemtype *)malloc(sizeof(selemtype);e1-next=s-t