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

文檔來源為:從網(wǎng)絡(luò)收集整理.word版本可編輯.歡迎下載支持.【結(jié)構(gòu)】數(shù)據(jù)結(jié)構(gòu)圖的遍歷實(shí)驗(yàn)報告文檔來源為:從網(wǎng)絡(luò)收集整理.word版本可編輯.歡迎下載支持.【結(jié)構(gòu)】數(shù)據(jù)結(jié)構(gòu)圖的遍歷實(shí)驗(yàn)報告全文共14頁，當(dāng)前為第1頁?！娟P(guān)鍵字】結(jié)構(gòu)【結(jié)構(gòu)】數(shù)據(jù)結(jié)構(gòu)圖的遍歷實(shí)驗(yàn)報告全文共14頁，當(dāng)前為第1頁。數(shù)據(jù)結(jié)構(gòu)圖的遍歷實(shí)驗(yàn)報告篇一：【數(shù)據(jù)結(jié)構(gòu)】圖的保存和遍歷實(shí)驗(yàn)報告

《數(shù)據(jù)結(jié)構(gòu)B》實(shí)驗(yàn)報告

系計(jì)算機(jī)與電子專業(yè)級班姓名學(xué)號XX年10月9日

1.上機(jī)題目：圖的保存和遍歷

2.詳細(xì)設(shè)計(jì)

#include

#defineGRAPHMAX10

#defineFALSE0

#defineTRUE1

#defineerrorprintf

#defineQueueSize30

typedefstruct

{

charvexs[GRAPHMAX];

intedges[GRAPHMAX][GRAPHMAX];

intn,e;

}MGraph;

intvisited[10];

typedefstruct

{

intfront,rear,count;

intdata[QueueSize];

}CirQueue;

voidInitQueue(CirQueue*Q)

{

Q->front=Q->rear=0;

Q->count=0;

}

intQueueEmpty(CirQueue*Q)

{

returnQ->count=QueueSize;

}

intQueueFull(CirQueue*Q)

{

returnQ->count==QueueSize;

【結(jié)構(gòu)】數(shù)據(jù)結(jié)構(gòu)圖的遍歷實(shí)驗(yàn)報告全文共14頁，當(dāng)前為第2頁。}

voidEnQueue(CirQueue*Q,intx)

{

if(QueueFull(Q))

error("Queueoverflow");

else

{Q->count++;

Q->data[Q->rear]=x;

Q->rear=(Q->rear+1)%QueueSize;

}

}

intDeQueue(CirQueue*Q)

{

inttemp;

if(QueueEmpty(Q))

{error("Queueunderflow");

returnNULL;

}

else

{temp=Q->data[Q->front];Q->count--;

Q->front=(Q->front+1)%QueueSize;

returntemp;

}

}

voidCreateMGraph(MGraph*G)

{

inti,j,k;

charch1,ch2;

printf("\n\t\t請輸入定點(diǎn)數(shù)，邊數(shù)并按回車（格式如：3，4）：");

scanf("%d,%d",

&(G->n),&(G->e));

for(i=0;in;i++)

{getchar();

printf("\n\t\t請輸入第%d個定點(diǎn)數(shù)并按回車：",i+1);

scanf("%c",&(G->vexs[i]));

}

for(i=0;in;i++)

for(j=0;jn;j++)

G->edges[i][j]=0;

【結(jié)構(gòu)】數(shù)據(jù)結(jié)構(gòu)圖的遍歷實(shí)驗(yàn)報告全文共14頁，當(dāng)前為第3頁。for(k=0;ke;k++)

{getchar();

printf("\n\t\t請輸入第%d條邊的頂點(diǎn)序號（格式如：i,j）：",k+1);

scanf("%c,%c",&ch1,&ch2);

for(i=0;ch1!=G->vexs[i];i++);

for(j=0;ch2!=G->vexs[j];j++);

G->edges[i][j]=1;

}

}

voidDFSM(MGraph*G,inti)

{

intj;

printf("\n\t\t深度優(yōu)先遍歷序列：%c\n",G->vexs[i]);

visited[i]=TRUE;

for(j=0;jn;j++)

if(G->edges[i][j]==1&&visited[j]!=1)////////////////

DFSM(G,j);

}

