//参考书本的202页 邻接表存储结构 30 页 顺序表的存储结构 213页 广度遍历
#include <stdio.h>
/*================================================定义一些特殊值的大小========================================*/
#define Maxsize 1000
#define MaxVertices 1000
#define MaxWeight 1000
typedef int DataType;
/*================================================定义的数据元素==============================================*/
typedef struct //定义顺序列表的结构体
{
DataType list[Maxsize];
int size;
}SeqList;
typedef struct//定义图
{
SeqList Vertices;
int edge[MaxVertices][MaxVertices];
int numOfEdges;
}AdjMGraph;
/*================================================顺序表的具体操作==============================================*/
void ListInitiate(SeqList *L) //初始化顺序表L
{
L->size=0;
}
int ListLength(SeqList L) //返回当前顺序表L的当前的数据的元素个数
{
return L.size;
}
int ListInsert(SeqList *L,int i,DataType X) //在顺序表L的第i个位置前插入数据元素值为 X 插入成功返回1 否则返回0
{
int j;
if(L->size>Maxsize)
{
printf("顺序表已经满了，无法进行插入操作！！\n");
return 0;
}
else if(i<0||i>L->size)
{
printf("参数输入的不合法！\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(SeqList *L,int i,DataType *x) //删除顺序表中的位置在i的元素，并且把这个删除的数据存储到x中
{
int j;
if(L->size<=0)
{
printf("顺序表是空的，没有元素可以删除！\n");
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(SeqList L,int i,DataType *x)//取顺序表中的第i个元素，并且把他保存到x中，成功返回1 失败返回0
{
if(i<0||i>L.size-1)
{
printf("参数i不合法！\n");
return 0;
}
else
{
*x=L.list[i];
return 1;
}
}
/*================================================图的实现的具体操作==============================================*/
void Initiate(AdjMGraph *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;
ListInitiate(&G->Vertices);
}
void InsertVertex(AdjMGraph *G,DataType vertex) //在图中插入节点vertex
{
ListInsert(&G->Vertices,G->Vertices.size,vertex); //顺序表尾插入
}
void InsertEde(AdjMGraph *G,int v1,int v2,int weight) //在图中插入边<v1,v2>的权值为weight
{
if(v1<0||v1>G->Vertices.size||v2<0||v2>G->Vertices.size)
{
printf("参数v1或者v2输入的不合法！！！\n");
exit(1);
}
G->edge[v1][v2]=weight;
G->numOfEdges++;
}
评论4