数据结构邻接矩阵,邻接表,图实验报告_数据结构图实验报告
数据结构邻接矩阵,邻接表,图实验报告由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“数据结构图实验报告”。
实验名称：数据结构实验五
实验内容：1.使用邻接矩阵建立一个图，深度遍历。2．使用邻接表建立一个图，广度遍历。3.建立一个图，存储结构自己确定，并进行拓扑排序。
实验代码：
1.#include “stdio.h” #define Infinity 100 #define MaxVertexNum 20 typedef enum {DG,DN,UDG,UDN} GraphKind;typedef int VRType;typedef char VertexType;bool Visit[MaxVertexNum];typedef struct ArcCell { VRType adj;}ArcCell,AdjMatrix[MaxVertexNum][MaxVertexNum];typedef struct
{
VertexType vexs[MaxVertexNum];
AdjMatrix arcs;
//邻接矩阵
int vexnum,arcnum;
//图的当前顶点数和弧数
GraphKind kind;}MGraph;
int LocateVex(MGraph G,VertexType v){ for(int i=0;i
if(v==G.vexs[i])
return i;} if(i = G.vexnum)
printf(“输入的顶点不合法n”);return 0;}
VertexType v1,v2;VRType w;void CreateUDG(MGraph &G){ int i,j,k;printf(“请输入顶点数：n”);scanf(“%d”,&G.vexnum);printf(“请输入弧数：n”);scanf(“%d”,&G.arcnum);i = 0;while(i
printf(“请输入第%d个顶点n”,i);
getchar();
scanf(“%c”,&G.vexs[i]);
++i;} for(i=0;i
for(j=0;j
G.arcs[i][j].adj = 0;} for(k=0;k
printf(“请输入一条边依附的顶点及权值（v1 v2 w）n”);
getchar();
scanf(“%c %c %d”,&v1,&v2,&w);
i =LocateVex(G,v1);
j =LocateVex(G,v2);
G.arcs[i][j].adj= w;
G.arcs[j][i] = G.arcs[i][j];
} return;}
void DFSTraverse(MGraph &G,int i){
printf(“%c ”,G.vexs[i]);Visit[i]=true;for(int j=0;j
if(G.arcs[i][j].adj==1&&!Visit[j])
{
DFSTraverse(G,j);
} } }
void DFS(MGraph &G){ int i;for(i=0;i
if(!Visit[i])
{
DFSTraverse(G,i);
} } }
void main(){ MGraph graph;CreateUDG(graph);printf(“顶点集合为：：”);for(int i=0;i
printf(“%c ”,graph.vexs[i]);printf(“n深度遍历结果是：”);DFS(graph);printf(“n”);return;}
2．#include “stdio.h” #include “stdlib.h” #define MaxVertexNum 20 typedef int InfoType;typedef char VertexType;typedef VertexType QElemType;bool visited[MaxVertexNum];
typedef struct ArcNode { int adjvex;
//该弧指向的顶点位置
struct ArcNode *nextarc;
//指向下一条弧的指针
InfoType *info;}ArcNode;
typedef struct VNode { VertexType data;
//顶点信息
ArcNode *firstarc;
//指向第一条依附该顶点的弧的指针 }VNode,AdjList[MaxVertexNum];
typedef struct { AdjList vertices;int vexnum,arcnum;
//图的当前顶点数和弧数 }ALGraph;
typedef struct QNode { QElemType data;struct QNode *next;}QNode,*Queueptr;
typedef struct { Queueptr front;Queueptr rear;}LinkQueue;
void InitQueue(LinkQueue &Q){ Q.front = Q.rear =(Queueptr)malloc(sizeof(QNode));if(!Q.front)return;Q.front->next = NULL;return;} void EnQueue(LinkQueue &Q,QElemType e){ Queueptr p = NULL;p =(Queueptr)malloc(sizeof(QNode));if(!p)return;p->data = e;p->next = NULL;Q.rear->next = p;Q.rear = p;return;}
QElemType DeQueue(LinkQueue &Q,QElemType &e){ Queueptr p;if(Q.front==Q.rear)return ' ';p = Q.front->next;e = p->data;Q.front->next = p->next;if(Q.rear==p)
Q.rear = Q.front;free(p);return e;}
int QueueEmpty(LinkQueue Q){ if(Q.front==Q.rear)
return 1;else
return 0;}
int Locate(ALGraph G,VertexType v){ for(int k=0;k
if(v==G.vertices[k].data)
return k;} if(k = G.vexnum)
printf(“输入的顶点不合法n”);return 0;}
void CreateALGraph(ALGraph &G){
VertexType v1,v2;int i,j,k;ArcNode *p,*r;printf(“请输入顶点数和弧数（以空格分开）: ”);scanf(“%d %d”,&G.vexnum,&G.arcnum);for(i=0;i
getchar();
printf(“请输入第%d个结点 : ”,i);
scanf(“%c”,&G.vertices[i].data);
G.vertices[i].firstarc = NULL;} for(i=0;i
printf(“请输入第%d条弧（格式：顶点 顶点（以空格隔开））
getchar();
scanf(”%c %c“,&v1,&v2);
k=Locate(G,v1);
j=Locate(G,v2);
p =(ArcNode*)malloc(sizeof(ArcNode));
r =(ArcNode*)malloc(sizeof(ArcNode));
p->adjvex = j;
p->info = NULL;
r->adjvex = k;
r->info = NULL;
p->nextarc=G.vertices[k].firstarc;
G.vertices[k].firstarc=p;
r->nextarc=G.vertices[j].firstarc;
G.vertices[j].firstarc=r;} return;}
void BFSTraverse(ALGraph G,QElemType x){ int i,v;ArcNode *p;QElemType v1;for(v=0;v
visited[v] = false;LinkQueue Q;
: ”,i);InitQueue(Q);EnQueue(Q,x);i = Locate(G,x);visited[i] = true;for(v=0;v
while(!QueueEmpty(Q))
{
DeQueue(Q,v1);
printf(“%c ”,v1);
i=Locate(G,v1);
p = G.vertices[i].firstarc;
while(p!=NULL)
{
if(!visited[p->adjvex])
{
visited[p->adjvex] = true;
EnQueue(Q,G.vertices[p->adjvex].data);
}
p = p->nextarc;
}
}
if(!visited[v])
{
visited[v] = true;
EnQueue(Q,G.vertices[v].data);
} } }
void main(){ char flag1;ALGraph graph2;QElemType x;CreateALGraph(graph2);flag1 = 'Y';while(flag1 == 'Y'||flag1 == 'y'){
printf(“请输入遍历的起点 : ”);
getchar();
scanf(“%c”,&x);
printf(“广度遍历结果是：n”);BFSTraverse(graph2,x);printf(“n继续遍历（Y/N）: ”);
getchar();
scanf(“%c”,&flag1);} return;} 3．
#include “stdio.h” #include “stdlib.h” #define StackInitSize 20 #define StackIncrement 5 #define MaxVertexNum 20 typedef int InfoType;typedef char VertexType;typedef VertexType SElemType;typedef struct { SElemType *base;SElemType *top;int stacksize;}SqStack;
typedef struct ArcNode { int adjvex;
struct ArcNode *nextarc;
InfoType *info;}ArcNode;
typedef struct VNode { int indegree;VertexType data;
ArcNode *firstarc;
}VNode,AdjList[MaxVertexNum];
typedef struct { AdjList vertices;int vexnum,arcnum;
}ALGraph;
//该弧指向的顶点位置 //指向下一条弧的指针
//顶点信息
//指向第一条依附该顶点的弧的指针
//图的当前顶点数和弧数
bool InitStack(SqStack &s){ s.base =(SElemType *)malloc(StackInitSize * sizeof(SElemType));if(!s.base)return false;s.top = s.base;s.stacksize = StackInitSize;return true;}
bool Pop(SqStack &s, int &e){ if(s.top==s.base)
return false;e = *--s.top;return true;}
bool Push(SqStack &s, int e){ if(s.top-s.base>=s.stacksize){
s.base =(SElemType sizeof(SElemType));
if(!s.base)
return false;
s.top = s.base+s.stacksize;
s.stacksize+=StackIncrement;} * s.top++ = e;return true;}
bool StackEmpty(SqStack s){ if(s.top == s.base)
return true;else
return false;}
int Locate(ALGraph G,VertexType v){
*)realloc(s.base,(s.stacksize+StackIncrement)* for(int k=0;k
if(v==G.vertices[k].data)
return k;} if(k = G.vexnum)
printf(“输入的顶点不合法n”);return 0;}
void CreateALGraph(ALGraph &G)
//邻接表存储 {
VertexType v1,v2;int i,j,k;ArcNode *p;printf(“请输入顶点数和弧数（以空格分开）: ”);scanf(“%d %d”,&G.vexnum,&G.arcnum);for(i=0;i
getchar();
printf(“请输入第%d个结点 : ”,i);
scanf(“%c”,&G.vertices[i].data);
G.vertices[i].firstarc = NULL;
G.vertices[i].indegree = 0;} for(i=0;i
printf(“请输入第%d条有向弧弧（格式：顶点 顶点（以空格隔开））
getchar();
scanf(”%c %c“,&v1,&v2);
k=Locate(G,v1);
j=Locate(G,v2);
p =(ArcNode*)malloc(sizeof(ArcNode));
p->adjvex = j;
p->info = NULL;
p->nextarc=G.vertices[k].firstarc;
G.vertices[k].firstarc=p;} return;}
void FindInDegree(ALGraph G ,int a[MaxVertexNum]){ int i,k;
: ”,i);ArcNode *p;for(i=0;i
for(p=G.vertices[i].firstarc;p;p=p->nextarc)
{
k = p->adjvex;
a[k] = ++G.vertices[k].indegree;
} } return;}
void TopologicalSort(ALGraph G)
//拓扑排序算法 { int i,j, count;ArcNode *p;SqStack s;int indegree[MaxVertexNum];for(i=0;i
indegree[i] = 0;FindInDegree(G,indegree);InitStack(s);for(i=0;i
if(!indegree[i])
Push(s,i);} count =0;while(!StackEmpty(s)){
Pop(s,i);
printf(“%c ”,G.vertices[i].data);
++count;
for(p=G.vertices[i].firstarc;p;p=p->nextarc)
{
j = p->adjvex;
if(!(--indegree[j]))Push(s,j);
} } if(count
printf(“错误!该有向图有回路!n”);else return;} void main(){ ALGraph graph3;CreateALGraph(graph3);printf(“拓扑排序的结果是 ：n”);TopologicalSort(graph3);printf(“n”);return;}
