數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)關(guān)于最短路徑問(wèn)題+二叉樹(shù)排序問(wèn)題

1、 課程設(shè)計(jì)綜合成績(jī)?cè)u(píng)定設(shè)計(jì)題目一： 二 叉 排 序 樹(shù) 設(shè)計(jì)題目二： 最 短 路 徑 問(wèn) 題 設(shè)計(jì)題目三： 考核項(xiàng)目分值ac得分設(shè)計(jì)情況（共70分）設(shè)計(jì)工作量與難度20設(shè)計(jì)工作量大與設(shè)計(jì)有一定難度設(shè)計(jì)工作量與難度一般，基本達(dá)到了要求設(shè)計(jì)方案15設(shè)計(jì)方案正確、合理設(shè)計(jì)方案較正確、基本合理，但不是最優(yōu)設(shè)計(jì)完成情況35完成了選題的設(shè)計(jì)內(nèi)容，設(shè)計(jì)功能完整，相關(guān)算法設(shè)計(jì)正確，程序結(jié)果正確、直觀(guān)性好基本完成了選題的設(shè)計(jì)內(nèi)容及主要選題功能，相關(guān)算法設(shè)計(jì)基本正確，程序結(jié)果正確設(shè)計(jì)報(bào)告（共15分）報(bào)告組織結(jié)構(gòu)及內(nèi)容10內(nèi)容組織及結(jié)構(gòu)合理、內(nèi)容充實(shí)、層次清晰、圖表得當(dāng)內(nèi)容組織及結(jié)構(gòu)較合理、內(nèi)容較充實(shí)、層次較清晰、

2、圖表應(yīng)用基本得當(dāng)報(bào)告排版格式5格式規(guī)范，完全符合要求格式基本規(guī)范，基本符合要求設(shè)計(jì)態(tài)度（共15分）15設(shè)計(jì)態(tài)度認(rèn)真、積極設(shè)計(jì)態(tài)度比較認(rèn)真綜合得分課程設(shè)計(jì)綜合成績(jī)（折合為優(yōu)、良、中、及格與不及格計(jì)）其它說(shuō)明：目 錄1.二叉排序樹(shù)11.1 問(wèn)題描述11.2 設(shè)計(jì)方案與概要設(shè)計(jì)21.3 詳細(xì)設(shè)計(jì)41.4 程序運(yùn)行說(shuō)明與結(jié)果112.最短路徑問(wèn)題132.1 問(wèn)題描述132.2 設(shè)計(jì)方案與概要設(shè)計(jì)162.3 詳細(xì)設(shè)計(jì)172.4 程序運(yùn)行說(shuō)明與結(jié)果273.總結(jié)與分析32數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)1. 二叉排序樹(shù)1.1 問(wèn)題描述知二叉排序樹(shù)的二叉鏈表存儲(chǔ)結(jié)構(gòu)的類(lèi)型定義如下：typedef struct node int

3、 data; /用整數(shù)表示一個(gè)結(jié)點(diǎn)的名 struct node *lchild,*rchild; /左右指針域bstnode,*bstree; （1）鍵盤(pán)輸入一個(gè)元素序列創(chuàng)建一棵如圖（1）的二叉排序樹(shù)，并輸出該二叉排序樹(shù)的中序遍歷序列；45556053402370371224 圖（1） （2）在圖（1）中所得的二叉排序樹(shù)中插入一個(gè)值為58的結(jié)點(diǎn)，輸出它的中序遍歷序列； （3）在題（2）中所得的二叉排序樹(shù)中刪除值為45的結(jié)點(diǎn)，輸出它的中序遍歷序列；（4）我們知道教材中p220給出的二叉排序樹(shù)的刪除操作算法中，是用左子樹(shù)中最右下結(jié)點(diǎn)來(lái)替代要被刪除的結(jié)點(diǎn)（即為要被刪除結(jié)點(diǎn)的中序前驅(qū)），也可以用右子樹(shù)

