大數(shù)據(jù)結(jié)構(gòu)算法課程設(shè)計程序報告計劃材料

1、大數(shù)據(jù)構(gòu)造及算法課程設(shè)計程序及報告計劃資料大數(shù)據(jù)構(gòu)造及算法課程設(shè)計程序及報告計劃資料大數(shù)據(jù)構(gòu)造及算法課程設(shè)計程序及報告計劃資料適用文案數(shù)據(jù)構(gòu)造與算法課程設(shè)計報告題目兩兩相連的房間問題：一所奇異的房屋，這所房屋里有n個房間，每個房間里有一些門通向其余房間，但是這些門十分奇異，它們只好從房間a開向房間b，也就是說，一扇從a開向b的門是不可以夠讓一個人從b房間走到a房間的。你能計算一下隨意兩個房間之間都相互相通嗎？問題分析此程序需要達成以下要求：在這所房屋里，從隨意一個房間開始，依據(jù)開門的方向，均能夠找到一個適合的路線，使得一個人能夠不重復的抵達其余的每一個房間，因此，需以每一個房間都為一次初步點來

2、走向其余的房間，以此來判斷這所房屋里的隨意兩個房間之間是否相互相通。實現(xiàn)本程序需要解決以下問題：怎樣表示每一個房間，即儲蓄房間的信息，而且還要確立這所房屋里的各個房間的地點。各個房間之間的門，以及門是從哪個房間開向哪個房間的該怎樣表示和儲蓄的。從某一個房間開始，怎樣走到其余各個房間，即怎樣對房間進行遍歷。為了在遍歷過程中，不重復的遍歷每一個房間，該怎樣標志已被遍歷過的房間，進而只接見未走過的房間。最后經(jīng)過什么的遍歷方式才能判斷各個房間之間能否相互相通。標準文檔適用文案數(shù)據(jù)構(gòu)造的選擇和綱領(lǐng)設(shè)計經(jīng)過對題目要求的理解，我們能夠用圖來表示這所房屋，而房屋中的各個房間就相當于圖中的各個結(jié)點，因為房間的門

3、是有方向的，一扇從a開向b的門是不可以夠讓一個人從b房間走到a房間的，進而可知該圖為有向圖，那么門就相當于有向圖中的弧，從一個門開向另一個門即代表有向圖中弧的初步點和停止點。關(guān)于圖的儲蓄，我采納毗鄰表的形式來儲蓄，并將每一個房間進行編號，關(guān)于毗鄰表，則需要定義一個毗鄰表結(jié)點種類、毗鄰表表頭結(jié)點種類，經(jīng)過表頭與結(jié)點的連結(jié)而將有向圖中弧的信息儲蓄起來。那么人從隨意一個房間走向另一個房間，即相當于有向圖中從一個結(jié)點依據(jù)弧的信息接見其余的結(jié)點，能夠采納深度優(yōu)先搜尋遍歷。假如從每一個結(jié)點以初步點開始一次遍歷就都能接見到其余結(jié)點的話則說明有向圖是連通圖，即該房屋里的各個房間能夠相互相通。定義一個全局的整形

4、變量flag，假如是連通圖的話則flag=1，不然flag=0。程序?qū)崿F(xiàn)的流程圖以下：定義毗鄰表結(jié)點種類、毗鄰表表頭結(jié)點種類給各個房間編號，以方便儲蓄初始化各個房間，標志讓其開始都為被接見過創(chuàng)立毗鄰表函數(shù)，由用戶輸入房間和門的信息，并存入毗鄰表中成立深度優(yōu)先搜尋函數(shù)，用遞歸的方式來遍歷各個房間main（）調(diào)用創(chuàng)立毗鄰表函數(shù)和深度優(yōu)先搜尋函數(shù)標準文檔否flag能否是兩兩房間不可以夠夠相互相通兩兩房間能夠相互相通等于1適用文案算法思想主假如把現(xiàn)實中的房屋變換成數(shù)據(jù)構(gòu)造與算法中圖的思想，并用毗鄰表的儲蓄方式來存儲圖，房屋里的房間即相當于圖中的一個個結(jié)點，門只好從一個房間開向另一個房間，則說了然該圖是

