圖的鄰接表存儲(chǔ)實(shí)現(xiàn)及深度優(yōu)先遍歷.doc

第四次實(shí)驗(yàn)報(bào)告 圖的鄰接表存儲(chǔ)實(shí)現(xiàn)及深度優(yōu)先遍歷 學(xué)號(hào)0708140119 電子072 姓名 陸萍萍一、 問(wèn)題描述1、 程序所能達(dá)到的基本功能 構(gòu)建以鄰接表形式存儲(chǔ)的表及實(shí)現(xiàn)深度優(yōu)先遍歷并輸出結(jié)果。 2、 輸入的形式和輸入值的范圍： 根據(jù)提示進(jìn)行輸入：先輸入要構(gòu)建的表的結(jié)點(diǎn)數(shù)和邊數(shù)，要求是整型；輸入各結(jié)點(diǎn)的代號(hào)，這里用char型，也可在源程序中改變其它形式；輸入各邊的頭結(jié)點(diǎn)和尾結(jié)點(diǎn)的代號(hào)；3、 輸出的形式 若正常輸入，則輸出深度優(yōu)先遍歷的最后結(jié)果。用各結(jié)點(diǎn)的代碼表示。測(cè)試數(shù)據(jù)要求第一組數(shù)據(jù)： 結(jié)點(diǎn)數(shù)和邊數(shù)：4 4 結(jié)點(diǎn)名稱(chēng)：a b c d 邊：a-b a-c b-c c-d 輸出a-b-c-d-over!第二組數(shù)據(jù)：圖如下：輸出a-b-c-d-e-f-g-over!4、 概要設(shè)計(jì)1、 抽象數(shù)據(jù)類(lèi)型，它們的作用/圖的結(jié)點(diǎn)類(lèi)templateclass TVex;/圖類(lèi)templateclass Graph/鏈表存儲(chǔ)2主程序流程及模塊調(diào)用關(guān)系(1) 主程序模塊： void main構(gòu)造一個(gè)圖，對(duì)T實(shí)例化（char）。調(diào)用Graph中的Create函數(shù)；調(diào)用Graph中的DFS函數(shù)；（2）調(diào)用關(guān)系如下TemplateTlinklistTemplateTvex TemplateGraph2、 核心算法的粗線(xiàn)條偽碼 5、 詳細(xì)設(shè)計(jì)（要求主要變量和語(yǔ)句加注釋?zhuān)?、 抽象數(shù)據(jù)類(lèi)型的實(shí)現(xiàn)：包括類(lèi)型定義和各個(gè)操作的實(shí)現(xiàn)。1) TVex的詳細(xì)設(shè)計(jì)（1）私有數(shù)據(jù)類(lèi)型的定義private： T m_elem;TLinklist m_arcs; 2)Graph的詳細(xì)設(shè)計(jì)（1）私有數(shù)據(jù)類(lèi)型的定義private：TVex Vextexmaxnum;int vexnum;int arcnum;int kind;int symbolmaxnum;（2）公有函數(shù)成員的定義Graph()；void Create();int LocateVex(T v);void DFS();void DFS_IN(int i); (3)具體實(shí)現(xiàn) templatevoid Graph:Create() T v1,v2; int i,j; cout*基本信息*endl; coutvexnumarcnum; cout*結(jié)點(diǎn)*endl; for(int l=0;lvexnum;l+) cout請(qǐng)輸入第l+1Vextexl.m_elem; cout*邊數(shù)*endl; for(int k=0;karcnum;k+) cout請(qǐng)輸入第k+1v1v2; i=LocateVex(v1); j=LocateVex(v2); Vextexi.m_arcs.InsertLate(j); Vextexj.m_arcs.InsertLate(i); cout*結(jié)果*endl;templateint Graph:LocateVex(T v) for(int i=0;ivexnum&Vextexi.m_elem!=v;i+); if(i=vexnum) return -1; else return i;templatevoid Graph:DFS() DFS_IN(0);coutover!endl;templatevoid Graph:DFS_IN(int i)int index; symboli=1; coutVextexi.m_elem; for(int j=0;j+) index=Vextexi.m_arcs.GetElem(j+1); if(index!=-1) if(symbolindex!=1) DFS_IN(index);else break; 2、 其他主要算法的實(shí)現(xiàn)將次要算法均設(shè)為Graph的公有函數(shù)成員3、 主程序的實(shí)現(xiàn)Void main()huffmanTree h;int *ww,n;char *cc;coutn;ww=new intn;cc=new charn;cout請(qǐng)依次輸入節(jié)點(diǎn)名稱(chēng)和權(quán)重：endl;for(int i=1;i=n;i+)cout第i個(gè)endl;coutcci-1;coutwwi-1;h.CreatehuffmanTree(cc,ww,n);h.huffmanTreecoding();四 .調(diào)試分析1、 設(shè)計(jì)與調(diào)試過(guò)程中遇到的問(wèn)題及分析、體會(huì)（1） 這個(gè)實(shí)驗(yàn)較簡(jiǎn)單，經(jīng)過(guò)對(duì)書(shū)本上已經(jīng)給出的c版程序的分析，很容易就寫(xiě)出了對(duì)整個(gè)實(shí)驗(yàn)的大體思路。（2） 這個(gè)程序不難，但前提是Tlinklist已經(jīng)做得做夠全面，在這個(gè)實(shí)驗(yàn)中發(fā)現(xiàn)了Tlinklist的很多不足，經(jīng)過(guò)改進(jìn)，才使得程序簡(jiǎn)單明了，如在其中增加了獲取長(zhǎng)度，獲取數(shù)據(jù)，在鏈表麼增加數(shù)據(jù)幾個(gè)函數(shù)，解決很多問(wèn)題。（3） 該程