4、中最左下結(jié)點(diǎn)來(lái)替代要被刪除的結(jié)點(diǎn)（即為要被刪除結(jié)點(diǎn)的中序后繼），根據(jù)此思路修改p220算法在寫(xiě)一個(gè)刪除操作，并利用修改后的刪除算法刪除圖（1）中二叉排序樹(shù)的值為45的結(jié)點(diǎn)，輸出它的中序遍歷序列；（5）利用題（2）中所得的二叉排序樹(shù)的所有葉子結(jié)點(diǎn)構(gòu)造一個(gè)帶頭結(jié)點(diǎn)的單鏈表l。要求不能破壞這棵二叉排序樹(shù)。所得的單鏈表l元素遞增，并輸出單鏈表l。（6）設(shè)計(jì)算法將圖（1）的二叉排序樹(shù)的左右子樹(shù)進(jìn)行交換。最后輸出所得到的二叉樹(shù)的中序遍歷序列。45556053402370371224所得二叉排序樹(shù)如圖所示： 圖（2）（7）用計(jì)算法統(tǒng)計(jì)并輸出圖（1）中所得的二叉排序樹(shù)中只有一個(gè)孩子結(jié)點(diǎn)的結(jié)點(diǎn)個(gè)數(shù)。（8）由圖（

5、1）的二叉排序樹(shù)，用計(jì)算法并編寫(xiě)程序輸出結(jié)點(diǎn)40的所有祖先結(jié)點(diǎn)。1.2 設(shè)計(jì)方案與概要設(shè)計(jì)1. 二叉排序樹(shù)應(yīng)用的存儲(chǔ)結(jié)構(gòu) typedef struct node / 二叉排序樹(shù)的存儲(chǔ)結(jié)構(gòu) int data; struct node *lchild,*rchild; bstnode,*bstree; typedef struct lnode /單鏈表的存儲(chǔ)結(jié)構(gòu) int data; struct lnode *next; lnode,*linklist;二叉排序樹(shù)的設(shè)計(jì)用到了單鏈表l。單鏈表l主要用于題（5）的設(shè)計(jì)，用來(lái)存儲(chǔ)圖（1）的二叉排序樹(shù)中所有葉子結(jié)點(diǎn)，并將其輸出。2.方案設(shè)計(jì)本方案設(shè)計(jì)主要

6、應(yīng)用二叉樹(shù)的性質(zhì)。創(chuàng)建空二叉排序樹(shù)t，再輸入圖（1）中的元素后向t插入所有元素，在插入時(shí)比根結(jié)點(diǎn)小的放在樹(shù)的左子樹(shù)，比根結(jié)點(diǎn)大則放在樹(shù)的右子樹(shù)，同時(shí)樹(shù)的左右子樹(shù)也要遵循這個(gè)規(guī)律。在刪除操作中當(dāng)只有一個(gè)結(jié)點(diǎn)時(shí)可直接刪除，否則用左子樹(shù)中最右下結(jié)點(diǎn)來(lái)替代要被刪除的結(jié)點(diǎn)進(jìn)行刪除操作，亦可用右子樹(shù)中最左下結(jié)點(diǎn)來(lái)替代要被刪除的結(jié)點(diǎn)進(jìn)行刪除操作，可視為同種刪除方法。尋找葉子節(jié)點(diǎn)時(shí)主要采用遞歸方法，從根結(jié)點(diǎn)開(kāi)始遍歷當(dāng)發(fā)現(xiàn)結(jié)點(diǎn)無(wú)左右孩子時(shí)則得到當(dāng)前的結(jié)點(diǎn)元素并用尾插法將其放入單鏈表中直至遍歷完畢，最后輸出單鏈表l。在二叉排序樹(shù)進(jìn)行左右子樹(shù)交換時(shí)新創(chuàng)建樹(shù)r避免對(duì)樹(shù)t的干擾，把樹(shù)t復(fù)制給樹(shù)r,調(diào)用樹(shù)r采用遞歸法和交

