專業(yè)課程設(shè)計(jì)任務(wù)書

1、電腦科學(xué)與技術(shù)專業(yè)課程設(shè)計(jì)任務(wù)書學(xué)生專業(yè)班級學(xué)號題目圖的遍歷課題性質(zhì)其他課題來源自擬課題指導(dǎo)教師同組主要內(nèi)容建立圖的存儲結(jié)構(gòu)輸出兩種遍歷任務(wù)要求對任息給正的圖頂點(diǎn)數(shù)和邊數(shù)自正義，建立匕的鄰接表輸出，然后利用棧的五種基本運(yùn)算活空堆棧，壓棧，彈出，取棧頂元素，判空棧實(shí)現(xiàn)圖的深度搜索遍歷和廣度優(yōu)先搜素遍歷算法參考文獻(xiàn)1 譚浩強(qiáng)，C程序設(shè)計(jì)第二版，北京,清華大學(xué)出版社,2005年1月2 嚴(yán)蔚敏，吳偉民，數(shù)據(jù)結(jié)構(gòu)C語言版，北京，清華大學(xué)出版社,2005年10月3 許卓群，楊冬青等，數(shù)據(jù)結(jié)構(gòu)與算法，高等教育出版社,20044 朱戰(zhàn)立，數(shù)據(jù)結(jié)構(gòu)，西安電子科技大學(xué)出版社,2003審查意見指導(dǎo)教師簽字：教研室主

2、任簽字：年月日說明：本表由指導(dǎo)教師填寫，由教研室主任審核后下達(dá)給選題學(xué)生，裝訂在設(shè)計(jì)論文首頁課程設(shè)計(jì)課程設(shè)計(jì)名稱：數(shù)據(jù)結(jié)構(gòu)專業(yè)班級：學(xué)生姓名：學(xué)號：指導(dǎo)教師：課程設(shè)計(jì)時(shí)間:一、需求分析對任意給定的圖頂點(diǎn)數(shù)和邊數(shù)自定義，建立它的鄰接表輸出，然后利用棧的五種基本運(yùn)算活空堆棧，壓棧，彈出，取棧頂元素，判空棧實(shí)現(xiàn)圖的深度搜索遍歷和廣度優(yōu)先搜素遍歷算法二、概要設(shè)計(jì)鄰接表是圖的一種鏈?zhǔn)酱鎯Y(jié)構(gòu)為，類似丁樹的孩子鏈表表法。在鄰接表中，對圖中每個(gè)頂點(diǎn)建立一個(gè)單鏈表，n個(gè)頂點(diǎn)，就要建n個(gè)鏈表。對丁無向圖，第i個(gè)單鏈表中的結(jié)點(diǎn)表示依賴丁頂點(diǎn)Vi的邊。對丁有向圖是以頂點(diǎn)Vi為尾的弧,這個(gè)單鏈表稱為頂點(diǎn)Vi的單鏈表（

3、即V的鄰接表）。單鏈表中每一個(gè)結(jié)點(diǎn)稱為表結(jié)點(diǎn)，應(yīng)包括兩個(gè)域：鄰接點(diǎn)域，用以存放與Vi相鄰接的頂點(diǎn)序號；鏈域用以指向民Vi鄰接的下一個(gè)結(jié)點(diǎn)。另外，每一個(gè)單鏈表設(shè)一個(gè)表頭結(jié)點(diǎn)。每一個(gè)表頭結(jié)點(diǎn)有兩個(gè)域，一個(gè)用來存放頂點(diǎn)vi的信息；另一個(gè)域用來指向Vi的鄰接表中的第一個(gè)結(jié)點(diǎn)。為了便丁管理和隨機(jī)訪問任一頂點(diǎn)的單鏈表，將所有單鏈表的頭結(jié)點(diǎn)組織成一個(gè)一維數(shù)組。vertexlinkadjvexnext頂點(diǎn)頂點(diǎn)鏈頭鏈針地址鄰接表的表頭和表結(jié)點(diǎn)形式typedefstructnode（intadjvex;/弧指向頂點(diǎn)的位置structnode*next;/指向下一條弧的指針edgenode;/表結(jié)點(diǎn)typedefs

