歐拉回路-數據結構與算法課程設計報告

合肥學院計算機科學與技術系課程設計報告2012～2013學年第2學期課程數據結構與算法設計課程設計課程設計名稱歐拉回路學生姓名學號專業(yè)班級計算機科學與技術11級3班指導教師2013年3月題目：歐拉回路是指不令筆離開紙面，可畫過圖中每條邊僅一次，且可以回到起點的一條回路?，F給定一個圖，問是否存在歐拉回路？一．問題分析和任務定義：題目要求判斷一個給定的圖中是否存在歐拉回路。由歐拉圖的定義，當一個圖存在歐拉回路時，該圖稱為歐拉圖。題目問是否存在歐拉回路即等價于問給定的圖是否為歐拉圖。所以，證明給定圖是歐拉圖就說明該圖存在歐拉回路，否則不存在歐拉回路。根據高等教育出版社出版屈婉玲、耿素云、張立昂主編的《離散數學》P.296定理15.1可知：無向圖G是歐拉圖當且僅當G是連通圖且沒有奇度頂點。要證明一個給定的圖是否為歐拉圖，證明給定的圖是連通圖且沒有奇度頂點即可。所以，解決題目中的問題就轉化為證明給定圖是否是連通圖且沒有奇度頂點。首先要確定一給定的圖是否為連通圖。這里我們可以通過圖的深度優(yōu)先搜索遍歷確定。從任意頂點出發(fā)，如果能深度優(yōu)先遍歷到所有的頂點就說明圖中所有的頂點都是連圖的即為連通圖。然后再確定給定的圖是否沒有奇度頂點。我們可以以鄰接矩陣的形式存儲給定的圖，對鄰接矩陣的每行分別行進行掃描，記錄每個頂點的度數，當每行掃描完后判斷該頂點的度數是否為奇數，存在奇度頂點直接結束掃描，說明存在奇度頂點，給定圖不是歐拉圖。即不存在歐拉回路。否則繼續(xù)掃描，當掃描完所有的行沒有發(fā)現奇度頂點，即說明給定圖沒有奇度頂點。當上述兩個問題都確定以后根據定理，當且僅當給定圖為連通圖且沒有奇度頂點時給定的圖為歐拉圖。由此可確定，給定的圖是否存在歐拉回路。二．數據結構的選擇與概要設計：數據結構的選擇：圖在我們所學的數據結構與算法課程中有四種存儲方式：鄰接矩陣、鄰接表、十字鏈表和鄰接多重表。本問題比較簡單，選用鄰接矩陣或鄰接矩陣就足夠了。在本課程設計中需要判斷是否有奇度頂點和是否為連通圖，用用鄰接表和鄰接矩陣在時間繁雜度沒有什么大的差別，在空間復雜度上，因為本題是無向圖，如果如果用鄰接表，儲存一條邊要儲存兩次，存儲指針比int型的空間消耗大，在圖不是很大的情況下，鄰接矩陣的空間復雜度要小。同時選用鄰接矩陣很容易得到圖中個頂點的度數。因為頂點只要求編號這一信息，所以就沒有用結構體存儲頂點信息，圖用鄰接矩陣要用結構體存儲。結構體定義如下：typedefstruct{ intn;//頂點個數 inte;//邊的條數 intvexs[MAX_VERTEX_NUM];//一維數組儲存頂點 intedges[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//二維數組儲存邊}MGraph;//圖2.概要設計首先將圖轉換為鄰接矩陣存儲起來，然后鄰接矩陣的每一行進行搜索得圖中到每個頂點的度數，如果有奇度頂點，輸出：不存在歐拉回路，即可結束程序。否則繼續(xù)判斷給定的圖是否為連通圖，如果是連通圖輸出：存在歐拉回路；否則輸出：不存在歐拉回路。結束程序。三．詳細設計和編碼：1.將圖轉化為鄰接矩陣存儲：先輸入圖中頂點個個數和邊的條數，對所有可能存在的邊初始化為0，再依次輸入邊的信息，即如果頂點1,2存在相連的邊，輸入12（1,2為自動給頂點分配的編碼）。將邊1,2的信息改為1。用函數MGraph*creat_MGraph();完成，返回鄰接矩陣的首地址即可。MGraph*creat_MGraph()//建立鄰接矩陣{ inti,j,k,n,e; MGraph*mg=malloc(sizeof(MGraph)); printf("請輸入頂點的個數："); scanf("%d",&n); printf("請輸入邊的條數："); scanf("%d",&e); mg->n=n; mg->e=e; getchar(); for(i=1;i<=n;i++) for(j=1;j<=n;j++) mg->edges[i][j]=0;//初始化鄰接矩陣表示的所有邊 printf("請輸入邊的信息:\n"); for(i=1;i<=e;i++) { scanf("%d%d",&j,&k); mg->edges[j][k]=1;mg->edges[k][j]=1;//標記存在的邊 } returnmg;//返回鄰接矩陣的首地址}2.搜索有沒有奇度頂點：對鄰接矩陣的每一行進行搜索，用num記錄頂點的度數（每次對新的頂點記錄前都將num置為0）。為了排除頂點自身環(huán)對判斷的影響，當遇到邊的兩頂點相同，忽略不計，這樣不會對結果產生影響。如果搜索到奇度頂點則結束intEuleriancycle(MGraph*mg);函數，返回0，搜索完成且沒有發(fā)現奇度頂點則返回1.intEuleriancycle(MGraph*mg)//判斷是否存在歐拉回路{ inti,j,num; for(i=1;i<=mg->n;i++)//從第一個頂點開始，判斷頂點的度數 { num=0;//初始化每個頂點的度數為0 for(j=1;j<=mg->n;j++) { if((mg->edges[i][j]!=0)&&(i!=j))//如果頂點i到j的邊存在度數加1 num=num+1; } if(num%2==1)//如果有哪個頂點的度數為奇數，直接退出循環(huán)，返回0 return0; } return1;//當所有的頂點都判斷完成還沒有退出本函數說明所有頂點度數均為偶數，返回1}3.判斷給定的圖是否為連通圖：本程序的深度優(yōu)先遍歷是一個遞歸的過程。其中visited[MAX_VERTEX_NUM]是一個輔助的全局變量，初始值均為0.表示該頂點沒有被訪問。訪問后用1表示。在深度優(yōu)先搜索時。我們需要調用dfs_trave()函數。在dfs_trave()中，針對每個沒有被訪問過的頂點調用dfs()函數，它是一個遞歸函數，完成從該頂點開始的深度優(yōu)先搜索。如果圖是一個連通圖，那么完成對visited數組的初始化后，在dfs_trave()中只需調用dfs()函數一次即可完成對圖的遍歷。當圖不是一個連通圖時，則在dfs_trave()中需要針對每個連通分量分別調用dfs()函數。根據dfs()函數被調用的次數就可以判斷給定的圖是否為連通圖。如果dfs()函數被調用一次則給定的圖是連通圖，否則不是連通圖。intdfs_trave(MGraph*mg)//深度優(yōu)先搜索遍歷{ inti,m=0; for(i=1;i<=mg->n;i++)//將輔助變量全部初始化為0，表明頂點沒有被訪問過 visited[i]=0; for(i=1;i<=mg->n;i++) if(visited[i]==0)//對沒有訪問過的頂點，調用深度優(yōu)先搜索函數 { dfs(mg,i);//深度優(yōu)先搜索 m=m+1;//如果是非連通圖，要調用1次以上，m用來記錄調用dfs函數的次數 } returnm;//返回調用dfs函數的次數}voiddfs(MGraph*mg,inti)//深度優(yōu)先搜索{ intj; visited[i]=1;//訪問該頂點 for(j=1;j<=mg->n;j++) if((visited[j]==0)&&(mg->edges[i][j]==1))//當頂點沒有被訪問過并且兩頂點存在邊 dfs(mg,j);//對該頂點深度優(yōu)先搜索}4.根據上述2,3可知，必須為連通圖且沒有奇度頂點才是歐拉圖即存在歐拉回路。5.流程圖如下（圖：1）：開始開始頂點數、邊數、邊信息頂點數、邊數、邊信息將圖轉化為鄰接矩陣將圖轉化為鄰接矩陣搜索圖中所有頂點的度數搜索圖中所有頂點的度數判斷是否存在奇度頂點判斷是否存在奇度頂點 Y N對圖進行深度優(yōu)先搜索遍歷對圖進行深度優(yōu)先搜索遍歷對圖進行深度優(yōu)先搜索遍歷對圖進行深度優(yōu)先搜索遍歷判斷圖是否為連通圖 判斷圖是否為連通圖 N Y不存在歐拉回路存在歐拉回路不存在歐拉回路存在歐拉回路結束結束圖：1流程圖四．上機調試過程：本次實驗中也遇到了一些小問題，通過在適當的位置加一些printf語句即可確定出現問題的語句大概的位置。加以分析、修改即可。在本次課程設計的第三組數據的測試時出現了不存在歐拉圖的錯誤結果，仔細分析可知，在（2,2）鄰接矩陣的對角線上，所以該點的度數在計算的時候就少1度。所以，在if((mg->edges[i][j]!=0)&&(i!=j))//如果頂點i到j的邊存在度數加1的判斷中增加了一個判斷，當該點存在環(huán)，則在度數的計數時忽略不計，這樣不會印象該點度數奇偶性的變化。這樣就很好的解決了，存在環(huán)對判斷結果的印象的問題。通過本次課程設計讓我更加深刻的體會到調試程序需要平心靜氣，仔細分析、研究。要有一個嚴謹的態(tài)度，這樣才能高效率的寫出優(yōu)質的代碼。五．測試結果與分析：測試數據的選擇：在測試中考慮到多種情況使用了多組數據，分別根據是否為連通圖、是否沒有奇度頂點設計了一下四組數據。第一組數據為連通圖且沒有奇度頂點，第二組數據為連通圖且有奇度頂點，第三組數據為連通圖、沒有奇度頂點且有環(huán)，第四組數據為非連通圖且有奇度頂點，第五組數據為非連通圖且沒有奇度頂點。每組數據進行多次測試。測試數據1：33121323測試結果：結果分析：測試數據表示一個3個頂點，3條邊的圖，頂點兩兩相連。如下:2-1所示：113232 圖：2-1測試1存在歐拉回路。測試結果正確。測試數據2：33321223測試結果： 結果分析：測試數據表示一個3個頂點，3條邊的圖，1,、2相連，2、3相連。如下圖2-2所示：1 12323圖：2-2測試2不存在歐拉回路。測試結果正確。測試數據:3：451213243422測試結果：結果分析：測試數據表示一個4個頂點，5條邊的圖，1、2相連，1、3相連,2、4相連,3、4相連，2、2相連。如下圖2-3所示：21213434 圖：2-3測試3存在歐拉回路。測試結果正確。測試數據4：5412344535測試結果：結果分析：測試數據表示一個5個頂點，4條邊的圖，1、2相連，3、4相連,4、5相連,3、5相連。如下:圖2-4所示：3131542542不存在歐拉回路。測試結果正確。 圖：2-4測試4測試數據5：66121323454656測試結果：結果分析：測試數據表示一個6個頂點，6條邊的圖，1、2相連，1、3相連,2、3相連,4、5相連，4、6相連，5、6相連。如下圖2-5所示：541541632632 圖：2-5不存在歐拉回路。測試結果正確。測試結果總結：通過對多種情況設計了多組數據多次測試如上，結果都得到了真確的結論。說明程序符合題目的要求，達到了實驗的目的。六．用戶使用說明：首先本程序中的所有頂點編號為1-N的整數。(0<N<1000)先輸入圖頂點的個數要求為一個正整數n，然后輸入圖所有邊的條數要求為正整數e，再圖邊數行整形數，每行兩個數（用空格相隔）表示一條邊所連接的兩個頂點編號。輸出結果即為題目的解。七．參考文獻：[1]王昆侖，李紅.數據結構與算法.北京：高等教育出版社，2007年6月第1版[2]屈婉玲，耿素云，張立昂.離散數學.北京：高等教育出版社，2008年3月第1版八．附錄：#include<stdio.h>#include<stdlib.h>#include<malloc.h>#defineMAX_VERTEX_NUM1000//頂點的最大個數typedefstruct{ intn;//頂點個數 inte;//邊的條數 intvexs[MAX_VERTEX_NUM];//一維數組儲存頂點 intedges[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//二維數組儲存邊}MGraph;//圖intvisited[MAX_VERTEX_NUM];//全局變量。在對頂點進行深度優(yōu)先搜索遍歷時的輔助變量數組intEuleriancycle(MGraph*mg);//判斷頂點的度數是否全為偶數，有奇數時輸出0，全為偶數時輸出1MGraph*creat_MGraph();//將圖轉化為鄰接矩陣儲存起來，返回鄰接矩陣的首地址intdfs_trave(MGraph*mg);//深度優(yōu)先搜索遍歷voiddfs(MGraph*mg,inti);//深度優(yōu)先搜索voidmain(){ intnum,m;//num用來接收頂點度數判斷的結果，m用來接收圖是否為連通圖的結果 MGraph*mg; mg=creat_MGraph();//建立鄰接矩陣 num=Euleriancycle(mg);//判斷頂點的度數是否全為偶數。全為偶數時num=1；否則num=0 if(num!=1) { printf("不存在歐拉圖！\n"); getchar(); exit(0); } m=dfs_trave(mg);//判斷圖是否為連通圖 if(m!=1) printf("不存在歐拉圖！\n"); else printf("存在歐拉圖！\n"); getch();}MGraph*creat_MGraph()//建立鄰接矩陣{ inti,j,k,n,e; MGraph*mg=malloc(sizeof(MGraph)); printf("請輸入頂點的個數："); scanf("%d",&n); printf("請輸入邊的條數："); scanf("%d",&e); mg->n=n; mg->e=e; getchar(); for(i=1;i<=n;i++) for(j=1;j<=n;j++) mg->edges[i][j]=0;//初始化鄰接矩陣表示的所有邊 printf("請輸入邊的信息:\n"); for(i=1;i<=e;i++) { scanf("%d%d",&j,&k); mg->edges[j][k]=1;mg->edges[k][j]=1;//標記存在的邊 } returnmg;//返回鄰接矩陣的首地址}intEuleriancycle(MGraph*mg)//判斷是否存在歐拉回路{ inti,j,num; for(i=1;i<=mg->n;i++)//從第一個頂點開始，判斷頂點的度數 { num=0;//初始化每個頂點的度數為0 for(j=1;j<=mg->n;j++) { If((mg->edges[i][j]!=0)&&(i!=j))//如果頂點i到j的邊存在度數加1 num=num+1; } if(num%2==1)//如果有哪個頂點的度數為奇數，直接退出循環(huán)，返回0 return0; } return1;//當所有的頂點都判斷完成還沒有退出本函數說明所有頂點度數均為偶數，返回1}intdfs_trave(MGraph*mg)//深度優(yōu)先搜索遍歷{ inti,m=0; for(i=1;i<=mg->n;i++)//將輔助變量全部初始化為0，表明頂點沒有被訪問過 visited[i]=0; for(i=1;i<=mg->n;i++) if(visited[i]==0)//對沒有訪問過的頂點，調用深度優(yōu)先搜索函數 { dfs(mg,i);//深度優(yōu)先搜索 m=m+1;//如果是非連通圖，要調用1次以上，m用來記錄調用dfs函數的次數 } returnm;//返回調用dfs函數的次數}voiddfs(MGraph*mg,inti)//深度優(yōu)先搜索{ intj; visited[i]=1;//訪問該頂點 for(j=1;j<=mg->n;j++) if((visited[j]==0)&&(mg->edges[i][j]==1))//當頂點沒有被訪問過并且兩頂點存在邊 dfs(mg,j);//對該頂點深度優(yōu)先搜索}

本科生學位論文論多媒體技術在教學中的應用姓名：指導教師：專業(yè)：教育管理專業(yè)年級：完成時間：

論多媒體技術在教學中的應用[摘要]多媒體不再是傳統的輔助教學工具，而是為構造一種新的網絡教學環(huán)境創(chuàng)造了條件，特別是對于教育社會化來說，多媒體網絡是一種更理想的傳播工具。多媒體本身具有：融合性、非線性化，無結構性、相互交涉性、可編輯性、實時性等特點；同時運用在教育教學上又有其特長：利于信息的存儲利用、是培養(yǎng)發(fā)散性思維的工具、促使學習個別化的實現。多媒體在教學中的應用有著多種的形式，它在提高學生學習興趣上有著積極的作用，同時它還能促進學生知識的獲取與保持、對教學信息進行有效的組織與管理、建構理想的學習環(huán)境，促進學生自主學習等多方面的效果。立足未來發(fā)展，利用多媒體網絡技術，開展教學試驗。[關鍵詞]多媒體網絡教學系統資源共享多媒體技術主要指多媒體計算機技術，加工、控制、編輯、變換，還可以查詢、檢索。人們借助于多媒體技術可以自然貼切地表達、傳播、處理各種視聽信息，并具有更多的參與性和創(chuàng)造性。當今多媒體已成為廣泛流傳的名詞，但人們對于它的認識，特別是對于它在教育教學方面如何更好應用，未知的因素還很多。

一、多媒體的教育特長任何一種媒體不管其怎樣先進，它只能是作為一種工具被應用到教育領域，能不能促進教育的改革，。。。。。。應當吸取教訓，加強理論研究，充分認識多媒體的特性及其教育特長，以便更好地在教育領域開發(fā)應用多媒體。

1、多媒體的特性

（1）融合性多種符號系統的融合是多媒體的特性之一，多媒體的這一特性區(qū)別于過去媒體符號系統的單一性或復合性。也就是說多媒體技術不是將符號系統疊加，而是具有整體性的融合。

（2）非線性化，無結構性因為多媒體是在超文本、，其組合結構是固定的、不變的。

（5）實時性多媒體信息中的聲音、活動視瀕、動畫于時間有密切聯系，對它們進行呈現、交互等集成處理是實時的。在顯示某一主體內容時，其視聽信息具有同步性。

2、多媒體的教育特長

（1）信息的存儲利用便利多媒體特別是多媒體WWW網絡信息的存儲、提取、雙向傳輸非常便利，它應用于教育，更利于教學信息傳播機制的建立。

（2）發(fā)散性思維的工具在培養(yǎng)學習者發(fā)散性思維方面…………或創(chuàng)造性思維的基礎。

（3）促使學習個別化的實現多媒體WWW網絡有利于個別化的實現。因為學習者各人需求、學習經驗、認知程度等不同，學習方法也有差異，由于多媒體教學信息的多角度多層次性，不具有固定的學習目標和既定學習路徑，學習者可以自定學習路徑選擇自己需要的學習內容。

四、迎接信息時代，運用多媒體技術，實現網絡教學傳播

21世紀是一個信息高速發(fā)展的時代，…………，首先必須認清以下問題：

（一）多媒體不等于光盤化

。。。。。。由于人們認為這就是