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

1、數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)報(bào)告題目?jī)蓛上噙B的房間問(wèn)題：一所奇怪的房子，這所房子里有n 個(gè)房間，每個(gè)房間里有一些門通向別的房間，可是這些門十分奇怪， 它們只能從房間 a 開向房間 b ，也就是說(shuō)，一扇從 a 開向 b 的門是不能讓一個(gè)人從 b 房間走到 a 房間的。你能計(jì)算一下任意兩個(gè)房間之間都互相相通嗎？問(wèn)題分析此程序需要完成如下要求：在這所房子里，從任意一個(gè)房間開始， 按照開門的方向，均能夠找到一個(gè)合適的路線， 使得一個(gè)人能夠不重復(fù)的到達(dá)其他的每一個(gè)房間， 所以，需以每一個(gè)房間都為一次起始點(diǎn)來(lái)走向其他的房間， 以此來(lái)判斷這所房子里的任意兩個(gè)房間之間是否互相相通。實(shí)現(xiàn)本程序需要解決以下問(wèn)題：1.

2、如何表示每一個(gè)房間， 即存儲(chǔ)房間的信息， 并且還要確定這所房子里的各個(gè)房間的位置。2. 各個(gè)房間之間的門，以及門是從哪個(gè)房間開向哪個(gè)房間的該如何表示和存儲(chǔ)的。3. 從某一個(gè)房間開始，如何走到其他各個(gè)房間，即如何對(duì)房間進(jìn)行遍歷。4. 為了在遍歷過(guò)程中，不重復(fù)的遍歷每一個(gè)房間，該如何標(biāo)記已被遍歷過(guò)的房間，從而只訪問(wèn)未走過(guò)的房間。5. 最后通過(guò)什么的遍歷方式才能判斷各個(gè)房間之間是否互相相通。數(shù)據(jù)結(jié)構(gòu)的選擇和概要設(shè)計(jì)通過(guò)對(duì)題目要求的理解， 我們可以用圖來(lái)表示這所房子，而房子中的各個(gè)房間就相當(dāng)于圖中的各個(gè)結(jié)點(diǎn)，由于房間的門是有方向的，一扇從a 開向 b 的門是不能讓一個(gè)人從b 房間走到 a 房間的，從而

3、可知該圖為有向圖，那么門就相當(dāng)于有向圖中的弧，從一個(gè)門開向另一個(gè)門即代表有向圖中弧的起始點(diǎn)和終止點(diǎn)。對(duì)于圖的存儲(chǔ)，我采用鄰接表的形式來(lái)存儲(chǔ)，并將每一個(gè)房間進(jìn)行編號(hào)，對(duì)于鄰接表，則需要定義一個(gè)鄰接表結(jié)點(diǎn)類型、鄰接表表頭結(jié)點(diǎn)類型， 通過(guò)表頭與結(jié)點(diǎn)的連接而將有向圖中弧的信息存儲(chǔ)起來(lái)。 那么人從任意一個(gè)房間走向另一個(gè)房間，即相當(dāng)于有向圖中從一個(gè)結(jié)點(diǎn)按照弧的信息訪問(wèn)其他的結(jié)點(diǎn)，可以采用深度優(yōu)先搜索遍歷。如果從每一個(gè)結(jié)點(diǎn)以起始點(diǎn)開始一次遍歷就都能訪問(wèn)到其他結(jié)點(diǎn)的話則說(shuō)明有向圖是連通圖，即該房子里的各個(gè)房間能夠互相相通。定義一個(gè)全局的整形變量flag ，如果是連通圖的話則flag=1 ，否則 flag=0

4、。程序?qū)崿F(xiàn)的流程圖如下：定義鄰接表結(jié)點(diǎn)類型、鄰接表表頭結(jié)點(diǎn)類型給各個(gè)房間編號(hào)，以方便存儲(chǔ)初始化各個(gè)房間，標(biāo)記讓其開始都為被訪問(wèn)過(guò)創(chuàng)建鄰接表函數(shù)，由用戶輸入房間和門的信息，并存入鄰接表中建立深度優(yōu)先搜索函數(shù)，用遞歸的方式來(lái)遍歷各個(gè)房間main（）調(diào)用創(chuàng)建鄰接表函數(shù)和深度優(yōu)先搜索函數(shù)否是flag 是否兩兩房間不可以互相相通兩兩房間可以互相相通等于 1算法思想主要是把現(xiàn)實(shí)中的房子轉(zhuǎn)換成數(shù)據(jù)結(jié)構(gòu)與算法中圖的思想，并用鄰接表的存儲(chǔ)方式來(lái)存儲(chǔ)圖， 房子里的房間即相當(dāng)于圖中的一個(gè)個(gè)結(jié)點(diǎn)，門只能從一個(gè)房間開向另一個(gè)房間，則說(shuō)明了該圖是有向圖，那么遍歷的過(guò)程中只能按照有向圖中弧所指的方向來(lái)遍歷。在深度優(yōu)先搜索遍