7、換法進(jìn)行左右子樹(shù)的交換。尋找只有一個(gè)孩子結(jié)點(diǎn)的結(jié)點(diǎn)個(gè)數(shù)時(shí)也是采用遞歸法，從根結(jié)點(diǎn)開(kāi)始遍歷當(dāng)發(fā)現(xiàn)結(jié)點(diǎn)只有左孩子或右孩子是則計(jì)數(shù)加1直至遍歷完畢，輸出最后的計(jì)數(shù)。在取某元素的祖先結(jié)點(diǎn)時(shí)，從根結(jié)點(diǎn)與該元素對(duì)比并尋找該元素，其所走路徑即為該元素的祖先結(jié)點(diǎn)路徑，因此用數(shù)組將該路徑存儲(chǔ)起來(lái)，并將其輸出。3. 設(shè)計(jì)程序的整體功能結(jié)構(gòu)（整體算法的描述）void create(bstree &t):用來(lái)創(chuàng)建樹(shù)，輸入樹(shù)的所有元素；int search(bstree t,int k,bstree &q)：對(duì)樹(shù)進(jìn)行查找，判斷元素是否存在樹(shù)中；void insert(bstree &t,int e)：對(duì)樹(shù)進(jìn)行元素插入；

8、void deletebst(bstree &t,int k,int &e)：刪除中序前驅(qū)，用左子樹(shù)中最右下結(jié)點(diǎn)來(lái)替代要被刪除的結(jié)點(diǎn)；void deletebst1(bstree &t,int k,int &e)：刪除中序后驅(qū)，用右子樹(shù)中最左下結(jié)點(diǎn)來(lái)替代要被刪除的結(jié)點(diǎn)；void outtree(bstree &t)：中序遍歷函數(shù)，并輸出t;int createlist(linklist &l): 創(chuàng)建單鏈表l并為空;int insertlist(linklist &l,int e)：用尾插法向單鏈表插入元素；void leaf(bstree t,linklist &l)：得到樹(shù)t的葉子節(jié)點(diǎn)，并

9、得到其結(jié)點(diǎn)； void outlist(linklist l)：輸出點(diǎn)鏈表； bstree copy(bstree t)：創(chuàng)建樹(shù)r,把樹(shù)t復(fù)制給r；void create1(bstree &r)：把樹(shù)r的左右子樹(shù)進(jìn)行交換； int jie(bstree r)：計(jì)算只有一個(gè)孩子結(jié)點(diǎn)元素的個(gè)數(shù); void bstree(bstree r,int e)：得到某元素的祖先結(jié)點(diǎn)并將其輸出； int main()：主函數(shù); 1.3 詳細(xì)設(shè)計(jì) #include #include #define true 1#define false 0#define max 20 typedef struct node /