5、有向圖，那么遍歷的過程中只好依據(jù)有向圖中弧所指的方素來遍歷。在深度優(yōu)先搜尋遍歷的算法中，關(guān)于連通圖的遍歷，以某一個結(jié)點為初步點開始遍歷，只需要遍歷一次就能夠接見到所有的結(jié)點，因此以此條件來判斷該圖是不是連通圖，即可得出房屋里的各個房間能否能夠相互相通。詳盡設(shè)計和主要編碼段第一構(gòu)造體種類，分別是毗鄰表中結(jié)點構(gòu)造種類Arcnode，其包括儲蓄房間號碼的整標準文檔適用文案形變量adjvex，和指向下一個結(jié)點的指針nextarc。毗鄰表中表頭結(jié)點構(gòu)造種類Vexnode，其相同包括儲蓄房間號碼的整形變量vexdata，和指向第一個毗鄰點的指針firstarc，同時定義一個Vexnode種類的一維數(shù)組，挨

6、次將房間的信息儲蓄在這個一位數(shù)組中。最后定義一個毗鄰表的構(gòu)造體種類，此中包括Vexnode種類的一維數(shù)組，將房屋中所有的房間號碼有序的儲蓄在一維數(shù)組中，以及兩個記錄房間個數(shù)和門的個數(shù)的整形變量。經(jīng)過以上構(gòu)造體種類的定義，即可獲得一個毗鄰表的儲蓄方式，進而將房屋變換成圖的思想把每個房間和每個門的信息都儲蓄在毗鄰表中。關(guān)于成立毗鄰表的函數(shù)，也就是將房間和門的信息由用戶輸入并儲蓄在毗鄰表中。將房間編號此后，對毗鄰表的表頭結(jié)點進行初始化：第一將房間的信息儲蓄進表頭結(jié)點中：for(i=1;iadjvex中，采納頭標準文檔適用文案插法，將表頭結(jié)點中firstarc指針所指向結(jié)點所有賦給p指針中的nexta

7、rc指針，再讓表頭結(jié)點中的firstarc從頭指向重生成的鏈表。代碼以下：printf(請輸入開門的方向(如門從001號房間開向010號房間，那么就輸入001：n);for(i=0;iadjvex=k;p-nextarc=alj.firstarc;alj.firstarc=p;關(guān)于深度優(yōu)先搜尋遍歷，我額外又定義了一個函數(shù)DFS_trave(ALGraphalg)，該函數(shù)的作用一是對所有的房間信息進行初始化，標志其未被接見過，二是在調(diào)用深度優(yōu)先搜尋遍歷函數(shù)后，判讀各個房間之間能否能夠相互相通。在接見房間的過程中，因為需要以每一個房間都為一次初始點開始遍歷，進行一次深度優(yōu)先搜尋遍歷后，必然其余的每

8、一個房間都被標志接見過了，才能代表各個房間之間是能夠相互相通的。注意，證明房間之間相互相通即證明該有向圖為連通圖，則以每一個房間為初步點時只需進行一次深度優(yōu)先搜尋遍歷，就能使每個結(jié)點都被接見過，這才能說明它是連通圖，不然就不是連通圖，即各個房間之間沒法相互相通。那么在標志房間能否被接見過，采納二維數(shù)組的方式標志visitedij。該二維數(shù)組的行下標代表以哪個房間為初步點開始遍歷的，即儲蓄初步點房間的號碼，用num表示，在一次遍歷中num的值是不變的，因為一次遍歷素來是以該房間為初步點的，列下表代表接見到哪個房間，也儲蓄該房間的號碼，因此列下表在一次遍歷中是變化的。初始化該標準文檔適用文案數(shù)組時

9、，令二維數(shù)組中所有的值都為0，代表所有的房間都未被接見過，當某一個房間被訪問過，則將代表這個房間的二維數(shù)組的值變成1，如：以005號房間為初步點，接見到了012號房間，則令visited512=1。代碼以下：voidDFS_trave(ALGraphalg)inti,j;for(i=1;i=alg.vexnum;i+)for(j=1;j=alg.vexnum;j+)visitedij=0;for(num=1;num=alg.vexnum;num+)DFS(alg,num);for(i=1;i=alg.vexnum;i+)for(j=1;jadjvex=0)DFS(alg,p-adjvex);p

10、=p-nextarc;上機調(diào)試狀況記錄在定義毗鄰表結(jié)點構(gòu)造種類中，剛開始的定義以下：typedefstructintadjvex;Arcnode*nextarc;Arcnode;出現(xiàn)了以下列圖所示的錯誤提示：標準文檔適用文案經(jīng)檢查，得悉，在構(gòu)造體種類中，定義Arcnode*nextarc中，編譯器還不知道Arcnode是什么意思，因此沒法定義一個Arcnode種類的指針變量，故需將代碼改為：typedefstructArcnodeintadjvex;Arcnode*nextarc;Arcnode;2.在剛開始運轉(zhuǎn)時，輸入的不是連通圖，程序輸出的結(jié)果倒是：“隨意兩個房間都能夠互相相通！”原由是因

11、為，剛開始在標志房間能否被接見過時我用的是一維數(shù)組來標志的，而默認人從第一個房間開始走向其余房間，當一次深度優(yōu)先搜尋遍歷后，所有的房間都能夠被接見過，即說明這個人都能夠抵達其余的所有房間，則說明各個房間之間是相互相通的。錯就錯在我默認以第一個房間為初步點去遍歷其余房間，即便一次遍歷后其余所有的房間都能夠被接見過，也只好說明從第一個房間能夠抵達其余的所有房間，其實不可以夠說明從其余的房間開始能夠抵達所有的房間。因此，需要以每一個房間都為一次初步點開始遍歷，因此應當采納二維數(shù)組來標志房間能否被接見過，只有以每一個房間為初步點都能接見到其余房間，才能說明各個房間之間是能夠相互相通的。還有個小錯誤，就

12、是在if條件判斷時，又是把判斷相等的符號寫成了賦值，即兩個等號寫成了一個等號，致使結(jié)果怎么也不對。標準文檔適用文案測試用例、結(jié)果及其算法性能分析標準文檔適用文案性能分析：在成立毗鄰表函數(shù)create_AdjListGraph()中，在輸入房間的個數(shù)后，對各個房間的信息進行初始化的時間性能為O(n)，輸入門的信息后，對開門的方向存入各個結(jié)點中，其時間性能為O(e)，最后又將表頭結(jié)點中一維數(shù)組的值一一賦給了定義的一個毗鄰表種類的變量alg中的一維數(shù)組vexticesi，其時間性能為O(n)，故總的時間性能為O(2n+e)。在深度優(yōu)先搜尋遍歷函數(shù)中，采納了遞歸的方法，而每一個房間都要調(diào)用n次深度優(yōu)先

13、搜尋遍歷函數(shù)，故n個房間在深度優(yōu)先搜尋中的時間性能為O(n2)。用戶使用說明1.房間數(shù)量最多為100個，因此在輸入房間數(shù)量時應輸入少于100的整數(shù)。2.輸入開門的方向時，假如門是從001號房間開向012號房間，則輸入001012，兩個房間之間用空格分開，不可以夠用逗號或其余符號，而且房間號碼也要輸入整數(shù)，前面0可以寫也能夠不寫。當輸入結(jié)束后，均以回車鍵結(jié)束。標準文檔適用文案參照文件王昆侖，李紅.數(shù)據(jù)構(gòu)造與算法.北京：中國鐵道第一版社，2011.附錄（圓滿源程序）#include#include#defineMAX_VERTEX_NUM100intflag=1;intnum;intvisited

14、MAX_VERTEX_NUMMAX_VERTEX_NUM;/visited二維數(shù)組用于判斷每個房間能否都被接見過typedefstructArcnode/毗鄰表中結(jié)點構(gòu)造種類的定義intadjvex;Arcnode*nextarc;Arcnode;typedefstruct/毗鄰表表頭結(jié)點構(gòu)造種類的定義intvexdata;Arcnode*firstarc;/指向第一個毗鄰點標準文檔適用文案Vexnode;typedefstruct/毗鄰表種類的定義VexnodevexticesMAX_VERTEX_NUM;intvexnum,arcnum;/vexnum記錄房間的個數(shù)，arcnum記錄門的個

15、數(shù)ALGraph;ALGraphcreate_AdjListGraph()/成立毗鄰表函數(shù)，將房間和門存入毗鄰表中inti,j,k,n,e;Arcnode*p;VexnodealMAX_VERTEX_NUM;printf(請輸入房間的數(shù)量：);scanf(%d,&n);for(i=1;i=n;i+)/初始化表頭結(jié)點數(shù)組ali.vexdata=i;ali.firstarc=NULL;printf(請輸入門的數(shù)量：);scanf(%d,&e);printf(請再輸入開門的方向(比方門從號房間開向號房間，那么就輸入010)：n);for(i=0;iadjvex=k;p-nextarc=alj.firstarc;alj.firstarc=p;ALGraphalg;for(i=1;iadjvex=0)DFS(alg,p-adjvex);p=p-nextarc;標準文檔適用文案voidDFS_trave(ALGraphalg)inti,j;for(i=1;i=alg.vexnum;i+)for(j=1;j=alg.vexnum;j+)visitedij=0;/初始化接見數(shù)組，即讓每一個結(jié)點都未被接見過for(num=1;