5、歷的算法中，對(duì)于連通圖的遍歷，以某一個(gè)結(jié)點(diǎn)為起始點(diǎn)開始遍歷，只需要遍歷一次就可以訪問(wèn)到所有的結(jié)點(diǎn)，所以以此條件來(lái)判斷該圖是否是連通圖，即可得出房子里的各個(gè)房間是否可以互相相通。詳細(xì)設(shè)計(jì)和主要編碼段首先結(jié)構(gòu)體類型，分別是鄰接表中結(jié)點(diǎn)結(jié)構(gòu)類型Arcnode ，其包含存儲(chǔ)房間的整形變量adjvex ，和指向下一個(gè)結(jié)點(diǎn)的指針nextarc 。鄰接表中表頭結(jié)點(diǎn)結(jié)構(gòu)類型Vexnode ，其同樣包含存儲(chǔ)房間的整形變量vexdata，和指向第一個(gè)鄰接點(diǎn)的指針firstarc，同時(shí)定義一個(gè)Vexnode 類型的一維數(shù)組， 依次將房間的信息存儲(chǔ)在這個(gè)一位數(shù)組中。最后定義一個(gè)鄰接表的結(jié)構(gòu)體類型，其中包含Vexnod

6、e類型的一維數(shù)組，將房子中所有的房間有序的存儲(chǔ)在一維數(shù)組中， 以及兩個(gè)記錄房間個(gè)數(shù)和門的個(gè)數(shù)的整形變量。通過(guò)以上結(jié)構(gòu)體類型的定義，即可得到一個(gè)鄰接表的存儲(chǔ)方式，從而將房子轉(zhuǎn)換成圖的思想把每個(gè)房間和每個(gè)門的信息都存儲(chǔ)在鄰接表中。對(duì)于建立鄰接表的函數(shù)，也就是將房間和門的信息由用戶輸入并存儲(chǔ)在鄰接表中。將房間編號(hào)以后，對(duì)鄰接表的表頭結(jié)點(diǎn)進(jìn)行初始化：首先將房間的信息存儲(chǔ)進(jìn)表頭結(jié)點(diǎn)中：for(i=1;i<=n;i+)ali.vexdata=i;ali.firstarc=NULL;讓數(shù)組 ali 是表頭結(jié)點(diǎn)Vexnodeali 的指針域初始化指向空。類型的，將房間的存儲(chǔ)在一維數(shù)組中的vexdata中

7、，并其次將門的信息存儲(chǔ)在鄰接表中，即通過(guò)表頭結(jié)點(diǎn)中的firstarc 指針域來(lái)指向第一個(gè)鄰接點(diǎn)，然后其它鄰接點(diǎn)的nextarc 指針域又指向下一個(gè)結(jié)點(diǎn)，從而將各個(gè)房間串起來(lái)。在用戶輸入門的信息時(shí)，如果門是從001 號(hào)房間開向010 號(hào)房間的，則讓用戶輸入001010 ，即確定了開門的方向，就相當(dāng)于有向圖中輸入弧的起始點(diǎn)和終止點(diǎn)，即可將門的所有信息都存儲(chǔ)進(jìn)來(lái)了，從而將這所房子用圖的思想存儲(chǔ)在鄰接表中。其中，每輸入一個(gè)門的信息，則動(dòng)態(tài)生成一個(gè)結(jié)點(diǎn)，讓一個(gè)指針p 指向該結(jié)點(diǎn)，將弧的終止點(diǎn)存入p->adjvex中，采用頭插法，將表頭結(jié)點(diǎn)中firstarc 指針?biāo)赶蚪Y(jié)點(diǎn)全部賦給p 指針中的nex

