課程設(shè)計--實驗報告相鄰數(shù)對isbn識別碼文本文件單詞統(tǒng)計送貨

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

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

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

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

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

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

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

8、設(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("請輸入整數(shù)的個數(shù)：\n");</p><p>　　scanf("%d",&n);</p><p>　　printf("請輸入整數(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ù)對如下：\n");</p><p

12、>　　for(i=0;i<1005;i++){//相鄰數(shù)對的篩選</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個相鄰數(shù)對\n",count);</p><p><b>　　}</b></p><p>　　1.4【測試及運行結(jié)果】<

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

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

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

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

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

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

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

21、。</p><p>　　2.3【設(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){//計算正確的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("請輸入ISBN碼：");</p><p><b>　　gets(a);</b></p><p>　　l=strlen(a)

25、;</p><p>　　for(i=0;a[i]!='\0';i++){//將‘-’刪除掉便于計算</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);//計算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);//錯誤則修改ISBN碼并輸出正確的ISBN碼</p><p>　　printf("%s",a);</p><p><b>　　}</b></p><p><

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

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

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

31、的單詞進行處理，單詞相同的則對應(yīng)數(shù)目加1，總單詞數(shù)目加1；單詞不同的總單詞加1，對應(yīng)單詞數(shù)目加1。主程序中通過文件進行讀取單詞，并將大寫的字母轉(zhuǎn)換為小寫的字母。然后進行單詞的排序，先按照單詞出現(xiàn)的頻率排序，然后按照首字母進行排序，最后對首字母相同的單詞進行排序。</p><p>　　數(shù)據(jù)流圖如圖3-1。</p><p>　　3.3【設(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)體，用于存放單詞及對應(yīng)的個數(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，對應(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、并將對應(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、詞對應(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;//將大寫字母處理為小寫字母</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，//所以去掉這一步按字母排序順序會打亂</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個單詞\n",sum);</p><p>　　//首先按照首字母進行排序</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>　　//然后首字母相同的單詞再進行排序</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單詞個數(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【測試及運行結(jié)果】</p><p><b>　　3.5【總結(jié)】</b></p><p>　　設(shè)置了全局?jǐn)?shù)組A和全局變量s用于存放單詞和單詞總數(shù)，用全局變量可以在使用對應(yīng)函數(shù)時直接進行修改。&

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

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

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

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

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

57、<p>　　數(shù)據(jù)流圖如圖4-1。</p><p>　　4.3【設(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("請輸入圖的頂點個數(shù)n:");</p><p>　　scanf("%d",&n)

59、;</p><p>　　printf("請輸入圖所對應(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){//求頂點V所連接的點的最短路徑所對應(yīng)的頂點</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(){//求已有頂點的最短路徑所對應(yīng)的頂點</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++)//初始化兩個頂點集</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)造的最小生成樹的邊及對應(yīng)權(quán)值為：\n");</p><p>　　for(;v<n;v++){</p><p><b>　　ei=mme();</b></p><p>　　if(mm[ei]==1){//判斷所找到的頂點是否

71、已經(jīng)加入頂點集</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];//計算最短路徑長度</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("最小生成樹的權(quán)值即最短路徑長度為:%d\n",min);</p><p><b>　　}</b></p><p>　　4.4【測試及運行結(jié)果】</p><p><b>　　4.5【總結(jié)】</b></p><p>　　在最初編寫程序時，沒有使用兩個算法，直到最后構(gòu)

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

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

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

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

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

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

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

82、頂點i,若包含，如果只存在這一條邊的情況下選擇i，反之選擇滿足條件的其他頂點j。</p><p>　　數(shù)據(jù)流圖如圖5-1。</p><p>　　5.3【設(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和已選點集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){//計算頂點度數(shù)為奇數(shù)的個數(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){//若邊存在且點i未被選擇時，則選擇該點</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){//若邊存在但點i已被選擇，則判斷v點是否存在其他邊存在且點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("請輸入交叉路口的數(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("請輸入%

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é)點有%d個\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【測試及運行結(jié)果】</p><p><b>　　5.5【總結(jié)

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