10、 二叉排序樹(shù)的存儲(chǔ)結(jié)構(gòu) int data; /用整數(shù)表示一個(gè)結(jié)點(diǎn)的名 struct node *lchild,*rchild; /左右指針域bstnode,*bstree; typedef struct lnode /單鏈表的存儲(chǔ)結(jié)構(gòu) int data; struct lnode *next; lnode,*linklist;創(chuàng)建樹(shù)函數(shù)：void create(bstree &t) int e; bstree q; t=null; printf(請(qǐng)輸入二叉樹(shù)的根：); scanf(%d,&e); printf(依次輸入個(gè)結(jié)點(diǎn)以-1結(jié)束：n); while(e!=-1) if(!search(t

11、,e,q) insert(t,e); scanf(%d,&e); 樹(shù)元素查找函數(shù)：int search(bstree t,int k,bstree &q) bstree p,f; p=t; f=null; if(p=null) return false; while(p) if(k=p-data) q=p; return true; else if(kdata) f=p; p=p-lchild; else f=p; p=p-rchild; q=f; return false; 對(duì)樹(shù)進(jìn)行插入函數(shù)：void insert(bstree &t,int e) bstree p,q; if(t=null

12、) p=(bstree)malloc(sizeof(bstnode); p-data=e; p-lchild=p-rchild=null; t=p; else if(!search(t,e,q) p=(bstree)malloc(sizeof(bstnode); p-data=e; p-lchild=p-rchild=null; if(edata) q-lchild=p; else q-rchild=p; 刪除函數(shù)（刪除中序前驅(qū)）： void deletebst(bstree &t,int k,int &e) bstree q,s,v,t; q=t; v=null; while(q) if(k

13、=q-data) break; else if(kdata) v=q; q=q-lchild; else v=q; q=q-rchild; if(!q) printf(我要?jiǎng)h除的數(shù)字不存在。n); return; e=q-data; if(q-lchild&q-rchild) s=q-lchild; v=q; while(s-rchild) v=s; s=s-rchild; q-data=s-data; q=s; if(q-lchild) t=q-lchild; else t=q-rchild; if(q=t) t=t; else if(q=v-lchild) v-lchild=t; else

14、 v-rchild=t; free(q); 刪除函數(shù)（刪除中序后繼）： void deletebst1(bstree &t,int k,int &e) bstree q,s,v,t; q=t; v=null; while(q) if(k=q-data) break; else if(kdata) v=q; q=q-lchild; else v=q; q=q-rchild; if(!q) printf(你要?jiǎng)h除的數(shù)字不存在。n); return; e=q-data; if(q-lchild&q-rchild) s=q-rchild; v=q; while(s-lchild) v=s; s=s-l

15、child; q-data=s-data; q=s; if(q-rchild) t=q-rchild; else t=q-lchild; if(q=t) t=t; else if(q=v-rchild) v-rchild=t; else v-lchild=t; free(q); 中序遍歷函數(shù)： void outtree(bstree &t) if(t) outtree(t-lchild); printf(%4d,t-data); outtree(t-rchild); 創(chuàng)建單鏈表： int createlist(linklist &l) /單鏈表初始化 l=(linklist)malloc(si

16、zeof(lnode); if(!l) return false; l-next=null; return true; 單鏈表插入函數(shù)： int insertlist(linklist &l,int e) /向單鏈表插入元素 lnode *p=l,*q; q=(lnode *)malloc(sizeof(lnode); if(!q) return false; while(p-next!=null) p=p-next; q-data=e; q-next=p-next; p-next=q; 葉子結(jié)點(diǎn)函數(shù): void leaf(bstree t,linklist &l) if(t) if(t-lc

17、hild=null&t-rchild=null) insertlist(l,t-data); leaf(t-lchild,l); leaf(t-rchild,l); 單鏈表輸出函數(shù)： void outlist(linklist l) /輸出單鏈表 lnode *p; p=l-next; while(p) printf(%4d,p-data); p=p-next;創(chuàng)建樹(shù)r函數(shù)： bstree copy(bstree t) /把樹(shù)t復(fù)制到樹(shù)r bstree r; if(t=null) return null; r=(bstree)malloc(sizeof(bstnode); r-data=t-d

18、ata; r-lchild=copy(t-lchild); r-rchild=copy(t-rchild); return r; 樹(shù)r左右子樹(shù)交換函數(shù)： void create1(bstree &r) bstree q; if(r) create1(r-lchild); create1(r-rchild); q=r-rchild; r-rchild=r-lchild; r-lchild=q; 計(jì)算只有一個(gè)孩子結(jié)點(diǎn)的函數(shù)： int jie(bstree r) int left,right,a; if(!r) return 0; if(r-lchild=null&r-rchild!=null) r

19、eturn 1; if(r-lchild!=null&r-rchild=null) return 1; left=jie(r-lchild); right=jie(r-rchild); a=left+right; return a; 祖先結(jié)點(diǎn)函數(shù)： void bstree(bstree r,int e) int vmax,i=0,j; bstree q=r; while(q) if(e=q-data) break; else if(edata) vi=q-data; q=q-rchild; else vi=q-data; q=q-lchild; +i; if(!q) return; for(j

20、=0;ji;j+) printf(%4d,vj); 主函數(shù)： int main() int e,k,a=0; char c; bstree t,r; linklist l; create(t); printf(1、該二叉排序樹(shù)的中序遍歷序列：n); outtree(t); r=copy(t); create1(r); printf(n2、輸入你插入的數(shù)字：); scanf(%d,&e); insert(t,e); outtree(t); printf(n3、請(qǐng)輸入你要?jiǎng)h除的數(shù)字：); scanf(%d,&k); deletebst(t,k,e); outtree(t); printf(n4、請(qǐng)

21、輸入你要?jiǎng)h除的數(shù)字：); scanf(%d,&k); deletebst1(t,k,e); outtree(t); createlist(l); printf(n5、是否輸出葉子結(jié)點(diǎn)構(gòu)成的單鏈表 y or n: ); scanf(%s,&c); if(c=y) leaf(t,l); outlist(l); printf(n6、是否輸出二叉排序樹(shù)的左右子樹(shù)進(jìn)行交換后的二叉樹(shù) y or n: ); scanf(%s,&c); if(c=y) outtree(r); printf(n7、是否輸出二叉排序樹(shù)中只有一個(gè)孩子結(jié)點(diǎn)的結(jié)點(diǎn)個(gè)數(shù) y or n: ); scanf(%s,&c); if(c=y)

22、printf(%4d,jie(r); printf(n8、請(qǐng)輸入要求祖先結(jié)點(diǎn)的元素: ); scanf(%d,&e); bstree(r,e); system(pause); return 0; 1.4 程序運(yùn)行說(shuō)明與結(jié)果1、創(chuàng)建二叉排序樹(shù)，并以中序遍歷輸出圖（1）：2、 向二叉排序樹(shù)插入元素58：3、刪除二叉排序樹(shù)元素45（刪除中序前驅(qū)）：4、刪除二叉排序樹(shù)元素45（刪除中序后繼）：由于在3中已刪除45，故給出提示，輸出原樹(shù)。5、輸出葉子結(jié)點(diǎn)：由于樹(shù)t在2中輸入58，故多了元素58。6、交換樹(shù)t的左右子樹(shù)，輸出圖（2）：中序遍歷輸出的圖（2）是圖（1）的倒序。7、 輸出只有一個(gè)子樹(shù)的結(jié)點(diǎn)個(gè)數(shù)

23、：8、查找元素40的祖先結(jié)點(diǎn)，并輸出：9、所有的運(yùn)行結(jié)果視圖：312. 最短路徑問(wèn)題2.1 問(wèn)題描述假設(shè)網(wǎng)中的頂點(diǎn)用一個(gè)整數(shù)來(lái)表示，并從0開(kāi)始編號(hào)，若網(wǎng)中有n個(gè)頂點(diǎn)，則這n個(gè)頂點(diǎn)為0，1，n-1。并假設(shè)網(wǎng)中不存在頂點(diǎn)到自身的弧。若網(wǎng)采用鄰接矩陣存儲(chǔ)結(jié)構(gòu)，則直接用一個(gè)二維數(shù)組來(lái)表示。如下圖所示的一個(gè)有向網(wǎng)：9 0124356136244457337211 圖（1）（1）基于圖的鄰接表存儲(chǔ)結(jié)構(gòu)重新設(shè)計(jì)dijkstra算法及其輸出算法，并以圖（1）的有向網(wǎng)為測(cè)試實(shí)例編程實(shí)現(xiàn)。（2）dijkstra算法適合求解權(quán)值非負(fù)的單源最短路徑問(wèn)題，即求一個(gè)頂點(diǎn)到其余各個(gè)頂點(diǎn)的最短路徑?，F(xiàn)給定一個(gè)有向網(wǎng)g=(v,

24、e)，各條邊上的權(quán)值均非負(fù)，給定g中一個(gè)頂點(diǎn)t，要求求出其余各個(gè)頂點(diǎn)到頂點(diǎn)t的最短路徑長(zhǎng)度并構(gòu)造最短路徑，這個(gè)問(wèn)題稱(chēng)為單目標(biāo)最短路徑問(wèn)題?；卩徑泳仃嚧鎯?chǔ)結(jié)構(gòu)設(shè)計(jì)算法并以圖（1）的有向網(wǎng)為測(cè)試實(shí)例編程實(shí)現(xiàn)。 （3）假設(shè)dijkstra算法采用鄰接矩陣存儲(chǔ)結(jié)構(gòu)，利用dijkstra算法求有向網(wǎng)中任意兩個(gè)頂點(diǎn)間的最短路徑長(zhǎng)度并構(gòu)造最短路徑。以圖（1）的有向網(wǎng)為測(cè)試實(shí)例編程實(shí)現(xiàn)。（4）假設(shè)dijkstra算法采用鄰接矩陣存儲(chǔ)結(jié)構(gòu)，求有向網(wǎng)中頂點(diǎn)i到頂點(diǎn)j的最短路徑長(zhǎng)度并輸出最短路徑，只求頂點(diǎn)i到頂點(diǎn)j的最短路徑，不能有冗余的循環(huán)，i和j從鍵盤(pán)輸入，并作為函數(shù)參數(shù)。（5）dijkstra算法不僅可以求

25、解有向網(wǎng)中權(quán)值非負(fù)的單源最短路徑問(wèn)題，對(duì)于無(wú)向網(wǎng)中權(quán)值非負(fù)的單源最短路徑問(wèn)題，同樣適用。設(shè)g=(v,e)是一個(gè)連通無(wú)向網(wǎng)，采用鄰接矩陣存儲(chǔ)結(jié)構(gòu)，每條邊上的權(quán)值均非負(fù)，從g中任取一個(gè)頂點(diǎn)i，考慮頂點(diǎn)i到各個(gè)頂點(diǎn)的最短路徑長(zhǎng)度：d(i,0)，d(i,1)，d(i,n-1)其中d(i,k)（0kn-1）表示頂點(diǎn)i到頂點(diǎn)k的最短路徑長(zhǎng)度，規(guī)定d(i,i)=0。這n個(gè)值中最大的那個(gè)稱(chēng)為頂點(diǎn)i的最大距離，記為l(i)，在所有頂點(diǎn)中，使l(i)達(dá)到最小的頂點(diǎn)稱(chēng)為網(wǎng)g的中心。利用dijkstra算法編程求解給定無(wú)向網(wǎng)的中心。例如，下面這個(gè)無(wú)向網(wǎng)的中心為頂點(diǎn)521354632261.51.8031.52.5圖（

26、2） （6）假設(shè)將5題中的網(wǎng)看成是一個(gè)礦區(qū)，它有7個(gè)礦，分別在頂點(diǎn)0,1，.,6處，這7個(gè)礦每天的礦產(chǎn)量分別是0：3000t，1：2000t，2：7000t，3：1000t，4：5000t，5：1000t，6：4000t，如下圖所示。21354632261.51.8031.52.5(3000)(5000)(7000)(1000)(2000)(1000)(4000)圖（3）現(xiàn)在要在頂點(diǎn)0,1，.,6中選一個(gè)來(lái)建選礦廠(chǎng)，如果選礦廠(chǎng)建在了頂點(diǎn)i，那么我們關(guān)心的是將各個(gè)礦生產(chǎn)的礦石都運(yùn)到頂點(diǎn)i處的運(yùn)輸量是多少，然后再來(lái)確定在哪里建選礦廠(chǎng)最好。一般情況下，我們以運(yùn)輸?shù)膖km數(shù)來(lái)度量運(yùn)輸量的大小，一噸貨物

27、運(yùn)輸一公里就叫1tkm。例如，如果選礦廠(chǎng)建在頂點(diǎn)0處，則總的運(yùn)輸量表示為g(0)，它等于g(0)=30000+20003+70005+10006.3+50009.3+10004.5+40006=122300(tkm) 如果選礦廠(chǎng)建在頂點(diǎn)1處，則總的運(yùn)輸量表示為g(1)，它等于 g(1)=30003+20000+70002+10003.3+50006.3+10001.5+40003=68300(tkm) 顯然，選礦廠(chǎng)建在頂點(diǎn)1要比建在頂點(diǎn)0處好，因?yàn)榻ㄔ陧旤c(diǎn)1處時(shí)運(yùn)輸量較小。當(dāng)然，頂點(diǎn)1是不是最好的還不能確定，應(yīng)把g(0)，g(1)，g(6)都算出來(lái)再比較一下，才可以選出一個(gè)最好的建廠(chǎng)地點(diǎn)。 一

28、般情況下，給定無(wú)向網(wǎng)g=(v,e)，采用鄰接矩陣存儲(chǔ)結(jié)構(gòu)，每條邊上的權(quán)值均非負(fù)，g的每個(gè)頂點(diǎn)i還有一個(gè)“產(chǎn)量”a(i)，對(duì)于每個(gè)頂點(diǎn)i，令：g(i)=a(0)d(0,i)+ a(1)d(1,i)+a(n-1)d(n-1,i)其中d(k,i)（0kn-1）表示頂點(diǎn)k到頂點(diǎn)i的最短路徑長(zhǎng)度。g(i)代表了把各個(gè)點(diǎn)的物資運(yùn)到頂點(diǎn)i處所花費(fèi)的tkm，對(duì)于具有n個(gè)頂點(diǎn)的無(wú)向網(wǎng)g來(lái)說(shuō)，使得g(i)達(dá)到最小的那個(gè)頂點(diǎn)i就稱(chēng)為該網(wǎng)的中央點(diǎn)，利用dijkstra算法編程求解給定無(wú)向網(wǎng)的中央點(diǎn)。 例如，上述圖（3）的中央點(diǎn)為頂點(diǎn)2。2.2 設(shè)計(jì)方案與概要設(shè)計(jì)1. 最短路徑問(wèn)題應(yīng)用的存儲(chǔ)結(jié)構(gòu) typedef str

29、uct arcnode int weight; int adjvex; struct arcnode *nextarc; arcnode; typedef struct vnode vertextype data; arcnode *firstarc; vnode; typedef struct vnode verticesmax; int vexnum,arcnum; int kind; algraph;應(yīng)用到很多的數(shù)組，其g100100用于鄰接矩陣存儲(chǔ)，d100用于存儲(chǔ)路徑長(zhǎng)度,path100用于存儲(chǔ)上一個(gè)鄰接點(diǎn),final100用于區(qū)分集合s和v，final=1時(shí)在集合s,final=0

30、時(shí)在集合v。2.方案設(shè)計(jì)通過(guò)鄰接表尋找有向圖中源點(diǎn)到各點(diǎn)的最短路徑，要先創(chuàng)建鄰接表。把dijkstra算法設(shè)計(jì)為利用鄰接表查找最短路徑的算法，在輸入源點(diǎn)后調(diào)用方法并進(jìn)行輸出操作。至于單目標(biāo)問(wèn)題創(chuàng)建一個(gè)與原鄰接表相反的逆鄰接表，如果創(chuàng)建成功則與源點(diǎn)問(wèn)題相同。任意兩點(diǎn)間的最短路徑是把個(gè)元素分別作為源點(diǎn)，依次調(diào)用方法并進(jìn)行輸出，得到任意兩點(diǎn)間的最短路徑。固定兩點(diǎn)的最短路徑是通過(guò)鄰接矩陣實(shí)現(xiàn)，利用dijkstra算法得到所有的最短路徑，在輸出時(shí)只輸出固定兩點(diǎn)的最短路徑。無(wú)向網(wǎng)的最短路徑方法亦可用dijkstra算法實(shí)現(xiàn)，得到以所有元素為源點(diǎn)的最短路徑，并獲得每個(gè)元素的最大距離，然后比較每個(gè)元素的最大距

31、離得到最小距離即為網(wǎng)g的中心。在獲得每個(gè)元素到個(gè)頂點(diǎn)距離時(shí)同時(shí)乘以每個(gè)元素的運(yùn)輸量，得到總運(yùn)輸量，進(jìn)行在比較得到運(yùn)輸量最小的元素即為該網(wǎng)的中央點(diǎn)。3. 設(shè)計(jì)程序的整體功能結(jié)構(gòu)（整體算法的描述）int locatevex(algraph &g, vertextype v)：查找元素是否存在有向圖中；void createdg(algraph &g,algraph &l)：創(chuàng)建鄰接表有向圖g和其逆鄰接表；void graphoutput(algraph &g)：用鄰接表輸出有向圖g;void dijkstra(int s,algraph &g) ：鄰接表型的dijkstra算法；void out(

32、int s,algraph &g)：鄰接表dijkstra算法的輸出；void out1(int s,algraph &l)：?jiǎn)文繕?biāo)的最短路徑輸出；void dijkstra(int n,int s,int v)：兩定點(diǎn)間的dijkstra算法；void out(int n,int s,int v)：兩定點(diǎn)間的路徑輸出；void dijkstra(int n, int s)：dijkstra算法；void out(int n, int s)：最短路徑輸出和獲得最大距離；void out1(int n, int s)：輸出總運(yùn)輸量；int main():主函數(shù)； 2.3 詳細(xì)設(shè)計(jì)題（1）、（2）