8、tarc 指針，再讓表頭結(jié)點(diǎn)中的firstarc 重新指向新生成的鏈表。代碼如下：printf("請(qǐng)輸入開門的方向( 如門從 001 號(hào)房間開向010 號(hào)房間，那么就輸入001010) ：n");for(i=0;i<e;i+)scanf("%d%d",&j,&k);p=(Arcnode*)malloc(sizeof(Arcnode);p->adjvex=k;p->nextarc=alj.firstarc;alj.firstarc=p;對(duì)于深度優(yōu)先搜索遍歷，我額外又定義了一個(gè)函數(shù)DFS_trave(ALGraph alg)

9、，該函數(shù)的作用一是對(duì)所有的房間信息進(jìn)行初始化，標(biāo)記其未被訪問(wèn)過(guò)，二是在調(diào)用深度優(yōu)先搜索遍歷函數(shù)后， 判讀各個(gè)房間之間是否可以互相相通。在訪問(wèn)房間的過(guò)程中，由于需要以每一個(gè)房間都為一次初始點(diǎn)開始遍歷，進(jìn)行一次深度優(yōu)先搜索遍歷后，必須其他的每一個(gè)房間都被標(biāo)記訪問(wèn)過(guò)了， 才能代表各個(gè)房間之間是可以互相相通的。注意，證明房間之間互相相通即證明該有向圖為連通圖，則以每一個(gè)房間為起始點(diǎn)時(shí)只要進(jìn)行一次深度優(yōu)先搜索遍歷，就能使每個(gè)結(jié)點(diǎn)都被訪問(wèn)過(guò)，這才能說(shuō)明它是連通圖，否則就不是連通圖，即各個(gè)房間之間無(wú)法互相相通。那么在標(biāo)記房間是否被訪問(wèn)過(guò)，采用二維數(shù)組的方式標(biāo)記visitedij。該二維數(shù)組的行下標(biāo)代表以哪個(gè)

10、房間為起始點(diǎn)開始遍歷的，即存儲(chǔ)起始點(diǎn)房間的，用num 表示，在一次遍歷中num 的值是不變的，因?yàn)橐淮伪闅v始終是以該房間為起始點(diǎn)的，列下表代表訪問(wèn)到哪個(gè)房間， 也存儲(chǔ)該房間的，所以列下表在一次遍歷中是變化的。初始化該數(shù)組時(shí)，令二維數(shù)組中所有的值都為0，代表所有的房間都未被訪問(wèn)過(guò)，當(dāng)某一個(gè)房間被訪問(wèn)過(guò)，則將代表這個(gè)房間的二維數(shù)組的值變?yōu)?，如：以 005 號(hào)房間為起始點(diǎn)，訪問(wèn)到了012 號(hào)房間，則令 visited512=1。代碼如下：void DFS_trave(ALGraph alg)int i,j;for(i=1;i<=alg.vexnum;i+)for(j=1;j<=alg.

11、vexnum;j+)visitedij=0;for(num=1;num<=alg.vexnum;num+)DFS(alg,num);for(i=1;i<=alg.vexnum;i+)for(j=1;j<=alg.vexnum;j+)if(visitedij=0)flag=0;break;if(flag=1)printf(" 任意兩個(gè)房間都可以互相相通！");elseprintf(" 任意兩個(gè)房間都不可以互相相通！");在深度優(yōu)先搜索函數(shù)中， 采用遞歸的方法反復(fù)調(diào)用深度優(yōu)先搜索函數(shù)， 定義一個(gè)指針 p ，當(dāng)指針指向某一個(gè)結(jié)點(diǎn)時(shí)，判斷該結(jié)點(diǎn)

12、是否為空，如不為空，再判斷該結(jié)點(diǎn)是否被訪問(wèn)過(guò)，如果沒(méi)有被訪問(wèn)過(guò)， 則調(diào)用一次深度優(yōu)先搜索遍歷函數(shù)， 并對(duì)該結(jié)點(diǎn)標(biāo)記上已被訪問(wèn)過(guò)， 當(dāng)遍歷到某一個(gè)結(jié)點(diǎn)的指針域 firstarc 指向 NULL 時(shí)，并且其它的結(jié)點(diǎn)都被訪問(wèn)過(guò)了，則一次遍歷結(jié)束。代碼如下：void DFS(ALGraph alg,int i)visitednumi=1;Arcnode *p=alg.vexticesi.firstarc;while(p!=NULL)if(visitednump->adjvex=0)DFS(alg,p->adjvex);p=p->nextarc;上機(jī)調(diào)試情況記錄1. 在定義鄰接表結(jié)點(diǎn)結(jié)

13、構(gòu)類型中，剛開始的定義如下： typedef structint adjvex;Arcnode *nextarc;Arcnode;出現(xiàn)了下圖所示的錯(cuò)誤提示：經(jīng)檢查，得知，在結(jié)構(gòu)體類型中，定義Arcnode *nextarc中，編譯器還不知道Arcnode是什么意思，所以無(wú)法定義一個(gè)Arcnode 類型的指針變量，故需將代碼改為：typedef struct Arcnodeint adjvex;Arcnode *nextarc;Arcnode;2.在剛開始運(yùn)行時(shí)，輸入的不是連通圖，程序輸出的結(jié)果卻是：“任意兩個(gè)房間都可以互相相通！ ”原因是由于， 剛開始在標(biāo)記房間是否被訪問(wèn)過(guò)時(shí)我用的是一維數(shù)組來(lái)