4、truct/頭結(jié)點(diǎn)charvertex;/頂點(diǎn)信息edgenode*link;/指向第一條依附該頂點(diǎn)的弧的指針vexnode,AdjListmaxvertexnum;建立鄰接表的方法是：首先將鄰接表表頭數(shù)組初始化，第i個(gè)表頭的vertex初始化為i,;link初始化為NULL然后讀入頂點(diǎn)對<i.j>,產(chǎn)生一個(gè)表結(jié)點(diǎn)，將j放入到該結(jié)點(diǎn)的adjvex域，將該結(jié)點(diǎn)鏈到鄰接表的表頭的T第i個(gè)表頭的link域上。2. 深度優(yōu)先遍歷算法輸出起始頂點(diǎn)，同時(shí)置起始頂點(diǎn)已訪問的標(biāo)記a取當(dāng)前棧頂頂點(diǎn)b假設(shè)棧頂頂點(diǎn)存在未被訪問的鄰接結(jié)點(diǎn)，則選擇一個(gè)頂點(diǎn)進(jìn)行一下步驟:輸出該頂點(diǎn)置該頂點(diǎn)已訪問標(biāo)記將該頂點(diǎn)進(jìn)

5、棧c否測當(dāng)前頂點(diǎn)退棧存儲結(jié)構(gòu)typedefstruct/棧int*data;/棧底指針3. int*top;/棧頂指針seqstack;廣度優(yōu)先遍歷算法置起始頂點(diǎn)已訪問標(biāo)記，并將該頂點(diǎn)入隊(duì)a取對頭頂點(diǎn)b依次訪問與頂點(diǎn)相鄰的未被訪問的頂點(diǎn)訪問該頂點(diǎn)置該頂點(diǎn)為已被訪問的標(biāo)記，并將它入隊(duì)c當(dāng)前對頭元素頂點(diǎn)出隊(duì)d重復(fù)進(jìn)行直到對空時(shí)結(jié)束三、運(yùn)行環(huán)境軟、硬件環(huán)境四、開發(fā)工具和編程語言開發(fā)工具和編程語言：數(shù)據(jù)結(jié)構(gòu)C語言數(shù)據(jù)結(jié)構(gòu)c語言五、詳細(xì)設(shè)計(jì)#include<stdio.h>#include<stdlib.h>#include<malloc.h>#defineFalse

6、0#defineTrue1#defineNull0#definemaxsize20/隊(duì)歹U的最大空間#definemaxvertexnum20/最大頂點(diǎn)數(shù)typedefstructnodeintadjvex;/弧指向頂點(diǎn)的位置structnode*next;/指向下一條弧的指針edgenode;/表結(jié)點(diǎn)typedefstruct/頭結(jié)點(diǎn)charvertex;/頂點(diǎn)信息edgenode*link;/指向第一條依附該頂點(diǎn)的弧的指釘vexnode,AdjListmaxvertexnum;typedefstruct/圖AdjListadjlist;intn,e;/n頂點(diǎn)數(shù)，e邊數(shù)Graph;typed

7、efstruct/棧int*data;/棧底指針int*top;/棧頂指針seqstack;/全局變量vexnodegmaxvertexnum;/先定義后使用vexnode,鄰接表g為全程變量intvisitedmaxvertexnum;/定義visit為全程向量voidCreatAdjList(Graph&G)inti,j,k;/i,j為鄰接點(diǎn)序號edgenode*s;charc;printf("請輸入定點(diǎn)數(shù)和邊數(shù)：n");scanf("%d,%d”,&G.n,&G.e);c=getchar();printf("請輸入頂點(diǎn)信息(

8、頂點(diǎn)號):n");for(i=1;i<=G.n;i+)/建立有n個(gè)頂點(diǎn)的頂點(diǎn)表printf("第樸頂點(diǎn)為",i);scanf("%c",&G.adjlisti.vertex);c=getchar();G.adjlisti.link=NULL;printf("請輸入邊的信息():n");for(k=1;k<=G.e;k+)/建立邊表printf(-請輸入請輸入第d>邊起始頂點(diǎn)編號：n",k);scanf("%d",&i);printf(-請輸入請輸入第d>邊

9、終頂點(diǎn)編號:n",k);scanf("%d",&j);s=(edgenode*)malloc(sizeof(edgenode);/分配頂點(diǎn)空間s->adjvex=j;s->next=G.adjlisti.link;G.adjlisti.link=s;voidDisplayAdjList(GraphG)inti;edgenode*q;for(i=1;i<=G.n;+i)q=G.adjlisti.link;printf("%d",i);while(q!=NULL)printf("->%d",q-&

10、gt;adjvex);q=q->next;printf("n");voidDFSAL(GraphG)edgenode*p;seqstacks;inti=1,t;for(i=1;i<=G.n;i+)visitedi=0;printf(-這是深度優(yōu)先遍歷，遍歷順序?yàn)?n");/輸出起始頂點(diǎn)s.data=(int*)malloc(maxsize*sizeof(seqstack);s.top=s.data;/初始化棧for(i=1;i<=G.n;i+)/考慮到圖可能不連通p=G.adjlisti.link;t=i；if(p=NULL)/p=NULL時(shí)，即

