數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計報告

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：doc 頁數(shù)：13 大?。?20.50KB 人氣指數(shù)：12 舉報 版權(quán)申訴

已閱讀1頁，還剩12頁未讀，繼續(xù)免費閱讀

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進行舉報或認領(lǐng)

文檔簡介

1、　　計算機科學(xué)與技術(shù)系　　課程設(shè)計報告　　2012 ～2013 學(xué)年第 2 學(xué)期　　2013 年 3月　　題目：<

2、;/p>　　歐拉回路是指不令筆離開紙面，可畫過圖中每條邊僅一次，且可以回到起點的一條回路。現(xiàn)給定一個圖，問是否存在歐拉回路？　　一．問題分析和任務(wù)定義：　　題目要求判斷一個給定的圖中是否存在歐拉回路。由歐拉圖的定義，當(dāng)一個圖存在歐拉回路時，該圖稱為歐拉圖。題目問是否存在歐拉回路即等價于問給定的圖是否為歐拉圖。所以，證明給定圖是

3、歐拉圖就說明該圖存在歐拉回路，否則不存在歐拉回路。根據(jù)高等教育出版社出版屈婉玲、耿素云、張立昂主編的《離散數(shù)學(xué)》P.296定理15.1可知：無向圖G是歐拉圖當(dāng)且僅當(dāng)G是連通圖且沒有奇度頂點。要證明一個給定的圖是否為歐拉圖，證明給定的圖是連通圖且沒有奇度頂點即可。所以，解決題目中的問題就轉(zhuǎn)化為證明給定圖是否是連通圖且沒有奇度頂點。　　首先要確定一給定的圖是否為連通圖。這里我們可以通過圖的深度優(yōu)先搜

4、索遍歷確定。從任意頂點出發(fā)，如果能深度優(yōu)先遍歷到所有的頂點就說明圖中所有的頂點都是連圖的即為連通圖。　　然后再確定給定的圖是否沒有奇度頂點。我們可以以鄰接矩陣的形式存儲給定的圖，對鄰接矩陣的每行分別行進行掃描，記錄每個頂點的度數(shù)，當(dāng)每行掃描完后判斷該頂點的度數(shù)是否為奇數(shù)，存在奇度頂點直接結(jié)束掃描，說明存在奇度頂點，給定圖不是歐拉圖。即不存在歐拉回路。否則繼續(xù)掃描，當(dāng)掃描完所有的行沒有發(fā)現(xiàn)奇度頂點

5、，即說明給定圖沒有奇度頂點。　　當(dāng)上述兩個問題都確定以后根據(jù)定理，當(dāng)且僅當(dāng)給定圖為連通圖且沒有奇度頂點時給定的圖為歐拉圖。由此可確定，給定的圖是否存在歐拉回路。　　二．?dāng)?shù)據(jù)結(jié)構(gòu)的選擇與概要設(shè)計：　　數(shù)據(jù)結(jié)構(gòu)的選擇：　　圖在我們所學(xué)的數(shù)

6、據(jù)結(jié)構(gòu)與算法課程中有四種存儲方式：鄰接矩陣、鄰接表、十字鏈表和鄰接多重表。本問題比較簡單，選用鄰接矩陣或鄰接矩陣就足夠了。在本課程設(shè)計中需要判斷是否有奇度頂點和是否為連通圖，用用鄰接表和鄰接矩陣在時間繁雜度沒有什么大的差別，在空間復(fù)雜度上，因為本題是無向圖，如果如果用鄰接表，儲存一條邊要儲存兩次，存儲指針比int型的空間消耗大，在圖不是很大的情況下，鄰接矩陣的空間復(fù)雜度要小。同時選用鄰接矩陣很容易得到圖中個頂點的度數(shù)。因為頂點只要求編號