33、和（3）代碼如下：#include #include #include #define max 20 typedef char vertextypemax; /頂點(diǎn)類(lèi)型typedef struct arcnode /有向圖,省略的第二個(gè)成員 int weight; int adjvex; struct arcnode *nextarc; arcnode; typedef struct vnode vertextype data; arcnode *firstarc; vnode; typedef struct vnode verticesmax; int vexnum,arcnum; int

34、kind; algraph;查找函數(shù)： int locatevex(algraph &g, vertextype v) int i; for (i=0;ig.vexnum;i+) if(strcmp(g.verticesi.data,v)=0) return i; return -1;創(chuàng)建有向圖： void createdg(algraph &g,algraph &l) int i,k,j,a,x,y; vertextype v1,v2; arcnode *p,*s; g.kind=3; printf(請(qǐng)輸入有向圖的頂點(diǎn)數(shù)：n); scanf(%d,&(g.vexnum); printf(請(qǐng)輸

35、入有向圖的邊數(shù):n); scanf(%d,&(g.arcnum); l.vexnum=g.vexnum; l.arcnum=g.arcnum; for(k=0;kg.vexnum;k+) getchar(); printf(輸入第%d個(gè)頂點(diǎn): ,k+1); scanf(%s,g.verticesk.data); strcpy(l.verticesk.data,g.verticesk.data); g.verticesk.firstarc=null; l.verticesk.firstarc=null; for(k=0;kg.arcnum;k+) getchar(); printf(輸入第%d邊

36、 和 權(quán)值n,k+1); scanf(%s%s%d,v1,v2,&a); i= locatevex (g,v1); j= locatevex (g,v2); x= locatevex (l,v1); y= locatevex (l,v2); if(i0 |j0|x0|yadjvex=j; s-adjvex=x; p-weight=a; s-weight=a; p-nextarc=g.verticesi.firstarc; s-nextarc=l.verticesy.firstarc; g.verticesi.firstarc =p; l.verticesy.firstarc =s; 輸出鄰接表

37、函數(shù)： void graphoutput(algraph &g) /鄰接表的輸出 int i; arcnode *s; for(i=0;i%4d 權(quán)值%d,s-adjvex,s-weight); s=s-nextarc; printf(n); 鄰接表dijkstra算法函數(shù)：int final100,d100,path100;void dijkstra(int s,algraph &g) int i,j,k,min,b; arcnode *p; p=g.verticess.firstarc; finals=1; for(i=0;iadjvex=p-weight; pathp-adjvex=s;

38、 p=p-nextarc; for(j=1;jg.vexnum;j+) min=999; for(i=0;ig.vexnum;i+) if(!finali&diadjvex; if(!finalb&p-weight+dkweight+dk; pathp-adjvex=k; p=p-nextarc; 鄰接表dijkstra算法輸出函數(shù)：void out(int s,algraph &g) int b100; int i,j,p,m; dijkstra(s, g); for(i=0;i=0;j-) printf(%4d,bj); printf(n); 單目標(biāo)輸出函數(shù)：void out1(int s,algraph &l) int b100; int i,j,p,m; dijkstra(s, l); for(i=0;il.ve