数据结构实验十一 图的创建与存储
数据结构实验十一 图的创建与存储
作业内容:
一、实验目的
1、 理解图的存储结构与基本操作;
2、 掌握图的创建过程
二、实验内容
1.请把下图以邻接矩阵的结构存储,并打印输出此邻接矩阵。
图的创建代码参考教材例题.
提示:首先构建图的逻辑模型,得出该图的顶点集和边集,调用相应的函数生成图的邻接矩阵,并打印出邻接矩阵。
2.用邻接表存储上图,并输出邻接表。(此题为选做)
三、【实验源代码】
//Sequence.h
typedef struct
{
ElemType list[MaxSize];
int size;
} SequenceList;
//顺序表初始化
void ListInitialize(SequenceList *L)
{
L->size = 0;
}
int ListLength(SequenceList L)
{
return L.size;
}
//顺序表插入操作
int ListInsert(SequenceList *L, int i, ElemType x)
{
int j;
if (L->size >= MaxSize)
{
printf("顺序表已满无法插入!\n");
return 0;
}
else if (i < 0 || i > L->size)
{
printf("参数i不合法!\n");
return 0;
}
else
{
for (j = L->size; j > i; j--)
{
L->list[j] = L->list[j-1];
}
L->list[i] = x;
L->size++;
}
return 1;
}
int ListDelete(SequenceList *L, int i, ElemType *x)
{
int j;
if (L->size <= 0)
{
printf("顺序表已空无数据可删!\n");
return 0;
}
else if (i < 0 || i > L->size-1)
{
printf("参数i不合法");
return 0;
}
else
{
*x = L->list[i];
for (j = i+1; j < L->size-1; j++)
{
L->list[j-1] = L->list[j];
}
L->size--;
return 1;
}
}
int ListGet(SequenceList L, int i, ElemType *x)
{
if (i < 0 || i > L.size-1)
{
printf("参数i不合法!\n");
return 0;
}
else
{
*x = L.list[i];
return 1;
}
}
//11.c
#include<stdio.h>
#include<stdlib.h>
#define MaxSize 100
#define MaxVertices 10
#define MaxEdges 100
#define MaxWeight 10000
typedef char ElemType;
#include"SequenceList.h"
typedef struct
{
SequenceList Vertices;
int edge[MaxVertices][MaxVertices];
int numOfEdges;
}MatrixGraph;
typedef struct
{
int row;
int col;
int weight;
}RCW;
//初始化
void Initiate(MatrixGraph *G,int n)
{
int i,j;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(i==j)
{
G->edge[i][j]=0;
}
else
{
G->edge[i][j]=MaxWeight;
}
}
}
G->numOfEdges=0;//边的条数置为0
ListInitialize(&G->Vertices);//顺序表初始化
}
//插入顶点
void InsertVertex(MatrixGraph *G,ElemType vertex)
{
ListInsert(&G->Vertices,G->Vertices.size,vertex);//
}
//插入边
void InsertEdge(MatrixGraph *G,int v1,int v2,int weight)
{
if(v1<0||v1>G->Vertices.size||v2<0||v2>G->Vertices.size)
{
printf("参数v1或参数v2越界出错!\n");
return;
}
G->edge[v1][v2]=weight;
G->numOfEdges++;
}
void CreatGraph(MatrixGraph *G,ElemType V[],int n,RCW E[],int e)
{
int i,k;
Initiate(G,n);
for(i=0;i<n;i++)
{
InsertVertex(G,V[i]);
}
for(k=0;k<e;k++)
{
InsertEdge(G,E[k].row,E[k].col,E[k].weight);
}
}
typedef struct Node
{
int adjvex;//邻接边的弧头顶点序号
struct Node *next;//单链表的下一个结点指针
}Edge;
typedef struct
{
ElemType data;//顶点数据元素
Edge *adj; //邻接边的头指针
}AdjLHeight;
typedef struct
{
AdjLHeight a[MaxVertices];//邻接表数组
int numOfVerts;//顶点个数
int numOfEdges;//边个数
}ListGraph;
typedef struct
{
int row;
int col;
} RC;
//初始化
AdjInitiate(ListGraph *G)
{
int i;
G->numOfVerts=0;
G->numOfEdges=0;
for(i=0;i<MaxVertices;i++)
{
G->a[i].adj=NULL;
}
}
//插入顶点
void InsertVertex2(ListGraph *G,int i,ElemType vertex)
{
if(i>=0&&i<MaxVertices)
{
G->a[i].data=vertex;
G->numOfVerts++;
}
else
printf("顶点越界");
}
//插入边
void InsertEdge2(ListGraph *G,int v1,int v2)
{
Edge *p;
if(v1<0||v1>=G->numOfVerts||v2<0||v2>=G->numOfVerts)
{
printf("参数v1或v2越界出错!\n");
exit(0);
}
p=(Edge*)malloc(sizeof(Edge));
p->adjvex=v2;
p->next=G->a[v1].adj;
G->a[v1].adj=p;
G->numOfEdges++;
}
//创建图
void CreatGraph2(ListGraph *G,ElemType v[],int n,RC d[],int e)
{
int i,k;
AdjInitiate(G);
for(i=0;i<n;i++)
{
InsertVertex2(G,i,v[i]);
}
for(k=0;k<e;k++)
{
InsertEdge2(G,d[k].row,d[k].col);
}
}
void main(void)
{
MatrixGraph g1;
ElemType a[]={'A','B','C','D','E','F'};
RCW rcw[]={{0,2,5},{0,3,30},{1,0,2},{1,4,8},{2,1,15},{2,5,7},{4,3,4},{5,3,10},{5,4,18}};
int n=6,e=9;
int i,j;
CreatGraph(&g1,a,n,rcw,e);
printf("顶点集合为:");
for(i=0;i<g1.Vertices.size;i++)
{
printf("%c ",g1.Vertices.list[i]);
}
printf("\n");
printf("邻接矩阵为:\n");
for(i=0;i<g1.Vertices.size;i++)
{
for(j=0;j<g1.Vertices.size;j++)
{
printf("%5d ",g1.edge[i][j]);
}
printf("\n");
}
printf("邻接表为:\n");
ListGraph g;
char b[]={'A','B','C','D','E','F'};
RC rc[]={{0,2},{0,3},{1,0},{1,4},{2,1},{2,5},{4,3},{5,3},{5,4}};
i=6,
e=9;
Edge *p;
CreatGraph2(&g,b,n,rc,e);
for(i=0;i<g.numOfVerts;i++)
{
printf("%c ",g.a[i].data);
p=g.a[i].adj;
while(p!=NULL)
{
printf("%d ",p->adjvex);
p=p->next;
}
printf("\n");
}
}
四、【实验结果】
五、【实验总结】
图的两种存储结构:邻接矩阵和邻接表。在代码中,首先定义了图的结构体MatrixGraph和ListGraph,分别表示邻接矩阵和邻接表。然后通过Initiate函数和AdjInitiate函数对图进行初始化,包括顶点和边的初始化。接着通过InsertVertex和InsertEdge函数,分别实现了向图中插入顶点和边的操作。最后,通过CreatGraph和CreatGraph2函数,将顶点和边的信息传入,创建了两个不同存储结构的图。
原文地址:https://blog.csdn.net/2301_76979886/article/details/142908513
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!