7、這一信息，所以就沒有用結(jié)構(gòu)體存儲頂點信息，圖用鄰接矩陣要用結(jié)構(gòu)體存儲。結(jié)構(gòu)體定義如下：　　typedef struct　　{　　int n;//頂點個數(shù)　　int e;//邊的條數(shù)　　int

8、vexs[MAX_VERTEX_NUM];//一維數(shù)組儲存頂點　　int edges[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//二維數(shù)組儲存邊　　}MGraph;//圖　　2.概要設(shè)計　　首先將圖轉(zhuǎn)換為鄰接矩

9、陣存儲起來，然后鄰接矩陣的每一行進行搜索得圖中到每個頂點的度數(shù)，如果有奇度頂點，輸出：不存在歐拉回路，即可結(jié)束程序。否則繼續(xù)判斷給定的圖是否為連通圖，如果是連通圖輸出：存在歐拉回路；否則輸出：不存在歐拉回路。結(jié)束程序。　　三．詳細設(shè)計和編碼：　　1.將圖轉(zhuǎn)化為鄰接矩陣存儲：　　先輸入圖中頂點個個數(shù)和邊的條數(shù)，對所

10、有可能存在的邊初始化為0，再依次輸入邊的信息，即如果頂點1,2存在相連的邊，輸入1 2 （1,2為自動給頂點分配的編碼）。將邊1,2的信息改為1。用函數(shù)MGraph *creat_MGraph();完成，返回鄰接矩陣的首地址即可。　　MGraph *creat_MGraph()//建立鄰接矩陣　　{

11、;　　int i,j,k,n,e;　　MGraph *mg=malloc(sizeof(MGraph));　　printf("請輸入頂點的個數(shù)：");　　scanf("%d",&n);　　printf(

12、"請輸入邊的條數(shù)：");　　scanf("%d",&e);　　mg->n=n;　　mg->e=e;　　getchar();</p&

13、gt;　　for(i=1;i<=n;i++)　　for(j=1;j<=n;j++)　　mg->edges[i][j]=0;//初始化鄰接矩陣表示的所有邊　　printf("請輸入邊的信息:\n");　　for(i

14、=1;i<=e;i++)　　{　　scanf("%d%d",&j,&k);　　mg->edges[j][k]=1;mg->edges[k][j]=1;//標(biāo)記存在的邊<b&g

15、t;　　}　　return mg;//返回鄰接矩陣的首地址　　}　　2.搜索有沒有奇度頂點：　　對鄰接矩陣的每一行進行搜索，用num記錄頂點的度數(shù)（每次對新的頂點記錄前都將num置為0）。為了排除頂點自身環(huán)對判斷的

16、影響，當(dāng)遇到邊的兩頂點相同，忽略不計，這樣不會對結(jié)果產(chǎn)生影響。如果搜索到奇度頂點則結(jié)束int Euleriancycle(MGraph *mg);函數(shù)，返回0，搜索完成且沒有發(fā)現(xiàn)奇度頂點則返回1.　　int Euleriancycle(MGraph *mg)//判斷是否存在歐拉回路　　{<

17、;p>　　int i,j,num;　　for(i=1;i<=mg->n;i++)//從第一個頂點開始，判斷頂點的度數(shù)　　{　　num=0;//初始化每個頂點的度數(shù)為0　　for(j=1;j<=mg->n;

18、j++)　　{　　if((mg->edges[i][j]!=0)&&(i!=j))//如果頂點i到j(luò)的邊存在度數(shù)加1　　num=num+1;　　}&l

19、t;p>　　if(num%2==1)//如果有哪個頂點的度數(shù)為奇數(shù)，直接退出循環(huán)，返回0　　return 0;　　}　　return 1;//當(dāng)所有的頂點都判斷完成還沒有退出本函數(shù)說明所有頂點度數(shù)均為偶數(shù)，返回1<b&g

20、t;　　}　　3. 判斷給定的圖是否為連通圖：　　本程序的深度優(yōu)先遍歷是一個遞歸的過程。其中visited[MAX_VERTEX_NUM]是一個輔助的全局變量，初始值均為0.表示該頂點沒有被訪問。訪問后用1表示。在深度優(yōu)先搜索時。我們需要調(diào)用dfs_trave()函數(shù)。在dfs_trave()中，針對每個沒有被訪問過的頂點調(diào)用dfs(

21、)函數(shù)，它是一個遞歸函數(shù)，完成從該頂點開始的深度優(yōu)先搜索。如果圖是一個連通圖，那么完成對visited數(shù)組的初始化后，在dfs_trave()中只需調(diào)用dfs()函數(shù)一次即可完成對圖的遍歷。當(dāng)圖不是一個連通圖時，則在dfs_trave()中需要針對每個連通分量分別調(diào)用dfs()函數(shù)。根據(jù)dfs()函數(shù)被調(diào)用的次數(shù)就可以判斷給定的圖是否為連通圖。如果dfs()函數(shù)被調(diào)用一次則給定的圖是連通圖，否則不是連通圖。<

