C语言《数据结构》——图的概念和创建，遍历

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

前言

提示：这里可以添加本文要记录的大概内容：

例如：随着计算机网络的发展，编程成了一种很常见且重要的职业，学好编程就要学好数据结构，下面将介绍数据结构中的图结构。

提示：以下是本篇文章正文内容，下面案例可供参考

一、什么是“图”

图（Graph）结构是一种非线性的数据结构，图在实际生活中有很多例子，比如交通运输网，地铁网络，社交网络，计算机中的状态执行（自动机）等等都可以抽象成图结构。图结构比树结构复杂的非线性结构。

二、图的基础知识和表示

1.图的基础

2.图的分类

有向图和无向图

带权图和不带权图

邻接矩阵

带权值的图，不连通的边用无穷表示，连通的边用边的权值表示。

代码如下（示例）：

//数据结构之图;
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
int main(void)
{
	int Graph[5][5] = { 0 };//先初始化为零。
	Graph[0][2] = 1;
	Graph[0][4] = 1;
	Graph[1][0] = 1;
	Graph[1][2] = 1;
	Graph[2][3] = 1;
	Graph[3][4] = 1;
	Graph[4][3] = 1;
	for (int i = 0; i < 5; i++)
	{
		for (int j = 0; j < 5; j++)
		{
			printf("%5d", Graph[i][j]);
		}
		putchar('\n');
	}
}

2.图的另一种表示——邻接表

邻接表是一种顺序表和链表的组成结构，顺序表的每一个结点都是一个链式表的头结点。这种表可以运用到散列表中，线性探测法。前面的散列表已经介绍。

代码如下（示例）：

//图——邻接表
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<Windows.h>
#include<string.h>
#define true 2
#define false -2
#define ok 1
#define erro -1
typedef int elemstyle;
//构建链表结构体;
typedef struct node 
{
	elemstyle key;
	struct node* next;
}GraphNode;
typedef struct graph
{
	GraphNode* pn;
	int n;//代表顺序表的长度;
}GraphList;
//创建结点;
GraphNode* creatGraphNode(elemstyle val)
{
	GraphNode* newnode = (GraphNode*)malloc(sizeof(GraphNode));
	newnode->key = val;
	newnode->next = NULL;
	return newnode;
}
//邻接表的初始化;
GraphList* Init_Graph(int n)
{
	GraphNode* pn = (GraphNode*)malloc(sizeof(GraphNode)*n);
	for (int i = 0; i < n; i++)
	{
		pn[i].key = i;
		pn[i].next = NULL;
	}
	GraphList* pt = (GraphList*)malloc(sizeof(GraphList));
	pt->n = n;
	pt->pn = pn;
	return pt;
}
//邻接表创建成功后，就可以对有联系的结点进行连接;
int insert_GraphNode(GraphList*pt,int pos,int pval)//pos代表连接的数据，pval代表连接数据的值.
{
	assert(pt != NULL);
	GraphNode* Node = creatGraphNode(pval);
		GraphNode* pmove = &(pt->pn[pos]);
		GraphNode* curr=pt->pn[pos].next;
		while (curr)
		{
			pmove = curr;
			curr = curr->next;
		}
		pmove->next = Node;
	return ok;
}
//遍历邻接表;
int printGraph(GraphList* pt)
{
	assert(pt != NULL);
	for (int i = 0; i < pt->n; i++)
	{
		printf("%3d:", pt->pn[i].key);
		GraphNode* curr = pt->pn[i].next;
		while (curr)
		{
			printf("->%3d", curr->key);
			curr = curr->next;
		}
		putchar('\n');
	}
	return true;
}
//调试函数;
int main(void)
{
	GraphList* pt;
	int n;
	scanf("%d", &n);
	pt=Init_Graph(n);
	insert_GraphNode(pt, 0, 2);
	insert_GraphNode(pt, 0, 3);
	insert_GraphNode(pt, 1, 0);
	insert_GraphNode(pt, 1, 2);
	insert_GraphNode(pt, 2, 3);
	insert_GraphNode(pt, 3, 4);
	printGraph(pt);
}

该处使用的url网络请求的数据。

这里只是简单的一个邻接表的实现；可以参考一下。

总结

图作为一种数据结构，他与树的不同在于它不再是一种简单的线性结构，他是一种复杂的非线性结构，具有更大的使用价值，如和广义表，散列表结合起来使用更好，可以解决很多问题。