《數據結構》實驗報告

?

學號：? 2018329621200 ??	機器號?? 10-414-28? ? ? ?	姓名：? 申屠志剛???
日期：? 2019/12/9??? ?????	程序名：???? main.cpp???? ????????????????????????
實驗內容：?? 無向圖鄰接表的構造????

一、目的和要求（需求分析）：

1、掌握鄰接表的存儲結構以及鄰接表的建立和操作。

2、 構造一個無向圖的鄰接表，要求從鍵盤輸入圖的頂點數和圖的邊數，并顯示所構造的鄰接表）

實驗拓展：

1.? 構建有向圖的鄰接表

2.? 判斷邊是否存在

3.? 求頂點的度數

二、程序設計的基本思想，原理和算法描述：

鄰接表是數組與鏈表相結合的存儲方法，相比于順序存儲結構（鄰接矩陣），節省空間。

三、調試和運行程序過程中產生的問題及采取的措施：

1、度數求法；

措施：添加邊時即記錄度數。

2、對應節點和節點編號；

措施：歷遍查找。

3、區分有向圖和無向圖；

措施：添加標記，以判斷是否添加反向邊。

四、源程序及注釋：

/* *@Author: STZG *@Language: C++ */ #include <bits/stdc++.h>#define MAXVEX 30 using namespace std; int visited[MAXVEX]; int n,m; typedef char VertexType; typedef struct ArcNode {int adjvex; /*鄰接點序號*/VertexType data; /*鄰接點信息*/struct ArcNode *nextarc;char *info; } ArcNode; typedef struct VNode {VertexType data; /*結點信息*/ArcNode *firstarc; /*指向下一個邊結點*/ }VNode,AdjList[MAXVEX];typedef struct //圖結構 {AdjList vertices;int vexnum,arcnum; //圖的當前頂點數與弧數int in[MAXVEX],out[MAXVEX]; }ALGraph; int LocateVex(ALGraph G,char v) //查找值為v的頂點在頂點向量G.vexs[]中的位置 {int i;for(i=0;i<G.vexnum;i++)if(v==G.vertices[i].data)return i;return -1; }int FirstAdjVex(ALGraph G,char v)//返回v的第一個鄰接頂點的序號 {int i;ArcNode *p;i=LocateVex(G,v); //i為頂點v在圖G中的序號if(i==-1)return -1;p=G.vertices[i].firstarc;if(p)return p->adjvex;elsereturn -1; }int NextAdjVex(ALGraph G,char v,char w)//返回v的(相對于w)的下一個鄰接頂點的序號 {int i,j;ArcNode *p,*q;i=LocateVex(G,v);j=LocateVex(G,w);if(i==-1||j==-1||i==j)return -1;p=G.vertices[i].firstarc; //p指向v的鄰接頂點鏈表中的第一個鄰接頂點while(p->nextarc&&p->adjvex!=j) //找到鄰接頂點wp=p->nextarc;if(p->nextarc) //找到鄰接頂點w，且w非v的最后一個鄰接頂點{q=p->nextarc;return q->adjvex; //返回v的(相對于w)的下一個鄰接頂點的序號}elsereturn -1; //沒有找到w或w是v的最后一個鄰接頂點 }int Visit(char v) {printf("%c ",v);return 1; } int add(ALGraph &G,int i,int j){ArcNode *p,*q;G.out[i]++;G.in[j]++;p=(ArcNode *)malloc(sizeof(ArcNode));p->adjvex=j;p->info=NULL;p->nextarc=NULL;if(!G.vertices[i].firstarc)G.vertices[i].firstarc=p;else{//找尾結點for(q=G.vertices[i].firstarc;q->nextarc;q=q->nextarc);q->nextarc=p; //插入到鏈表尾} } int CreateDG(ALGraph &G) //采用鄰接表表示，構造有向圖G {int v,e,i,j,t,f;ArcNode *p,*q;char tail,head;printf("輸入頂點個數:");scanf("%d",&v);if(v<0)return 0;G.vexnum=v;printf("輸入弧的條數:");scanf("%d",&e);if(e<0)return 0;G.arcnum=e;printf("無向圖/有向圖(0/1):");scanf("%d",&f);printf("建立DG:\n");for(t=0;t<G.vexnum;t++) //建立頭結點順序表{fflush(stdin);printf("輸入%d的信息:",t+1);scanf("%c",&G.vertices[t].data);G.vertices[t].firstarc=NULL; //初始化該頭結點指針域G.in[t]=0;G.out[t]=0;}for(t=0;t<G.arcnum;t++) //建立表結點鏈表(每個頂點的鄰接頂點鏈表){fflush(stdin);printf("輸入弧的信息(弧尾-弧頭)");scanf("%c%*c%c",&tail,&head);i=LocateVex(G,tail);j=LocateVex(G,head);if(i==-1||j==-1||i==j)return 0;add(G,i,j);if(f)add(G,j,i);}return 1; }int DFS(ALGraph G,int v) //從第v個頂點出發，遞歸的深度優先遍歷有向圖G {int w;visited[v]=-1;printf("%c ",G.vertices[v].data);w=FirstAdjVex(G,G.vertices[v].data);for(;w>=0;w=NextAdjVex(G,G.vertices[v].data,G.vertices[w].data))if(!visited[w])DFS(G,w); //對v的尚未訪問的鄰接頂點w遞歸調用DFS()return 1; }int DFSTraverse(ALGraph G) //深度優先搜索遍歷圖G {int i;for(i=0;i<G.vexnum;i++)visited[i]=0;for(i=0;i<G.vexnum;i++)if(!visited[i])DFS(G,i);return 1; } void printALGraph(ALGraph G){for(int i=0;i<G.vexnum;i++){printf("%c|%d-->",G.vertices[i].data,i);for(ArcNode* q=G.vertices[i].firstarc;q;q=q->nextarc){printf("%d-->",q->adjvex);}printf("null\n");} } void printdegree(ALGraph G){printf("Node\t入度\t出度\t度\n");for(int i=0;i<G.vexnum;i++){printf("%c\t%d\t%d\t%d\n",G.vertices[i].data,G.in[i],G.out[i],G.in[i]+G.out[i]);} } int checkarc(ALGraph G){while(1){char tail,head;fflush(stdin);printf("輸入弧的信息(弧尾-弧頭)");scanf("%c%*c%c",&tail,&head);int i=LocateVex(G,tail);int j=LocateVex(G,head);if(i==-1||j==-1||i==j)return 0;int f=0;for(ArcNode* q=G.vertices[i].firstarc;q;q=q->nextarc){if(j==q->adjvex){f=1;break;}}if(f)printf("Yes\n");else printf("No\n");} } int main() {ALGraph G;printf("建立有向圖G\n");if(CreateDG(G)){printALGraph(G);printdegree(G);printf("深度優先搜索的順序:");DFSTraverse(G);printf("\n");}checkarc(G);return 0; }

五、運行輸出結果：

六、心得與體會：

1、掌握鄰接表的存儲結構以及鄰接表的建立和操作。

2、構造無向圖/有向圖的鄰接表。

3、轉換思想，記錄不變量。

?

?

?

?

?

總結

以上是生活随笔為你收集整理的《数据结构与算法》实验报告——无向图邻接表的构造的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。