22、;p>　　int dfs_trave(MGraph *mg)//深度優(yōu)先搜索遍歷　　{　　int i,m=0;　　for(i=1;i<=mg->n;i++)//將輔助變量全部初始化為0，表明頂點沒有被訪問過　　vi

23、sited[i]=0;　　for(i=1;i<=mg->n;i++)　　if(visited[i]==0)//對沒有訪問過的頂點，調(diào)用深度優(yōu)先搜索函數(shù)　　{　　dfs(mg,i);//深度優(yōu)先搜索&

24、lt;p>　　m=m+1;//如果是非連通圖，要調(diào)用1次以上，m用來記錄調(diào)用dfs函數(shù)的次數(shù)　　}　　return m;//返回調(diào)用dfs函數(shù)的次數(shù)　　}　　void dfs(MGraph

25、*mg,int i)//深度優(yōu)先搜索　　{　　int j;　　visited[i]=1;//訪問該頂點　　for(j=1;j<=mg->n;j++)<p&

26、gt;　　if((visited[j]==0)&&(mg->edges[i][j]==1))//當(dāng)頂點沒有被訪問過并且兩頂點存在邊　　dfs(mg,j);//對該頂點深度優(yōu)先搜索　　}　　4.根據(jù)上述2,3可知，必須為連通圖且沒有奇度頂點才是歐拉圖即存在

27、歐拉回路。　　5.流程圖如下（圖：1）：　　Y　　N　　N　　Y</p&

28、gt;　　圖：1流程圖　　四．上機調(diào)試過程：　　本次實驗中也遇到了一些小問題，通過在適當(dāng)?shù)奈恢眉右恍﹑rintf語句即可確定出現(xiàn)問題的語句大概的位置。加以分析、修改即可。　　在本次課程設(shè)計的第三組數(shù)據(jù)的測試時出現(xiàn)了不

29、存在歐拉圖的錯誤結(jié)果，仔細分析可知，在（2,2）鄰接矩陣的對角線上，所以該點的度數(shù)在計算的時候就少1度。所以，在if((mg->edges[i][j]!=0)&&(i!=j))//如果頂點i到j(luò)的邊存在度數(shù)加1 的判斷中增加了一個判斷，當(dāng)該點存在環(huán)，則在度數(shù)的計數(shù)時忽略不計，這樣不會印象該點度數(shù)奇偶性的變化。這樣就很好的解決了，存在環(huán)對判斷結(jié)果的印象的問題。　　通過本次課程

30、設(shè)計讓我更加深刻的體會到調(diào)試程序需要平心靜氣，仔細分析、研究。要有一個嚴謹?shù)膽B(tài)度，這樣才能高效率的寫出優(yōu)質(zhì)的代碼。　　五．測試結(jié)果與分析：　　測試數(shù)據(jù)的選擇：　　在測試中考慮到多種情況使用了多組數(shù)據(jù)，分別根據(jù)是否為連通圖、是否沒有奇度頂點設(shè)計了一下四組數(shù)據(jù)。第一組數(shù)據(jù)為連通圖

31、且沒有奇度頂點，第二組數(shù)據(jù)為連通圖且有奇度頂點，第三組數(shù)據(jù)為連通圖、沒有奇度頂點且有環(huán)，第四組數(shù)據(jù)為非連通圖且有奇度頂點，第五組數(shù)據(jù)為非連通圖且沒有奇度頂點。　　每組數(shù)據(jù)進行多次測試。　　測試數(shù)據(jù)1：　　3<

32、p>　　3　　1 2　　1 3　　2 3　　測試結(jié)果：

