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

1、電腦科學(xué)與技術(shù)專業(yè)課程設(shè)計任務(wù)書學(xué)生專業(yè)班級學(xué)號題目圖的遍歷課題性質(zhì)其他課題來源自擬課題指導(dǎo)教師同組主要內(nèi)容建立圖的存儲結(jié)構(gòu)輸出兩種遍歷任務(wù)要求對任息給正的圖頂點數(shù)和邊數(shù)自正義，建立匕的鄰接表輸出，然后利用棧的五種基本運(yùn)算活空堆棧，壓棧，彈出，取棧頂元素，判空棧實現(xiàn)圖的深度搜索遍歷和廣度優(yōu)先搜素遍歷算法參考文獻(xiàn)1 譚浩強(qiáng)，C程序設(shè)計第二版，北京,清華大學(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è)計論文首頁課程設(shè)計課程設(shè)計名稱：數(shù)據(jù)結(jié)構(gòu)專業(yè)班級：學(xué)生姓名：學(xué)號：指導(dǎo)教師：課程設(shè)計時間:一、需求分析對任意給定的圖頂點數(shù)和邊數(shù)自定義，建立它的鄰接表輸出，然后利用棧的五種基本運(yùn)算活空堆棧，壓棧，彈出，取棧頂元素，判空棧實現(xiàn)圖的深度搜索遍歷和廣度優(yōu)先搜素遍歷算法二、概要設(shè)計鄰接表是圖的一種鏈?zhǔn)酱鎯Y(jié)構(gòu)為，類似丁樹的孩子鏈表表法。在鄰接表中，對圖中每個頂點建立一個單鏈表，n個頂點，就要建n個鏈表。對丁無向圖，第i個單鏈表中的結(jié)點表示依賴丁頂點Vi的邊。對丁有向圖是以頂點Vi為尾的弧,這個單鏈表稱為頂點Vi的單鏈表（

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

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

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

6、0#defineTrue1#defineNull0#definemaxsize20/隊歹U的最大空間#definemaxvertexnum20/最大頂點數(shù)typedefstructnodeintadjvex;/弧指向頂點的位置structnode*next;/指向下一條弧的指針edgenode;/表結(jié)點typedefstruct/頭結(jié)點charvertex;/頂點信息edgenode*link;/指向第一條依附該頂點的弧的指釘vexnode,AdjListmaxvertexnum;typedefstruct/圖AdjListadjlist;intn,e;/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為鄰接點序號edgenode*s;charc;printf("請輸入定點數(shù)和邊數(shù)：n");scanf("%d,%d”,&G.n,&G.e);c=getchar();printf("請輸入頂點信息(

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

9、終頂點編號:n",k);scanf("%d",&j);s=(edgenode*)malloc(sizeof(edgenode);/分配頂點空間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)先遍歷，遍歷順序為: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時，即

11、該結(jié)點沒有鄰結(jié)點(if(!visitedt)(printf("%c”,G.adjlistt.vertex);/如果此時該結(jié)點沒有被訪問過，則訪問visitedt=True;continue;/即該結(jié)點沒有鄰結(jié)點，本次循環(huán)結(jié)束doif(p=NULL)/即到了圖的最底層s.top-;/沒有下個鄰接點，則退回前一個頂點p=G.adjlist*s.top.link;if(p!=NULL)t=p->adjvex;elseif(!visitedt)/該結(jié)點中p!=NULL且其沒有被訪問過printf("%c",G.adjlistt.vertex);/輸出該頂點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為起點的第一條邊，如果/p=NULLif(p=NULL)/如果該結(jié)點沒有鄰接點則輸出之if(!visitedt)printf("%c",G.adjlistt.vertex);elset=p->adjvex;/如果該結(jié)點有鄰接點，則把其鄰接點的頂點號賦值給telse/如果該結(jié)點被訪問過，且有鄰結(jié)點，p指向以當(dāng)前結(jié)點的鄰接點為起點的邊/也可能P=NULL(p

13、=p->next;if(p!=NULL)t=p->adjvex;/如果該鄰接點有鄰接點，則記下其鄰接點的位置while(s.top!=s.data);voidBFSAL(GraphG)(intv,Qmaxsize;edgenode*w;printf(-這是廣度優(yōu)先遍歷，遍歷順序為:n");intfront=0,rear=0;/輔助隊歹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+;/入隊while(front!=rear)(/隊不空front+;出隊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)建一個圖了鄰接表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ù)，使得再輸入頂點信息字符型后無法再執(zhí)行CreatAdjlist()中剩下的語句，導(dǎo)致創(chuàng)建失敗！再經(jīng)同學(xué)提醒后成功創(chuàng)建了圖。在圖的深度和廣度遍歷時，由于其出的思路不夠活晰，導(dǎo)致在寫時漏考慮了一些情況致使無法得出想要的結(jié)果。在參閱了一些資料后，將思路搞活楚后，利用非遞歸得到了想要的結(jié)果！七、測試結(jié)果八、參考文獻(xiàn)在“課程設(shè)計報告”的最后應(yīng)附上所參考的相關(guān)文獻(xiàn),參考文獻(xiàn)的書寫格式如下：書籍：作者，書名，版本，出版地，出版者，出版年，引用內(nèi)容所在頁碼論文：作者，論文篇名，刊物名

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

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

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