課程設(shè)計(jì)--實(shí)驗(yàn)報(bào)告相鄰數(shù)對(duì)isbn識(shí)別碼文本文件單詞統(tǒng)計(jì)送貨

1、<p><b>　　課程設(shè)計(jì)</b></p><p>　　課程名稱： 程序設(shè)計(jì)課程設(shè)計(jì) </p><p>　　設(shè)計(jì)名稱： 相鄰數(shù)對(duì)、ISBN識(shí)別碼 </p><p>　　文本文件單詞統(tǒng)計(jì)、構(gòu)造最小生成樹(shù)</p><p>　　送貨、學(xué)生信息管理系統(tǒng) </

2、p><p>　　專業(yè)班級(jí)： 學(xué)號(hào)： </p><p>　　學(xué)生姓名： </p><p>　　指導(dǎo)教師： </p><p>　　2017年06月21日</p><p><b>　　課程設(shè)計(jì)任務(wù)書(shū)</b&g

3、t;</p><p><b>　　注：</b></p><p>　　1.課程設(shè)計(jì)完成后，學(xué)生提交的歸檔文件應(yīng)按照：封面—任務(wù)書(shū)—說(shuō)明書(shū)—圖紙的順序進(jìn)行裝訂上交（大張圖紙不必裝訂）。</p><p>　　2.可根據(jù)實(shí)際內(nèi)容需要續(xù)表，但應(yīng)保持原格式不變。</p><p><b>　　目 錄</b><

4、;/p><p><b>　　1.相鄰數(shù)對(duì)2</b></p><p>　　2.ISBN識(shí)別碼4</p><p>　　3.文本文件單詞統(tǒng)計(jì)7</p><p>　　4.構(gòu)造可以使n個(gè)城市連接的最小生成樹(shù)13</p><p><b>　　5.送貨18</b></

5、p><p>　　6.學(xué)生信息管理系統(tǒng)23</p><p><b>　　題目一 相鄰數(shù)對(duì)</b></p><p><b>　　1.1【問(wèn)題描述】</b></p><p>　　給定 n 個(gè)不同的整數(shù)，問(wèn)這些數(shù)中有多少對(duì)整數(shù)，它們的值正好相差 1。</p><p><b>

6、;　　輸入格式</b></p><p>　　輸入的第一行包含一個(gè)整數(shù)n，表示給定整數(shù)的個(gè)數(shù)。</p><p>　　第二行包含所給定的n個(gè)整數(shù)。</p><p><b>　　輸出格式</b></p><p>　　輸出一個(gè)整數(shù)，表示值正好相差1的數(shù)對(duì)的個(gè)數(shù)。</p><p>　　1.2【設(shè)

7、計(jì)及分析】</p><p>　　先設(shè)定一個(gè)全局?jǐn)?shù)組a，數(shù)組的大小盡量大，數(shù)組的下標(biāo)對(duì)應(yīng)的是輸入的整數(shù)范圍。數(shù)組內(nèi)0表示沒(méi)有對(duì)應(yīng)于該下標(biāo)的整數(shù)，1表示有對(duì)應(yīng)于該下標(biāo)的整數(shù)。將數(shù)組全部初始化為0，表示沒(méi)有進(jìn)行輸入。然后輸入整數(shù)個(gè)數(shù)和相應(yīng)的整數(shù)對(duì)數(shù)組進(jìn)行修改，然后進(jìn)行相鄰數(shù)對(duì)篩選得出數(shù)對(duì)及數(shù)對(duì)的個(gè)數(shù)。</p><p>　　數(shù)據(jù)流圖如圖1-1。</p><p>　　1.3【

8、設(shè)計(jì)功能的實(shí)現(xiàn)】</p><p>　　#include<stdio.h></p><p>　　int a[1005];</p><p>　　void inita(int *a){//初始化數(shù)組</p><p><b>　　int n=0;</b></p><p>　　for(;n<

9、;1004;n++)</p><p><b>　　a[n]=0;</b></p><p><b>　　}</b></p><p>　　void main(){</p><p>　　int n,i,m,count=0;</p><p><b>　　inita(a);&

10、lt;/b></p><p>　　printf("請(qǐng)輸入整數(shù)的個(gè)數(shù)：\n");</p><p>　　scanf("%d",&n);</p><p>　　printf("請(qǐng)輸入整數(shù)：\n");</p><p>　　for(i=0;i<n;i++){//修改數(shù)組內(nèi)容&

11、lt;/p><p>　　scanf("%d",&m);</p><p><b>　　a[m]=1;</b></p><p><b>　　}</b></p><p>　　printf("輸入的整數(shù)中的相鄰數(shù)對(duì)如下：\n");</p><p

12、>　　for(i=0;i<1005;i++){//相鄰數(shù)對(duì)的篩選</p><p>　　if((a[i]==1)&&(a[i+1]==1)){</p><p>　　printf("(%d,%d)",i,i+1);</p><p><b>　　count+=1;</b></p><

13、p><b>　　}</b></p><p><b>　　}</b></p><p>　　printf("\n輸入的整數(shù)中共有%d個(gè)相鄰數(shù)對(duì)\n",count);</p><p><b>　　}</b></p><p>　　1.4【測(cè)試及運(yùn)行結(jié)果】<

