數(shù)據(jù)結構與算法實驗報告-圖

1、數(shù)據(jù)結構與算法實驗報告-圖 導讀：就愛閱讀網(wǎng)友為您分享以下“數(shù)據(jù)結構與算法實驗報告-圖”的資訊，希望對您有所幫助，感謝您對的支持! 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(鄰接表構造成功nntt鄰接矩陣構造成功！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) /返回鄰接表中該弧的第一個節(jié)點指向的位置 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個頂點的鄰接表中指向j的節(jié)點的后面節(jié)點的指向 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 沈 陽 工 程 學 院 學 生 實 驗 報 告 （課程名稱： 數(shù)據(jù)結構與算法 ） 圖 實驗題目： 1 一、實驗目的 1掌握圖的基本存儲方法。 2掌握有關圖的操作算法并用高級語言實現(xiàn)。 3熟練掌握圖的兩種搜索路徑的遍歷方法。 4掌握圖的有關應用。 二、實驗環(huán)境 Turbo C或是

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

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

7、/儲存是否被檢索過 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)先搜索相關函數(shù)-*/ void Depth_First_Searc

8、h(); /深度優(yōu)先搜索 void DFS(int *visited,int i); int FirstAdjVex(int i); /返回鄰接表中該弧的第一個節(jié)點指向的位置 int NextAdjVex(int i,int j); /返回第i個頂點的鄰接表中指向j的節(jié)點的后面節(jié)點的指向 /*-*/ /*-廣度優(yōu)先搜索相關函數(shù)-*/ void Breadth_First_Search(); /廣度優(yōu)先搜素 void EnQueue(int i); /元素入隊 int DeQueue(); /元素出隊 void inputQueue();/輸出隊列中的元素 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(請輸入圖的種類：ntt1

10、.無向圖ntt2.有向圖n fflush(stdin); scanf( list.GraphKind=matric.GraphKind; system( system( printf(請輸入頂點數(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(請輸入圖的種類：ntt1.無向圖ntt2.有向圖n fflush(stdin); scanf( list.GraphKind=matric.GraphKind; system( system( printf(請輸入頂點數(shù)： fflush(stdin); 5 scanf( list.vexnum=matric.vexnum; printf(請輸入弧數(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(請輸入第%d個頂點: ff

13、lush(stdin); scanf( list.vexnodei.vex=matric.vexsi; printf(頂點集輸入成功！n system( system( printf(請輸入弧集(輸入模式：“弧頭，弧尾,權值”,若為無權圖，則權值均輸入”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(鄰接表構造成功nntt鄰接矩陣構造成功！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) /元素入隊 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入隊成功！n /inputQueue(); int DeQueue() /元素出隊 14 if(queue.count=0)

17、 printf(隊列為空！無法完成輸出操作！n else temqueuenode=queue.head; queue.head=queue.head-next; queue.count-; /printf(元素%c出隊成功！n /inputQueue(); return temqueuenode-local; void inputQueue() for(i=0,temqueuenode=queue.head;inext) printf(隊列中第%d個元素：%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.程序運行分析 (1)主菜單 16 圖1 主菜單 (2) 初始化鄰接表與鄰接矩陣 圖 2 初始化鄰接表與鄰接矩陣 17 圖1 主菜單 (2) 初始化鄰接表與鄰接矩陣 圖 2 初始化鄰接表與鄰接矩陣 17 (3)輸入頂點集 圖 3 輸入