太原理工《程序設(shè)計(jì)課程設(shè)計(jì)》實(shí)驗(yàn)報(bào)告

《太原理工《程序設(shè)計(jì)課程設(shè)計(jì)》實(shí)驗(yàn)報(bào)告》由會(huì)員分享，可在線閱讀，更多相關(guān)《太原理工《程序設(shè)計(jì)課程設(shè)計(jì)》實(shí)驗(yàn)報(bào)告（19頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、 《程序設(shè)計(jì)》課程設(shè)計(jì) 姓 名： 學(xué) 號(hào)： 班 級(jí)： 指導(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），并且班級(jí)評(píng)議成績高于80分（>80）的學(xué)生均可獲得； 3

2、) 成績優(yōu)秀獎(jiǎng)，每人2000元，期末平均成績高于90分（>90）的學(xué)生均可獲得； 4) 西部獎(jiǎng)學(xué)金，每人1000元，期末平均成績高于85分（>85）的西部省份學(xué)生均可獲得； 5) 班級(jí)貢獻(xiàn)獎(jiǎng)，每人850元，班級(jí)評(píng)議成績高于80分（>80）的學(xué)生干部均可獲得； 只要符合條件就可以得獎(jiǎng)，每項(xiàng)獎(jiǎng)學(xué)金的獲獎(jiǎng)人數(shù)沒有限制，每名學(xué)生也可以同時(shí)獲得多項(xiàng)獎(jiǎng)學(xué)金。例如姚林的期末平均成績是87分，班級(jí)評(píng)議成績82分，同時(shí)他還是一位學(xué)生干部，那么他可以同時(shí)獲得五四獎(jiǎng)學(xué)金和班級(jí)貢獻(xiàn)獎(jiǎng)，獎(jiǎng)金總數(shù)是4850元。 功能： 給出若干學(xué)生的相關(guān)數(shù)據(jù)，請(qǐng)計(jì)算哪些同學(xué)獲得的獎(jiǎng)金總數(shù)最高（假設(shè)總有同學(xué)能滿足獲得獎(jiǎng)學(xué)金的條件

3、）。 輸入數(shù)據(jù)格式格式： 輸入的第一行是一個(gè)整數(shù)N（1 <= N <= 100），表示學(xué)生的總數(shù)。接下來的N行每行是一位學(xué)生的數(shù)據(jù)，從左向右依次是姓名，期末平均成績，班級(jí)評(píng)議成績，是否是學(xué)生干部，是否是西部省份學(xué)生，以及發(fā)表的論文數(shù)。姓名是由大小寫英文字母組成的長度不超過20的字符串（不含空格）；期末平均成績和班級(jí)評(píng)議成績都是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é)生的姓名，