14、;/p><p><b>　　1.5【總結(jié)】</b></p><p>　　該題目比較簡(jiǎn)單，在經(jīng)過(guò)老師的指導(dǎo)，有了大概的設(shè)計(jì)思想并進(jìn)行代碼的編寫(xiě)。</p><p>　　在寫(xiě)代碼的過(guò)程中，用了全局?jǐn)?shù)組a，在初始化數(shù)組后對(duì)其進(jìn)行調(diào)整，但是在編寫(xiě)過(guò)程中，沒(méi)有考慮好各變量的關(guān)系，調(diào)整數(shù)組時(shí)發(fā)生了數(shù)據(jù)與輸入數(shù)據(jù)不一致的情況，此時(shí)雖然沒(méi)有語(yǔ)法錯(cuò)誤，但經(jīng)過(guò)檢查后發(fā)現(xiàn)

15、了邏輯錯(cuò)誤，然后增加了一個(gè)變量進(jìn)行修改。</p><p>　　該程序比較簡(jiǎn)單，但是覺(jué)得數(shù)組大部分的空間沒(méi)有利用，有一定的資源浪費(fèi)，在運(yùn)算速度上也是比較慢的。</p><p>　　題目二 ISBN識(shí)別碼</p><p><b>　　2.1【問(wèn)題描述】</b></p><p>　　每一本正式出版的圖書(shū)都有一個(gè) ISBN 號(hào)碼

16、與之對(duì)應(yīng)，ISBN 碼包括 9 位數(shù)字、1 位識(shí)別碼和 3 位分隔符，其規(guī)定格式如“x-xxx-xxxxx-x”，其中符號(hào)“-”是分隔符（鍵盤(pán)上的減號(hào)），最后一位是識(shí)別碼，例如 0-670-82162-4 就是一個(gè)標(biāo)準(zhǔn)的 ISBN 碼。ISBN 碼的首位數(shù)字表示書(shū)籍的出版語(yǔ)言，例如 0 代表英語(yǔ)；第一個(gè)分隔符“-”之后的三位數(shù)字代表出版社，例如 670 代表維京出版社；第二個(gè)分隔之后的五位數(shù)字代表該書(shū)在出版社的編號(hào)；最后一位為識(shí)別碼。&

17、lt;/p><p>　　識(shí)別碼的計(jì)算方法如下：</p><p>　　首位數(shù)字乘以 1 加上次位數(shù)字乘以 2……以此類推，用所得的結(jié)果 mod 11，所得的余數(shù)即為識(shí)別碼，如果余數(shù)為 10，則識(shí)別碼為大寫(xiě)字母 X。例如 ISBN 號(hào)碼 0-670-82162-4 中的識(shí)別碼 4 是這樣得到的：對(duì) 067082162 這 9 個(gè)數(shù)字，從左至右，分別乘以 1，2，…，9，再求和，即0×1+

18、6×2+……+2×9=158，然后取 158 mod 11 的結(jié)果 4 作為識(shí)別碼。</p><p>　　編寫(xiě)程序判斷輸入的 ISBN 號(hào)碼中識(shí)別碼是否正確，如果正確，則僅輸出“Right”；如果錯(cuò)誤，則輸出是正確的 ISBN 號(hào)碼。</p><p><b>　　輸入格式</b></p><p>　　輸入只有一行，是一個(gè)字符

19、序列，表示一本書(shū)的 ISBN 號(hào)碼（保證輸入符合 ISBN 號(hào)碼的格式要求）。</p><p><b>　　輸出格式</b></p><p>　　輸出一行，假如輸入的 ISBN 號(hào)碼的識(shí)別碼正確，那么輸出“Right”，否則，按照規(guī)定的格式，輸出正確的 ISBN 號(hào)碼（包括分隔符“-”）。</p><p>　　2.2【設(shè)計(jì)及分析】</p&

20、gt;<p>　　用一個(gè)函數(shù)來(lái)計(jì)算正確的ISBN碼。在主函數(shù)中，先輸入一個(gè)字符串存放于全局?jǐn)?shù)組a中，然后用對(duì)字符串中特定符號(hào)‘-’進(jìn)行刪除，并保存與數(shù)組a1中，原數(shù)組不變。處理數(shù)組a1，用judge函數(shù)來(lái)計(jì)算正確的ISBN碼，然后對(duì)數(shù)組a1中的ISBN碼與計(jì)算的值是否相等，相等則輸出RIGHT，反之將計(jì)算出的ISBN碼賦值給數(shù)組a中的ISBN碼，并輸出數(shù)組a。</p><p>　　數(shù)據(jù)流圖如圖2-1

