数据结构 --- 图的存储

有向带权图 矩阵法描述

数据结构 --- c语言图的基础_考拉爱睡觉鸭~的博客-CSDN博客

存放顶点需要顶点数组，用二维数组存储方便比较

一行存放一个顶点，二维数组可以存放多个字符串，存放多个顶点，顶点用字符串表示

让用户输入边的信息

#include 
#include 
#include 
#include 
#define MAX 100
//图的结构体描述
typedef struct graph 
{
	int arcnum;				                    //边数 
	int vexnum;				                    //顶点数
	char vextex[MAX][20];                       //存放多个顶点-> 顶点用字符串表示
	int  matrix[MAX][MAX];	                    //权值
}GRAPH,*LPGRAPH;
//定位-> 通过起点知道所在行数 通过终点知道所在列数 要找的图 要找的顶点
int searchPos(LPGRAPH g, const char* v) 
{
	for (int i = 0; i < g->vexnum; i++)          
	{
		if (strcmp(g->vextex[i], v) == 0)       //行数与顶点数比较-> 字符串比较
		{
			return i;                           //相等说明找到所在行
		}
	}
	return -1;                                  //没找到返回-1
}
//创建图-> 用结构体描述一个图
LPGRAPH createGraph()                           //让用户输入边的信息
{
	LPGRAPH g = (LPGRAPH)malloc(sizeof(GRAPH));
	assert(g);
	printf("输入边和顶点数:");
	scanf_s("%d%d", &g->arcnum, &g->vexnum);
	printf("请输入顶点:");                       //初始化顶点数组
	for (int i = 0; i < g->vexnum; i++) 
	{
		scanf_s("%s", g->vextex[i], 20);	    //一行存储一个顶点-> 给二维数组做初始化
	}
	//把所有位置置为0 当做未连通状态-> 矩阵没有初始化 没有连通的状态不知道是多少
	//memset(g->matrix, 0, sizeof(int) * 100*100);
	for (int i = 0; i < MAX; i++) 
	{
		for (int j = 0; j < MAX; j++) 
		{
			g->matrix[i][j] = 0;
		}
	}
	char v1[20];			//起点
	char v2[20];			//终点
	int  vrt;				//权值-> 描述边
	int i = 0;
	int j = 0;
	printf("输入各条边的信息:\n");
	for (int k = 0; k < g->arcnum; k++) 
	{
		scanf_s("%s%s%d", v1, 20, v2, 20, &vrt);  //输入一条边
		//把权值填充到矩阵中-> 要知道它所在的行和列
		//行和列的求解
		i = searchPos(g, v1);                     //通过第一个顶点找行数
		j = searchPos(g, v2);                     //通过第二个顶点找列数
		//没有找到相关顶点防御性代码
		if (i == -1 || j == -1) 
		{
			printf("输入顶点有误!\n");
			k--;                                  //还原k的值
			continue;
		}
		g->matrix[i][j] = vrt;                    //把权值放到当前行当前列的矩阵中
	}
	printf("- - - - - - - - - - - - - - - - - - - - - \n");
	return g;
}

//打印图 要打印的图
void  printGraph(LPGRAPH g) 
{
	for (int i = 0; i < g->vexnum; i++) 
	{
		printf("\t%s", g->vextex[i]);
	}
	printf("\n");
	for (int i = 0; i < g->vexnum; i++) 
	{
		printf("%s\t", g->vextex[i]);               //先打印顶点
		for (int j = 0; j < g->vexnum; j++) 
		{
			printf("%d\t", g->matrix[i][j]);        //再打印矩阵
		}
		printf("\n");
	}
    printf("- - - - - - - - - - - - - - - - - - - - - \n");
}

int main() 
{
	LPGRAPH g = createGraph();
	printGraph(g);
	return 0;
}

/*输出*/

输入边和顶点数：7 5
请输入顶点:1 2 3 4 5
输入各条边的信息:
1 2 4
1 4 4
2 3 8
3 4 9
4 5 5
5 2 5
5 3 7
- - - - - - - - - - - - - - - - - - - - - 
        1       2       3       4       5
