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