21、。</p><p>　　2.3【設(shè)計(jì)功能的實(shí)現(xiàn)】</p><p>　　#include<stdio.h></p><p>　　#include<math.h></p><p>　　#include<string.h></p><p>　　char a[100],a1[100];<

22、;/p><p>　　int judge(char *a){//計(jì)算正確的ISBN碼</p><p>　　int i=0,l,s=0,m;</p><p>　　for(;i<9;i++){</p><p><b>　　a[i]-=48;</b></p><p>　　l=a[i]*(i+1);<

23、;/p><p><b>　　s=s+l;</b></p><p><b>　　}</b></p><p><b>　　m=s%11;</b></p><p><b>　　return m;</b></p><p><b>　　

24、}</b></p><p>　　void main(){</p><p>　　int i,m,j=0,l;</p><p>　　printf("請(qǐng)輸入ISBN碼：");</p><p><b>　　gets(a);</b></p><p>　　l=strlen(a)

25、;</p><p>　　for(i=0;a[i]!='\0';i++){//將‘-’刪除掉便于計(jì)算</p><p>　　if(a[i]!='-')</p><p>　　a1[j++]=a[i];</p><p><b>　　else</b></p><p>　　a1

26、[j]=a[i];}</p><p>　　m=judge(a1);//計(jì)算ISBN碼</p><p>　　//printf("%d",m);</p><p>　　if(m==(a1[9]-48))//判斷ISBN碼是否正確</p><p>　　printf("RIGHT");//正確輸出RIGHT&l

27、t;/p><p><b>　　else</b></p><p>　　{a[l-1]=(m+48);//錯(cuò)誤則修改ISBN碼并輸出正確的ISBN碼</p><p>　　printf("%s",a);</p><p><b>　　}</b></p><p><

28、;b>　　}</b></p><p>　　2.4【測(cè)試及運(yùn)行結(jié)果】</p><p><b>　　2.5【總結(jié)】</b></p><p>　　在編寫(xiě)程序框架時(shí)，我準(zhǔn)備先實(shí)現(xiàn)ISBN碼的正確計(jì)算與修改，所以先使用的是整數(shù)進(jìn)行計(jì)算，在整數(shù)計(jì)算成功后修改為題目中所要求的字符串輸入。</p><p>　　在對(duì)字符

29、串進(jìn)行處理時(shí)，要考慮字符‘-’在字符串中的位置，最初打算用三個(gè)數(shù)組來(lái)控制計(jì)算，但在計(jì)算過(guò)程中出現(xiàn)了錯(cuò)誤。然后采取將字符串中的‘-’刪除并存儲(chǔ)于新的數(shù)組a1中，原始數(shù)組不變。</p><p>　　在初始框架中，計(jì)算是針對(duì)整數(shù)進(jìn)行的，在對(duì)字符串進(jìn)行處理時(shí)，要考慮其與整數(shù)的關(guān)系，才能得到正確的計(jì)算值。在修改數(shù)組a時(shí)也需要考慮計(jì)算值之間的轉(zhuǎn)換。</p><p>　　題目三 文本文件單詞統(tǒng)計(jì)<

30、/p><p><b>　　3.1【問(wèn)題描述】</b></p><p>　　要統(tǒng)計(jì)英文文本文件中出現(xiàn)了哪些單詞，就要從文件中讀取字符，讀取出來(lái)的連續(xù)英文字符認(rèn)為是一個(gè)單詞，遇空格或標(biāo)點(diǎn)符號(hào)單詞結(jié)束。</p><p>　　3.2【設(shè)計(jì)及分析】</p><p>　　先構(gòu)建一個(gè)結(jié)構(gòu)體用于存放單詞及對(duì)應(yīng)的數(shù)目，然后用一個(gè)函數(shù)來(lái)對(duì)所獲取

31、的單詞進(jìn)行處理，單詞相同的則對(duì)應(yīng)數(shù)目加1，總單詞數(shù)目加1；單詞不同的總單詞加1，對(duì)應(yīng)單詞數(shù)目加1。主程序中通過(guò)文件進(jìn)行讀取單詞，并將大寫(xiě)的字母轉(zhuǎn)換為小寫(xiě)的字母。然后進(jìn)行單詞的排序，先按照單詞出現(xiàn)的頻率排序，然后按照首字母進(jìn)行排序，最后對(duì)首字母相同的單詞進(jìn)行排序。</p><p>　　數(shù)據(jù)流圖如圖3-1。</p><p>　　3.3【設(shè)計(jì)功能的實(shí)現(xiàn)】</p><p>

32、　　#include<stdio.h></p><p>　　#include<string.h></p><p>　　#include <stdlib.h></p><p>　　struct word{//結(jié)構(gòu)體，用于存放單詞及對(duì)應(yīng)的個(gè)數(shù)</p><p>　　char str[30];</p>

33、<p><b>　　int num;</b></p><p><b>　　}A[1000];</b></p><p>　　int sum;//記錄總的單詞數(shù)</p><p>　　void chuli(char s[]){//處理獲取的單詞</p><p><b>　　int i