4、第二行是這名學(xué)生獲得的獎(jiǎng)金總數(shù)。如果有兩位或兩位以上的學(xué)生獲得的獎(jiǎng)金最多，輸出他們之中在輸入文件中出現(xiàn)最早的學(xué)生的姓名。第三行是這N個(gè)學(xué)生獲得的獎(jiǎng)學(xué)金的總數(shù)。 【設(shè)計(jì)需求及分析】 定義結(jié)構(gòu)體student，包含name[20](名字),Qg(期末平均成績),Cg(班級(jí)評(píng)議成績),sg[2](是否是學(xué)生干部),xb[2](是否是西部學(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ù)直接相加即可。 【設(shè)計(jì)功

5、能的實(shí)現(xiàn)】（用C語言） 設(shè)計(jì)如下： #include #include #include struct student { char name[20]; int Qg; int Cg; char sg[2]; char xb[2]; int lw; int money; }; void main() { struct student *array; array=NULL; int N,i,zs=0,max=0,j=-1; //zs為總獎(jiǎng)學(xué)金數(shù)量，j為獎(jiǎng)學(xué)金最多的人序號(hào)

6、，max為最多獎(jiǎng)學(xué)金 char s[2]="Y"; scanf("%d",&N); array=(struct student*)malloc(N*sizeof(struct student)); if(array==0) { printf("FAIL"); exit(0); } for (i = 0; i < N; i++) { int num=0; scanf("%s",&array[i].name); scanf("%d",&array[i].Qg); scanf("%d",&array[i].Cg); scanf("%s",&arr

7、ay[i].sg); scanf("%s",&array[i].xb); scanf("%d",&array[i].lw); if(array[i].Qg>80&&array[i].lw>0) num+=8000; if(array[i].Qg>85&&array[i].Cg>80) num+=4000; if(array[i].Qg>90) num+=2000; if(array[i].Qg>80&&!strcmp(array[i].xb,s)) num+=1000; if(array[i].Qg>80&&!strcmp(arr

8、ay[i].sg,s)) num+=850; array[i].money=num; zs+=num; } for(i = 0; i < N; i++) { if(max

9、(array); /*釋放由malloc函數(shù)申請(qǐng)的內(nèi)存塊*/ } 【實(shí)例測(cè)試及運(yùn)行結(jié)果】 4個(gè)學(xué)生，獎(jiǎng)學(xué)金最多的是ChenRuiyi，金額為9000,獎(jiǎng)學(xué)金總數(shù)為28700 【使用說明】 注意一定要按照按要求輸入，由于規(guī)定了輸入輸出格式，所以我并沒有加上超出范圍的提示說明，按要求輸入才能得到正確的計(jì)算結(jié)果。 【心得體會(huì)】 由于對(duì)結(jié)構(gòu)體動(dòng)態(tài)數(shù)組的使用還沒有怎么熟悉，一開始花費(fèi)了不少時(shí)間去查閱書籍，而一旦數(shù)組建立好，先其中添加和查詢數(shù)據(jù)就是相當(dāng)于對(duì)普通數(shù)組的操作，實(shí)現(xiàn)起來也簡單易懂，只是按要求在結(jié)構(gòu)體內(nèi)加了限定條件，為了按照要求輸出，超出限制時(shí)并不能給出提

10、示，這一點(diǎn)有待提高。 【問題描述】 問題： 某次科研調(diào)查時(shí)得到了n個(gè)自然數(shù)，每個(gè)數(shù)均不超過1500000000（*109）。已知不相同的數(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ù)；第2~n+1行每行一個(gè)自然數(shù)。 輸出數(shù)據(jù)格式格式： 結(jié)果保

11、存在文件中，文件包含m行（m為n個(gè)自然數(shù)中不相同數(shù)的個(gè)數(shù)），按照自然數(shù)從小到大的順序輸出。每行輸出兩個(gè)整數(shù)，分別是自然數(shù)和該數(shù)出現(xiàn)的次數(shù)，其間用一個(gè)空格隔開。 【測(cè)試數(shù)據(jù)】 8 2 4 2 4 5 100 2 100 2 3 4 2 5 1 100 2 由于數(shù)據(jù)量可能很大，要注意程序的運(yùn)行效率。 【設(shè)計(jì)需求及分析】 定義順序表，元素類型為：Element，順序表類型為：SeqList，用順序表的數(shù)組data記錄自然數(shù)和該數(shù)出現(xiàn)的次數(shù)。定義如下： typedef struct data{ long int number;/*數(shù)字*

12、/ long int count;/*該數(shù)字出現(xiàn)的個(gè)數(shù)*/ } Element; typedef struct list{ Element data[10000]; /*存儲(chǔ)自然數(shù)和該數(shù)出現(xiàn)的次數(shù)*/ int length; /*存儲(chǔ)不同自然數(shù)的個(gè)數(shù),即順序表的長度*/ } SeqList; 只有一個(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)文件。其后對(duì)保存進(jìn)入數(shù)組的數(shù)據(jù)進(jìn)行冒泡排序，最后將排好序的數(shù)組放入文件中，

13、關(guān)文件。 【設(shè)計(jì)功能的實(shí)現(xiàn)】（用C語言） 設(shè)計(jì)如下： #include #include typedef struct data{ long int number; long int count; }Element; typedef struct list{ Element data[10000]; /*存儲(chǔ)自然數(shù)和該數(shù)出現(xiàn)的次數(shù)*/ int length; /*存儲(chǔ)不同自然數(shù)的個(gè)數(shù),即順序表的長度*/ }SeqList; void main() { Elemen

14、t 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)容讀取并儲(chǔ)存 while(i

15、ta[i].count=1; Se.length=1; } else{ for(k=0;k

16、length-1;i++) for(j=0;jSe.data[j+1].number) { t1=Se.data[j].number; Se.data[j].number=Se.data[j+1].number; Se.data[j+1].number=t1; t2=Se.data[j].count; Se.data[j].count=Se.data[j+1].count; Se.data[j+1].count=t2; } } //輸入文件 if((fp=fopen("G:\\cou

17、nt.out.txt","w"))==NULL) { printf("fail!\n"); exit(0); } for(k=0;k

18、，我個(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)符號(hào)分隔。 【設(shè)計(jì)需求及分析】 要統(tǒng)計(jì)英文文本文件中出現(xiàn)了哪些單詞，就要從文件中讀取字符，讀取出來的連續(xù)英文字符認(rèn)為是一個(gè)單詞，遇空格或標(biāo)點(diǎn)符號(hào)單詞結(jié)束。 使用線性表記錄單詞以及每個(gè)單詞出現(xiàn)的次數(shù)。線性表中的單詞按字典順序存儲(chǔ)。 線性表的順序存儲(chǔ)結(jié)構(gòu)如下： #define LIST_INIT_SIZE 100 //線性表存儲(chǔ)空間的初始分

19、配量 #define LISTINCREMENT 10 //線性表存儲(chǔ)空間的分配增量 typedef struct{ char word[21] //存儲(chǔ)單詞，不超過20個(gè)字符 int count; //單詞出現(xiàn)的次數(shù) } ElemType; typedef struct{ ElemType *elem; //存儲(chǔ)空間基址 int length; //當(dāng)前長度 int listsize; //當(dāng)前分配的存儲(chǔ)容量

20、 } Seqlist; ⑴順序表的初始化：InitList(SqList &L) ⑵順序表上查找指定的單詞：LocateElem(SqList &L,char *s) 若找到，單詞的出現(xiàn)次數(shù)增1，返回0，否則返回該單詞的插入位置。 ⑶在順序表上插入新的單詞：InsertList(SqList &L,int i，char *s) 要求按字典順序有序。新單詞的出現(xiàn)次數(shù)為1. ⑷輸出順序表上存儲(chǔ)的單詞統(tǒng)計(jì)信息：PrintList(SqList &L) 輸出文件中每個(gè)單詞出現(xiàn)的次數(shù)以及文件中總的單詞數(shù)(可輸出到文件中)。 統(tǒng)計(jì)過程如下： （1）輸入要統(tǒng)計(jì)單詞的文本文件名，

