c语言数据结构-图


一、现实世界中图的产生

在数据结构中:常见的数据结构有:
有一个父节点 多个子节点,这种数据结构可以组成一个树结构。
有一个父节点 一个子节点,这种数据结构就是一种典型的线性结构。
假如一个节点可能有多个父节点 多个子节点,或者可能与任意其它元素曾在子/父节点之间的关联,那么我们就把这类节点称之为图。
通过数据结构图,我们可以描述自然界任意一类事物的关系。


二、c语言数据结构图-概念

一个图包含:
一个顶点集合;
一个边的集合;
如果图中的边存在方向,那么我们就称图为有向图;反之则称之为无向图。
有向图-无向图

三、图的存储方式

图的存储方式有两种:

3.1邻接矩阵存储方法

邻接矩阵存储方法称之为数组存储方法,主要方式为:
采用两个数组存储一个图;
一个一维数组用来存放图中的数据;
一个是二维数组用来存储顶点之间的关系,称之为邻接矩阵。


例3.1.1:
3.1.1.1 一个具有n个节点的图
3.1.1.2 定义一个一维数组a[n-1],将图上的数据信息存放在 a[0] a[1] a[2] a[3] … a[n-2] a[n-1]
图节点A0 上的数据信息存放在a[0]上, 图节点A2 存放至 a[1] … 第n个节点上的数据信息存放至a[n-1]上
3.1.1.3 定义一个二维数组来存储节点上的关系
b[n-1][n-1];
b[a][b]=1;//代表第a个节点到b节点之间有边
b[a][b]=0;//代表第a个节点到b节点之间无边

描述上面一个有向图的二维数组和一维数组表示法


我们只需操作一维数组b[n]就可以操作图上的数据。



3.2 采用邻接表的方式对图进行存储


邻接矩阵的存储方式,不适用与边比较少的图中,因为边比较少,如果采用邻接矩阵的存储方式,会占用大量的存储空间。

邻接表的方式是采用顺序表和链表的方式来存储一个图的信息。
链表用来存储边的信息
数组用来存放顶点的数据信息。
对图中的每一个顶点建立一个链表,用来存放此节点边的情况及指向下一个节点情况。
举一个链表存储图情况的例子:

3.2.1 邻接表存储图的实现
#define _DINGDIANNUM 10
typedef struct Node{
int weiZhi; //在数组中的位置
struct Node *next;//指向下一个边
}Node;
typedef struct VNode{
节点数据类型 data; //图节点上的数据
Node *firstNode; //图的第一条边
} VNode;

VNode Array[_DINGDIANNUM];



四、采用链表存储图结构

采用c语言存储一个图时,首先我们必须熟悉一个图结构在现实中的表现:
画一个图结构:
有向图


存储结构分析:
上图拥有3个顶点 分别为A1 、A2、 A3
拥有三条边 分别为A2-A1 、A2->A3 、A3->A1

存储方式:
定义一个链表
typedef struct VNode{
int data;
struct Node *firstNode;
}VNode;

顶点

所指向顶点

所指向顶点
A1

A2(firstNode指向A1)

A1(firstNode指向A3)

A3(firstNode指向NULL)
A3(firstNode指向A1)

A1(firstNode指向NULL)

采用一个数组来存储所有的店,采用链表来存储边的信息。

设计代码

#include "stdio.h"
#include "stdlib.h"

typedef struct Node{
   int weiZhi;
   struct Node *next;
}Node;

typedef struct VNode{
   int data;
   struct Node *firstNode;
}VNode;

/*
创建一个图
*/
void createPic(
int jieDian,VNode G[]
){
   int i=0;
   int t=0;
   Node *n,*n1;
   /*验证节点数 是否等于VNode数 如果不等于则报错*/

   /*第一步 生成三个节点,并存储节点数据*/
   for(i=0;i< jieDian;i++){
       t =0;
       printf("请输入第%d节点上的数据\n",i);
       scanf("%d",&t);
       G[i].data =t;
       G[i].firstNode =NULL;
   }

   /*第二步 依次生成每个节点都对应的边*/
   for(i=0;i< jieDian;i++){
       t =0;
       printf("请输入第%d节点上的边",i);
       scanf("%d",&t);
       while(t !=-1){
         n =(Node *)malloc(sizeof(Node));
         n->next =NULL;
         n->weiZhi = t;
         if(n ==NULL) {printf("创建边链表失败!");exit(0);}
         if(G[i].firstNode ==NULL)
           { 
              G[i].firstNode = n;
           }
          else
           {
             n1 = G[i].firstNode ;
             while(n1)
              {
                n1 =n1->next;
              }
             n1 = n; 
           }
        scanf("%d",&t);
      }
   }
   
}

int main(){
  VNode G[3];
  createPic(3,G);
  return 1;
}
    
       

相关阅读:
c语言数据结构-树
c语言 数据结构 --二叉树
c语言数据结构-链表
c语言数据结构-栈