34、,j;</b></p><p>　　int flag=0;</p><p>　　for(i=0;i<=sum;i++){</p><p>　　if(strcmp(A[i].str,s)==0){//相同的單詞，單詞總數(shù)加1，對(duì)應(yīng)單詞數(shù)量加1，標(biāo)志flag變成1</p><p>　　A[i].num++;</p>

35、<p><b>　　flag=1;</b></p><p><b>　　sum++;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　if(flag==0){//單詞不同，則加入單詞，

36、并將對(duì)應(yīng)的單詞數(shù)和單詞總數(shù)量加1</p><p>　　for(j=0;j<30;j++)</p><p>　　A[sum].str[j]=s[j];</p><p>　　A[sum].num++;</p><p><b>　　sum++;</b></p><p><b>　　}&l

37、t;/b></p><p><b>　　}</b></p><p>　　int main(){</p><p>　　char ch,s[30];</p><p>　　int i,flag=0,l;</p><p>　　int ii,jj;</p><p>　　stru

38、ct word a;</p><p><b>　　FILE *fp;</b></p><p>　　fp=fopen("tyut.txt","r");</p><p>　　if(fp==NULL){</p><p>　　printf("文件為空!");</p

39、><p><b>　　}</b></p><p><b>　　sum=0;</b></p><p><b>　　ch=NULL;</b></p><p>　　for(i=0;i<1000;i++)</p><p>　　A[i].num=0;//將所有單

40、詞對(duì)應(yīng)的數(shù)目設(shè)置為0</p><p>　　while(ch!=-1){</p><p>　　for(i=0;i<30;i++)</p><p>　　s[i]='\0';</p><p>　　ch=fgetc(fp);</p><p>　　if((ch>=65&&ch<=

41、90)||(ch>=97&&ch<=122)){//從文件中獲取字母</p><p>　　for(i=0;;i++){</p><p>　　if(ch>=65&&ch<=90) ch=ch+32;//將大寫(xiě)字母處理為小寫(xiě)字母</p><p><b>　　s[i]=ch;</b></p

42、><p>　　ch=fgetc(fp);</p><p>　　if((ch>=65&&ch<=90)||(ch>=97&&ch<=122))</p><p><b>　　continue;</b></p><p>　　else break;</p><

43、;p><b>　　}</b></p><p>　　chuli(s);//處理所獲取的單詞s</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　//將單詞按照出現(xiàn)的頻率排序，便于后面的按字母順序排序，由于之前初始化A的sum

44、=0，//所以去掉這一步按字母排序順序會(huì)打亂</p><p>　　for(ii=0;ii<sum;ii++){</p><p>　　for(jj=ii+1;jj<sum;jj++)</p><p>　　if(A[ii].num<A[jj].num){</p><p><b>　　a=A[jj];</b>

45、</p><p>　　A[jj]=A[ii];</p><p>　　A[ii]=a;}}</p><p>　　printf("文件中一共包含%d個(gè)單詞\n",sum);</p><p>　　//首先按照首字母進(jìn)行排序</p><p>　　for(ii=0;A[ii].num!=0;ii++)<

46、/p><p>　　for(jj=ii+1;A[jj].num!=0;jj++){</p><p>　　if(A[ii].str[0]>A[jj].str[0]){</p><p><b>　　a=A[jj];</b></p><p>　　A[jj]=A[ii];</p><p><b>

47、;　　A[ii]=a;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　//然后首字母相同的單詞再進(jìn)行排序</p><p>　　for(ii=0;A[ii].num!=0;ii++)</p><p>　

48、　for(jj=ii+1;A[jj].num!=0;jj++){</p><p><b>　　l=0;</b></p><p>　　while(A[ii].str[l]==A[jj].str[l]){</p><p><b>　　l++;</b></p><p>　　if(A[ii].str[l]&

49、gt;A[jj].str[l]){</p><p><b>　　a=A[jj];</b></p><p>　　A[jj]=A[ii];</p><p><b>　　A[ii]=a;</b></p><p><b>　　}}</b></p><p><

50、;b>　　}</b></p><p>　　for(i=0;A[i].num !=0;i++)</p><p>　　printf("%s單詞個(gè)數(shù)有：%d\n",A[i].str,A[i].num);</p><p>　　printf("\n\n");</p><p><b>

51、　　return 0;</b></p><p><b>　　}</b></p><p>　　3.4【測(cè)試及運(yùn)行結(jié)果】</p><p><b>　　3.5【總結(jié)】</b></p><p>　　設(shè)置了全局?jǐn)?shù)組A和全局變量s用于存放單詞和單詞總數(shù)，用全局變量可以在使用對(duì)應(yīng)函數(shù)時(shí)直接進(jìn)行修改。&

