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

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