21、打開相應(yīng)的文件； （2）初始化順序表； （3）從文本文件中讀取字符，直到文件結(jié)束。具體描述如下： while (讀文件沒有結(jié)束結(jié)束) { 過濾單詞前的非字母字符； 讀取一個(gè)單詞，以字符串形式存儲(chǔ)在一個(gè)字符數(shù)組中； 在線性表中查找該單詞，若找到，單詞的出現(xiàn)次數(shù)加1，否則返回其插入位置； 上一步中，若沒找到，則進(jìn)行插入操作； 處理下一個(gè)單詞。 } （4）關(guān)閉文件，輸出統(tǒng)計(jì)結(jié)果。 【設(shè)計(jì)功能的實(shí)現(xiàn)】（用C語言） 設(shè)計(jì)如下： #include #include #

22、include #define LIST_INIT_SIZE 100 //線性表存儲(chǔ)空間的初始分配量 #define LISTINCREMENT 10 //線性表存儲(chǔ)空間的分配增量 typedef struct{ char word[21]; //存儲(chǔ)單詞，不超過20個(gè)字符 int count; //單詞出現(xiàn)的次數(shù) } ElemType; typedef struct{ ElemType *elem; //存儲(chǔ)空間基址 int leng

23、th; //當(dāng)前長度 int listsize; //當(dāng)前分配的存儲(chǔ)容量 } 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 LocateEl

24、em(SqList &L,char *word) { int low,high,mid; low=0; high=L.length-1; while(low<=high) { mid=(low+high)/2; if(strcmp(word,L.elem[mid].word)==0) { L.elem[mid].count++; return 0; } else if(strcmp(word,L.elem[mid].word)<0) high=mid-1; else low=mid

25、+1; } return low+1;//返回該單詞的插入位置 } //在順序表上插入新的單詞 int InsertList(SqList &L,int i,char *word) { int j; ElemType *base; if(L.length>=L.listsize) { base=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType)); if(base==NULL)return 0; L.listsize=L.listsize+LISTINCRE

26、MENT; L.elem=base; } for(j=L.length;j>=i;j--) L.elem[j]=L.elem[j-1]; strcpy(L.elem[i-1].word,word); L.elem[i-1].count=1; L.length++; return 1; } //輸出順序表上存儲(chǔ)的單詞統(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,

