数据结构实验十一 图的创建与存储

数据结构实验十一 图的创建与存储

作业内容:
一、实验目的

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）！