33、　　結(jié)果分析：測試數(shù)據(jù)表示一個3個頂點，3條邊的圖，頂點兩兩相連。如下:2-1所示：　　圖：2-1 測試1　　存在歐拉回路。測試結(jié)果正確。　　測試數(shù)據(jù)2：　　3</p&

34、gt;　　3　　3 2　　1 2　　2 3　　測試結(jié)果：&l

35、t;/p>　　結(jié)果分析：測試數(shù)據(jù)表示一個3個頂點，3條邊的圖，1,、2相連，2、3相連。如下圖2-2所示：　　圖：2-2 測試2　　不存在歐拉回路。測試結(jié)果正確。　　測試數(shù)據(jù):3：　　4

36、　　5　　1 2　　1 3　　2 4

37、3 4　　2 2　　測試結(jié)果： 　　結(jié)果分析：測試數(shù)據(jù)表示一個4個頂點，5條邊的圖，1、2相連，1、3相連,2、4相連,3、4相連，2、2相連。如下圖2-3所示：<b&g

38、t;　　圖：2-3 測試3　　存在歐拉回路。測試結(jié)果正確。　　測試數(shù)據(jù)4：　　5　　4<b

39、>　　1 2　　3 4 　　4 5　　3 5　　測試結(jié)果：<p&

40、gt;　　結(jié)果分析：測試數(shù)據(jù)表示一個5個頂點，4條邊的圖，1、2相連，3、4相連,4、5相連,3、5相連。如下:圖2-4所示：　　不存在歐拉回路。測試結(jié)果正確。圖：2-4 測試4　　測試數(shù)據(jù)5：　　6<p

41、>　　6　　1 2 　　1 3　　2 3　　4 5&

42、lt;p>　　4 6　　5 6　　測試結(jié)果：　　結(jié)果分析：測試數(shù)據(jù)表示一個6個頂點，6條邊的圖，1、2相連，1、3相連,2、3相連,4、5相連，4、6相連，5、6相連。如下圖2-5所示：<

43、/p>　　圖：2-5　　不存在歐拉回路。測試結(jié)果正確。　　測試結(jié)果總結(jié)：通過對多種情況設(shè)計了多組數(shù)據(jù)多次測試如上，結(jié)果都得到了真確的結(jié)論。說明程序符合題目的要求，達到了實驗的目的。　　六．用戶使用說明：<

44、/p>　　首先本程序中的所有頂點編號為1-N的整數(shù)。(0<N<1000)　　先輸入圖頂點的個數(shù)要求為一個正整數(shù)n，然后輸入圖所有邊的條數(shù)要求為正整數(shù)e，再圖邊數(shù)行整形數(shù)，每行兩個數(shù)（用空格相隔）表示一條邊所連接的兩個頂點編號。輸出結(jié)果即為題目的解。　　七．參考文獻：</p

45、>　　[1] 王昆侖，李紅. 數(shù)據(jù)結(jié)構(gòu)與算法. 北京：高等教育出版社，2007年6月第1版　　[2] 屈婉玲，耿素云，張立昂. 離散數(shù)學(xué). 北京：高等教育出版社，2008年3月第1版　　八．附錄：　　#include<stdio.h>&

46、lt;/p>　　#include<stdlib.h>　　#include<malloc.h>　　#define MAX_VERTEX_NUM 1000//頂點的最大個數(shù)　　typedef struct

47、　{　　int n;//頂點個數(shù)　　int e;//邊的條數(shù)　　int vexs[MAX_VERTEX_NUM];//一維數(shù)組儲存頂點　　int edges[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//二維數(shù)組儲存邊</p

48、>　　}MGraph;//圖　　int visited[MAX_VERTEX_NUM];//全局變量。在對頂點進行深度優(yōu)先搜索遍歷時的輔助變量數(shù)組　　int Euleriancycle(MGraph *mg);//判斷頂點的度數(shù)是否全為偶數(shù)，有奇數(shù)時輸出0，全為偶數(shù)時輸出1　　MGra