52、lt;/p><p>　　在獲取單詞時(shí)，如果不進(jìn)行大小寫(xiě)轉(zhuǎn)換的話，相同的單詞會(huì)因?yàn)榇笮?xiě)的不同而出現(xiàn)兩次甚至多次，與題意不符，所以在獲取單詞的同時(shí)可以將大小寫(xiě)進(jìn)行統(tǒng)一，便于最后統(tǒng)計(jì)的正確性。在本次實(shí)驗(yàn)我選擇的是將大小寫(xiě)字母統(tǒng)一為小寫(xiě)字母，然后進(jìn)行統(tǒng)計(jì)排序。</p><p>　　在對(duì)所獲取的單詞進(jìn)行排序時(shí)，先按單詞出現(xiàn)的頻率排序，將數(shù)組A中sum值為0的一律排到最后，便于進(jìn)行下一步統(tǒng)計(jì)。第二步按照

53、首字母進(jìn)行排序，大致將單詞進(jìn)行了分段。第三步按照首字母相同的單詞組進(jìn)行排序，最終完成題目的要求。在排序的部分中，感覺(jué)程序過(guò)于繁瑣，可以進(jìn)行一些優(yōu)化。</p><p>　　題目四 構(gòu)造可以使n個(gè)城市連接的最小生成樹(shù)</p><p><b>　　4.1【問(wèn)題描述】</b></p><p>　　給定一個(gè)地區(qū)的n個(gè)城市間的距離網(wǎng)，用Prim算法或Kru

54、skal算法建立最小生成樹(shù)，并計(jì)算得到的最小生成樹(shù)的代價(jià)。</p><p><b>　　基本要求： </b></p><p>　　城市間的距離網(wǎng)采用鄰接矩陣表示，鄰接矩陣的存儲(chǔ)結(jié)構(gòu)定義采用課本中給出的定義，若兩個(gè)城市之間不存在道路，則將相應(yīng)邊的權(quán)值設(shè)為自己定義的無(wú)窮大值。 </p><p>　　要求在屏幕上顯示得到的最小生成

55、樹(shù)中包括了哪些城市間的道路，并顯示得到的最小生成樹(shù)的代價(jià)。 </p><p>　　表示城市間距離網(wǎng)的鄰接矩陣（要求至少6個(gè)城市，10條邊）。</p><p>　　4.2【設(shè)計(jì)及分析】</p><p>　　在考慮使用Prim 算法還是Kruskal 算法時(shí)，我選擇使用prim算法。雖然kruskal算法算法思想簡(jiǎn)單，但是在算法實(shí)現(xiàn)上需要判斷新加入的邊是否會(huì)構(gòu)

56、成回路，而prim算法不需要進(jìn)行判斷，構(gòu)成的就是最小生成樹(shù)。prim算法中需要判斷所選擇的點(diǎn)是否已在點(diǎn)集中，若存在，則選擇次小邊所對(duì)應(yīng)的點(diǎn)。</p><p>　　在實(shí)現(xiàn)prim算法時(shí)，先建立了一個(gè)全局?jǐn)?shù)組用于構(gòu)建鄰接矩陣，然后使用了兩個(gè)函數(shù)，一個(gè)用于選擇頂點(diǎn)v所對(duì)應(yīng)最短邊的點(diǎn)，另一個(gè)用于選擇在已有點(diǎn)集中選擇最短邊所對(duì)應(yīng)的點(diǎn)。主函數(shù)中先初始化兩個(gè)點(diǎn)集，規(guī)定一個(gè)起點(diǎn)，然后進(jìn)行最小生成樹(shù)的構(gòu)造。</p>

57、<p>　　數(shù)據(jù)流圖如圖4-1。</p><p>　　4.3【設(shè)計(jì)功能的實(shí)現(xiàn)】</p><p>　　#include <stdio.h></p><p>　　#define m1 999;</p><p>　　int mm[20],l;</p><p>　　int nodelist[20][20]

