太原理工大學(xué)軟件學(xué)院課程設(shè)計(jì)-相鄰數(shù)對(duì)、ISBN識(shí)別碼文本文件單詞統(tǒng)計(jì)、構(gòu)造最小生成樹送貨、學(xué)生信息管理系統(tǒng)

課程設(shè)計(jì) 課程名稱： 程序設(shè)計(jì)課程設(shè)計(jì) 設(shè)計(jì)名稱： 相鄰數(shù)對(duì)、ISBN識(shí)別碼 文本文件單詞統(tǒng)計(jì)、構(gòu)造最小生成樹 送貨、學(xué)生信息管理系統(tǒng) 專業(yè)班級(jí)： 學(xué)號(hào)： 學(xué)生姓名： 指導(dǎo)教師： 2017年06月21日太原理工大學(xué)課程設(shè)計(jì)任務(wù)書學(xué)生姓名專業(yè)班級(jí) 課程名稱程序設(shè)計(jì)課程設(shè)計(jì)（Programming Curriculum Design）設(shè)計(jì)名稱相鄰數(shù)對(duì),ISBN識(shí)別碼,文本文件單詞統(tǒng)計(jì)等設(shè)計(jì)周數(shù)2設(shè)計(jì)任務(wù)主要設(shè)計(jì)參數(shù)1.基本要求掌握C或C+語(yǔ)言、結(jié)構(gòu)化程序和面向?qū)ο蟪绦蛟O(shè)計(jì)方法、數(shù)據(jù)結(jié)構(gòu)和離散數(shù)學(xué)理論知識(shí)，熟悉C或C+程序的開(kāi)發(fā)環(huán)境及調(diào)試過(guò)程，鞏固和加深對(duì)理論課中知識(shí)的理解，提高學(xué)生對(duì)所學(xué)知識(shí)的綜合運(yùn)用能力。2.培養(yǎng)學(xué)生以下技能培養(yǎng)學(xué)生查閱參考資料、手冊(cè)的自學(xué)能力，通過(guò)獨(dú)立思考深入鉆研問(wèn)題，學(xué)會(huì)自己分析、解決問(wèn)題。通過(guò)對(duì)所選題目分析，找出解決方法，設(shè)計(jì)算法，編制程序與調(diào)試程序。能熟練調(diào)試程序，在教師的指導(dǎo)下，完成課題任務(wù)。按課程設(shè)計(jì)報(bào)告的要求撰寫設(shè)計(jì)報(bào)告。設(shè)計(jì)內(nèi)容設(shè)計(jì)要求1.設(shè)計(jì)內(nèi)容相鄰數(shù)對(duì)；ISBN識(shí)別碼；文本文件單詞統(tǒng)計(jì)；構(gòu)造可以使n個(gè)城市連接的最小生成樹；送貨；學(xué)生信息管理系統(tǒng)2.設(shè)計(jì)要求至少完成上述設(shè)計(jì)內(nèi)容中的4個(gè)設(shè)計(jì)題目；對(duì)每個(gè)題目要給出設(shè)計(jì)方案、功能模塊劃分、算法思想；選擇使用的數(shù)據(jù)結(jié)構(gòu)；給出題目的程序?qū)崿F(xiàn)；按要求撰寫設(shè)計(jì)報(bào)告。主要參考資 料1.程序設(shè)計(jì)課程設(shè)計(jì)指導(dǎo)書；2.程序設(shè)計(jì)技術(shù)、數(shù)據(jù)結(jié)構(gòu)等課程教材；3. 其他自選的相關(guān)資料。學(xué)生提交歸檔文件 課程設(shè)計(jì)報(bào)告封面應(yīng)給出專業(yè)、班級(jí)、姓名、學(xué)號(hào)、指導(dǎo)教師和完成日期。每個(gè)設(shè)計(jì)題目的內(nèi)容包括以下幾項(xiàng)：設(shè)計(jì)題目、問(wèn)題描述、問(wèn)題分析、功能實(shí)現(xiàn)、測(cè)試實(shí)例及運(yùn)行結(jié)果、源程序清單。注：1.課程設(shè)計(jì)完成后，學(xué)生提交的歸檔文件應(yīng)按照：封面任務(wù)書說(shuō)明書圖紙的順序進(jìn)行裝訂上交（大張圖紙不必裝訂）。2.可根據(jù)實(shí)際內(nèi)容需要續(xù)表，但應(yīng)保持原格式不變。指導(dǎo)教師簽名： 日期：2017.6.3目 錄1.相鄰數(shù)對(duì)22.ISBN識(shí)別碼43.文本文件單詞統(tǒng)計(jì)74.構(gòu)造可以使n個(gè)城市連接的最小生成樹135.送貨186.學(xué)生信息管理系統(tǒng)23I題目一 相鄰數(shù)對(duì)1.1【問(wèn)題描述】給定 n 個(gè)不同的整數(shù)，問(wèn)這些數(shù)中有多少對(duì)整數(shù)，它們的值正好相差 1。輸入格式輸入的第一行包含一個(gè)整數(shù)n，表示給定整數(shù)的個(gè)數(shù)。第二行包含所給定的n個(gè)整數(shù)。輸出格式輸出一個(gè)整數(shù)，表示值正好相差1的數(shù)對(duì)的個(gè)數(shù)。1.2【設(shè)計(jì)及分析】先設(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ù)。數(shù)據(jù)流圖如圖1-1。圖1-11.3【設(shè)計(jì)功能的實(shí)現(xiàn)】#includeint a1005;void inita(int *a)/初始化數(shù)組int n=0;for(;n1004;n+)an=0;void main()int n,i,m,count=0; inita(a); printf(請(qǐng)輸入整數(shù)的個(gè)數(shù)：n);scanf(%d,&n); printf(請(qǐng)輸入整數(shù)：n);for(i=0;in;i+)/修改數(shù)組內(nèi)容scanf(%d,&m);am=1;printf(輸入的整數(shù)中的相鄰數(shù)對(duì)如下：n);for(i=0;i1005;i+)/相鄰數(shù)對(duì)的篩選if(ai=1)&(ai+1=1)printf(%d,%d),i,i+1);count+=1; printf(n輸入的整數(shù)中共有%d個(gè)相鄰數(shù)對(duì)n,count);1.4【測(cè)試及運(yùn)行結(jié)果】1.5【總結(jié)】1. 該題目比較簡(jiǎn)單，在經(jīng)過(guò)老師的指導(dǎo)，有了大概的設(shè)計(jì)思想并進(jìn)行代碼的編寫。2. 在寫代碼的過(guò)程中，用了全局?jǐn)?shù)組a，在初始化數(shù)組后對(duì)其進(jìn)行調(diào)整，但是在編寫過(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)了邏輯錯(cuò)誤，然后增加了一個(gè)變量進(jìn)行修改。3. 該程序比較簡(jiǎn)單，但是覺(jué)得數(shù)組大部分的空間沒(méi)有利用，有一定的資源浪費(fèi)，在運(yùn)算速度上也是比較慢的。題目二 ISBN識(shí)別碼2.1【問(wèn)題描述】每一本正式出版的圖書都有一個(gè) ISBN 號(hào)碼與之對(duì)應(yīng)，ISBN 碼包括 9 位數(shù)字、1 位識(shí)別碼和 3 位分隔符，其規(guī)定格式如“x-xxx-xxxxx-x”，其中符號(hào)“-”是分隔符（鍵盤上的減號(hào)），最后一位是識(shí)別碼，例如 0-670-82162-4 就是一個(gè)標(biāo)準(zhǔn)的 ISBN 碼。ISBN 碼的首位數(shù)字表示書籍的出版語(yǔ)言，例如 0 代表英語(yǔ)；第一個(gè)分隔符“-”之后的三位數(shù)字代表出版社，例如 670 代表維京出版社；第二個(gè)分隔之后的五位數(shù)字代表該書在出版社的編號(hào)；最后一位為識(shí)別碼。識(shí)別碼的計(jì)算方法如下：首位數(shù)字乘以 1 加上次位數(shù)字乘以 2以此類推，用所得的結(jié)果 mod 11，所得的余數(shù)即為識(shí)別碼，如果余數(shù)為 10，則識(shí)別碼為大寫字母 X。例如 ISBN 號(hào)碼 0-670-82162-4 中的識(shí)別碼 4 是這樣得到的：對(duì) 067082162 這 9 個(gè)數(shù)字，從左至右，分別乘以 1，2，9，再求和，即01+62+29=158，然后取 158 mod 11 的結(jié)果 4 作為識(shí)別碼。編寫程序判斷輸入的 ISBN 號(hào)碼中識(shí)別碼是否正確，如果正確，則僅輸出“Right”；如果錯(cuò)誤，則輸出是正確的 ISBN 號(hào)碼。輸入格式輸入只有一行，是一個(gè)字符序列，表示一本書的 ISBN 號(hào)碼（保證輸入符合 ISBN 號(hào)碼的格式要求）。輸出格式輸出一行，假如輸入的 ISBN 號(hào)碼的識(shí)別碼正確，那么輸出“Right”，否則，按照規(guī)定的格式，輸出正確的 ISBN 號(hào)碼（包括分隔符“-”）。2.2【設(shè)計(jì)及分析】用一個(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。數(shù)據(jù)流圖如圖2-1。圖2-1 2.3【設(shè)計(jì)功能的實(shí)現(xiàn)】#include#include#includechar a100,a1100;int judge(char *a)/計(jì)算正確的ISBN碼int i=0,l,s=0,m;for(;i9;i+)ai-=48;l=ai*(i+1);s=s+l; m=s%11; return m;void main()int i,m,j=0,l;printf(請(qǐng)輸入ISBN碼：);gets(a);l=strlen(a);for(i=0;ai!=0;i+)/將-刪除掉便于計(jì)算if(ai!=-)a1j+=ai;elsea1j=ai; m=judge(a1);/計(jì)算ISBN碼/printf(%d,m);if(m=(a19-48)/判斷ISBN碼是否正確 printf(RIGHT);/正確輸出RIGHTelseal-1=(m+48);/錯(cuò)誤則修改ISBN碼并輸出正確的ISBN碼 printf(%s,a); 2.4【測(cè)試及運(yùn)行結(jié)果】 2.5【總結(jié)】1、 在編寫程序框架時(shí)，我準(zhǔn)備先實(shí)現(xiàn)ISBN碼的正確計(jì)算與修改，所以先使用的是整數(shù)進(jìn)行計(jì)算，在整數(shù)計(jì)算成功后修改為題目中所要求的字符串輸入。2、 在對(duì)字符串進(jìn)行處理時(shí)，要考慮字符-在字符串中的位置，最初打算用三個(gè)數(shù)組來(lái)控制計(jì)算，但在計(jì)算過(guò)程中出現(xiàn)了錯(cuò)誤。然后采取將字符串中的-刪除并存儲(chǔ)于新的數(shù)組a1中，原始數(shù)組不變。3、 在初始框架中，計(jì)算是針對(duì)整數(shù)進(jìn)行的，在對(duì)字符串進(jìn)行處理時(shí)，要考慮其與整數(shù)的關(guān)系，才能得到正確的計(jì)算值。在修改數(shù)組a時(shí)也需要考慮計(jì)算值之間的轉(zhuǎn)換。題目三 文本文件單詞統(tǒng)計(jì)3.1【問(wèn)題描述】要統(tǒng)計(jì)英文文本文件中出現(xiàn)了哪些單詞，就要從文件中讀取字符，讀取出來(lái)的連續(xù)英文字符認(rèn)為是一個(gè)單詞，遇空格或標(biāo)點(diǎn)符號(hào)單詞結(jié)束。3.2【設(shè)計(jì)及分析】先構(gòu)建一個(gè)結(jié)構(gòu)體用于存放單詞及對(duì)應(yīng)的數(shù)目，然后用一個(gè)函數(shù)來(lái)對(duì)所獲取的單詞進(jìn)行處理，單詞相同的則對(duì)應(yīng)數(shù)目加1，總單詞數(shù)目加1；單詞不同的總單詞加1，對(duì)應(yīng)單詞數(shù)目加1。主程序中通過(guò)文件進(jìn)行讀取單詞，并將大寫的字母轉(zhuǎn)換為小寫的字母。然后進(jìn)行單詞的排序，先按照單詞出現(xiàn)的頻率排序，然后按照首字母進(jìn)行排序，最后對(duì)首字母相同的單詞進(jìn)行排序。數(shù)據(jù)流圖如圖3-1。圖3-13.3【設(shè)計(jì)功能的實(shí)現(xiàn)】#include#include#include struct word/結(jié)構(gòu)體，用于存放單詞及對(duì)應(yīng)的個(gè)數(shù)char str30;int num;A1000;int sum;/記錄總的單詞數(shù)void chuli(char s)/處理獲取的單詞int i,j;int flag=0;for(i=0;i=sum;i+)if(strcmp(Ai.str,s)=0)/相同的單詞，單詞總數(shù)加1，對(duì)應(yīng)單詞數(shù)量加1，標(biāo)志flag變成1Ai.num+;flag=1;sum+;if(flag=0)/單詞不同，則加入單詞，并將對(duì)應(yīng)的單詞數(shù)和單詞總數(shù)量加1for(j=0;j30;j+)Asum.strj=sj;Asum.num+;sum+;int main()char ch,s30;int i,flag=0,l;int ii,jj;struct word a;FILE *fp;fp=fopen(tyut.txt,r);if(fp=NULL)printf(文件為空!);sum=0;ch=NULL;for(i=0;i1000;i+)Ai.num=0;/將所有單詞對(duì)應(yīng)的數(shù)目設(shè)置為0while(ch!=-1)for(i=0;i=65&ch=97&ch=65&ch=65&ch=97&ch=122)continue;else break;chuli(s);/處理所獲取的單詞s/將單詞按照出現(xiàn)的頻率排序，便于后面的按字母順序排序，由于之前初始化A的sum=0，/所以去掉這一步按字母排序順序會(huì)打亂for(ii=0;iisum;ii+)for(jj=ii+1;jjsum;jj+)if(Aii.numAjj.str0)a=Ajj;Ajj=Aii;Aii=a;/然后首字母相同的單詞再進(jìn)行排序for(ii=0;Aii.num!=0;ii+)for(jj=ii+1;Ajj.num!=0;jj+)l=0;while(Aii.strl=Ajj.strl)l+;if(Aii.strlAjj.strl)a=Ajj;Ajj=Aii; Aii=a;for(i=0;Ai.num !=0;i+)printf(%s單詞個(gè)數(shù)有：%dn,Ai.str,Ai.num);printf(nn);return 0;3.4【測(cè)試及運(yùn)行結(jié)果】3.5【總結(jié)】1、 設(shè)置了全局?jǐn)?shù)組A和全局變量s用于存放單詞和單詞總數(shù)，用全局變量可以在使用對(duì)應(yīng)函數(shù)時(shí)直接進(jìn)行修改。2、 在獲取單詞時(shí)，如果不進(jìn)行大小寫轉(zhuǎn)換的話，相同的單詞會(huì)因?yàn)榇笮懙牟煌霈F(xiàn)兩次甚至多次，與題意不符，所以在獲取單詞的同時(shí)可以將大小寫進(jìn)行統(tǒng)一，便于最后統(tǒng)計(jì)的正確性。在本次實(shí)驗(yàn)我選擇的是將大小寫字母統(tǒng)一為小寫字母，然后進(jìn)行統(tǒng)計(jì)排序。3、 在對(duì)所獲取的單詞進(jìn)行排序時(shí)，先按單詞出現(xiàn)的頻率排序，將數(shù)組A中sum值為0的一律排到最后，便于進(jìn)行下一步統(tǒng)計(jì)。第二步按照首字母進(jìn)行排序，大致將單詞進(jìn)行了分段。第三步按照首字母相同的單詞組進(jìn)行排序，最終完成題目的要求。在排序的部分中，感覺(jué)程序過(guò)于繁瑣，可以進(jìn)行一些優(yōu)化。題目四 構(gòu)造可以使n個(gè)城市連接的最小生成樹4.1【問(wèn)題描述】給定一個(gè)地區(qū)的n個(gè)城市間的距離網(wǎng)，用Prim算法或Kruskal算法建立最小生成樹，并計(jì)算得到的最小生成樹的代價(jià)?；疽螅?、 城市間的距離網(wǎng)采用鄰接矩陣表示，鄰接矩陣的存儲(chǔ)結(jié)構(gòu)定義采用課本中給出的定義，若兩個(gè)城市之間不存在道路，則將相應(yīng)邊的權(quán)值設(shè)為自己定義的無(wú)窮大值。2、 要求在屏幕上顯示得到的最小生成樹中包括了哪些城市間的道路，并顯示得到的最小生成樹的代價(jià)。3、 表示城市間距離網(wǎng)的鄰接矩陣（要求至少6個(gè)城市，10條邊）。4.2【設(shè)計(jì)及分析】在考慮使用Prim 算法還是Kruskal 算法時(shí)，我選擇使用prim算法。雖然kruskal算法算法思想簡(jiǎn)單，但是在算法實(shí)現(xiàn)上需要判斷新加入的邊是否會(huì)構(gòu)成回路，而prim算法不需要進(jìn)行判斷，構(gòu)成的就是最小生成樹。prim算法中需要判斷所選擇的點(diǎn)是否已在點(diǎn)集中，若存在，則選擇次小邊所對(duì)應(yīng)的點(diǎn)。在實(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)行最小生成樹的構(gòu)造。數(shù)據(jù)流圖如圖4-1。圖4-1PRIM算法4.3【設(shè)計(jì)功能的實(shí)現(xiàn)】#include #define m1 999;int mm20,l;int nodelist2020,n,d20,p20;void readgraph()/初始化鄰接矩陣int i,j;printf(請(qǐng)輸入圖的頂點(diǎn)個(gè)數(shù)n:);scanf(%d,&n);printf(請(qǐng)輸入圖所對(duì)應(yīng)的鄰接矩陣:n);for(i=1;i=n;i+)for(j=1;j=n;j+)scanf(%d,&nodelistij);printf(n);printf(已成功建立鄰接矩陣n);for(i=1;i=n;i+)for(j=1;j=n;j+)printf(%5d,nodelistij);printf(n); int mine(int v)/求頂點(diǎn)V所連接的點(diǎn)的最短路徑所對(duì)應(yīng)的頂點(diǎn)int min1,i,ii;min1=nodelistv1;ii=1; for(i=1;i=n;i+)if(nodelistvimin1) min1=nodelistvi;ii=i; else continue;return ii;int mme()/求已有頂點(diǎn)的最短路徑所對(duì)應(yīng)的頂點(diǎn)int ei,ej,i; ei=mine(1);l=1;for(i=2;i=nodelistiej)ei=ej;l=i;return ei;void main()int min,m20,v,i,ei,j;char ding7=A,B,C,D,E,F,G;min=0;readgraph();v=1;for(i=0;i=n;i+)/初始化兩個(gè)頂點(diǎn)集mi=1;mmi=0;m1=0;mm1=1;printf(所構(gòu)造的最小生成樹的邊及對(duì)應(yīng)權(quán)值為：n);for(;vn;v+)ei=mme();if(mmei=1)/判斷所找到的頂點(diǎn)是否已經(jīng)加入頂點(diǎn)集nodelistlei=1000;nodelisteil=1000;v-=1;else mmei=1;mei=0; printf(%c到%c權(quán)值為%d,dingl-1,dingei-1,nodelistlei);min+=nodelistlei;/計(jì)算最短路徑長(zhǎng)度nodelistlei=1000;nodelisteil=1000;printf(n);printf(最小生成樹的權(quán)值即最短路徑長(zhǎng)度為:%dn,min);4.4【測(cè)試及運(yùn)行結(jié)果】4.5【總結(jié)】1、 在最初編寫程序時(shí)，沒(méi)有使用兩個(gè)算法，直到最后構(gòu)建生成樹需要判斷是否構(gòu)成回路時(shí)才發(fā)現(xiàn)沒(méi)有使用算法思想。2、 在編寫算法的過(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)度。3、 在初始化鄰接矩陣時(shí)需要自己手動(dòng)輸入，當(dāng)矩陣比較大時(shí)，輸入矩陣比較麻煩而且可能出現(xiàn)出入錯(cuò)誤的情況，這一點(diǎn)需要改進(jìn)，初步的想法是可以用文件的讀取方式進(jìn)行初始化。題目五 送貨5.1【問(wèn)題描述】為了增加公司收入，F(xiàn)公司新開(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)，街道不會(huì)在其他位置與其他街道相交。每個(gè)交叉路口都至少連接著一條街道，有的交叉路口可能只連接著一條或兩條街道。基本需求：小明希望設(shè)計(jì)一個(gè)方案，從編號(hào)為1的交叉路口出發(fā)，每次必須沿街道去往街道另一端的路口，再?gòu)男碌穆房诔霭l(fā)去往下一個(gè)路口，直到所有的街道都經(jīng)過(guò)了正好一次。輸入數(shù)據(jù)格式：輸入的第一行包含兩個(gè)整數(shù)n,m(1n10,n-1m20)，表示交叉路口的數(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è)路口之間最多有一條街道。輸出輸出格式：如果小明可以經(jīng)過(guò)每條街道正好一次，則輸出一行包含m+1個(gè)整數(shù)p1,p2,p3,.,pm+1，表示小明經(jīng)過(guò)的路口的順序，相鄰兩個(gè)整數(shù)之間用一個(gè)空格分隔。如果有多種方案滿足條件，則輸出字典序最小的一種方案，即首先保證p1最小，p1最小的前提下再保證p2最小，依此類推。如果不存在方案使得小明經(jīng)過(guò)每條街道正好一次，則輸出一個(gè)整數(shù)-1。5.2【設(shè)計(jì)及分析】經(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，若不包含則選出頂點(diǎn)i,若包含，如果只存在這一條邊的情況下選擇i，反之選擇滿足條件的其他頂點(diǎn)j。數(shù)據(jù)流圖如圖5-1。圖5-15.3【設(shè)計(jì)功能的實(shí)現(xiàn)】#include int a100100,b100;void chushihua(int l)/初始化鄰接矩陣a和已選點(diǎn)集bint i,j;for(i=1;i=100;i+)for(j=1;j=100;j+)aij=0;for(i=1;i=100;i+)bi=0;int shezhi(int m)/設(shè)置鄰接矩陣int a1,b1,i;for(i=1;i=m;i+)scanf(%d,%d,&a1,&b1);aa1b1=1;ab1a1=1;return 0;int odd(int n)/計(jì)算頂點(diǎn)度數(shù)為奇數(shù)的個(gè)數(shù)int l=0,i,j,m,s;for(i=1;i=n;i+)m=0;s=0;for(j=1;j=n;j+)if (aij=1)m+;s=m%2;if(s=1)l+;return l;int xuanze(int v,int n)/選擇路徑int i,j;for(i=1;i=n;i+)if(avi=1)&bi!=1)/若邊存在且點(diǎn)i未被選擇時(shí)，則選擇該點(diǎn)avi=0;a