voidBFSM(MGraph*G,intk)

{inti,j;

CirQueueQ;

InitQueue(&Q);

printf("\n\t\t廣度優(yōu)先遍歷序列：%c\n",G->vexs[k]);

visited[k]=TRUE;

EnQueue(&Q,k);

while(!QueueEmpty(&Q))

{i=DeQueue(&Q);

for(j=0;jn;j++)

if(G->edges[i][j]==1&&visited[j]!=1)

{visited[j]=TRUE;

EnQueue(&Q,j);

}

}

}

voidDFSTraverseM(MGraph*G)

{

inti;

for(i=0;in;i++)

visited[i]=FALSE;

【結(jié)構(gòu)】數(shù)據(jù)結(jié)構(gòu)圖的遍歷實(shí)驗(yàn)報告全文共14頁，當(dāng)前為第4頁。for(i=0;in;i++)

if(!visited[i])DFSM(G,i);

}

voidBFSTraverseM(MGraph*G)

{

inti;

for(i=0;in;i++)

visited[i]=FALSE;

for(i=0;in;i++)

if(!visited[i])BFSM(G,i);

}

voidmain()

{

MGraph*G,a;

charch1;

inti,j,ch2;

G=&a;

printf("\n\t\t建立一個有向圖的鄰接矩陣表示\n");

CreateMGraph(G);

printf("\n\t\t已建立一個有向圖的鄰接矩陣保存\n");

for(i=0;in;i++)

{printf("\n\t\t");

for(j=0;jn;j++)

printf("%5d",G->edges[i][j]);

}

getchar();

ch1='y';

while(ch1=='y'||ch1=='Y')

{printf("\n");

printf("\n\t\t圖的保存與遍歷");

printf("\n\t\t********************************");

printf("\n\t\t*1-----更新鄰接矩陣*");

printf("\n\t\t*2-----深度優(yōu)先遍歷*");

printf("\n\t\t*3-----廣度優(yōu)先遍歷*");

printf("\n\t\t*0-----退出*");

printf("\n\t\t********************************");

}

}printf("\n\t\t請選擇菜單號（0----3）");scanf("%d",&ch2);getchar();switch(ch2){case1:CreateMGraph(G);printf("\n\t\t圖的鄰接矩陣保存建立完成\n");break;case【結(jié)構(gòu)】數(shù)據(jù)結(jié)構(gòu)圖的遍歷實(shí)驗(yàn)報告全文共14頁，當(dāng)前為第5頁。2:DFSTraverseM(G);break;case3:BFSTraverseM(G);break;case0:ch1='n';break;default:printf("\n\t\t輸出錯誤！清重新輸入！");}

3.調(diào)試分析

（1）調(diào)試過程中主要遇到哪些問題？是如何解決的？

由于實(shí)習(xí)之初對鄰接表的保存結(jié)構(gòu)了解不是很清楚，所以在運(yùn)行出了一個小錯誤，即在輸出鄰接表時，每個結(jié)點(diǎn)都少了一個鄰接點(diǎn)。通過仔細(xì)分析，發(fā)現(xiàn)是輸出鄰接表的語句不對，其中的for（）循環(huán)語句中的控制條件：p->next!=NULL出了問題。將其改成p!=NULL后，鄰接表便可順利輸出。下面就是經(jīng)修改后以有向圖G1和無向圖G2為例的程序運(yùn)行結(jié)果

（2）經(jīng)驗(yàn)和體會：

必須培養(yǎng)嚴(yán)謹(jǐn)?shù)目茖W(xué)態(tài)度。自己在編程時經(jīng)常因?yàn)橐恍╊愃朴凇吧倭朔痔枴钡男″e誤而導(dǎo)致錯誤，不夠認(rèn)真細(xì)致，這給自己帶來了許多麻煩。編程是一件十分嚴(yán)謹(jǐn)?shù)氖虑?，容不得馬虎。所以在今后自己一定要培養(yǎng)嚴(yán)謹(jǐn)?shù)目茖W(xué)態(tài)度。我想這不僅是對于程序設(shè)計(jì)，做任何事都應(yīng)如此。

4.測試結(jié)果