14、標(biāo)記的，而默認(rèn)人從第一個(gè)房間開始走向其他房間，當(dāng)一次深度優(yōu)先搜索遍歷后，所有的房間都能夠被訪問(wèn)過(guò)，即說(shuō)明這個(gè)人都能夠到達(dá)其他的所有房間， 則說(shuō)明各個(gè)房間之間是互相相通的。 錯(cuò)就錯(cuò)在我默認(rèn)以第一個(gè)房間為起始點(diǎn)去遍歷其他房間， 即使一次遍歷后其他所有的房間都能夠被訪問(wèn)過(guò)，也只能說(shuō)明從第一個(gè)房間能夠到達(dá)其他的所有房間， 并不能說(shuō)明從其它的房間開始能夠到達(dá)所有的房間。 所以， 需要以每一個(gè)房間都為一次起始點(diǎn)開始遍歷， 所以應(yīng)該采用二維數(shù)組來(lái)標(biāo)記房間是否被訪問(wèn)過(guò)， 只有以每一個(gè)房間為起始點(diǎn)都能訪問(wèn)到其他房間， 才能說(shuō)明各個(gè)房間之間是可以互相相通的。3. 還有個(gè)小錯(cuò)誤，就是在 if 條件判斷時(shí)，又是把判斷

15、相等的符號(hào)寫成了賦值，即兩個(gè)等號(hào)寫成了一個(gè)等號(hào)，導(dǎo)致結(jié)果怎么也不對(duì)。測(cè)試用例、結(jié)果及其算法性能分析性能分析：在建立鄰接表函數(shù)create_AdjListGraph()中，在輸入房間的個(gè)數(shù)后，對(duì)各個(gè)房間的信息進(jìn)行初始化的時(shí)間性能為O(n) ，輸入門的信息后，對(duì)開門的方向存入各個(gè)結(jié)點(diǎn)中，其時(shí)間性能為O(e) ，最后又將表頭結(jié)點(diǎn)中一維數(shù)組的值一一賦給了定義的一個(gè)鄰接表類型的變量alg 中的一維數(shù)組vexticesi ，其時(shí)間性能為O(n) ，故總的時(shí)間性能為O(2n+e) 。在深度優(yōu)先搜索遍歷函數(shù)中，采用了遞歸的方法，而每一個(gè)房間都要調(diào)用n 次深度優(yōu)先搜索遍歷函數(shù)，故n 個(gè)房間在深度優(yōu)先搜索中的時(shí)間

16、性能為O(n2) 。用戶使用說(shuō)明1.房間數(shù)目最多為100 個(gè)，所以在輸入房間數(shù)目時(shí)應(yīng)輸入少于100 的整數(shù)。2. 輸入開門的方向時(shí)，如果門是從001 號(hào)房間開向 012 號(hào)房間，則輸入 001 012 ，兩個(gè)房間之間用空格分開，不能用逗號(hào)或其他符號(hào)，并且房間也要輸入整數(shù)，前面0 可以寫也可以不寫。3.當(dāng)輸入結(jié)束后，均以回車鍵結(jié)束。參考文獻(xiàn)1王昆侖，紅 . 數(shù)據(jù)結(jié)構(gòu)與算法. ：中國(guó)鐵道，2011.附錄（完整源程序）#include<stdio.h>#include<malloc.h>#define MAX_VERTEX_NUM 100int flag=1;int num;

17、int visitedMAX_VERTEX_NUMMAX_VERTEX_NUM;/visited二維數(shù)組用于判斷每個(gè)typedef struct Arcnodeint adjvex;Arcnode *nextarc;Arcnode;房間是否都被訪問(wèn)過(guò)/ 鄰接表中結(jié)點(diǎn)結(jié)構(gòu)類型的定義typedef struct/ 鄰接表表頭結(jié)點(diǎn)結(jié)構(gòu)類型的定義int vexdata;Arcnode *firstarc;/ 指向第一個(gè)鄰接點(diǎn)Vexnode;typedef struct/ 鄰接表類型的定義Vexnode vexticesMAX_VERTEX_NUM;int vexnum,arcnum;/vexnum記錄

18、房間的個(gè)數(shù)，ALGraph;arcnum記錄門的個(gè)數(shù)ALGraph create_AdjListGraph()int i,j,k,n,e;Arcnode *p;Vexnode alMAX_VERTEX_NUM;/ 建立鄰接表函數(shù)，將房間和門存入鄰接表中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)輸入門的數(shù)目：");scanf("%d",&e);printf(" 請(qǐng)?jiān)佥斎腴_門的方向( 比如門從號(hào)房間開向號(hào)房間，那么就輸入010) ：n");for(i=0;i<e;i+)scanf("%d%d",&j,&k);p=(Arcnode*)malloc(sizeof(Arcnode);p->adjvex=k;p->nextarc=alj.firstarc;alj.firstarc=p;ALGraph alg;for(i=1;i<=n;i+)alg.vexticesi=ali;/ 將al數(shù)組中的房間號(hào)依次存儲(chǔ)在鄰接表表頭結(jié)