27、"文章共有%d個(gè)單詞\n出現(xiàn)次數(shù)(按字典排序)\n\n",n); fprintf(fw,"單詞 出現(xiàn)次數(shù)\n",n); for(i=0;i

28、=0,i; FILE *fp; InitList(L); printf("給出文件名(G盤):\n"); scanf("%s",&filename); sprintf(filename1,"G:\\%s.txt",filename); getchar(); if((fp=fopen(filename1,"r"))==NULL) { printf("未找到相關(guān)文件!\n"); exit(0); } ch=fgetc(fp); while(ch!=EOF) { if((ch>='A'&&ch<='Z')||(ch>='a'&&ch<

29、='z')) { ch=ch>='A'&&ch<='Z'?ch+32:ch;//單詞都變成小寫比較 word[j++]=ch; mark=1; } else { if(mark==1){ if(j>20) printf("文章中部分單詞太長不予統(tǒng)計(jì)"); num++; word[j]='\0'; mark=0; j=0; i=LocateElem(L,word); if(i>0) InsertList(L,i,word

30、); } } ch=fgetc(fp); } fclose(fp); printf("統(tǒng)計(jì)完成，單詞計(jì)數(shù).txt文件在G盤生成。"); PrintList(L,num); } 【實(shí)例測(cè)試及運(yùn)行結(jié)果】 【使用說明】 文件要提前建立好才能用。 【心得體會(huì)】 一開始沒有頭緒，后來看了提示新建了三個(gè)函數(shù)，寫起來就方便許多了，最主要的一個(gè)函數(shù)是用二分法查找順序表上的單詞，找到了個(gè)數(shù)加一，沒找到就返回，向順序表中添加單詞，其余的就是之前的文件輸入輸出，不同之前的是一開始的文件名是用戶指定的，然后統(tǒng)計(jì)的信息放在另外一個(gè)文件中即可。

31、 【問題描述】 在交通網(wǎng)絡(luò)非常發(fā)達(dá),交通工具和交通方式不斷更新的今天,人們?cè)诔霾?、旅游或做其他出行時(shí)，不僅關(guān)心節(jié)省交通費(fèi)用，而且對(duì)里程和所需要的時(shí)間等問題也感興趣。對(duì)于這樣一個(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ā)對(duì)圖作廣度優(yōu)先搜索，一旦遇到頂點(diǎn)B就終

32、止。由此所得廣度優(yōu)先生成樹上，從根頂點(diǎn)A到頂點(diǎn)B的路徑就是中轉(zhuǎn)次數(shù)最少的路徑。路徑上A與B之間的頂點(diǎn)就是路徑的中轉(zhuǎn)站，但這只是一類最簡單的圖的最短路徑問題。系統(tǒng)還可以回答諸如此類的等等的路徑選擇問題。 設(shè)計(jì)一個(gè)交通咨詢系統(tǒng)，為出差、旅游或做其他出行的客人提供各種路徑選擇信息查詢服務(wù)。 【設(shè)計(jì)需求及分析】 設(shè)計(jì)一個(gè)交通咨詢系統(tǒng)，能讓旅客咨詢從任一個(gè)城市頂點(diǎn)到另一城市頂點(diǎn)之間的最短路徑（里程）或最低花費(fèi)或最少時(shí)間等問題。對(duì)于不同的咨詢要求，可輸入城市間的路程或所需時(shí)間或所需費(fèi)用。 本設(shè)計(jì)共分三部分，一是建立交通網(wǎng)絡(luò)圖的存儲(chǔ)結(jié)構(gòu)；二是解決單源最短路徑問題；三是實(shí)現(xiàn)任兩個(gè)城市頂點(diǎn)之間的最短路徑

33、問題。 建立圖的存儲(chǔ)結(jié)構(gòu) 鄰接矩陣是表示圖形中頂點(diǎn)之間相鄰關(guān)系的矩陣。圖的鄰接矩陣是定義如下的n階方陣： 設(shè)G=（V，E）是一個(gè)圖，結(jié)點(diǎn)集為。 G的鄰接矩陣 當(dāng)鄰接矩陣的行表頭、列表頭順序一定時(shí)，一個(gè)圖的鄰接矩陣表示是唯一的。 圖的鄰接矩陣表示，除了需用一個(gè)二維數(shù)組存儲(chǔ)頂點(diǎn)之間的相鄰關(guān)系的鄰接矩陣外，通常還需要使用一個(gè)具有n個(gè)元素的一維數(shù)組來存儲(chǔ)頂點(diǎn)信息，其中下標(biāo)為i的元素存儲(chǔ)頂點(diǎn)i的信息。因此，圖的鄰接矩陣的存儲(chǔ)結(jié)構(gòu)定義如下： #definf MVNum 50 //最大頂點(diǎn)數(shù) typedef struct { VertexType vexs[MVNum

