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

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