1、數(shù)據(jù)結(jié)構(gòu)實驗報告標(biāo)題：圖1.存儲圖的鄰接矩陣和鄰接表(a)需求分析對于下圖所示的有向圖g，編寫一個程序來完成以下功能：1.建立g的鄰接矩陣并輸出2.從g的鄰接矩陣生成一個鄰接表并輸出3.然后從2的鄰接表中生成相應(yīng)的鄰接矩陣并輸出(2)系統(tǒng)設(shè)計1.此程序中使用的所有抽象數(shù)據(jù)類型的定義；typedef結(jié)構(gòu) int no信息類型信息； vertextype/頂點類型typedef結(jié)構(gòu)/圖形的定義 int edgesmaxvmaxv；int vexnum，arcnumvextype vexmaxv； mgraph/圖的鄰接矩陣類型typedef結(jié)構(gòu)陽極/弧的節(jié)點結(jié)構(gòu)類型 int adjvexstruc

2、t陽極* nextarc信息類型信息； arcnode頂點類型定義；typedef結(jié)構(gòu)vnode /與標(biāo)頭相鄰的節(jié)點類型頂點數(shù)據(jù)；arcnode * firstarc/指向第一個弧 vnodetypedef vnode adjlistmaxv；/adjlist是鄰接表類型typedef結(jié)構(gòu) adjlist adjlist/鄰接表int n，e； algraph/圖的相鄰表類型2.主程序流程，各程序模塊間的層次調(diào)用關(guān)系，函數(shù)調(diào)用關(guān)系圖：主()dispadj(g)；輸出鄰接表gdispmat(g)；輸出鄰接矩陣gmattolist(g，g)；將鄰接矩陣g轉(zhuǎn)換成鄰接表g3.列出各功能模塊的主要功能和

3、輸入輸出參數(shù)空matto列表(圖g，算法g)將鄰接矩陣g轉(zhuǎn)換成鄰接表g。void dispmat(mgraph g)輸出鄰接矩陣g?？誨ispadj(代數(shù)* g)輸出鄰接表g。int out度(代數(shù)* g，int v)找出圖中每個頂點的度(3)調(diào)試分析調(diào)試過程中仍有一些拼寫錯誤，經(jīng)過檢查可以及時糾正。有些是語法設(shè)計中的小錯誤，比如一些參數(shù)的初始值設(shè)置錯誤，使得程序調(diào)試出錯。經(jīng)過小組討論和分析，這些結(jié)果得到了修正，算法的性能得到了提高，時間復(fù)雜度也盡可能地降低了。將鄰接矩陣g轉(zhuǎn)化為鄰接表g并輸出鄰接表g的算法時間復(fù)雜度為o (n 2)。通過這次實驗，我們對圖形的存儲方法有了更深的印象。(4)測試

4、結(jié)果測試結(jié)果：(1)有向圖g的鄰接矩陣是0 1 0 40 0 9 23 5 8 00 0 6 0(2)由圖g的鄰接矩陣轉(zhuǎn)換而來的鄰接表是：0:1 31:2 32:0 1 23:2(5)用戶手冊不需要輸入?yún)?shù)(6)附錄源程序#包括#包括# define xv 100/最大頂點數(shù)#定義inf 32767 /inf意味著typedef int infotypetypedef結(jié)構(gòu)int no/頂點數(shù)信息類型信息；/頂點其他信息 vertextype/頂點類型typedef結(jié)構(gòu)/圖形的定義整數(shù)邊maxvmaxv；/鄰接矩陣int vexnum，arcnum/頂點數(shù)，弧數(shù)vextype vexmaxv；/

5、存儲頂點信息 mgraph/圖的鄰接矩陣類型typedef結(jié)構(gòu)陽極/弧的節(jié)點結(jié)構(gòu)類型int adjvex/弧的結(jié)束位置struct陽極* nextarc/指向下一個弧的指針信息類型信息；/用于存儲重量的弧線信息 arcnode頂點類型定義；typedef結(jié)構(gòu)vnode /與標(biāo)頭相鄰的節(jié)點類型頂點數(shù)據(jù)；/頂點信息arcnode * firstarc/指向第一個弧 vnodetypedef vnode adjlistmaxv；/adjlist是鄰接表類型typedef結(jié)構(gòu)adjlist adjlist/鄰接表int n，e；/圖中的頂點數(shù)n和邊數(shù)e algraph/圖的相鄰表類型空matto列表(

6、m圖g，算法* g)/將鄰接矩陣g轉(zhuǎn)換為鄰接表 i，j，n=g . vex num；/n是頂點的數(shù)量arcnode *p。g=(algraph *)malloc(sizeof(algraph)；對于(i=0；iadjlisti。第一個弧=空；對于(i=0；i=0；j -)if (g.edgesij！=0)/鄰接矩陣的當(dāng)前元素不是0p=(arcnode *)malloc(sizeof(arcnode)；/創(chuàng)建節(jié)點*pp-adj vex=j；p-info=g . edgesij；p-nextarc=g-adjlisti.firstarc/將*p鏈到鏈表后g-adjlisti.第一弧=p；

7、g-n=n .g-e=g弧數(shù)；void dispmat(管理圖形g)/輸出鄰接矩陣gint i，j；對于(i=0；在；在p=g-adjlisti.firstarcif (p！=空)打印格式(=: ，1)；而(p！=空)printf(=，p-adj vex)；p=p-下一個??；printf( n )；int outender(algraph * g，int v)/求圖中每個頂點的出度arcnode *p .int n=0；p=g-adjlistv.firstarc同時(p！=空) n；p=p-下一個??；返回n；void main()int i，j；g1格拉夫；代數(shù)* g；int amaxv4=0，1，0，4，0，0，9，2，3，5，8，0，0，0，6，0，；g .vex num=4；g . arc num=8；對于(i=0；在德國)；/輸入頂點數(shù)和邊數(shù)scanf(% c ，