1       0       4       0       4       0
2       0       0       8       0       0
3       0       0       0       9       0
4       0       0       0       0       5
5       0       5       7       0       0
- - - - - - - - - - - - - - - - - - - - - 

 无向无权图 邻接表法表示

#include 
#include 
#include 
#include 
#include 
#define MAX 100

//邻接表横向链表节点描述
typedef struct ArcNode 
{
	int index;            //存的是序号-> 不是存顶点的元素
	struct ArcNode* next; //链表的特性
}NODE,*LPNODE;

//创建节点-> 把用户的数据变成一个节点 
LPNODE createNode(int index) 
{
	LPNODE newNode = (LPNODE)malloc(sizeof(NODE));
	assert(newNode);
	newNode->index = index;
	newNode->next = NULL;
	return newNode;
}

//插入节点-> 无头链表头插法会修改表头的指向 用二级指针
void insertNode(LPNODE* headNode, int index) 
{
	LPNODE newNode = createNode(index);
	newNode->next = (*headNode);          
	(*headNode)= newNode;
}

//把顶点数组的信息封装为结构体 增加指针表示横向链表-> 每一个顶点都有数据和节点从而形成邻接表-> 顶点中包含指针
typedef struct VNode 
{
	char data[20];          //顶点-> 数组
	LPNODE firstNode;       //指针-> 表示横向链表
}VNODE,*LPVNODE,ARRAY[MAX]; //ARRAY结构体数组别名

//封装图的信息
typedef struct graph 
{
	int arcnum;             //边数
	int vexnum;             //顶点数
	ARRAY vextex;			//顶点数组-> 用别名定义一个数组
}GRAPH,*LPGRAPH;

//定位
int searchPos(LPGRAPH g, const char* v) 
{
	for (int i = 0; i < g->vexnum; i++) 
	{
		if (strcmp(g->vextex[i].data, v) == 0)
			return i;
	}
	return -1;
}

//创建图
LPGRAPH createGraph() 
{
	LPGRAPH g = (LPGRAPH)malloc(sizeof(GRAPH));
	assert(g);
	printf("请输入边和顶点数:");
	scanf_s("%d%d", &g->arcnum, &g->vexnum);
	printf("请输入所有顶点:");
	for (int i = 0; i < g->vexnum; i++) 
	{
		scanf_s("%s", g->vextex[i].data, 20);    //把顶点输入到结构体数组中 字符串用数组名
		g->vextex[i].firstNode = NULL;           //每一个顶点的指针都要做初始化
	}
	char v1[20];    //第一条边
	char v2[20];    //第二条边
	int i = 0;
	int j = 0;
	printf("请输入边的信息:\n");
	for (int k = 0; k < g->arcnum; k++) 
	{
		scanf_s("%s%s", v1, 20, v2, 20);
		i = searchPos(g,v1);                     //定位
		j = searchPos(g,v2);
		insertNode(&g->vextex[i].firstNode, j);  //A:0 B:1 把1插到A链表后面 把0插到B链表后面
		insertNode(&g->vextex[j].firstNode, i);  //无向图要做两次插入 A是B的邻接顶点 B也是A的邻接顶点
	}
	return g;
}

//遍历图
void printGraph(LPGRAPH g) 
{
	for (int i = 0; i < g->vexnum; i++) 
	{
		printf("%s:\t", g->vextex[i].data);     //遍历顶点数组
		LPNODE pmove = g->vextex[i].firstNode;  //打印顶点后面的数据-> 链表的遍历
		while (pmove != NULL) 
		{
			printf("%s\t", g->vextex[pmove->index].data); //链表中存的是序号-> 打印顶点信息
			pmove = pmove->next;
		}
		printf("\n");
	}
}

int main() 
{
	LPGRAPH g = createGraph();
	printGraph(g);
	return 0;
}

/*输出*/

请输入边和顶点数:7 5
请输入所有顶点:A B C D E
请输入边的信息:
A B
A D
B C
C D
C E
D E
B E
//顺序由边的插入顺序决定
A:      D       B        
B:      E       C       A
C:      E       D       B
D:      E       C       A
E:      B       D       C