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

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

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

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

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

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

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

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

8、一個(gè)房間都被標(biāo)志接見(jiàn)過(guò)了，才能代表各個(gè)房間之間是能夠相互相通的。注意，證明房間之間相互相通即證明該有向圖為連通圖，則以每一個(gè)房間為初步點(diǎn)時(shí)只需進(jìn)行一次深度優(yōu)先搜尋遍歷，就能使每個(gè)結(jié)點(diǎn)都被接見(jiàn)過(guò)，這才能說(shuō)明它是連通圖，不然就不是連通圖，即各個(gè)房間之間沒(méi)法相互相通。那么在標(biāo)志房間能否被接見(jiàn)過(guò)，采納二維數(shù)組的方式標(biāo)志visitedij。該二維數(shù)組的行下標(biāo)代表以哪個(gè)房間為初步點(diǎn)開(kāi)始遍歷的，即儲(chǔ)蓄初步點(diǎn)房間的號(hào)碼，用num表示，在一次遍歷中num的值是不變的，因?yàn)橐淮伪闅v素來(lái)是以該房間為初步點(diǎn)的，列下表代表接見(jiàn)到哪個(gè)房間，也儲(chǔ)蓄該房間的號(hào)碼，因此列下表在一次遍歷中是變化的。初始化該標(biāo)準(zhǔn)文檔適用文案數(shù)組時(shí)

9、，令二維數(shù)組中所有的值都為0，代表所有的房間都未被接見(jiàn)過(guò)，當(dāng)某一個(gè)房間被訪(fǎng)問(wèn)過(guò)，則將代表這個(gè)房間的二維數(shù)組的值變成1，如：以005號(hào)房間為初步點(diǎn)，接見(jiàn)到了012號(hào)房間，則令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;上機(jī)調(diào)試狀況記錄在定義毗鄰表結(jié)點(diǎn)構(gòu)造種類(lèi)中，剛開(kāi)始的定義以下：typedefstructintadjvex;Arcnode*nextarc;Arcnode;出現(xiàn)了以下列圖所示的錯(cuò)誤提示：標(biāo)準(zhǔn)文檔適用文案經(jīng)檢查，得悉，在構(gòu)造體種類(lèi)中，定義Arcnode*nextarc中，編譯器還不知道Arcnode是什么意思，因此沒(méi)法定義一個(gè)Arcnode種類(lèi)的指針變量，故需將代碼改為：typedefstructArcnodeintadjvex;Arcnode*nextarc;Arcnode;2.在剛開(kāi)始運(yùn)轉(zhuǎn)時(shí)，輸入的不是連通圖，程序輸出的結(jié)果倒是：“隨意兩個(gè)房間都能夠互相相通！”原由是因

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

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

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

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

15、數(shù)ALGraph;ALGraphcreate_AdjListGraph()/成立毗鄰表函數(shù)，將房間和門(mén)存入毗鄰表中inti,j,k,n,e;Arcnode*p;VexnodealMAX_VERTEX_NUM;printf(請(qǐng)輸入房間的數(shù)量：);scanf(%d,&n);for(i=1;i=n;i+)/初始化表頭結(jié)點(diǎn)數(shù)組ali.vexdata=i;ali.firstarc=NULL;printf(請(qǐng)輸入門(mén)的數(shù)量：);scanf(%d,&e);printf(請(qǐng)?jiān)佥斎腴_(kāi)門(mén)的方向(比方門(mén)從號(hào)房間開(kāi)向號(hào)房間，那么就輸入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;標(biāo)準(zhǔn)文檔適用文案voidDFS_trave(ALGraphalg)inti,j;for(i=1;i=alg.vexnum;i+)for(j=1;j=alg.vexnum;j+)visitedij=0;/初始化接見(jiàn)數(shù)組，即讓每一個(gè)結(jié)點(diǎn)都未被接見(jiàn)過(guò)for(num=1;