數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告圖的遍歷.doc

《數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告圖的遍歷.doc》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、第3小組實(shí)驗(yàn)報(bào)告數(shù)據(jù)結(jié)構(gòu)試驗(yàn)報(bào)告實(shí)驗(yàn)四圖的存儲(chǔ)及應(yīng)用實(shí)驗(yàn)題目：圖的遍歷問(wèn)題專業(yè)班級(jí)：計(jì)科系1405班組長(zhǎng)：張紀(jì)遠(yuǎn)（）組員：周振軍（）朱新祥（）梁麗蓉（）段慧娟（）2016年6月1日18第3小組實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)類型__綜合設(shè)計(jì)__實(shí)驗(yàn)室_軟件實(shí)驗(yàn)室三__一、實(shí)驗(yàn)題目圖的存儲(chǔ)及應(yīng)用二、實(shí)驗(yàn)?zāi)康暮鸵?．掌握?qǐng)D的存儲(chǔ)思想及其存儲(chǔ)實(shí)現(xiàn)2．掌握?qǐng)D的深度、廣度優(yōu)先遍歷算法思想及其程序?qū)崿F(xiàn)3．掌握?qǐng)D的常見(jiàn)應(yīng)用算法的思想及其程序?qū)崿F(xiàn)三、需求分析1．問(wèn)題描述使用菜單實(shí)現(xiàn)圖的相關(guān)算法,如鍵盤輸入以下結(jié)點(diǎn)數(shù)據(jù)：太原、成都、北京、上海、天津

2、、大連、河北，建立一個(gè)有向圖或無(wú)向圖（自定）的鄰接表并輸出該鄰接表；在圖的鄰接表的基礎(chǔ)上計(jì)算各頂點(diǎn)的度，并輸出；以有向圖的鄰接表為基礎(chǔ)實(shí)現(xiàn)輸出它的拓?fù)渑判蛐蛄?；采用鄰接表存?chǔ)實(shí)現(xiàn)無(wú)向圖的深度優(yōu)先遍歷；采用鄰接表存儲(chǔ)實(shí)現(xiàn)無(wú)向圖的廣度優(yōu)先遍歷；采用鄰接矩陣存儲(chǔ)實(shí)現(xiàn)無(wú)向圖的最小生成樹(shù)的PRIM算法2.設(shè)計(jì)分析調(diào)用菜單項(xiàng)，分別調(diào)用相應(yīng)的子函數(shù)。注意頂點(diǎn)存儲(chǔ)地名，使用字符數(shù)組來(lái)實(shí)現(xiàn)。3.結(jié)構(gòu)類型定義typedefcharvextype[10];/*頂點(diǎn)數(shù)據(jù)類型*/typedefintedgetype;/*邊數(shù)據(jù)類型*/typede

3、fstruct{vextypevex[MAXSIZE];edgetypearc[MAXSIZE][MAXSIZE];intvexnum,arcnum;}Mgraph;typedefstructnode{intadjvex;structnode*next}EdgeNode;typedefstructnode{vextypevex;EdgeNode*firstedge;}VexNode;typedefstruct{VexNodeadjvex[MAXSIZE];18第3小組實(shí)驗(yàn)報(bào)告intn,e;}ALGraph;二、概要設(shè)計(jì)為

4、了實(shí)現(xiàn)上述程序功能，代碼如下：#include#include#includetypedefstructnode{//邊表結(jié)點(diǎn)intadj;//邊表結(jié)點(diǎn)數(shù)據(jù)域structnode*next;}node;typedefstructvnode{//頂點(diǎn)表結(jié)點(diǎn)charname[20];node*fnext;}vnode,AList[20];typedefstruct{AListList;//鄰接表intv,e;//頂點(diǎn)樹(shù)和邊數(shù)}*Graph;//建立無(wú)向鄰接表Graph

5、CreatDG(){GraphG;inti,j,k;node*s;G=malloc(20*sizeof(vnode));printf("請(qǐng)輸入圖的頂點(diǎn)數(shù)和邊數(shù)(空格隔開(kāi))：");scanf("%d%d",&G->v,&G->e);//讀入頂點(diǎn)數(shù)和邊數(shù)for(i=0;iv;i++){printf("請(qǐng)輸入圖中第%d元素：",i+1);scanf("%s",G->List[i].name);//讀入頂點(diǎn)信息18第3小組實(shí)驗(yàn)報(bào)告G->List[i].fnext=NULL;//邊表置為空表}for(k=0;ke;

6、k++){printf("請(qǐng)請(qǐng)輸入第%d條邊的兩頂點(diǎn)序號(hào)(空格隔開(kāi))：",k+1);scanf("%d%d",&i,&j);//讀入邊（Vi,Vj）的頂點(diǎn)對(duì)序號(hào);s=(node*)malloc(sizeof(node));//生成邊表結(jié)點(diǎn)s->adj=j;s->next=G->List[i].fnext;G->List[i].fnext=s;//將新結(jié)點(diǎn)*s插入頂點(diǎn)Vi的邊表頭部s=(node*)malloc(sizeof(node));s->adj=i;//鄰接點(diǎn)序號(hào)為is->next=G->List[j].fnext

7、;G->List[j].fnext=s;//將新結(jié)點(diǎn)*s插入頂點(diǎn)Vj的邊表頭部}returnG;}//有向鄰接圖GraphCreatAG(){GraphG;inti,j,k;node*q;G=malloc(20*sizeof(vnode));printf("請(qǐng)輸入圖的頂點(diǎn)數(shù)和邊數(shù)【空格隔開(kāi)】：");scanf("%d%d",&G->v,&G->e);for(i=0;iv;i++){printf("請(qǐng)輸入圖中第%d元素：",i+1);scanf("%s",&G->List[i].name);//讀入頂點(diǎn)信息G->L

8、ist[i].fnext=NULL;}for(k=0;ke;k++){printf("請(qǐng)請(qǐng)輸入第%d邊的兩頂點(diǎn)序號(hào)【空格隔開(kāi)】：",k+1);scanf("%d%d",&i,&j);18第3小組實(shí)驗(yàn)報(bào)告q=(node*)malloc(sizeof(node));//生成新邊表結(jié)點(diǎn)sq->adj=j;//鄰接點(diǎn)