34、]; //頂點(diǎn)數(shù)組，類型假定為char型 Adjmatrix arcs[MVNum][MVNum]; //鄰接矩陣，假定為int型 }MGraph; 單源最短路徑 最短路徑的提法很多。在這里先討論單源最短路徑問題：即已知有向圖（帶權(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）是

35、一個(gè)有向圖，結(jié)點(diǎn)集為，，cost是表示G的鄰接矩陣，cost[i][j]表示有向邊的權(quán)。若不存在有向邊，則cost[i][j]的權(quán)為無窮大（這里取值為32767）。設(shè)S是一個(gè)集合，其中的每個(gè)元素表示一個(gè)頂點(diǎn)，從源點(diǎn)到這些頂點(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)前的最短距離，其初值為dist[i]=cost[v1][i],i=1,2,……,n。從S之外的頂點(diǎn)集合V-S中選出一個(gè)頂點(diǎn)w，使dist[w]的值最小。于是從源點(diǎn)到達(dá)w只通過S中頂點(diǎn)，把w加入集合S中，調(diào)整dist中記錄的從源點(diǎn)到V-S中每個(gè)頂

36、點(diǎn)v的距離：從原來的dist[v]和dist[w]+cost[w][v]中選擇較小的值作為新的dist[v]。重復(fù)上述過程，直到V-S為空。 最終結(jié)果是：S記錄了從源點(diǎn)到該頂點(diǎn)存在最短路徑的頂點(diǎn)集合，數(shù)組dist記錄了源點(diǎn)到V中其余各頂點(diǎn)之間的最短路徑，path是最短路徑的路徑數(shù)組，其中path[i]表示從源點(diǎn)到頂點(diǎn)i之間的最短路徑的前驅(qū)頂點(diǎn)。 因此，迪杰斯特拉算法可用自然語言描述如下： 初始化S和D，置空最短路徑終點(diǎn)集，置初始的最短路徑值； S[v1]=TRUE; D[v1]=0； //S集初始時(shí)只有源點(diǎn)，源點(diǎn)到源點(diǎn)的距離為0； While (S集中頂點(diǎn)數(shù)

37、始循環(huán)，每次求得v1到某個(gè)v頂點(diǎn)的最短路徑，并加v到S集中； S[v]=TRUE； 更新當(dāng)前最短路徑及距離； } 任意一對(duì)頂點(diǎn)間最短路徑 任意一對(duì)頂點(diǎn)間最短路徑問題，是對(duì)于給定的有向網(wǎng)絡(luò)圖G=（V，E），要對(duì)G中任意一對(duì)頂點(diǎn)有序?qū)Α皏,w(vw)”,找出v到w的最短路徑。 要解決這個(gè)問題，我們可以依次把有向網(wǎng)絡(luò)圖中每個(gè)頂點(diǎn)作為源點(diǎn)，重復(fù)執(zhí)行前面討論的迪杰斯特拉算法n次，即可以求得每對(duì)頂點(diǎn)之間的最短路徑。 這里還可以用另外一種方法，稱作費(fèi)洛伊德（Floyd）算法。 費(fèi)洛伊德（Floyd）算法算法的基本思想是：假設(shè)求從頂點(diǎn) vi到vj的最短路徑。如果從vi到vj存在一條長度為arc

38、s[i][j]的路徑，該路徑不一定是最短路徑，還需要進(jìn)行n次試探。首先考慮路徑和是否存在。如果存在，則比較和< vi,v1,vj >的路徑長度，取長度較短者為當(dāng)前所求得的最短路徑。該路徑是中間頂點(diǎn)序號(hào)不大于1的最短路徑。其次，考慮從vi到vj是否包含有頂點(diǎn)v2為中間頂點(diǎn)的路徑，若沒有，則說明從vi到vj的當(dāng)前最短路徑就是前一步求出的；若有，那么可分解為和,而這兩條路徑是前一次找到的中間頂點(diǎn)序號(hào)不大于1的最短路徑，將這兩條路徑長度相加就得到路徑

