數(shù)據(jù)結(jié)構(gòu)與算法實(shí)驗(yàn)報(bào)告-圖

1、數(shù)據(jù)結(jié)構(gòu)與算法實(shí)驗(yàn)報(bào)告-圖 導(dǎo)讀：就愛(ài)閱讀網(wǎng)友為您分享以下“數(shù)據(jù)結(jié)構(gòu)與算法實(shí)驗(yàn)報(bào)告-圖”的資訊，希望對(duì)您有所幫助，感謝您對(duì)的支持! q=(ArcNode *)malloc(sizeof(ArcNode); q-weight=weight; q-adjvex=m1; if(list.vexnoden1.firstArc=NULL) list.vexnoden1.firstArc=q; q-next=NULL; else q-next=list.vexnoden1.firstArc; list.vexnoden1.firstArc=q; printf(鄰接表構(gòu)造成功nntt鄰接矩陣構(gòu)造成功！n s

2、ystem( system( void inputMatric() /輸出鄰接矩陣 printf(鄰接矩陣：n printf( for(i=0;i printf( printf( for(i=0;inext) printf( printf( 10 int FirstAdjVex(int i) /返回鄰接表中該弧的第一個(gè)節(jié)點(diǎn)指向的位置 int a; if(list.vexnodei.firstArc=NULL) a=-1; else a=list.vexnodei.firstArc-adjvex; / printf(/ return a; int NextAdjVex(int i,int j)

3、/返回第i個(gè)頂點(diǎn)的鄰接表中指向j的節(jié)點(diǎn)的后面節(jié)點(diǎn)的指向 int a; for(p=list.vexnodei.firstArc;p!=NULL;p=p-next) if(p-adjvex=j) break; if(p=NULL) return -1; else if(p-next=NULL) return -1; else return p-next-adjvex; void Depth_First_Search() /深度優(yōu)先搜索 11 printf(深度優(yōu)先搜索:n for(i=0;i0;j=NextAdjVex(i,j) if(!visitedj) DFS(visited,j); voi

4、d Breadth_First_Search() /廣度優(yōu)先搜素 printf(廣度優(yōu)先搜素:n for(i=0;i list.visitedi=0; for(i=0;inext) if(!visitedp-adjvex) printf( visitedp-adjvex=1; EnQueue(p-adjvex); 13 沈 陽(yáng) 工 程 學(xué) 院 學(xué) 生 實(shí) 驗(yàn) 報(bào) 告 （課程名稱： 數(shù)據(jù)結(jié)構(gòu)與算法 ） 圖 實(shí)驗(yàn)題目： 1 一、實(shí)驗(yàn)?zāi)康?1掌握?qǐng)D的基本存儲(chǔ)方法。 2掌握有關(guān)圖的操作算法并用高級(jí)語(yǔ)言實(shí)現(xiàn)。 3熟練掌握?qǐng)D的兩種搜索路徑的遍歷方法。 4掌握?qǐng)D的有關(guān)應(yīng)用。 二、實(shí)驗(yàn)環(huán)境 Turbo C或是

5、Visual C+ 三、實(shí)驗(yàn)內(nèi)容與要求 實(shí)驗(yàn)1 建立無(wú)向圖的鄰接矩陣或鄰接表存儲(chǔ)并輸出 本題給出了一個(gè)無(wú)向圖的鄰接矩陣存儲(chǔ)表示，在此基礎(chǔ)上稍加改動(dòng)就可以實(shí)現(xiàn)有向圖、無(wú)向圖和有向網(wǎng)的鄰接矩陣表示。 實(shí)驗(yàn)2 建立圖的鄰接矩陣或鄰接表存儲(chǔ)并在此基礎(chǔ)上實(shí)現(xiàn)圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷 圖的廣度優(yōu)先遍歷用非遞歸方法很容易理解，非遞歸方法需要輔助隊(duì)列Q以及出隊(duì)、入隊(duì)函數(shù)。 四、實(shí)驗(yàn)過(guò)程及結(jié)果分析 1.程序代碼 #include #include #define MAXSIZE 50 typedef struct /鄰接矩陣結(jié)構(gòu)體 int arcsMAXSIZEMAXSIZE; /矩陣數(shù)組 char *v

6、exs; /頂點(diǎn)向量 int vexnum,arcnum; 2 int GraphKind; /圖的種類，1無(wú)向圖，2有向圖 Matric; typedef struct ArcNode /鄰接表弧的結(jié)構(gòu)體 int adjvex; /該弧指向定點(diǎn)的位置 int weight; struct ArcNode *next; ArcNode; typedef struct VexNode /鄰接表的數(shù)組節(jié)點(diǎn) char vex; ArcNode * firstArc; VexNode ; typedef struct /鄰接表的頂點(diǎn)數(shù)組 VexNode *vexnode; int *visited;

7、/儲(chǔ)存是否被檢索過(guò) int vexnum,arcnum; int GraphKind; List; typedef struct QueueNode int local; struct QueueNode *next; 3 QueueNode; typedef struct QueueNode *head; QueueNode *rear; int count; Queue; typedef struct char adjvex; int lowcost; CloseDge; CloseDge *closedge; /*-深度優(yōu)先搜索相關(guān)函數(shù)-*/ void Depth_First_Searc

8、h(); /深度優(yōu)先搜索 void DFS(int *visited,int i); int FirstAdjVex(int i); /返回鄰接表中該弧的第一個(gè)節(jié)點(diǎn)指向的位置 int NextAdjVex(int i,int j); /返回第i個(gè)頂點(diǎn)的鄰接表中指向j的節(jié)點(diǎn)的后面節(jié)點(diǎn)的指向 /*-*/ /*-廣度優(yōu)先搜索相關(guān)函數(shù)-*/ void Breadth_First_Search(); /廣度優(yōu)先搜素 void EnQueue(int i); /元素入隊(duì) int DeQueue(); /元素出隊(duì) void inputQueue();/輸出隊(duì)列中的元素 4 void BFS(int * vi

9、sited,int i); /*-*/ void create(); /創(chuàng)建鄰接矩陣,鄰接矩陣 void inputMatric();/輸出鄰接矩陣 void inputList();/輸出鄰接表 int mininum(CloseDge *closedge); int i,j,m,n; int weight; char head,rear,m1,n1; Matric matric; List list; Queue queue; QueueNode *temqueuenode; ArcNode *p,*q ; void create() /創(chuàng)建鄰接矩陣 printf(請(qǐng)輸入圖的種類：ntt1

10、.無(wú)向圖ntt2.有向圖n fflush(stdin); scanf( list.GraphKind=matric.GraphKind; system( system( printf(請(qǐng)輸入頂點(diǎn)數(shù)： fflush(stdin); 5 void BFS(int * visited,int i); /*-*/ void create(); /創(chuàng)建鄰接矩陣,鄰接矩陣 void inputMatric();/輸出鄰接矩陣 void inputList();/輸出鄰接表 int mininum(CloseDge *closedge); int i,j,m,n; int weight; char head

11、,rear,m1,n1; Matric matric; List list; Queue queue; QueueNode *temqueuenode; ArcNode *p,*q ; void create() /創(chuàng)建鄰接矩陣 printf(請(qǐng)輸入圖的種類：ntt1.無(wú)向圖ntt2.有向圖n fflush(stdin); scanf( list.GraphKind=matric.GraphKind; system( system( printf(請(qǐng)輸入頂點(diǎn)數(shù)： fflush(stdin); 5 scanf( list.vexnum=matric.vexnum; printf(請(qǐng)輸入弧數(shù)： f

12、flush(stdin); scanf( list.arcnum=matric.arcnum; queue.count=0; queue.head=NULL; queue.rear=NULL; matric.vexs=(char *)malloc(sizeof(char)*(matric.vexnum); list.vexnode=(VexNode *)malloc(sizeof(VexNode)*matric.vexnum); list.visited=(int *)malloc(sizeof(int)*list.vexnum); for(i=0;i printf(請(qǐng)輸入第%d個(gè)頂點(diǎn): ff

13、lush(stdin); scanf( list.vexnodei.vex=matric.vexsi; printf(頂點(diǎn)集輸入成功！n system( system( printf(請(qǐng)輸入弧集(輸入模式：“弧頭，弧尾,權(quán)值”,若為無(wú)權(quán)圖，則權(quán)值均輸入”1“):n for(i=0;i if(head=matric.vexsm) m1=m; for(n=0;nweight=weight; p-adjvex=n1; if(list.vexnodem1.firstArc=NULL) list.vexnodem1.firstArc=p; p-next=NULL; else p-next=list.ve

14、xnodem1.firstArc; list.vexnodem1.firstArc=p; if(matric.GraphKind=1) matric.arcsn1m1=weight; 8 q=(ArcNode *)malloc(sizeof(ArcNode); q-weight=weight; q-adjvex=m1; if(list.vexnoden1.firstArc=NULL) list.vexnoden1.firstArc=q; q-next=NULL; else q-next=list.vexnoden1.firstArc; list.vexnoden1.firstArc=q; pr

15、intf(鄰接表構(gòu)造成功nntt鄰接矩陣構(gòu)造成功！n system( system( void inputMatric() /輸出鄰接矩陣 printf(鄰接矩陣：n printf( for(i=0;i list.visitedi=0; for(i=0;inext) if(!visitedp-adjvex) printf( visitedp-adjvex=1; EnQueue(p-adjvex); 13 if(queue.count!=0) BFS(visited,DeQueue(); void EnQueue(int i) /元素入隊(duì) temqueuenode=(QueueNode *)ma

16、lloc(sizeof(QueueNode); temqueuenode-local=i; if(queue.count=0) queue.head=temqueuenode; queue.rear=temqueuenode; temqueuenode-next=NULL; queue.count+; else queue.rear-next=temqueuenode; queue.rear=temqueuenode; queue.count+; /printf(元素%c入隊(duì)成功！n /inputQueue(); int DeQueue() /元素出隊(duì) 14 if(queue.count=0)

17、 printf(隊(duì)列為空！無(wú)法完成輸出操作！n else temqueuenode=queue.head; queue.head=queue.head-next; queue.count-; /printf(元素%c出隊(duì)成功！n /inputQueue(); return temqueuenode-local; void inputQueue() for(i=0,temqueuenode=queue.head;inext) printf(隊(duì)列中第%d個(gè)元素：%cn 15 int main() create(); inputMatric(); printf( system( system( inputList(); printf( system( system( Depth_First_Search(); printf( system( system( Breadth_First_Search(); printf( system( return 0; 2.程序運(yùn)行分析 (1)主菜單 16 圖1 主菜單 (2) 初始化鄰接表與鄰接矩陣 圖 2 初始化鄰接表與鄰接矩陣 17 圖1 主菜單 (2) 初始化鄰接表與鄰接矩陣 圖 2 初始化鄰接表與鄰接矩陣 17 (3)輸入頂點(diǎn)集 圖 3 輸入