58、,n,d[20],p[20];</p><p>　　void readgraph(){//初始化鄰接矩陣</p><p><b>　　int i,j;</b></p><p>　　printf("請(qǐng)輸入圖的頂點(diǎn)個(gè)數(shù)n:");</p><p>　　scanf("%d",&n)

59、;</p><p>　　printf("請(qǐng)輸入圖所對(duì)應(yīng)的鄰接矩陣:\n");</p><p>　　for(i=1;i<=n;i++){</p><p>　　for(j=1;j<=n;j++)</p><p>　　scanf("%d",&nodelist[i][j]);</p&g

60、t;<p><b>　　}</b></p><p>　　printf("\n");</p><p>　　printf("已成功建立鄰接矩陣\n");</p><p>　　for(i=1;i<=n;i++){</p><p>　　for(j=1;j<=n;j

61、++)</p><p>　　printf("%5d",nodelist[i][j]);</p><p>　　printf("\n");</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　

62、int mine(int v){//求頂點(diǎn)V所連接的點(diǎn)的最短路徑所對(duì)應(yīng)的頂點(diǎn)</p><p>　　int min1,i,ii;</p><p>　　min1=nodelist[v][1];</p><p><b>　　ii=1;</b></p><p>　　for(i=1;i<=n;i++){</p>

63、<p>　　if(nodelist[v][i]<min1){</p><p>　　min1=nodelist[v][i];</p><p><b>　　ii=i;</b></p><p><b>　　}</b></p><p>　　else continue;</p>

64、<p><b>　　}</b></p><p>　　return ii;</p><p><b>　　}</b></p><p>　　int mme(){//求已有頂點(diǎn)的最短路徑所對(duì)應(yīng)的頂點(diǎn)</p><p>　　int ei,ej,i;</p><p>　　ei=

65、mine(1);</p><p><b>　　l=1;</b></p><p>　　for(i=2;i<=n;i++){</p><p>　　if(mm[i]!=0)</p><p>　　{ej=mine(i);</p><p>　　if(nodelist[l][ei]>=nodeli

66、st[i][ej])</p><p><b>　　{</b></p><p><b>　　ei=ej;</b></p><p><b>　　l=i;</b></p><p><b>　　}}</b></p><p><b&g

67、t;　　}</b></p><p>　　return ei;</p><p><b>　　}</b></p><p>　　void main(){</p><p>　　int min,m[20],v,i,ei,j;</p><p>　　char ding[7]={'A'

68、,'B','C','D','E','F','G'};</p><p><b>　　min=0;</b></p><p>　　readgraph();</p><p><b>　　v=1;</b></p><p

69、>　　for(i=0;i<=n;i++)//初始化兩個(gè)頂點(diǎn)集</p><p><b>　　{m[i]=1;</b></p><p><b>　　mm[i]=0;}</b></p><p><b>　　m[1]=0;</b></p><p><b>　　mm

70、[1]=1;</b></p><p>　　printf("所構(gòu)造的最小生成樹(shù)的邊及對(duì)應(yīng)權(quán)值為：\n");</p><p>　　for(;v<n;v++){</p><p><b>　　ei=mme();</b></p><p>　　if(mm[ei]==1){//判斷所找到的頂點(diǎn)是否

71、已經(jīng)加入頂點(diǎn)集</p><p>　　nodelist[l][ei]=1000;</p><p>　　nodelist[ei][l]=1000;</p><p><b>　　v-=1;</b></p><p><b>　　}</b></p><p>　　else {mm[ei]

72、=1;</p><p><b>　　m[ei]=0;</b></p><p>　　printf("%c到%c權(quán)值為%d",ding[l-1],ding[ei-1],nodelist[l][ei]);</p><p>　　min+=nodelist[l][ei];//計(jì)算最短路徑長(zhǎng)度</p><p>　

73、　nodelist[l][ei]=1000;</p><p>　　nodelist[ei][l]=1000;</p><p>　　printf("\n");</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　

74、　printf("最小生成樹(shù)的權(quán)值即最短路徑長(zhǎng)度為:%d\n",min);</p><p><b>　　}</b></p><p>　　4.4【測(cè)試及運(yùn)行結(jié)果】</p><p><b>　　4.5【總結(jié)】</b></p><p>　　在最初編寫(xiě)程序時(shí)，沒(méi)有使用兩個(gè)算法，直到最后構(gòu)

75、建生成樹(shù)需要判斷是否構(gòu)成回路時(shí)才發(fā)現(xiàn)沒(méi)有使用算法思想。</p><p>　　在編寫(xiě)算法的過(guò)程中，發(fā)現(xiàn)判斷是否構(gòu)成回路的函數(shù)比較復(fù)雜一點(diǎn)，雖然kruskal算法思想簡(jiǎn)單，但是在實(shí)現(xiàn)方面覺(jué)得prim算法更容易一點(diǎn)。在選出最短邊所對(duì)應(yīng)的頂點(diǎn)后，只需要判斷該頂點(diǎn)是否已經(jīng)包含在點(diǎn)集，若包含，則選次短邊所對(duì)的頂點(diǎn)并繼續(xù)判斷，反之則將該頂點(diǎn)加入到點(diǎn)集中，逐步構(gòu)造出最短路徑并計(jì)算出最短路徑長(zhǎng)度。</p><p

76、>　　在初始化鄰接矩陣時(shí)需要自己手動(dòng)輸入，當(dāng)矩陣比較大時(shí)，輸入矩陣比較麻煩而且可能出現(xiàn)出入錯(cuò)誤的情況，這一點(diǎn)需要改進(jìn)，初步的想法是可以用文件的讀取方式進(jìn)行初始化。</p><p><b>　　題目五 送貨</b></p><p><b>　　5.1【問(wèn)題描述】</b></p><p>　　為了增加公司收入，F(xiàn)

77、0;公司新開(kāi)設(shè)了物流業(yè)務(wù)。由于 F 公司在業(yè)界的良好口碑，物流業(yè)務(wù)一開(kāi)通即受到了消費(fèi)者的歡迎，物流業(yè)務(wù)馬上遍及了城市的每條街道。然而，F(xiàn) 公司現(xiàn)在只安排了小明一個(gè)人負(fù)責(zé)所有街道的服務(wù)。任務(wù)雖然繁重，但是小明有足夠的信心，他拿到了城市的地圖，準(zhǔn)備研究最好的方案。城市中有 n 個(gè)交叉路口，m 條街道連接在這些交叉路口之間，每條街道的首尾都正好連接著一個(gè)交叉路口。除開(kāi)街道的首尾端點(diǎn)，

78、街道不會(huì)在其他位置與其他街道相交。每個(gè)交叉路口都至少連接著一條街道，有的交叉路口可能只連接著一條或兩條街道。</p><p><b>　　基本需求：</b></p><p>　　小明希望設(shè)計(jì)一個(gè)方案，從編號(hào)為1的交叉路口出發(fā)，每次必須沿街道去往街道另一端的路口，再?gòu)男碌穆房诔霭l(fā)去往下一個(gè)路口，直到所有的街道都經(jīng)過(guò)了正好一次。</p><p>　

79、　輸入數(shù)據(jù)格式：輸入的第一行包含兩個(gè)整數(shù) n, m(1≤n≤10, n-1≤m≤20)，表示交叉路口的數(shù)量和街道的數(shù)量，交叉路口從 1 到 n 標(biāo)號(hào)。 接下來(lái)m行，每行兩個(gè)整數(shù)a,b，表示和標(biāo)號(hào)為a的交叉路口和標(biāo)號(hào)為b的交叉路口之間有一條街道，街道是雙向的，小明可以從任意一端走向另一端。兩個(gè)路口之間最多有一條街道。</p><p>

80、　　輸出輸出格式：如果小明可以經(jīng)過(guò)每條街道正好一次，則輸出一行包含m+1個(gè)整數(shù)p1,p2,p3,...,pm+1，表示小明經(jīng)過(guò)的路口的順序，相鄰兩個(gè)整數(shù)之間用一個(gè)空格分隔。如果有多種方案滿足條件，則輸出字典序最小的一種方案，即首先保證p1最小，p1最小的前提下再保證p2最小，依此類推。 </p><p>　　如果不存在方案使得小明經(jīng)過(guò)每條街道正好一次，則輸出一個(gè)整數(shù)-1。</p><

81、p>　　5.2【設(shè)計(jì)及分析】</p><p>　　經(jīng)過(guò)查閱資料，發(fā)現(xiàn)解決該問(wèn)題需要使用歐拉回路的算法。在圖構(gòu)建完成后，需要先判斷圖中頂點(diǎn)度數(shù)為奇數(shù)的個(gè)數(shù)l，l為0或2時(shí)存在回路，反之不存在回路。首先用函數(shù)初始化和設(shè)置鄰接矩陣，然后用函數(shù)計(jì)算圖中頂點(diǎn)度數(shù)是奇數(shù)的個(gè)數(shù)。在主函數(shù)中進(jìn)行判斷，若滿足存在回路的條件，則用選擇頂點(diǎn)的函數(shù)構(gòu)建路徑。選擇頂點(diǎn)的函數(shù)中，要判斷被選則的頂點(diǎn)i是否已經(jīng)包含在點(diǎn)集b，若不包含則選出

82、頂點(diǎn)i,若包含，如果只存在這一條邊的情況下選擇i，反之選擇滿足條件的其他頂點(diǎn)j。</p><p>　　數(shù)據(jù)流圖如圖5-1。</p><p>　　5.3【設(shè)計(jì)功能的實(shí)現(xiàn)】</p><p>　　#include <stdio.h></p><p>　　int a[100][100],b[100];</p><p&g

83、t;　　void chushihua(int l){//初始化鄰接矩陣a和已選點(diǎn)集b</p><p><b>　　int i,j;</b></p><p>　　for(i=1;i<=100;i++)</p><p>　　for(j=1;j<=100;j++)</p><p>　　a[i][j]=0;</

84、p><p>　　for(i=1;i<=100;i++)</p><p><b>　　b[i]=0;</b></p><p><b>　　}</b></p><p>　　int shezhi(int m){//設(shè)置鄰接矩陣</p><p>　　int a1,b1,i;<

85、/p><p>　　for(i=1;i<=m;i++){</p><p>　　scanf("%d,%d",&a1,&b1);</p><p>　　a[a1][b1]=1;</p><p>　　a[b1][a1]=1;}</p><p><b>　　return 0;<

86、/b></p><p><b>　　}</b></p><p>　　int odd(int n){//計(jì)算頂點(diǎn)度數(shù)為奇數(shù)的個(gè)數(shù)</p><p>　　int l=0,i,j,m,s;</p><p>　　for(i=1;i<=n;i++){</p><p><b>　　m=0;

87、</b></p><p><b>　　s=0;</b></p><p>　　for(j=1;j<=n;j++){</p><p>　　if (a[i][j]==1)</p><p><b>　　m++;</b></p><p><b>　　}<

88、;/b></p><p><b>　　s=m%2;</b></p><p><b>　　if(s==1)</b></p><p><b>　　l++;</b></p><p><b>　　}</b></p><p><b

89、>　　return l;</b></p><p><b>　　}</b></p><p>　　int xuanze(int v,int n){//選擇路徑</p><p><b>　　int i,j;</b></p><p>　　for(i=1;i<=n;i++){</

90、p><p>　　if((a[v][i]==1)&&b[i]!=1){//若邊存在且點(diǎn)i未被選擇時(shí)，則選擇該點(diǎn)</p><p>　　a[v][i]=0;</p><p>　　a[i][v]=0;</p><p><b>　　b[i]=1;</b></p><p><b>　　r

91、eturn i;</b></p><p><b>　　}</b></p><p>　　else if((a[v][i]==1)&&b[i]==1){//若邊存在但點(diǎn)i已被選擇，則判斷v點(diǎn)是否存在其他邊存在且點(diǎn)j未被選擇的情況， 若存在，則返回j;反之返回i</p><p>　　for(j=i+1;j<=n;j+

92、+){</p><p>　　if((a[v][j]==1)&&b[j]!=1){</p><p>　　a[v][j]=0;</p><p>　　a[j][v]=0;</p><p><b>　　b[j]=1;</b></p><p>　　return j;}</p>

93、<p>　　else return i;</p><p><b>　　}</b></p><p><b>　　return i;</b></p><p><b>　　}</b></p><p>　　else continue;</p><p>

94、<b>　　}</b></p><p>　　return 0;}</p><p>　　void main(){</p><p>　　int m,i,j,end[1000],a1=0,l,n;</p><p>　　printf("請(qǐng)輸入交叉路口的數(shù)量和街道的數(shù)量:\n");</p>&l

95、t;p>　　scanf("%d",&n);</p><p>　　scanf("%d",&m);</p><p>　　chushihua(n);</p><p>　　// printf("%d",n);</p><p>　　printf("請(qǐng)輸入%

96、d條街道：",m);</p><p>　　shezhi(m);</p><p>　　/*for(i=1;i<=n;i++)</p><p>　　for(j=1;j<=n;j++)</p><p>　　printf("%d",a[i][j]);</p><p>　　printf

97、("\n");</p><p><b>　　*/</b></p><p><b>　　l=odd(n);</b></p><p>　　printf("奇數(shù)度的結(jié)點(diǎn)有%d個(gè)\n",l);</p><p>　　if(l!=0&&l!=2){<

98、/p><p>　　printf("-1\n");</p><p>　　printf("不存在路徑！");}</p><p><b>　　else{</b></p><p>　　printf("存在路徑\n");</p><p><b&g

99、t;　　j=1;</b></p><p><b>　　b[1]=1;</b></p><p><b>　　end[1]=1;</b></p><p>　　for(i=1;i<=(m+1);i++){//調(diào)用選擇函數(shù)</p><p>　　a1=xuanze(j,n);</p&g

100、t;<p>　　end[i+1]=a1;</p><p><b>　　j=a1;</b></p><p><b>　　}</b></p><p>　　printf("構(gòu)成的路徑為：\n");</p><p>　　for(i=1;i<=(m+1);i++)//輸

101、出生成的路徑</p><p>　　printf("%d ",end[i]);</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　5.4【測(cè)試及運(yùn)行結(jié)果】</p><p><b>　　5.5【總結(jié)

102、】</b></p><p>　　看過(guò)題目后要先去查閱資料，在知道處理的算法后要仔細(xì)閱讀算法，了解算法的核心思想。在掌握算法后才可以進(jìn)行編程，不然會(huì)做很多的無(wú)用功，浪費(fèi)了時(shí)間和精力。</p><p>　　在初始化矩陣時(shí)，發(fā)現(xiàn)最初設(shè)置的全局變量n沒(méi)有被賦值，經(jīng)過(guò)修改后把變量n設(shè)置在了主函數(shù)內(nèi)。</p><p>　　在編寫(xiě)選擇函數(shù)時(shí)，對(duì)情況的判斷掌握的不太好，