39、vj>的長度。將該長度與前一次中求出的從vi到vj的中間頂點(diǎn)序號(hào)不大于1的最短路徑比較，取其長度較短者作為當(dāng)前求得的從vi到vj的中間頂點(diǎn)序號(hào)不大于2的最短路徑。依此類推，直到頂點(diǎn)vn加入當(dāng)前從vi到vj的最短路徑后，選出從vi到vj的中間頂點(diǎn)序號(hào)不大于n的最短路徑為止。由于圖G中頂點(diǎn)序號(hào)不大于n，所以vi到vj的中間頂點(diǎn)序號(hào)不大于n的最短路徑，已考慮了所有頂點(diǎn)作為中間頂點(diǎn)的可能性，因此，它就是vi到vj的最短路徑。 【設(shè)計(jì)功能的實(shí)現(xiàn)】（用C語言） 設(shè)計(jì)如下： #include #include #define MVNum 50 #defi

40、ne Maxint 32767 enum boolean{FALSE,TRUE};// 枚舉類型 typedef char VertexType; typedef int Adjmatrix; typedef struct{ VertexType vexs[MVNum]; //頂點(diǎn)數(shù)組，類型假定為char型 Adjmatrix arcs[MVNum][MVNum]; //鄰接矩陣，假定為int型 }MGraph; int D1[MVNum],p1[MVNum]; int D[MVNum][MVNum],p[MVNum][MVNum]; void CreateMG

41、raph(MGraph * G,int n,int e) { int i,j,k,w; for(i=1;i<=n;i++) G->vexs[i]=(char)i; for(i=1;i<=n;i++) for(j=1;j<=n;j++) G->arcs[i][j]=Maxint; printf("輸入%d條邊的i,j,w:\n",e); for(k=1;k<=e;k++){ scanf("%d,%d,%d",&i,&j,&w); G->arcs[i][j]=w; } printf("有向圖建立完成\n");//建立有向圖的

42、存儲(chǔ)結(jié)構(gòu) } void Dijkstra(MGraph *G,int v1,int n)//迪杰斯特拉算法，最短路徑 { int D2[MVNum],p2[MVNum]; int v,i,w,min; enum boolean S[MVNum]; for(v=1;v<=n;v++) { S[v]=FALSE; D2[v]=G->arcs[v1][v]; if(D2[v]

43、 { min=Maxint; for(w=1;w<=n;w++) if(!S[w] && D2[w]arcs[v][w]arcs[v][w]; p2[w]=v; } } printf("路徑長度 路徑\n"); for(i=1;i<=n;i++) {

44、 printf("%5d",D2[i]); printf("%5d",i); v=p2[i]; while(v!=0) { printf("<-%d",v); v=p2[v]; } printf("\n"); } } void Floyd(MGraph *G,int n)//費(fèi)洛伊德算法 { int i,j,k; for(i=1;i<=n;i++) for(j=1;j<=n;j++) { if( G->arcs[i][j]!=Maxint) p[i][j]=j; else

45、 p[i][j]=0; D[i][j]=G->arcs[i][j]; } for(k=1;k<=n;k++) { for(i=1;i<=n;i++) for(j=1;j<=n;j++) { if(D[i][k]+D[k][j]

46、=(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); printf("2.求任意的兩個(gè)城市之間的最短路徑\n"); Floyd(G,n); printf("輸入源點(diǎn)（或起點(diǎn)）和終點(diǎn):v,

47、w:"); scanf("%d,%d",&v,&w); k=p[v][w]; 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=p[k][w]; } printf("--%d",w); printf("徑路長度:%d\n",D[v][w]); } } 【實(shí)例測(cè)試及運(yùn)行結(jié)果】 實(shí)際圖： 【使用說明】 輸入格式：個(gè)數(shù)，邊數(shù) i，j，k 其余按照要求即可使用。 【心得體會(huì)】 這個(gè)程序是算法設(shè)計(jì)課程的內(nèi)容，用到了迪杰斯特拉算法和費(fèi)洛伊德算法，一開始則是用數(shù)據(jù)結(jié)構(gòu)中圖結(jié)構(gòu)體建立。雖然之前已經(jīng)學(xué)過了其算法如何實(shí)現(xiàn)，不過自己編寫確實(shí)有難度，想起來也麻煩，更重要的是還是有向圖，還有方向問題，總之雖然困難重重，但是通過不懈的努力終于解決了問題，寫出代碼。