11、該結(jié)點(diǎn)沒有鄰結(jié)點(diǎn)(if(!visitedt)(printf("%c”,G.adjlistt.vertex);/如果此時(shí)該結(jié)點(diǎn)沒有被訪問過，則訪問visitedt=True;continue;/即該結(jié)點(diǎn)沒有鄰結(jié)點(diǎn)，本次循環(huán)結(jié)束doif(p=NULL)/即到了圖的最底層s.top-;/沒有下個(gè)鄰接點(diǎn)，則退回前一個(gè)頂點(diǎn)p=G.adjlist*s.top.link;if(p!=NULL)t=p->adjvex;elseif(!visitedt)/該結(jié)點(diǎn)中p!=NULL且其沒有被訪問過printf("%c",G.adjlistt.vertex);/輸出該頂點(diǎn)visit

12、edt=True;/置為已訪問if(G.adjlistt.link=NULL)continue;*s.top=t;s.top+;/進(jìn)棧p=G.adjlistt.link;/p指針指到以G.adjlistt.vertex為起點(diǎn)的第一條邊，如果/p=NULLif(p=NULL)/如果該結(jié)點(diǎn)沒有鄰接點(diǎn)則輸出之if(!visitedt)printf("%c",G.adjlistt.vertex);elset=p->adjvex;/如果該結(jié)點(diǎn)有鄰接點(diǎn)，則把其鄰接點(diǎn)的頂點(diǎn)號賦值給telse/如果該結(jié)點(diǎn)被訪問過，且有鄰結(jié)點(diǎn)，p指向以當(dāng)前結(jié)點(diǎn)的鄰接點(diǎn)為起點(diǎn)的邊/也可能P=NULL(p

13、=p->next;if(p!=NULL)t=p->adjvex;/如果該鄰接點(diǎn)有鄰接點(diǎn)，則記下其鄰接點(diǎn)的位置while(s.top!=s.data);voidBFSAL(GraphG)(intv,Qmaxsize;edgenode*w;printf(-這是廣度優(yōu)先遍歷，遍歷順序?yàn)?n");intfront=0,rear=0;/輔助隊(duì)歹U置空for(v=1;v<=G.n;v+)visitedv=0;for(v=1;v<=G.n;v+)if(!visitedv)(visitedv=1;printf("%c",G.adjlistv.vertex)

14、;Qrear=v;rear+;/入隊(duì)while(front!=rear)(/隊(duì)不空front+;出隊(duì)w=G.adjlistv.link;while(w)(if(!visitedw->adjvex)(visitedw->adjvex=1;/訪問w;printf("%c”,G.adjlistw->adjvex.vertex);Qrear=w->adjvex;rear+;w=w->next;voidmain()(GraphG;intchoice;charch;printf("-創(chuàng)建鄰接表存儲的圖");CreatAdjList(G);prin

15、tf("已創(chuàng)建一個(gè)圖了鄰接表n");DisplayAdjList(G)while(ch!='n')(printf("n請選擇操作：");printf("n1-深度優(yōu)先遍歷：");printf("n2-廣度優(yōu)先遍歷");printf("n3-退出n");scanf("%d",&choice);switch(choice)(case1:DFSAL(G);break;case2:BFSAL(G);break;case3:ch='n'break

16、;default:ch='n'六、調(diào)試分析在圖的創(chuàng)建過程中就遇到了問題，應(yīng)為少了接受字符的getchar()函數(shù)，使得再輸入頂點(diǎn)信息字符型后無法再執(zhí)行CreatAdjlist()中剩下的語句，導(dǎo)致創(chuàng)建失?。≡俳?jīng)同學(xué)提醒后成功創(chuàng)建了圖。在圖的深度和廣度遍歷時(shí)，由于其出的思路不夠活晰，導(dǎo)致在寫時(shí)漏考慮了一些情況致使無法得出想要的結(jié)果。在參閱了一些資料后，將思路搞活楚后，利用非遞歸得到了想要的結(jié)果！七、測試結(jié)果八、參考文獻(xiàn)在“課程設(shè)計(jì)報(bào)告”的最后應(yīng)附上所參考的相關(guān)文獻(xiàn),參考文獻(xiàn)的書寫格式如下：書籍：作者，書名，版本，出版地，出版者，出版年，引用內(nèi)容所在頁碼論文：作者，論文篇名，刊物名

17、，年月卷，論文在刊物中的頁碼要求：必須獨(dú)立完成，不能互相抄襲。設(shè)計(jì)完成后，將所完成的工作交由老師檢查。并寫出一份詳細(xì)的實(shí)習(xí)報(bào)告。數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)總結(jié)“要想學(xué)好一門語言，就要多用它！”雖然老師課上講一些算法的思路彳艮活楚，但是光靠課堂上的一些理論的知識遠(yuǎn)遠(yuǎn)不夠的。那些只是一個(gè)基礎(chǔ)，只有通過自己上機(jī)調(diào)試發(fā)現(xiàn)問題，解決問題才能更好，更深入的學(xué)好這門語言，運(yùn)用好這門語言！就拿這次的課程設(shè)計(jì)來說，課程設(shè)計(jì)的目的是培養(yǎng)學(xué)生綜合運(yùn)用所學(xué)知識，發(fā)現(xiàn)，提出，分析和解決實(shí)際問題，鍛煉實(shí)踐能力的重要環(huán)節(jié)，是對學(xué)生實(shí)際工作能力的具體訓(xùn)練和考察過程.從拿到題目到完成整個(gè)編程，才短短一個(gè)星期?？墒菂s學(xué)到很多很多的東西，同

18、時(shí)不僅可以穩(wěn)固了以前所學(xué)過的知識，而且增強(qiáng)了自己的分析和調(diào)試能力。這次我抽到的題目是圖的遍歷，這是之前的一道上機(jī)題，只是要求有點(diǎn)不同罷了。因此，開始準(zhǔn)備實(shí)驗(yàn)比較晚，覺得即使實(shí)驗(yàn)中遇到困難了，到時(shí)問一下同學(xué)一會就能解決的。而且在寫程序過程中一直把重點(diǎn)放在深度優(yōu)先遍歷和廣度優(yōu)先遍歷那部分，覺得那才是整個(gè)課題的重點(diǎn)?？墒橇钗覜]想到的是，在用鄰接表創(chuàng)建圖的過程中就出現(xiàn)問題了，在CreatAdjList()函數(shù)中，在進(jìn)入創(chuàng)建頂點(diǎn)信息的for循環(huán)之后，直接跳出了CreatAdjList()函數(shù)。本能的去查看循環(huán)條件可是當(dāng)確定循環(huán)條件沒錯(cuò)時(shí)，真的對它素手無冊了。請教了幾個(gè)同學(xué)，在那調(diào)試了半天也沒結(jié)果。后來在

19、機(jī)房一位經(jīng)常調(diào)試程序的同學(xué)，一眼便看出了問題所在。是因?yàn)樯倭艘粋€(gè)接受字符的getchar:函數(shù)。照他說的在一些地方增加了getchar函數(shù)，調(diào)試了一下，真的能順利創(chuàng)建了。小小高興了一番！回去時(shí)忘保存修改稿，于是在自己的電腦上改，可是怎么都創(chuàng)建不成功。于是就在程序中瞎試，幾乎把getchar在哪都試了，最后搞了半天也不成。就在網(wǎng)上拼命找getchar函數(shù)的用法，“getchar；的用法很多：一種就是你這個(gè)程序用到的活空回車符這種情況一般發(fā)生在在循環(huán)中涉及到輸入的情況；還有一種是某些編譯平臺IDE)在運(yùn)行程序時(shí)并沒有在程序運(yùn)行后給人看結(jié)果的時(shí)間這時(shí)候在程序最后加上getchar就能造成程序的暫停給程序員度結(jié)果的時(shí)機(jī)”,在了解了大致的用法后，再改，可是還是不行。后來才發(fā)現(xiàn)是安裝了近一年但卻從未運(yùn)行過的運(yùn)行環(huán)境出問題了?？墒峭ㄟ^這次的經(jīng)歷讓我了解到了，其實(shí)如果要學(xué)好一門語言，平常的一些小的知識點(diǎn)自己也要多留意，不能無視。因?yàn)橐恍┛此撇黄鹧鄣男≈R點(diǎn)的殘缺就有可能導(dǎo)致你的程序整