49、ph *creat_MGraph();//將圖轉(zhuǎn)化為鄰接矩陣儲存起來，返回鄰接矩陣的首地址　　int dfs_trave(MGraph *mg);//深度優(yōu)先搜索遍歷　　void dfs(MGraph *mg,int i);//深度優(yōu)先搜索　　void main()&l

50、t;b>　　{　　int num,m;//num用來接收頂點度數(shù)判斷的結(jié)果，m用來接收圖是否為連通圖的結(jié)果　　MGraph *mg;　　mg=creat_MGraph();//建立鄰接矩陣　　num=Euleriancycle(mg);//判斷頂

51、點的度數(shù)是否全為偶數(shù)。全為偶數(shù)時num=1；否則num=0　　if(num!=1)　　{　　printf("不存在歐拉圖！\n");　　getchar();

52、;　　exit(0);　　}　　m=dfs_trave(mg);//判斷圖是否為連通圖　　if(m!=1)　　printf("不存在歐拉圖！\n");<

53、;/p>　　else　　printf("存在歐拉圖！\n");　　getch();　　}　　MGraph *c

54、reat_MGraph()//建立鄰接矩陣　　{　　int i,j,k,n,e;　　MGraph *mg=malloc(sizeof(MGraph));　　printf("請輸入頂點的個數(shù)：");

55、;　　scanf("%d",&n);　　printf("請輸入邊的條數(shù)：");　　scanf("%d",&e);　　mg->n=n;

56、;　　mg->e=e;　　getchar();　　for(i=1;i<=n;i++)　　for(j=1;j<=n;j++)　　mg->edges[i][j]=0;//初始化鄰接矩陣表示的所有邊

57、;　　printf("請輸入邊的信息:\n");　　for(i=1;i<=e;i++)　　{　　scanf("%d%d",&j,&k);　　mg-&g

58、t;edges[j][k]=1;mg->edges[k][j]=1;//標(biāo)記存在的邊　　}　　return mg;//返回鄰接矩陣的首地址　　}　　int Euleriancycle(MGr

59、aph *mg)//判斷是否存在歐拉回路　　{　　int i,j,num;　　for(i=1;i<=mg->n;i++)//從第一個頂點開始，判斷頂點的度數(shù)　　{

60、　　num=0;//初始化每個頂點的度數(shù)為0　　for(j=1;j<=mg->n;j++)　　{　　If((mg->edges[i][j]!=0)&&(i!=j))//如果頂點i到j(luò)的邊存在度數(shù)加1

61、　　num=num+1;　　}　　if(num%2==1)//如果有哪個頂點的度數(shù)為奇數(shù)，直接退出循環(huán)，返回0　　return 0;　　}<p&g

62、t;　　return 1;//當(dāng)所有的頂點都判斷完成還沒有退出本函數(shù)說明所有頂點度數(shù)均為偶數(shù)，返回1　　}　　int dfs_trave(MGraph *mg)//深度優(yōu)先搜索遍歷　　{　　in

63、t i,m=0;　　for(i=1;i<=mg->n;i++)//將輔助變量全部初始化為0，表明頂點沒有被訪問過　　visited[i]=0;　　for(i=1;i<=mg->n;i++)　　if(visited[i]==0)//對沒有訪問過的頂點

64、，調(diào)用深度優(yōu)先搜索函數(shù)　　{　　dfs(mg,i);//深度優(yōu)先搜索　　m=m+1;//如果是非連通圖，要調(diào)用1次以上，m用來記錄調(diào)用dfs函數(shù)的次數(shù)　　}

65、;　　return m;//返回調(diào)用dfs函數(shù)的次數(shù)　　}　　void dfs(MGraph *mg,int i)//深度優(yōu)先搜索　　{　　int j;<

66、;/p>　　visited[i]=1;//訪問該頂點　　for(j=1;j<=mg->n;j++)　　if((visited[j]==0)&&(mg->edges[i][j]==1))//當(dāng)頂點沒有被訪問過并且兩頂點存在邊　　dfs(mg,j);//對

眾賞文庫> 全部分類> 畢業(yè)設(shè)計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計報告

文檔簡介

溫馨提示

最新文檔

評論

數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計報告

文檔簡介

溫馨提示

最新文檔

評論

免費下載