數(shù)據(jù)結(jié)構(gòu)上機(jī)實(shí)驗(yàn)--圖-全文預(yù)覽
【正文】 f++。} printf(“該隊(duì)列的長度為:%d”,f)。if(==)printf(“該鏈隊(duì)為空”)。Q){} void LengthQueue(LinkQueue amp。} if(==)printf(“該鏈隊(duì)為空”)。next=pnext。Q){ QueuePtr p。=p。printf(“元素%d入隊(duì)成功”,e)。else printf(“該鏈隊(duì)不為空:”)。QueuePtr p。void QueueEmpty(LinkQueue Q){} void EnQueue(LinkQueue amp。Q){} ==(QueuePtr)malloc(sizeof(QNode))。typedef struct { QueuePtr front。（2）設(shè)計(jì)一個(gè)使用對(duì)頭指針和計(jì)數(shù)器的順序循環(huán)隊(duì)列抽象數(shù)據(jù)類型，其中操作包括：初始化，入隊(duì)列，出隊(duì)列，取對(duì)頭元素和判斷隊(duì)列是否為空；（3）編寫主函數(shù)進(jìn)行測(cè)試。特別是隊(duì)滿和隊(duì)空的描述方法；3．掌握棧與隊(duì)列的數(shù)據(jù)類型描述及特點(diǎn)；； 。L,int i)（5）編寫鏈表銷毀子函數(shù)void DestroyLinkList(LinkList amp。鏈表中每一個(gè)元素稱為“結(jié)點(diǎn)”，每個(gè)結(jié)點(diǎn)都應(yīng)包括兩個(gè)部分：一為用戶需要用的實(shí)際數(shù)據(jù)，二為下一個(gè)結(jié)點(diǎn)的地址。coutDestroyLinkList(L)。couti。coutx。CreatLinkList(L,j)。free(L)。while(Lnext!=NULL){ q=pnext。void DestroyLinkList(LinkList amp。pnext=qnext。amp。LinkList p,q。pnext=s。j} if(!p||ji1){ p=pnext。int j=0。p=Lnext。int i=0。} } int PrintLinkList(LinkList amp。cinpdata。Lnext=NULL。void CreatLinkList(LinkList amp。三﹑實(shí)驗(yàn)內(nèi)容：（1）（2）（3）（4）創(chuàng)建一個(gè)鏈表 在鏈表中插入元素 在鏈表中刪除一個(gè)元素 銷毀鏈表 四﹑實(shí)驗(yàn)步驟與程序include include typedef struct LNode {int data。用戶使用說明：說明如何使用你的程序，詳細(xì)列出每一步操作步驟。實(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è)置增加圖節(jié)點(diǎn)和邊的函數(shù)第二，實(shí)現(xiàn)圖形化輸出圖的路徑的功能第三，主函數(shù)設(shè)計(jì)簡(jiǎn)單，不要過于累贅1)利用dfs算法衍生生成判斷是否為連通圖的連通算法2)采用graph類實(shí)現(xiàn)所有圖的所有算法，所需的數(shù)據(jù)類型均在私有成員內(nèi)，封裝 3)利用convert函數(shù)采取象意輸入，采用ABCD的節(jié)點(diǎn)輸入方式而并非轉(zhuǎn)化成01234再輸入。//打印路徑長度和遍歷} 時(shí)間復(fù)雜度為：n^2七．判斷連通圖算法template bool Graph::judgegraph(){ DFS(convert(vertex[0]))。amp。s[v] = 1。path[v]=1。if(disk[i]!= maxs)path[i] = v。for(int i = 0。i++){if(vset[i] == sn2)vset[i] = sn1。int sn2 = vset[n]。}}第8頁 北京郵電大學(xué)信息與通信工程學(xué)院} } 4,時(shí)間復(fù)雜度：時(shí)間復(fù)雜度O(n2)，適合稠密圖1,關(guān)鍵思路先構(gòu)造一個(gè)只含n個(gè)頂點(diǎn)的子圖SG，然后從權(quán)值最小的邊開始，若它的添加不使SG中產(chǎn)生回路，則在SG上加上這條邊，如此重復(fù)，直至加上n1條邊為止。j++)//設(shè)置輔助數(shù)組{if((lowcost[j]!= 0 amp。j++)//循環(huán)n1次{int k = Mininum(lowcost)。lowcost[i] = arc[0][i]。(VU)的最小權(quán)值邊第6頁 北京郵電大學(xué)信息與通信工程學(xué)院第7頁 北京郵電大學(xué)信息與通信工程學(xué)院3。//當(dāng)存在回路時(shí)，則連通深一層遍歷} 時(shí)間復(fù)雜度：O(n2)空間復(fù)雜度：棧的深度O(n)輔助空間O(n)第4頁 北京郵電大學(xué)信息與通信工程學(xué)院三．廣度遍歷BFS ①訪問頂點(diǎn)v ②依次訪問v的所有未被訪問的鄰接點(diǎn)v1,v2,v3…③分別從v1,v2,v3…出發(fā)依次訪問它們未被訪問的鄰接點(diǎn) ④反復(fù)①②③，直到所有和v路徑相通的頂點(diǎn)都被訪問到；，visited[v]=1(隊(duì)列非空) v=隊(duì)頭元素出隊(duì) 訪問隊(duì)頭元素的所有未訪問的鄰接點(diǎn) 時(shí)間復(fù)雜度：O(n2)空間復(fù)雜度：輔助空間O(n)——普里姆算法1,關(guān)鍵思路一般情況下，假設(shè)n個(gè)頂點(diǎn)分成兩個(gè)集合：U(包含已落在生成樹上的結(jié)點(diǎn))和VU(尚未落在生成樹上的頂點(diǎn))，則在所有連通U中頂點(diǎn)和VU中頂點(diǎn)的邊中選取權(quán)值最小的邊。j vnum。//采用無向圖帶權(quán)值的鄰接矩陣} cout for(k = 0。//初始化權(quán)值的大小}visited[k] = 0。kfor(i = 0。for(k = 0。 存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)：1．不帶權(quán)值的無向圖鄰接矩陣第1頁 北京郵電大學(xué)信息與通信工程學(xué)院[備注]：、BFS、DFS 采用無權(quán)值的無向圖鄰接矩陣存儲(chǔ)方式 、KRUSKAL、 關(guān)鍵算法分析第2頁 北京郵電大學(xué)信息與通信工程學(xué)院一．圖的鄰接矩陣構(gòu)造函數(shù)：： template Graph::Graph(f a[], int n, int e)//帶權(quán)值的圖的構(gòu)造函數(shù) { int i, j, k, height。如果不連通，求連通分量的個(gè)數(shù)（3）編寫算法，判斷圖中任意兩個(gè)頂點(diǎn)的連通性（4）編寫算法，判斷圖中是否存在回路。第一篇：數(shù)據(jù)結(jié)構(gòu)上機(jī)實(shí)驗(yàn)圖數(shù)據(jù)結(jié)構(gòu)上機(jī)實(shí)驗(yàn)六實(shí)驗(yàn)內(nèi)容:圖的基本操作實(shí)驗(yàn)要求:1)))：可單獨(dú)完成，也可兩人一組。（2）編寫算法，判斷圖的連通性。圖的基本功能：圖的建立圖的銷毀深度優(yōu)先遍歷圖廣度優(yōu)先遍歷圖使用普里姆算法生成最小生成樹使用克魯斯卡爾算法生成最小生成樹求指定頂點(diǎn)到其他各頂點(diǎn)的最短路徑其他：比如連通性判斷等自定義操作編寫測(cè)試main()函數(shù)測(cè)試圖的正確性本實(shí)驗(yàn)要求掌握?qǐng)D基本操作的實(shí)現(xiàn)方法，了解最小生成樹的思想和相關(guān)概念，了解最短路徑的思想和相關(guān)概念，學(xué)習(xí)使用圖解決實(shí)際問題的能力。arum = e。}//初始化頂點(diǎn)for(k = 0。if(i == k)arc[k][i] = 0。arc[convert(s2)][convert(s1)] = arc[convert(s1)][convert(s2)]。i++){if(arc[k][i] ==1)cout else cout //打印鄰接矩陣的格式}cout } cout 第3頁 北京郵電大學(xué)信息與通信工程學(xué)院有構(gòu)造可知，初始化時(shí)其時(shí)間復(fù)雜度：O(n2)二．深度優(yōu)先便利DFS:①從某頂點(diǎn)v出發(fā)并訪問②訪問v的第一個(gè)未訪問的鄰接點(diǎn)w，訪問w的第一個(gè)未訪問的鄰接點(diǎn)u，……③若當(dāng)前頂點(diǎn)的所有鄰接點(diǎn)都被訪問過，則回溯，從上一級(jí)頂點(diǎn)的下一個(gè)未訪問過的頂點(diǎn)開始深度優(yōu)先遍歷④直到所有和v路徑相通的頂點(diǎn)都被訪問到； ：深度優(yōu)先遍歷示意圖 ：template void Graph::DFS(int v){ cout for(int j = 0。(arc[v][j] = 1))DFS(j)。// U224。i++)//輔助數(shù)組存儲(chǔ)所有到的V0邊{adjvex[i] = 0。j vnum。j vnum。adjvex[j] = k。int
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1