采用測試數(shù)據(jù)，列出實(shí)際的輸入、輸出結(jié)果。

篇二：數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)-圖的遍歷和最小生成樹

實(shí)驗(yàn)名稱：圖的遍歷和最小生成樹

實(shí)驗(yàn)內(nèi)容：

給定無向帶權(quán)圖G如下，

1.請分別用深度優(yōu)先和廣度優(yōu)先兩種方法從結(jié)點(diǎn)v1開始對G進(jìn)行遍歷。

2.構(gòu)造G的最小生成樹。

編程完成上述功能。

要求：

1.必須完成圖的保存功能。圖的輸入可由命令行完成。

2.按遍歷到的先后順序依次輸出G中各結(jié)點(diǎn)內(nèi)容。

3.以文本形式輸出生成樹中各條邊以及它們的權(quán)值。

一、概要設(shè)計(jì)

圖的保存使用數(shù)組表示法，即鄰接矩陣保存，結(jié)構(gòu)體包含圖的鄰接矩陣，當(dāng)前頂點(diǎn)數(shù)和弧數(shù)。圖的初始化使用二重循環(huán)得到頂點(diǎn)和表的權(quán)值，鄰接矩陣的打印使用二重for循環(huán)。然后把圖各邊的權(quán)值按從小到大排序；然后依次把最小邊加入進(jìn)來，即生成最小生成樹?？唆斔箍査惴ǎ杭僭O(shè)WN=(V,{E})是一個含有n個頂點(diǎn)的連通網(wǎng)，按照構(gòu)造最小生成樹的過程為：先構(gòu)造一個只含n個頂點(diǎn)，而邊集為空的子圖，之后，從網(wǎng)的邊集E中選取一條權(quán)值最小的邊，若該條邊的兩個頂點(diǎn)分屬不同的樹，則將其加入子圖，反之，若該條邊的兩個頂點(diǎn)已落在同一棵樹上，則不可取，而應(yīng)該取下一條權(quán)值最小的邊再試之。依次類推，直至只有一棵樹，也即子圖中含有n-1條邊為止。

圖的抽象數(shù)據(jù)類型:

ADTGraph{

數(shù)據(jù)對象V:V是具有相同特性的數(shù)據(jù)元素的集合,稱為點(diǎn)集.數(shù)據(jù)關(guān)系R:

R={VR}

【結(jié)構(gòu)】數(shù)據(jù)結(jié)構(gòu)圖的遍歷實(shí)驗(yàn)報告全文共14頁，當(dāng)前為第6頁。VR={(v,w)|v,w屬于V,(v,w)表示v和w之間存在的路徑}

基本操作P:

CreatGraph(&G,V,VR)

初始條件:V是圖的頂點(diǎn)集,VR是圖中弧的集合.

操作結(jié)果:按V和VR是定義構(gòu)造圖G.

Sort(edge*,MGraph*)

初始條件:圖G存在，各邊權(quán)值已知；

操作結(jié)果:對權(quán)值進(jìn)行排序；

Find(int*,int)

初始條件:前者為已存在的集合，后者為集合中的元素；

操作結(jié)果:查找函數(shù)，確定后者所屬子集；

MiniSpanTree(MGraph*)

初始條件:圖G存在，各邊權(quán)值已知；

操作結(jié)果:生成最小樹；

Swapn(edge*,int,int)

初始條件:圖G存在，各邊權(quán)值已知；

操作結(jié)果:交換某兩個邊的權(quán)值；

2圖的保存結(jié)構(gòu)

typedefstruct

{

intadj;

intweight;

}AdjMatrix[MAX][MAX];

typedefstruct

{

AdjMatrixarc;

intvexnum,arcnum;

}MGraph;

typedefstruct

{

intbegin;

intend;

intweight;

}edge;

3本程序包含的模塊

}

1）初始化操作，結(jié)構(gòu)體定義；

2）函數(shù)聲明模塊；

3）函數(shù)定義模塊；

【結(jié)構(gòu)】數(shù)據(jù)結(jié)構(gòu)圖的遍歷實(shí)驗(yàn)報告全文共14頁，當(dāng)前為第7頁。4）主程序模塊

Main()

