《太原理工《程序設(shè)計(jì)課程設(shè)計(jì)》實(shí)驗(yàn)報(bào)告》由會員分享，可在線閱讀，更多相關(guān)《太原理工《程序設(shè)計(jì)課程設(shè)計(jì)》實(shí)驗(yàn)報(bào)告（19頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。
1、程序設(shè)計(jì)課程設(shè)計(jì)姓 名：學(xué) 號：班 級：指導(dǎo)教師： 成 績：2015年7月1日【問題描述】問題：某校的慣例是在每學(xué)期的期末考試之后發(fā)放獎(jiǎng)學(xué)金。發(fā)放的獎(jiǎng)學(xué)金共有五種，獲取的條件各自不同：1) 院士獎(jiǎng)學(xué)金，每人8000元，期末平均成績高于80分（80），并且在本學(xué)期內(nèi)發(fā)表1篇或1篇以上論文的學(xué)生均可獲得；2) 五四獎(jiǎng)學(xué)金，每人4000元，期末平均成績高于85分（85），并且班級評議成績高于80分（80）的學(xué)生均可獲得；3) 成績優(yōu)秀獎(jiǎng)，每人2000元，期末平均成績高于90分（90）的學(xué)生均可獲得；4) 西部獎(jiǎng)學(xué)金，每人1000元，期末平均成績高于85分（85）的西部省份學(xué)生均可獲得；5) 班級貢獻(xiàn)
2、獎(jiǎng)，每人850元，班級評議成績高于80分（80）的學(xué)生干部均可獲得；只要符合條件就可以得獎(jiǎng)，每項(xiàng)獎(jiǎng)學(xué)金的獲獎(jiǎng)人數(shù)沒有限制，每名學(xué)生也可以同時(shí)獲得多項(xiàng)獎(jiǎng)學(xué)金。例如姚林的期末平均成績是87分，班級評議成績82分，同時(shí)他還是一位學(xué)生干部，那么他可以同時(shí)獲得五四獎(jiǎng)學(xué)金和班級貢獻(xiàn)獎(jiǎng)，獎(jiǎng)金總數(shù)是4850元。功能：給出若干學(xué)生的相關(guān)數(shù)據(jù)，請計(jì)算哪些同學(xué)獲得的獎(jiǎng)金總數(shù)最高（假設(shè)總有同學(xué)能滿足獲得獎(jiǎng)學(xué)金的條件）。輸入數(shù)據(jù)格式格式：輸入的第一行是一個(gè)整數(shù)N（1 = N = 100），表示學(xué)生的總數(shù)。接下來的N行每行是一位學(xué)生的數(shù)據(jù)，從左向右依次是姓名，期末平均成績，班級評議成績，是否是學(xué)生干部，是否是西部省份學(xué)生
3、，以及發(fā)表的論文數(shù)。姓名是由大小寫英文字母組成的長度不超過20的字符串（不含空格）；期末平均成績和班級評議成績都是0到100之間的整數(shù)（包括0和100）；是否是學(xué)生干部和是否是西部省份學(xué)生分別用一個(gè)字符表示，Y表示是，N表示不是；發(fā)表的論文數(shù)是0到10的整數(shù)（包括0和10）。每兩個(gè)相鄰數(shù)據(jù)項(xiàng)之間用一個(gè)空格分隔。輸出數(shù)據(jù)格式：輸出包括三行，第一行是獲得最多獎(jiǎng)金的學(xué)生的姓名，第二行是這名學(xué)生獲得的獎(jiǎng)金總數(shù)。如果有兩位或兩位以上的學(xué)生獲得的獎(jiǎng)金最多，輸出他們之中在輸入文件中出現(xiàn)最早的學(xué)生的姓名。第三行是這N個(gè)學(xué)生獲得的獎(jiǎng)學(xué)金的總數(shù)。【設(shè)計(jì)需求及分析】定義結(jié)構(gòu)體student，包含name20(名字)
4、,Qg(期末平均成績),Cg(班級評議成績),sg2(是否是學(xué)生干部),xb2(是否是西部學(xué)生),money(獎(jiǎng)學(xué)金)。只有一個(gè)主函數(shù)，用結(jié)構(gòu)體定義一個(gè)動(dòng)態(tài)數(shù)組，先給定數(shù)組長度N，然后在for循環(huán)中循環(huán)N次輸入N個(gè)學(xué)生的數(shù)據(jù)，每次輸入完一組，就直接按要求得出其獎(jiǎng)學(xué)金數(shù)，最后找出獎(jiǎng)學(xué)金最多的人和他的名字，N個(gè)學(xué)生的獎(jiǎng)學(xué)金總數(shù)直接相加即可?！驹O(shè)計(jì)功能的實(shí)現(xiàn)】（用C語言）設(shè)計(jì)如下：#include#include#include struct student char name20; int Qg; int Cg; char sg2; char xb2; int lw; int money;void
5、 main()struct student *array;array=NULL;int N,i,zs=0,max=0,j=-1;/zs為總獎(jiǎng)學(xué)金數(shù)量，j為獎(jiǎng)學(xué)金最多的人序號，max為最多獎(jiǎng)學(xué)金char s2=Y;scanf(%d,&N);array=(struct student*)malloc(N*sizeof(struct student);if(array=0)printf(FAIL);exit(0); for (i = 0; i 80&arrayi.lw0)num+=8000;if(arrayi.Qg85&arrayi.Cg80)num+=4000;if(arrayi.Qg90) nu
6、m+=2000;if(arrayi.Qg80&!strcmp(arrayi.xb,s)num+=1000;if(arrayi.Qg80&!strcmp(arrayi.sg,s)num+=850;arrayi.money=num;zs+=num; for(i = 0; i N; i+)if(maxarrayi.money) j=i; max=arrayi.money; if(j=-1) printf(無人得到獎(jiǎng)學(xué)金);else printf(%sn%dn%dn,arrayj.name,arrayj.money,zs); free(array); /*釋放由malloc函數(shù)申請的內(nèi)存塊*/【實(shí)例測
7、試及運(yùn)行結(jié)果】 4個(gè)學(xué)生，獎(jiǎng)學(xué)金最多的是ChenRuiyi，金額為9000,獎(jiǎng)學(xué)金總數(shù)為28700【使用說明】 注意一定要按照按要求輸入，由于規(guī)定了輸入輸出格式，所以我并沒有加上超出范圍的提示說明，按要求輸入才能得到正確的計(jì)算結(jié)果?！拘牡皿w會】 由于對結(jié)構(gòu)體動(dòng)態(tài)數(shù)組的使用還沒有怎么熟悉，一開始花費(fèi)了不少時(shí)間去查閱書籍，而一旦數(shù)組建立好，先其中添加和查詢數(shù)據(jù)就是相當(dāng)于對普通數(shù)組的操作，實(shí)現(xiàn)起來也簡單易懂，只是按要求在結(jié)構(gòu)體內(nèi)加了限定條件，為了按照要求輸出，超出限制時(shí)并不能給出提示，這一點(diǎn)有待提高。【問題描述】問題：某次科研調(diào)查時(shí)得到了n個(gè)自然數(shù)，每個(gè)數(shù)均不超過1500000000（*109）。已
8、知不相同的數(shù)不超過10000個(gè)，現(xiàn)在需要統(tǒng)計(jì)這些自然數(shù)各自出現(xiàn)的次數(shù)，并按照自然數(shù)從小到大的順序輸出統(tǒng)計(jì)結(jié)果。功能： 從文件中每讀出一個(gè)數(shù)據(jù)，就在順序表中查找，若存在，則該數(shù)出現(xiàn)次數(shù)增，否則將該數(shù)插入數(shù)組中，出現(xiàn)次數(shù)為，插入后使順序表中的數(shù)據(jù)按自然數(shù)有序。輸入數(shù)據(jù)格式格式：原始數(shù)據(jù)保存在文件中，文件包含n+1行。第1行是整數(shù)n(1=n=200000)，表示自然數(shù)的個(gè)數(shù)；第2n+1行每行一個(gè)自然數(shù)。輸出數(shù)據(jù)格式格式：結(jié)果保存在文件中，文件包含m行（m為n個(gè)自然數(shù)中不相同數(shù)的個(gè)數(shù)），按照自然數(shù)從小到大的順序輸出。每行輸出兩個(gè)整數(shù)，分別是自然數(shù)和該數(shù)出現(xiàn)的次數(shù)，其間用一個(gè)空格隔開。【測試數(shù)據(jù)】824
9、24510021002 34 25 1100 2由于數(shù)據(jù)量可能很大，要注意程序的運(yùn)行效率?！驹O(shè)計(jì)需求及分析】定義順序表，元素類型為：Element，順序表類型為：SeqList，用順序表的數(shù)組data記錄自然數(shù)和該數(shù)出現(xiàn)的次數(shù)。定義如下： typedef struct data long int number;/*數(shù)字*/ long int count;/*該數(shù)字出現(xiàn)的個(gè)數(shù)*/ Element;typedef struct listElement data10000; /*存儲自然數(shù)和該數(shù)出現(xiàn)的次數(shù)*/int length; /*存儲不同自然數(shù)的個(gè)數(shù),即順序表的長度*/ SeqList;只有一
10、個(gè)函數(shù)主函數(shù)，首先打開文件，按格式讀取文件內(nèi)容到結(jié)構(gòu)體數(shù)組中，先讀取數(shù)字總數(shù)，然后設(shè)置循環(huán)讀取數(shù)字，有重復(fù)則將該數(shù)字的數(shù)量加1，無重復(fù)則新建一個(gè)數(shù)字，其數(shù)量為1，長度加1，關(guān)文件。其后對保存進(jìn)入數(shù)組的數(shù)據(jù)進(jìn)行冒泡排序，最后將排好序的數(shù)組放入文件中，關(guān)文件?！驹O(shè)計(jì)功能的實(shí)現(xiàn)】（用C語言）設(shè)計(jì)如下：#include#includetypedef struct data long int number; long int count; Element;typedef struct list Element data10000; /*存儲自然數(shù)和該數(shù)出現(xiàn)的次數(shù)*/ int length; /*存儲不同
11、自然數(shù)的個(gè)數(shù),即順序表的長度*/ SeqList;void main() Element El;SeqList Se;int i=0,j,k,n,p,t1,t2;FILE *fp;if(fp=fopen(G:count.in.txt,r)=NULL)printf(fail!n);exit(0);fscanf(fp,%d,&n);/一個(gè)數(shù)字都沒有if(n=0)printf(文件無數(shù)字！);exit(1);/將文件內(nèi)容讀取并儲存while(in)fscanf(fp,%d,&p);if(i=0)Se.datai.number=p;Se.datai.count=1;Se.length=1;elsefo
12、r(k=0;kSe.length&p!=Se.datak.number;k+);if(kSe.length) /有重復(fù)數(shù)字Se.datak.count+;else /無重復(fù)數(shù)字Se.datak.number=p;Se.datak.count=1;Se.length+;k+;i+;fclose(fp);/冒泡排序for(i=0;iSe.length-1;i+)for(j=0;jSe.dataj+1.number)t1=Se.dataj.number;Se.dataj.number=Se.dataj+1.number;Se.dataj+1.number=t1;t2=Se.dataj.count;S
13、e.dataj.count=Se.dataj+1.count;Se.dataj+1.count=t2;/輸入文件if(fp=fopen(G:count.out.txt,w)=NULL)printf(fail!n);exit(0);for(k=0;kSe.length;k+)fprintf(fp,%d %dn,Se.datak.number,Se.datak.count);fclose(fp);【實(shí)例測試及運(yùn)行結(jié)果】【使用說明】 按照要求輸入數(shù)字進(jìn)入count.in文件即可。【心得體會】 花費(fèi)了很多的時(shí)間去熟悉文件的輸入輸出，一開始并未按格式讀取文件內(nèi)容，計(jì)算結(jié)果全部是亂碼，后來看書修改了代碼才
14、能正常讀取和錄取，對于排序算法，我個(gè)人比較熟悉冒泡排序，就直接用冒泡排序?qū)ζ溥M(jìn)行排序，實(shí)現(xiàn)起來也還可以。【問題描述】設(shè)計(jì)C或C+程序，統(tǒng)計(jì)一個(gè)英文文本文件中，出現(xiàn)了多少個(gè)單詞，每個(gè)單詞出現(xiàn)了幾次。連續(xù)的英文字符都認(rèn)為單詞(不包括數(shù)字)，單詞之間用空格或標(biāo)點(diǎn)符號分隔。 【設(shè)計(jì)需求及分析】要統(tǒng)計(jì)英文文本文件中出現(xiàn)了哪些單詞，就要從文件中讀取字符，讀取出來的連續(xù)英文字符認(rèn)為是一個(gè)單詞，遇空格或標(biāo)點(diǎn)符號單詞結(jié)束。使用線性表記錄單詞以及每個(gè)單詞出現(xiàn)的次數(shù)。線性表中的單詞按字典順序存儲。線性表的順序存儲結(jié)構(gòu)如下：#define LIST_INIT_SIZE 100 /線性表存儲空間的初始分配量#defin
15、e LISTINCREMENT 10 /線性表存儲空間的分配增量typedef struct char word21 /存儲單詞，不超過20個(gè)字符 int count; /單詞出現(xiàn)的次數(shù) ElemType;typedef struct ElemType *elem; /存儲空間基址 int length; /當(dāng)前長度int listsize; /當(dāng)前分配的存儲容量 Seqlist;順序表的初始化：InitList(SqList &L)順序表上查找指定的單詞：LocateElem(SqList &L,char *s) 若找到，單詞的出現(xiàn)次數(shù)增1，返回0，否則返回該單詞的插入位置。在順序表上插入新
16、的單詞：InsertList(SqList &L,int i，char *s) 要求按字典順序有序。新單詞的出現(xiàn)次數(shù)為1.輸出順序表上存儲的單詞統(tǒng)計(jì)信息：PrintList(SqList &L) 輸出文件中每個(gè)單詞出現(xiàn)的次數(shù)以及文件中總的單詞數(shù)(可輸出到文件中)。統(tǒng)計(jì)過程如下：（1）輸入要統(tǒng)計(jì)單詞的文本文件名，打開相應(yīng)的文件；（2）初始化順序表；（3）從文本文件中讀取字符，直到文件結(jié)束。具體描述如下：while (讀文件沒有結(jié)束結(jié)束) 過濾單詞前的非字母字符； 讀取一個(gè)單詞，以字符串形式存儲在一個(gè)字符數(shù)組中； 在線性表中查找該單詞，若找到，單詞的出現(xiàn)次數(shù)加1，否則返回其插入位置； 上一步中，若
17、沒找到，則進(jìn)行插入操作； 處理下一個(gè)單詞。（4）關(guān)閉文件，輸出統(tǒng)計(jì)結(jié)果?！驹O(shè)計(jì)功能的實(shí)現(xiàn)】（用C語言）設(shè)計(jì)如下：#include#include#include#define LIST_INIT_SIZE 100 /線性表存儲空間的初始分配量#define LISTINCREMENT 10 /線性表存儲空間的分配增量typedef struct char word21; /存儲單詞，不超過20個(gè)字符 int count; /單詞出現(xiàn)的次數(shù) ElemType;typedef struct ElemType *elem; /存儲空間基址 int length; /當(dāng)前長度 int listsize
18、; /當(dāng)前分配的存儲容量 SqList;/構(gòu)造空線性表int InitList(SqList &L) L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType);if(!L.elem)return 0;L.length=0;L.listsize=LIST_INIT_SIZE;return 1;/順序表上查找指定的單詞(二分法)int LocateElem(SqList &L,char *word)int low,high,mid;low=0;high=L.length-1;while(low=high)mid=(low+high)/2;if
19、(strcmp(word,L.elemmid.word)=0)L.elemmid.count+;return 0;else if(strcmp(word,L.elemmid.word)=L.listsize)base=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType);if(base=NULL)return 0;L.listsize=L.listsize+LISTINCREMENT;L.elem=base;for(j=L.length;j=i;j-)L.elemj=L.elemj-1;strcpy(L.el
20、emi-1.word,word);L.elemi-1.count=1;L.length+;return 1;/輸出順序表上存儲的單詞統(tǒng)計(jì)信息void PrintList(SqList &L,int num)FILE *fw;int i;int n=num;fw=fopen(G:單詞計(jì)數(shù).txt,w);fprintf(fw,文章共有%d個(gè)單詞n出現(xiàn)次數(shù)(按字典排序)nn,n);fprintf(fw,單詞 出現(xiàn)次數(shù)n,n);for(i=0;i=A&ch=a&ch=A&ch20)printf(文章中部分單詞太長不予統(tǒng)計(jì));num+; wordj=0; mark=0; j=0; i=LocateEle
21、m(L,word); if(i0)InsertList(L,i,word);ch=fgetc(fp);fclose(fp);printf(統(tǒng)計(jì)完成，單詞計(jì)數(shù).txt文件在G盤生成。);PrintList(L,num);【實(shí)例測試及運(yùn)行結(jié)果】【使用說明】 文件要提前建立好才能用。【心得體會】 一開始沒有頭緒，后來看了提示新建了三個(gè)函數(shù)，寫起來就方便許多了，最主要的一個(gè)函數(shù)是用二分法查找順序表上的單詞，找到了個(gè)數(shù)加一，沒找到就返回，向順序表中添加單詞，其余的就是之前的文件輸入輸出，不同之前的是一開始的文件名是用戶指定的，然后統(tǒng)計(jì)的信息放在另外一個(gè)文件中即可?！締栴}描述】在交通網(wǎng)絡(luò)非常發(fā)達(dá),交通工具
22、和交通方式不斷更新的今天,人們在出差、旅游或做其他出行時(shí)，不僅關(guān)心節(jié)省交通費(fèi)用，而且對里程和所需要的時(shí)間等問題也感興趣。對于這樣一個(gè)人們關(guān)心的問題，可用一個(gè)圖結(jié)構(gòu)來表示交通網(wǎng)絡(luò)系統(tǒng)，利用計(jì)算機(jī)建立一個(gè)交通咨詢系統(tǒng)。圖中的頂點(diǎn)表示城市，邊表示城市之間的交通關(guān)系。這個(gè)交通系統(tǒng)可以回答出行旅客提出的各種路徑選擇問題。例如，問題之一：“一位旅客要從A城到B城，他希望選擇一條途中中轉(zhuǎn)次數(shù)最少的路線?！奔僭O(shè)圖中每一站都需要換車，那么這個(gè)問題反映到圖上就是要找一條從頂點(diǎn)A到頂點(diǎn)B的所含邊數(shù)目最少的路徑。我們只需要從頂點(diǎn)A出發(fā)對圖作廣度優(yōu)先搜索，一旦遇到頂點(diǎn)B就終止。由此所得廣度優(yōu)先生成樹上，從根頂點(diǎn)A到頂點(diǎn)
23、B的路徑就是中轉(zhuǎn)次數(shù)最少的路徑。路徑上A與B之間的頂點(diǎn)就是路徑的中轉(zhuǎn)站，但這只是一類最簡單的圖的最短路徑問題。系統(tǒng)還可以回答諸如此類的等等的路徑選擇問題。設(shè)計(jì)一個(gè)交通咨詢系統(tǒng)，為出差、旅游或做其他出行的客人提供各種路徑選擇信息查詢服務(wù)?！驹O(shè)計(jì)需求及分析】設(shè)計(jì)一個(gè)交通咨詢系統(tǒng)，能讓旅客咨詢從任一個(gè)城市頂點(diǎn)到另一城市頂點(diǎn)之間的最短路徑（里程）或最低花費(fèi)或最少時(shí)間等問題。對于不同的咨詢要求，可輸入城市間的路程或所需時(shí)間或所需費(fèi)用。本設(shè)計(jì)共分三部分，一是建立交通網(wǎng)絡(luò)圖的存儲結(jié)構(gòu)；二是解決單源最短路徑問題；三是實(shí)現(xiàn)任兩個(gè)城市頂點(diǎn)之間的最短路徑問題。建立圖的存儲結(jié)構(gòu)鄰接矩陣是表示圖形中頂點(diǎn)之間相鄰關(guān)系的矩
24、陣。圖的鄰接矩陣是定義如下的n階方陣：設(shè)G=（V，E）是一個(gè)圖，結(jié)點(diǎn)集為。G的鄰接矩陣當(dāng)鄰接矩陣的行表頭、列表頭順序一定時(shí)，一個(gè)圖的鄰接矩陣表示是唯一的。圖的鄰接矩陣表示，除了需用一個(gè)二維數(shù)組存儲頂點(diǎn)之間的相鄰關(guān)系的鄰接矩陣外，通常還需要使用一個(gè)具有n個(gè)元素的一維數(shù)組來存儲頂點(diǎn)信息，其中下標(biāo)為i的元素存儲頂點(diǎn)i的信息。因此，圖的鄰接矩陣的存儲結(jié)構(gòu)定義如下：#definf MVNum 50 /最大頂點(diǎn)數(shù)typedef struct VertexType vexsMVNum; /頂點(diǎn)數(shù)組，類型假定為char型 Adjmatrix arcsMVNumMVNum; /鄰接矩陣，假定為int型MGrap
25、h;單源最短路徑最短路徑的提法很多。在這里先討論單源最短路徑問題：即已知有向圖（帶權(quán)），我們希望找出從某個(gè)源點(diǎn)SV到G中其余各頂點(diǎn)的最短路徑。為了敘述方便，我們把路徑上的開始點(diǎn)稱為源點(diǎn)，路徑的最后一個(gè)頂點(diǎn)為終點(diǎn)。那么，如何求得給定有向圖的單源最短路徑呢？迪杰斯特拉（Dijkstra）提出按路徑長度遞增產(chǎn)生諸點(diǎn)的最短路徑算法，稱之為迪杰斯特拉算法。迪杰斯特拉算法求最短路徑的實(shí)現(xiàn)思想是：設(shè)G=（V，E）是一個(gè)有向圖，結(jié)點(diǎn)集為，cost是表示G的鄰接矩陣，costij表示有向邊的權(quán)。若不存在有向邊，則costij的權(quán)為無窮大（這里取值為32767）。設(shè)S是一個(gè)集合，其中的每個(gè)元素表示一個(gè)頂點(diǎn)，從源點(diǎn)
26、到這些頂點(diǎn)的最短距離已經(jīng)求出。設(shè)頂點(diǎn)v1為源點(diǎn)，集合S的初態(tài)只包含一個(gè)元素，即頂點(diǎn)v1。數(shù)組dist記錄從源點(diǎn)到其他頂點(diǎn)當(dāng)前的最短距離，其初值為disti=costv1i,i=1,2,n。從S之外的頂點(diǎn)集合V-S中選出一個(gè)頂點(diǎn)w，使distw的值最小。于是從源點(diǎn)到達(dá)w只通過S中頂點(diǎn)，把w加入集合S中，調(diào)整dist中記錄的從源點(diǎn)到V-S中每個(gè)頂點(diǎn)v的距離：從原來的distv和distw+costwv中選擇較小的值作為新的distv。重復(fù)上述過程，直到V-S為空。最終結(jié)果是：S記錄了從源點(diǎn)到該頂點(diǎn)存在最短路徑的頂點(diǎn)集合，數(shù)組dist記錄了源點(diǎn)到V中其余各頂點(diǎn)之間的最短路徑，path是最短路徑的路徑
27、數(shù)組，其中pathi表示從源點(diǎn)到頂點(diǎn)i之間的最短路徑的前驅(qū)頂點(diǎn)。因此，迪杰斯特拉算法可用自然語言描述如下：初始化S和D，置空最短路徑終點(diǎn)集，置初始的最短路徑值；Sv1=TRUE; Dv1=0； /S集初始時(shí)只有源點(diǎn)，源點(diǎn)到源點(diǎn)的距離為0；While (S集中頂點(diǎn)數(shù)n)開始循環(huán)，每次求得v1到某個(gè)v頂點(diǎn)的最短路徑，并加v到S集中；Sv=TRUE；更新當(dāng)前最短路徑及距離；任意一對頂點(diǎn)間最短路徑任意一對頂點(diǎn)間最短路徑問題，是對于給定的有向網(wǎng)絡(luò)圖G=（V，E），要對G中任意一對頂點(diǎn)有序?qū)Α皏,w(vw)”,找出v到w的最短路徑。要解決這個(gè)問題，我們可以依次把有向網(wǎng)絡(luò)圖中每個(gè)頂點(diǎn)作為源點(diǎn)，重復(fù)執(zhí)行前面討
28、論的迪杰斯特拉算法n次，即可以求得每對頂點(diǎn)之間的最短路徑。這里還可以用另外一種方法，稱作費(fèi)洛伊德（Floyd）算法。費(fèi)洛伊德（Floyd）算法算法的基本思想是：假設(shè)求從頂點(diǎn) vi到vj的最短路徑。如果從vi到vj存在一條長度為arcsij的路徑，該路徑不一定是最短路徑，還需要進(jìn)行n次試探。首先考慮路徑和是否存在。如果存在，則比較和的路徑長度，取長度較短者為當(dāng)前所求得的最短路徑。該路徑是中間頂點(diǎn)序號不大于1的最短路徑。其次，考慮從vi到vj是否包含有頂點(diǎn)v2為中間頂點(diǎn)的路徑，若沒有，則說明從vi到vj的當(dāng)前最短路徑就是前一步求出的；若有，那么可分解為和,而這兩條路徑是前一次找到的中間頂點(diǎn)序號不大
29、于1的最短路徑，將這兩條路徑長度相加就得到路徑的長度。將該長度與前一次中求出的從vi到vj的中間頂點(diǎn)序號不大于1的最短路徑比較，取其長度較短者作為當(dāng)前求得的從vi到vj的中間頂點(diǎn)序號不大于2的最短路徑。依此類推，直到頂點(diǎn)vn加入當(dāng)前從vi到vj的最短路徑后，選出從vi到vj的中間頂點(diǎn)序號不大于n的最短路徑為止。由于圖G中頂點(diǎn)序號不大于n，所以vi到vj的中間頂點(diǎn)序號不大于n的最短路徑，已考慮了所有頂點(diǎn)作為中間頂點(diǎn)的可能性，因此，它就是vi到vj的最短路徑。【設(shè)計(jì)功能的實(shí)現(xiàn)】（用C語言）設(shè)計(jì)如下：#include#include#define MVNum 50#define Maxint 327
30、67enum booleanFALSE,TRUE;/ 枚舉類型typedef char VertexType;typedef int Adjmatrix;typedef structVertexType vexsMVNum; /頂點(diǎn)數(shù)組，類型假定為char型Adjmatrix arcsMVNumMVNum; /鄰接矩陣，假定為int型MGraph;int D1MVNum,p1MVNum;int DMVNumMVNum,pMVNumMVNum;void CreateMGraph(MGraph * G,int n,int e)int i,j,k,w;for(i=1;ivexsi=(char)i;f
31、or(i=1;i=n;i+)for(j=1;jarcsij=Maxint;printf(輸入%d條邊的i,j,w:n,e);for(k=1;karcsij=w;printf(有向圖建立完成n);/建立有向圖的存儲結(jié)構(gòu)void Dijkstra(MGraph *G,int v1,int n)/迪杰斯特拉算法，最短路徑int D2MVNum,p2MVNum;int v,i,w,min;enum boolean SMVNum;for(v=1;varcsv1v;if(D2vMaxint)p2v=v1;elsep2v=0;D2v1=0; Sv1=TRUE;for(i=2;in;i+)min=Maxint
32、;for(w=1;w=n;w+)if(!Sw & D2wmin)v=w;min=D2w;Sv=TRUE;for(w=1;warcsvwarcsvw;p2w=v;printf(路徑長度 路徑n);for(i=1;i=n;i+)printf(%5d,D2i);printf(%5d,i);v=p2i;while(v!=0)printf(-%d,v);v=p2v;printf(n);void Floyd(MGraph *G,int n)/費(fèi)洛伊德算法int i,j,k;for(i=1;i=n;i+)for(j=1;jarcsij!=Maxint)pij=j;elsepij=0;Dij=G-arcsij
33、;for(k=1;k=n;k+)for(i=1;i=n;i+)for(j=1;j=n;j+)if(Dik+DkjDij) Dij=Dik+Dkj;pij=pik;void main() MGraph *G; int e,n,v,w,k; G=(MGraph *)malloc(sizeof(MGraph); printf(輸入圖中頂點(diǎn)個(gè)數(shù)和邊數(shù)n,e:); scanf(%d,%d,&n,&e); CreateMGraph(G,n,e); printf(1.求一個(gè)城市到所有城市的最短路徑n); printf(求單源路徑，輸入源點(diǎn)v :); scanf(%d,&v); Dijkstra(G,v,n)
34、; printf(2.求任意的兩個(gè)城市之間的最短路徑n); Floyd(G,n); printf(輸入源點(diǎn)（或起點(diǎn)）和終點(diǎn):v,w:); scanf(%d,%d,&v,&w); k=pvw; if (k=0) printf(頂點(diǎn)%d 到 %d 無路徑!n,v,w); else printf(從頂點(diǎn)%d 到 %d 最短路徑路徑是:%d,v,w,v); while (k!=w) printf(-%d,k); k=pkw; printf(-%d,w); printf(徑路長度:%dn,Dvw); 【實(shí)例測試及運(yùn)行結(jié)果】實(shí)際圖：【使用說明】 輸入格式：個(gè)數(shù)，邊數(shù) i，j，k 其余按照要求即可使用?！拘牡皿w會】 這個(gè)程序是算法設(shè)計(jì)課程的內(nèi)容，用到了迪杰斯特拉算法和費(fèi)洛伊德算法，一開始則是用數(shù)據(jù)結(jié)構(gòu)中圖結(jié)構(gòu)體建立。雖然之前已經(jīng)學(xué)過了其算法如何實(shí)現(xiàn)，不過自己編寫確實(shí)有難度，想起來也麻煩，更重要的是還是有向圖，還有方向問題，總之雖然困難重重，但是通過不懈的努力終于解決了問題，寫出代碼。
太原理工《程序設(shè)計(jì)課程設(shè)計(jì)》實(shí)驗(yàn)報(bào)告
