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

數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)報(bào)告題目兩兩相連的房間問題：一所奇怪的房子，這所房子里有n個(gè)房間，每個(gè)房間里有一些門通向別的房間，可是這些門十分奇怪，它們只能從房間a開向房間b，也就是說，一扇從a開向b的門是不能讓一個(gè)人從b房間走到a房間的。你能計(jì)算一下任意兩個(gè)房間之間都互相相通嗎？問題分析此程序需要完成如下要求：在這所房子里，從任意一個(gè)房間開始，按照開門的方向，均能夠找到一個(gè)合適的路線，使得一個(gè)人能夠不重復(fù)的到達(dá)其他的每一個(gè)房間，所以，需以每一個(gè)房間都為一次起始點(diǎn)來走向其他的房間，以此來判斷這所房子里的任意兩個(gè)房間之間是否互相相通。實(shí)現(xiàn)本程序需要解決以下問題：如何表示每一個(gè)房間，即存儲(chǔ)房間的信息，并且還要確定這所房子里的各個(gè)房間的位置。各個(gè)房間之間的門，以及門是從哪個(gè)房間開向哪個(gè)房間的該如何表示和存儲(chǔ)的。從某一個(gè)房間開始，如何走到其他各個(gè)房間，即如何對(duì)房間進(jìn)行遍歷。為了在遍歷過程中，不重復(fù)的遍歷每一個(gè)房間，該如何標(biāo)記已被遍歷過的房間，從而只訪問未走過的房間。最后通過什么的遍歷方式才能判斷各個(gè)房間之間是否互相相通。數(shù)據(jù)結(jié)構(gòu)的選擇和概要設(shè)計(jì)通過對(duì)題目要求的理解，我們可以用圖來表示這所房子，而房子中的各個(gè)房間就相當(dāng)于圖中的各個(gè)結(jié)點(diǎn)，由于房間的門是有方向的，一扇從a開向b的門是不能讓一個(gè)人從b房間走到a房間的，從而可知該圖為有向圖，那么門就相當(dāng)于有向圖中的弧，從一個(gè)門開向另一個(gè)門即代表有向圖中弧的起始點(diǎn)和終止點(diǎn)。對(duì)于圖的存儲(chǔ)，我采用鄰接表的形式來存儲(chǔ)，并將每一個(gè)房間進(jìn)行編號(hào)，對(duì)于鄰接表，則需要定義一個(gè)鄰接表結(jié)點(diǎn)類型、鄰接表表頭結(jié)點(diǎn)類型，通過表頭與結(jié)點(diǎn)的連接而將有向圖中弧的信息存儲(chǔ)起來。那么人從任意一個(gè)房間走向另一個(gè)房間，即相當(dāng)于有向圖中從一個(gè)結(jié)點(diǎn)按照弧的信息訪問其他的結(jié)點(diǎn)，可以采用深度優(yōu)先搜索遍歷。如果從每一個(gè)結(jié)點(diǎn)以起始點(diǎn)開始一次遍歷就都能訪問到其他結(jié)點(diǎn)的話則說明有向圖是連通圖，即該房子里的各個(gè)房間能夠互相相通。定義一個(gè)全局的整形變量flag，如果是連通圖的話則flag=1，否則flag=0。程序?qū)崿F(xiàn)的流程圖如下:算法思想主要是把現(xiàn)實(shí)中的房子轉(zhuǎn)換成數(shù)據(jù)結(jié)構(gòu)與算法中圖的思想，并用鄰接表的存儲(chǔ)方式來存儲(chǔ)圖，房子里的房間即相當(dāng)于圖中的一個(gè)個(gè)結(jié)點(diǎn)，門只能從一個(gè)房間開向另一個(gè)房間，則說明了該圖是有向圖，那么遍歷的過程中只能按照有向圖中弧所指的方向來遍歷。在深度優(yōu)先搜索遍歷的算法中，對(duì)于連通圖的遍歷，以某一個(gè)結(jié)點(diǎn)為起始點(diǎn)開始遍歷，只需要遍歷一次就可以訪問到所有的結(jié)點(diǎn)，所以以此條件來判斷該圖是否是連通圖，即可得出房子里的各個(gè)房間是否可以互相相通。詳細(xì)設(shè)計(jì)和主要編碼段首先結(jié)構(gòu)體類型，分別是鄰接表中結(jié)點(diǎn)結(jié)構(gòu)類型Arcnode，其包含存儲(chǔ)房間號(hào)碼的整形變量adjvex，和指向下一個(gè)結(jié)點(diǎn)的指針nextarc。鄰接表中表頭結(jié)點(diǎn)結(jié)構(gòu)類型Vexnode，其同樣包含存儲(chǔ)房間號(hào)碼的整形變量vexdata，和指向第一個(gè)鄰接點(diǎn)的指針firstarc，同時(shí)定義一個(gè)Vexnode類型的一維數(shù)組，依次將房間的信息存儲(chǔ)在這個(gè)一位數(shù)組中。最后定義一個(gè)鄰接表的結(jié)構(gòu)體類型，其中包含Vexnode類型的一維數(shù)組，將房子中所有的房間號(hào)碼有序的存儲(chǔ)在一維數(shù)組中，以及兩個(gè)記錄房間個(gè)數(shù)和門的個(gè)數(shù)的整形變量。通過以上結(jié)構(gòu)體類型的定義，即可得到一個(gè)鄰接表的存儲(chǔ)方式，從而將房子轉(zhuǎn)換成圖的思想把每個(gè)房間和每個(gè)門的信息都存儲(chǔ)在鄰接表中。對(duì)于建立鄰接表的函數(shù)，也就是將房間和門的信息由用戶輸入并存儲(chǔ)在鄰接表中。將房沒有落日般的瑰麗，沒有流云般的飄逸，但可以有水晶般的清純與透明。沒有大山般的巍峨，沒有湖水般的輕柔，但可以有巖石般的堅(jiān)毅與穩(wěn)重。沒有大海般的浩瀚，沒有瀑布般的飛瀉，但可以有泥土般的樸素與隨和。風(fēng)從水上走過，留下粼粼波紋;駱駝從沙漠上走過，留下深深的腳印;哨鴿從天空飛過，留下串串歡韻;歲月從樹林穿過，留下圈圈年輪。啊，朋友，我們從時(shí)代的舞臺(tái)走過，將給社會(huì)留下些什么?花從春走過，留下縷縷花香;葉從夏走過，留下片片蔭涼;風(fēng)從秋走過，留下陣陣金浪;雪從冬走過，留下種種希望。啊，朋友，我們從人生的四季走過，將給人生留下些什么？間編號(hào)以后，對(duì)鄰接表的表頭結(jié)點(diǎn)進(jìn)行初始化：首先將房間的信息存儲(chǔ)進(jìn)表頭結(jié)點(diǎn)中：for(i=1;i<=n;i++){al[i].vexdata=i;al[i].firstarc=NULL;}數(shù)組al[i]是表頭結(jié)點(diǎn)Vexnode類型的，將房間的號(hào)碼存儲(chǔ)在一維數(shù)組中的vexdata中，并讓al[i]的指針域初始化指向空。其次將門的信息存儲(chǔ)在鄰接表中，即通過表頭結(jié)點(diǎn)中的firstarc指針域來指向第一個(gè)鄰接點(diǎn)，然后其它鄰接點(diǎn)的nextarc指針域又指向下一個(gè)結(jié)點(diǎn)，從而將各個(gè)房間串起來。在用戶輸入門的信息時(shí)，如果門是從001號(hào)房間開向010號(hào)房間的，則讓用戶輸入001010，即確定了開門的方向，就相當(dāng)于有向圖中輸入弧的起始點(diǎn)和終止點(diǎn)，即可將門的所有信息都存儲(chǔ)進(jìn)來了，從而將這所房子用圖的思想存儲(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指針中的nextarc指針，再讓表頭結(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=al[j].firstarc;al[j].firstarc=p;}對(duì)于深度優(yōu)先搜索遍歷，我額外又定義了一個(gè)函數(shù)DFS_trave(ALGraphalg),該函數(shù)的作用一是對(duì)所有的房間信息進(jìn)行初始化，標(biāo)記其未被訪問過，二是在調(diào)用深度優(yōu)先搜索遍歷函數(shù)后，判讀各個(gè)房間之間是否可以互相相通。在訪問房間的過程中，由于需要以每一個(gè)房間都為一次初始點(diǎn)開始遍歷，進(jìn)行一次深度優(yōu)先搜索遍歷后，必須其他的每一個(gè)房間都被標(biāo)記訪問過了，才能代表各個(gè)房間之間是可以互相相通的。注意，證明房間之間互相相通即證明該有向圖為連通圖，則以每一個(gè)房間為起始點(diǎn)時(shí)只要進(jìn)行一次深度優(yōu)先搜索遍歷，就能使每個(gè)結(jié)點(diǎn)都被訪問過，這才能說明它是連通圖，否則就不是連通圖，即各個(gè)房間之間無法互相相通。那么在標(biāo)記房間是否被訪問過，采用二維數(shù)組的方式標(biāo)記visited[i][j]。該二維數(shù)組的行下標(biāo)代表以哪個(gè)房間為起始點(diǎn)開始遍歷的，即存儲(chǔ)起始點(diǎn)房間的號(hào)碼，用num表示，在一次遍歷中num的值是不變的，因?yàn)橐淮伪闅v始終是以該房間為起始點(diǎn)的，列下表代表訪問到哪個(gè)房間，也存儲(chǔ)該房間的號(hào)碼，所以列下表在一次遍歷中是變化的。初始化該數(shù)組時(shí)，令二維數(shù)組中所有的值都為0，代表所有的房間都未被訪問過，當(dāng)某一個(gè)房間被訪問過，則將代表這個(gè)房間的二維數(shù)組的值變?yōu)?，如：以005號(hào)房間為起始點(diǎn)，訪問到了012號(hào)房間，則令visited[5][12]=1。代碼如下：voidDFS_trave(ALGraphalg){inti,j;for(i=1;i<=alg.vexnum;i++)for(j=1;j<=alg.vexnum;j++)visited[i][j]=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(visited[i][j]==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)是否為空，如不為空，再判斷該結(jié)點(diǎn)是否被訪問過，如果沒有被訪問過，則調(diào)用一次深度優(yōu)先搜索遍歷函數(shù)，并對(duì)該結(jié)點(diǎn)標(biāo)記上已被訪問過，當(dāng)遍歷到某一個(gè)結(jié)點(diǎn)的指針域firstarc指向NULL時(shí)，并且其它的結(jié)點(diǎn)都被訪問過了，則一次遍歷結(jié)束。代碼如下：voidDFS(ALGraphalg,inti){visited[num][i]=1;Arcnode*p=alg.vextices[i].firstarc;while(p!=NULL){if(visited[num][p->adjvex]==0)DFS(alg,p->adjvex);p=p->nextarc;}}上機(jī)調(diào)試情況記錄在定義鄰接表結(jié)點(diǎn)結(jié)構(gòu)類型中，剛開始的定義如下：typedefstruct{intadjvex;Arcnode*nextarc;}Arcnode;出現(xiàn)了下圖所示的錯(cuò)誤提示：日rror匚2143：syntaxmirror:miwwirLg'beEore：'errorC4430:missingtypespecifier-intaEEuiriHil.Note:C++dueEnotsupportdefault-int:errorC4430:miEsingtyjwspecifier-intaseijitied.Note：C++doesnotsupportdefaijlt-interrorC2039:'rLext：=Lt_cJ:isnutamemberofJAi-cnode''cpp(8):seedecl：=Lra+ionofJAi-crLode-'errorC2039:'rLext：=Lrc'':isnotamemberof'虹血門腥'■zpp(8):seedecl：=LrationofJAi-cnode''>1經(jīng)檢查，得知，在結(jié)構(gòu)體類型中，定義Arcnode*nextarc中，編譯器還不知道Arcnode是什么意思，所以無法定義一個(gè)Arcnode類型的指針變量，故需將代碼改為：typedefstructArcnode{intadjvex;Arcnode*nextarc;}Arcnode;在剛開始運(yùn)行時(shí)，輸入的不是連通圖，程序輸出的結(jié)果卻是：''任意兩個(gè)房間都可以互相相通！〃原因是由于，剛開始在標(biāo)記房間是否被訪問過時(shí)我用的是一維數(shù)組來標(biāo)記的，而默認(rèn)人從第一個(gè)房間開始走向其他房間，當(dāng)一次深度優(yōu)先搜索遍歷后，所有的房間都能夠被訪問過，即說明這個(gè)人都能夠到達(dá)其他的所有房間，則說明各個(gè)房間之間是互相相通的。錯(cuò)就錯(cuò)在我默認(rèn)以第一個(gè)房間為起始點(diǎn)去遍歷其他房間，即使一次遍歷后其他所有的房間都能夠被訪問過，也只能說明從第一個(gè)房間能夠到達(dá)其他的所有房間，并不能說明從其它的房間開始能夠到達(dá)所有的房間。所以，需要以每一個(gè)房間都為一次起始點(diǎn)開始遍歷，所以應(yīng)該采用二維數(shù)組來標(biāo)記房間是否被訪問過，只有以每一個(gè)房間為起始點(diǎn)都能訪問到其他房間，才能說明各個(gè)房間之間是可以互相相通的。還有個(gè)小錯(cuò)誤，就是在if條件判斷時(shí)，又是把判斷相等的符號(hào)寫成了賦值，即兩個(gè)等號(hào)寫成了一個(gè)等號(hào)，導(dǎo)致結(jié)果怎么也不對(duì)。測(cè)試用例、結(jié)果及其算法性能分析

請(qǐng)鋤入房間的數(shù)目：4請(qǐng)親入右的數(shù)ao請(qǐng)醫(yī)輸入開門的方向《比如門從3131淞32&304，那么就輸A001010＞：.±.請(qǐng)鋤入房間的數(shù)目：4請(qǐng)親入右的數(shù)ao請(qǐng)醫(yī)輸入開門的方向《比如門從3131淞32&304，那么就輸A001010＞：.±.跚3跚1002003意兩個(gè)房間都可以互相相通!請(qǐng)按任意鍵繼續(xù);--，那么就輸A001010＞：輸入開I。屆方向《比如門從叫1號(hào)房間開向阪。號(hào)房間3101愁3&3959505002SB5SB5堿翎1任意兩個(gè)房間都不可以相通！請(qǐng)按任意鍵繼續(xù)---eC:\￥TKDQ￥S\syst3101愁3&3959505002094005094005002H01005002094005094005002H01005潮3涵1頃堿泗3S04潤4b弱…?遂意兩個(gè)房間都可以互相相通！請(qǐng)技任意鍵繼續(xù);,.?一性能分析：在建立鄰接表函數(shù)create_AdjListGraph()中，在輸入房間的個(gè)數(shù)后，對(duì)各個(gè)房間的信息進(jìn)行初始化的時(shí)間性能為O(n)，輸入門的信息后，對(duì)開門的方向存入各個(gè)結(jié)點(diǎn)中，其時(shí)間性能為0(e)，最后又將表頭結(jié)點(diǎn)中一維數(shù)組的值一一賦給了定義的一個(gè)鄰接表類型的變量alg中的一維數(shù)組vextices[i]，其時(shí)間性能為0(n)，故總的時(shí)間性能為0(2n+e)。在深度優(yōu)先搜索遍歷函數(shù)中，采用了遞歸的方法，而每一個(gè)房間都要調(diào)用n次深度優(yōu)先搜索遍歷函數(shù)，故n個(gè)房間在深度優(yōu)先搜索中的時(shí)間性能為0(n2)。

用戶使用說明房間數(shù)目最多為100個(gè)，所以在輸入房間數(shù)目時(shí)應(yīng)輸入少于100的整數(shù)。輸入開門的方向時(shí)，如果門是從001號(hào)房間開向012號(hào)房間，則輸入001012，兩個(gè)房間之間用空格分開，不能用逗號(hào)或其他符號(hào)，并且房間號(hào)碼也要輸入整數(shù)，前面0可以寫也可以不寫。當(dāng)輸入結(jié)束后，均以回車鍵結(jié)束。參考文獻(xiàn)[1]王昆侖，李紅.數(shù)據(jù)結(jié)構(gòu)與算法.北京：中國鐵道出版社，2011.附錄(完整源程序)#include<stdio.h>#include<malloc.h>#defineMAX_VERTEX_NUM100intflag=1;intnum;intvisited[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//visited二維數(shù)組用于判斷每個(gè)房間是否都被訪問過typedefstructArcnode{〃鄰接表中結(jié)點(diǎn)結(jié)構(gòu)類型的定義intadjvex;Arcnode*nextarc;}Arcnode;typedefstruct{intvexdata;Arcnode*firstarc;}Vexnode;typedefstruct{intvexdata;Arcnode*firstarc;}Vexnode;Vexnodevextices[MAX_VERTEX_NUM];intvexnum,arcnum;//vexnum記錄房間的個(gè)數(shù)，arcnum記錄門的個(gè)數(shù)}ALGraph;ALGraphcreate_AdjListGraph(){〃建立鄰接表函數(shù)，將房間和門存入鄰接表中inti,j,k,n,e;風(fēng)從水上走過，留下粼粼波紋;駱駝從沙漠上走過，留下深深的腳印;哨鴿從天空飛過，留下串串歡韻;歲月從樹林穿過，留下圈圈年輪。啊，朋友，我們從時(shí)代的舞臺(tái)走過，將給社會(huì)留下些什么?花從春走過，留下縷縷花香;葉從夏走過，留下片片蔭涼;風(fēng)從秋走過，留下陣陣金浪;雪從冬走過，留下種種希望。啊，朋友，我們從人生的四季走過，將給人生留下些什么？Arcnode*p;Vexnodeal[MAX_VERTEX_NUM];printf("請(qǐng)輸入房間的數(shù)目：");scanf("%d”,&n);for(i=1;i<=n;i++){〃初始化表頭結(jié)點(diǎn)數(shù)組al[i].vexdata=i;al[i].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=al[j].firstarc;al[j].firstarc=p;}ALGraphalg;for(i=1;i<=n;i++)alg.vextices[i]=al[i];〃將al數(shù)組中的房間號(hào)依次存儲(chǔ)在鄰接表表頭結(jié)點(diǎn)的一維數(shù)組vextices中alg.vexnum=n;alg.arcnum=e;returnalg;}