太原理工《程序設(shè)計課程設(shè)計》實驗報告

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