【正文】 et[i] = sn1。//集合sn2全部改成sn1}}j++。} } 時間復雜度O(nlogn)，適合稀疏圖六．最短路徑——Dijkstra算法 ? 按路徑長度遞增的次序產(chǎn)生源點到其余各頂點的最短路徑。? 1)設置集合s存儲已求得的最短路徑的頂點，? 2)初始狀態(tài)：s=源點v ? 3)疊代算法：? 直接與v相連的最近頂點vi,加入s ? 從v經(jīng)過vi可以到達的頂點中最短的，加入s……第10頁 北京郵電大學信息與通信工程學院emplate void Graph::ShotPath(f x)//關于最短路徑的初始化 { int v=convert(x)。for(int i = 0。i vnum。i++)//初始化路徑和點{s[i]=0。disk[i] = arc[v][i]。if(disk[i]!= maxs)path[i] = v。else path[i] =1。} s[v] = 1。disk[v] = 0。path[v]=1。for(int i = 0。i vnum。i++)//反復經(jīng)過從該點到其他點的路徑{if((v = FindMin())==1)continue。s[v] = 1。for(int j = 0。j vnum。j++)if(!s[j] amp。amp。(disk[j]arc[v][j] + disk[v])){第11頁 北京郵電大學信息與通信工程學院disk[j] = arc[v][j] + disk[v]。path[j] = v。} } Print()。//打印路徑長度和遍歷} 時間復雜度為：n^2七．判斷連通圖算法template bool Graph::judgegraph(){ DFS(convert(vertex[0]))。if(count==vnum){coutreturn false。} else {coutreturn true。} }時間復雜度：n^2：第12頁 北京郵電大學信息與通信工程學院函數(shù)流程圖：構造下面所示圖的鄰接矩陣：第13頁 北京郵電大學信息與通信工程學院 DFS PRIM算法的實現(xiàn)第14頁 北京郵電大學信息與通信工程學院第15頁 北京郵電大學信息與通信工程學院插入V0位置后打印距離并開始回溯總結問題一：prim算法中解決方法：調(diào)整循環(huán)條件，修正函數(shù)體注意有無Next的區(qū)別第16頁 北京郵電大學信息與通信工程學院問題二：BFS和DFS同時在一個類里作用時會輸出錯誤解決方案：每次BFS/DFS使用時都把visited數(shù)組初始化一遍問題三：在最短路徑，經(jīng)常出現(xiàn)了停止輸入的情況解決方法：改return為continue，并修改打印算法 通過本次實驗，基本熟練掌握了c++基本語句，尤其對圖的結構及應用有了較深了解；調(diào)試代碼時盡量做到完成一個代碼段調(diào)試一次，可以最快檢測出錯誤所在；類的封裝和調(diào)用，類的共有成員和私有成員的設置。第一，設置增加圖節(jié)點和邊的函數(shù)第二，實現(xiàn)圖形化輸出圖的路徑的功能第三，主函數(shù)設計簡單，不要過于累贅1)利用dfs算法衍生生成判斷是否為連通圖的連通算法2)采用graph類實現(xiàn)所有圖的所有算法，所需的數(shù)據(jù)類型均在私有成員內(nèi)，封裝 3)利用convert函數(shù)采取象意輸入，采用ABCD的節(jié)點輸入方式而并非轉化成01234再輸入。4)BFS中采用c++標準庫的。5)打印鄰接矩陣時，打印出非鏈接的∞符號和與自身路徑的0距離 6)判斷圖為非連通圖后，提示輸入錯誤，重新輸入圖元素第17頁第三篇：《數(shù)據(jù)結構》上機實驗的目的和要求《數(shù)據(jù)結構》上機實驗的目的和要求通過上機實驗加深對課程內(nèi)容的理解，增加感性認識，提高軟件設計、編寫及調(diào)試程序的能力。要求所編的程序能正確運行，并提交實驗報告。實驗報告的基本要求為：需求分析：陳述程序設計的任務，強調(diào)程序要做什么，明確規(guī)定：（1）輸入的形式和輸出值的范圍；（2）輸出的形式；（3）程序所能達到的功能；（4）測試數(shù)據(jù)：包括正確的輸入輸出結果和錯誤的輸入及輸出結果。概要設計：說明用到的數(shù)據(jù)結構定義、主程序的流程及各程序模塊之間的調(diào)用關系。詳細設計：提交帶注釋的源程序或者用偽代碼寫出每個操作所涉及的算法。調(diào)試分析：（1）調(diào)試過程中所遇到的問題及解決方法；（2）算法的時空分析；（3）經(jīng)驗與體會。用戶使用說明：說明如何使用你的程序，詳細列出每一步操作步驟。測試結果：列出對于給定的輸入所產(chǎn)生的輸出結果。若有可能，測試隨輸入規(guī)模的增長所用算法的實際運行時間的變化。第四篇：數(shù)據(jù)結構上機實驗報告數(shù)據(jù)結構實驗報告課程 數(shù)據(jù)結構 _ 院 系專業(yè)班級 實驗地點姓 名 學 號實驗時間 指導老師數(shù)據(jù)結構上機實驗報告1一﹑實驗名稱：實驗一——鏈表二﹑實驗目的：；，熟練掌握鏈式存儲結構的描述方法；（建表、插入、刪除等），加深對鏈表的本質的理解。三﹑實驗內(nèi)容：（1）（2）（3）（4）創(chuàng)建一個鏈表 在鏈表中插入元素 在鏈表中刪除一個元素 銷毀鏈表 四﹑實驗步驟與程序include include typedef struct LNode {int data。struct LNode *next。}Lnode, *LinkList。//假設下面的鏈表均為帶頭結點。void CreatLinkList(LinkList amp。L,int j){//建立一個鏈表L,數(shù)據(jù)為整數(shù)，數(shù)據(jù)由鍵盤隨機輸入。LinkList p,q。L=(LinkList)malloc(sizeof(Lnode))。Lnext=NULL。q=L。coutfor(int i=0。i{p=(LinkList)malloc(sizeof(Lnode))。cinpdata。pnext=qnext。qnext=p。q=p。} } int PrintLinkList(LinkList amp。L){//輸出鏈表L的數(shù)據(jù)元素LinkList p。} void LinkListLengh(LinkList amp。L){//計算鏈表L的數(shù)據(jù)元素個數(shù)。int i=0。p=Lnext。if(Lnext==NULL){} cout{coutdatap=pnext。} cout} LinkList p。p=Lnext。while(p){i++。p=pnext。} coutLinkList p,s。int j=0。p=L。while(pamp。amp。j} if(!p||ji1){ p=pnext。++j。}} coutdata=x。snext=pnext。pnext=s。return 1。int DeleteLinkList(LinkList amp。L,int i){//刪除鏈表L的第I個數(shù)據(jù)元素。LinkList p,q。int j=0。p=L。while(pnextamp。amp。j} if(!(pnext)||ji1){ p=pnext。++j。}} coutnext。pnext=qnext。i=qdata。free(q)。return 1。void DestroyLinkList(LinkList amp。L){//銷毀鏈表L。LinkList p,q。p=Lnext。while(Lnext!=NULL){ q=pnext。Lnext=q。free(p)。} p=q。free(L)。coutLinkList L。int i,j,x。coutj。CreatLinkList(L,j)。LinkListLengh(L)。PrintLinkList(L)。couti。coutx。InsertLinkList(L,i,x)。LinkListLengh(L)。PrintLink