{

調(diào)用函數(shù)生成圖；

判斷圖是否為空；（空則從新輸入）

調(diào)用函數(shù)生成最小生成樹；

退出；

二、詳細(xì)設(shè)計(jì)

#include

#include

usingnamespacestd;

#defineint_max10000

#defineinf9999

#definemax20

//…………鄰接矩陣定義……typedefstructArcCell

{

intadj;

char*info;

}ArcCell,AdjMatrix[max][max];

typedefstruct

{

charvexs[max];

AdjMatrixarcs;

intvexnum,arcnum;

}MGraph_L;

//^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^intlocalvex(MGraph_LG,charv)//返回V的位置

{

inti=0;

while(G.vexs[i]!=v)

++i;

returni;

}

intcreatMGraph_L(MGraph_L&G)//創(chuàng)建圖用鄰接矩陣表示

{

charv1,v2;

inti,j,w;

G.vexnum=7;G.arcnum=12;

for(i=0;i!=G.vexnum;++i)

【結(jié)構(gòu)】數(shù)據(jù)結(jié)構(gòu)圖的遍歷實(shí)驗(yàn)報告全文共14頁，當(dāng)前為第8頁。{

coutcin>>G.vexs[i];

}

for(i=0;i!=G.vexnum;++i)

for(j=0;j!=G.vexnum;++j)

{

G.arcs[i][j].adj=int_max;

G.arcs[i][j].info=NULL;

}

G.arcs[0][1].adj=24;

G.arcs[1][0].adj=24;

G.arcs[0][2].adj=8;

G.arcs[2][0].adj=8;

G.arcs[0][3].adj=15;

G.arcs[3][0].adj=15;

G.arcs[1][4].adj=6;

G.arcs[4][1].adj=6;

G.arcs[1][6].adj=3;

G.arcs[6][1].adj=3;

G.arcs[2][4].adj=7;

G.arcs[4][2].adj=7;

G.arcs[2][5].adj=3;

G.arcs[5][2].adj=3;

G.arcs[3][5].adj=5;

G.arcs[5][3].adj=5;

G.arcs[3][6].adj=4;

G.arcs[6][3].adj=4;

G.arcs[4][5].adj=2;

G.arcs[5][4].adj=2;

G.arcs[4][6].adj=9;

G.arcs[6][4].adj=9;

G.arcs[5][6].adj=3;

G.arcs[6][5].adj=3;

coutreturnG.vexnum;

}

voidljjzprint(MGraph_LG)//鄰接矩陣的輸出

{

inti,j;

for(i=0;i!=G.vexnum;++i)

【結(jié)構(gòu)】數(shù)據(jù)結(jié)構(gòu)圖的遍歷實(shí)驗(yàn)報告全文共14頁，當(dāng)前為第9頁。{

for(j=0;j!=G.vexnum;++j)

coutcout}

}

intvisited[max];//訪問標(biāo)記

intwe;

typedefstructarcnode//弧結(jié)點(diǎn)

{

intadjvex;//該弧指向的頂點(diǎn)的位置

structarcnode*nextarc;//弧尾相同的下一條弧

char*info;//該弧信息

}arcnode;

typedefstructvnode//鄰接鏈表頂點(diǎn)頭接點(diǎn)

{

chardata;//結(jié)點(diǎn)信息

arcnode*firstarc;//指向第一條依附該結(jié)點(diǎn)的弧的指針

}vnode,adjlist;

typedefstruct//圖的定義

{

adjlistvertices[max];

intvexnum,arcnum;

intkind;

}algraph;

//…………隊(duì)列定義……typedefstructqnode

{

intdata;

structqnode*next;

}qnode,*queueptr;

typedefstruct

{

queueptrfront;

queueptrrear;

}linkqueue;

//………………………typedefstructacr

{

intpre;//弧的一結(jié)點(diǎn)

intbak;//弧另一結(jié)點(diǎn)

intweight;//弧的權(quán)

}edg;

【結(jié)構(gòu)】數(shù)據(jù)結(jié)構(gòu)圖的遍歷實(shí)驗(yàn)報告全文共14頁，當(dāng)前為第10頁。intcreatadj(algraph&gra,MGraph_LG)//用鄰接表保存圖{

inti=0,j=0;

arcnode*arc,*tem,*p;

for(i=0;i!=G.vexnum;++i)

{

gra.vertices[i].data=G.vexs[i];

gra.vertices[i].firstarc=NULL;

}

for(i=0;i!=G.vexnum;++i)

{

for(j=0;j!=G.vexnum;++j)

{

if(gra.vertices[i].firstarc==NULL)

{

if(G.arcs[i][j].adj!=int_max&&j!=G.vexnum)

{

arc=(arcnode*)malloc(sizeof(arcnode));

arc->adjvex=j;

gra.vertices[i].firstarc=arc;

arc->nextarc=NULL;

p=arc;

++j;

while(G.arcs[i][j].adj!=int_max&&j!=G.vexnum)

{

tem=(arcnode*)malloc(sizeof(arcnode));

tem->adjvex=j;

gra.vertices[i].firstarc=tem;

tem->nextarc=arc;

arc=tem;

++j;

}

--j;

}

}

else

{

if(G.arcs[i][j].adj!=int_max&&j!=G.vexnum)

{

arc=(arcnode*)malloc(sizeof(arcnode));

【結(jié)構(gòu)】數(shù)據(jù)結(jié)構(gòu)圖的遍歷實(shí)驗(yàn)報告全文共14頁，當(dāng)前為第11頁。arc->adjvex=j;

p->nextarc=arc;

篇三：數(shù)據(jù)結(jié)構(gòu)圖的遍歷實(shí)驗(yàn)報告

題目：圖的遍歷的實(shí)現(xiàn)

完成日期：

一、需求分析

1.本演示程序中，輸入的數(shù)據(jù)類型均為整型數(shù)據(jù)，不允許輸入字符等其他數(shù)據(jù)類型，且需要按照提示內(nèi)容進(jìn)行輸入，成對的關(guān)系數(shù)據(jù)必須在所建立的圖中已經(jīng)存在對應(yīng)的結(jié)點(diǎn)。

2.演示程序以用戶和計(jì)算機(jī)的對話方式執(zhí)行，在計(jì)算機(jī)終端上顯示的提示信息的說明下，按照要求輸入數(shù)據(jù)，運(yùn)算結(jié)果在其后顯示。

3.本程序?qū)崿F(xiàn)分別基于鄰接矩陣和鄰接表保存結(jié)構(gòu)的有、無向圖，有、無向網(wǎng)的建立和遍歷。遍歷分DFS和BFS兩種算法，并分別以遞歸和非遞歸形式實(shí)現(xiàn)。

4.測試數(shù)據(jù)：

（1）無向圖結(jié)點(diǎn)數(shù)4弧數(shù)3結(jié)點(diǎn)：1234結(jié)點(diǎn)關(guān)系：12；13；24

（2）有向圖結(jié)點(diǎn)數(shù)6弧數(shù)6結(jié)點(diǎn)：123456結(jié)點(diǎn)關(guān)系：12；13；24；35；36；25

二、概要設(shè)計(jì)

為實(shí)現(xiàn)上述程序功能，圖的保存結(jié)構(gòu)分為鄰接矩陣和鄰接表兩種。遍歷過程中借助了棧和隊(duì)列的保存結(jié)構(gòu)。

1.鄰接矩陣保存結(jié)構(gòu)的圖定義：

ADTmgraph{

數(shù)據(jù)對象V：V是具有相同特性的的數(shù)據(jù)元素的集合，成為頂點(diǎn)集。

數(shù)據(jù)關(guān)系R:

R=｛VR｝

VR={|v,w?V且P(v,w),表示從v到w的弧，謂詞P(v,w)定義了弧的意義或信息}

基本操作P：

locatevex(G,mes)；

初始條件：圖G存在，mes和G中頂點(diǎn)有相同的特征。

操作結(jié)果：若G中存在頂點(diǎn)u，則返回該頂點(diǎn)在圖中位置；否則返回其他信息。

createudn(&G)；

初始條件：圖G存在。

操作結(jié)果：創(chuàng)建無向圖。

createdn(&G)；

初始條件：圖G存在。

操作結(jié)果：創(chuàng)建有向圖。

createudg(&G)；

初始條件：圖G存在。

操作結(jié)果：創(chuàng)建無向網(wǎng)。

createdg(&G)；

【結(jié)構(gòu)】數(shù)據(jù)結(jié)構(gòu)圖的遍歷實(shí)驗(yàn)報告全文共14頁，當(dāng)前為第12頁。初始條件：圖G存在。

操作結(jié)果：創(chuàng)建有向網(wǎng)。

DFS(G,v)；

初始條件：圖G已經(jīng)存在并被賦值，v是圖中某個頂點(diǎn)的位置坐標(biāo)。

操作結(jié)果：深度優(yōu)先搜索遍歷圖G，訪問頂點(diǎn)時使用函數(shù)visit.

BFS(G,v)；

初始條件：圖G已經(jīng)存在并被賦值，v是圖中某個頂點(diǎn)的位置坐標(biāo)。

操作結(jié)果：廣度優(yōu)先搜索遍歷圖G，訪問頂點(diǎn)時使用函數(shù)visit.

visit(a)；

初始條件：a為圖中的某個頂點(diǎn)值。

操作結(jié)果：訪問頂點(diǎn)a，本程序中作用結(jié)果為輸出頂點(diǎn)值。

｝ADTmgraph

2.鄰接表保存結(jié)構(gòu)的圖定義：

ADTalgraph{

數(shù)據(jù)對象V：V是具有相同特性的的數(shù)據(jù)元素的集合，成為頂點(diǎn)集。

數(shù)據(jù)關(guān)系R:

R=｛VR｝

VR={|v,w?V且P(v,w),表示從v到w的弧，謂詞P(v,w)定義了弧的意義或信息}

基本操作P：

locatevex(G,mes)；

初始條件：圖G存在，mes和G中頂點(diǎn)有相同的特征。

操作結(jié)果：若G中存在頂點(diǎn)u，則返回該頂點(diǎn)在圖中位置；否則返回其他信息。

createudn(&G)；

初始條件：圖G存在。

操作結(jié)果：創(chuàng)建無向圖。

createdn(&G)；

初始條件：圖G存在。

操作結(jié)果：創(chuàng)建有向圖。

createudg(&G)；

初始條件：圖G存在。

操作結(jié)果：創(chuàng)建無向網(wǎng)。

createdg(&G)；

初始條件：圖G存在。

操作結(jié)果：創(chuàng)建有向網(wǎng)。

DFS(G,v)；

初始條件：圖G已經(jīng)存在并被賦值，v是圖中某個頂點(diǎn)的位置坐標(biāo)。

操作結(jié)果：深度優(yōu)先搜索遍歷圖G，訪問頂點(diǎn)時使用函數(shù)visit.

BFS(G,v)；

初始條件：圖G已經(jīng)存在并被賦值，v是圖中某個頂點(diǎn)的位置坐標(biāo)。

【結(jié)構(gòu)】數(shù)據(jù)結(jié)構(gòu)圖的遍歷實(shí)驗(yàn)報告全文共14頁，當(dāng)前為第13頁。操作結(jié)果：廣度優(yōu)先搜索遍歷圖G，訪問頂點(diǎn)時使用函數(shù)visit.

visit(a)；

初始條件：a為圖中的某個頂點(diǎn)值。

操作結(jié)果：訪問頂點(diǎn)a，本程序中作用結(jié)果為輸出頂點(diǎn)值。

｝ADTalgraph

3.主程序流程：

定義并創(chuàng)建圖

statuscreatgraph(mgraph&G)

{

coutintkind;

scanf("%d",&kind);

switch(kind)//通過選擇確定創(chuàng)建哪一種圖；

{

case1:returncreatedg(G);

case2:returncreatedn(G);

case3:returncreateudg(G);

case4:returncreateudn(G);

default:returnerror;

}

}

然后采用DFS或BFS進(jìn)行遍歷（訪問結(jié)果為輸出頂點(diǎn)值）。

4.函數(shù)的調(diào)用關(guān)系圖：

main

visitlocatevexlinkqueueenqueuegetheaddequeuedestroyqueue

其中，當(dāng)DFS使用遞歸算法時相關(guān)的棧操作不使用，當(dāng)BFS使用遞歸算法時相關(guān)的隊(duì)列操作仍