[科普中国]-数据存储表示法

简介

数据存储对象包括数据流在加工过程中产生的临时文件或加工过程中需要查找的信息。数据以某种格式记录在计算机内部或外部存储介质上。数据存储要命名，这种命名要反映信息特征的组成含义。数据流反映了系统中流动的数据，表现出动态数据的特征；数据存储反映系统中静止的数据，表现出静态数据的特征。1

在计算机科学中，数据存储表示法一般是指数据的存储结构表示方法，来表示数据之间的联系。例如稀疏矩阵，有邻接矩阵与邻接表两种存储表示法来表示数据之间的关系。

数据存储结构数据结构数据结构指的是数据之间的相互关系，即数据的组织形式。

1．数据结构一般包括以下三方面内容：

① 数据元素之间的逻辑关系，也称数据的逻辑结构（Logical Structure）；数据的逻辑结构是从逻辑关系上描述数据，与数据的存储无关，是独立于计算机的。数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。

② 数据元素及其关系在计算机存储器内的表示，称为数据的存储结构（Storage Structure）；数据的存储结构是逻辑结构用计算机语言的实现（亦称为映象），它依赖于计算机语言。对机器语言而言，存储结构是具体的。一般，只在高级语言的层次上讨论存储结构。

③ 数据的运算，即对数据施加的操作。数据的运算定义在数据的逻辑结构上，每种逻辑结构都有一个运算的集合。最常用的检索、插入、删除、更新、排序等运算实际上只是在抽象的数据上所施加的一系列抽象的操作。所谓抽象的操作，是指我们只知道这些操作是"做什么"，而无须考虑"如何做"。只有确定了存储结构之后，才考虑如何具体实现这些运算。

分类在不产生混淆的前提下，常将数据的逻辑结构简称为数据结构。数据的逻辑结构有两大类：

（1）线性结构
线性结构的逻辑特征是：若结构是非空集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。
线性表是一个典型的线性结构。栈、队列、串等都是线性结构。

（2）非线性结构
非线性结构的逻辑特征是：一个结点可能有多个直接前趋和直接后继。数组、广义表、树和图等数据结构都是非线性结构。2

树的表示法1、双亲表示法

在树中除了根结点以外，其他结点都会仅有一个双亲结点。

将数组中的下标用于表示双亲结点的位置或者是左孩子或者右孩子或是由兄弟。当然，这样的结构依赖于存储的顺序是采用的是层序遍历。

2、孩子的多重链表表示法

这种表示方法分2种，一种是多重链表表示法，即用树的度就表示一个节点指针域的个数，这样很大程度上浪费了内存资源。第二种是孩子链表表示法，即一个节点的指针域的个数和其孩子的个数（该节点的度）相等。

3、孩子链表表示法

用多个单链表表示孩子，在同一个单链表中的孩子有着共同的双亲。

有孩子链表表示法衍生出来的双亲孩子表示法，既是将双亲表示法和孩子链表表示法相结合起来了，将孩子与双亲，双亲与孩子之间的关系展示出来，可以不用遍历便可寻找孩子的双亲或者双亲的孩子。

4、孩子兄弟表示法

存储区域分三块，中间那块存储结点的数据，左边指向该节点的第一个孩子，右边指向该节点的右兄弟。3

图的表示法邻接矩阵:

有向图的邻接矩阵

具有n个顶点的有向图可以用一个n′n的方形矩阵表示。假设该矩阵的名称为M，则当是该有向图中的一条弧时，M[i,j]=1；否则M[i,j]=0。第i个顶点的出度为矩阵中第i行中"1"的个数；入度为第i列中"1"的个数，并且有向图弧的条数等于矩阵中"1"的个数。

无向图的邻接矩阵

具有n个顶点的无向图也可以用一个n′n的方形矩阵表示。假设该矩阵的名称为M，则当（vi,vj）是该无向图中的一条边时，M[i,j]=M[j,i]=1；否则，M[i,j]=M[j,j]=0。第i个顶点的度为矩阵中第i 行中"1"的个数或第i列中"1"的个数。图中边的数目等于矩阵中"1"的个数的一半，这是因为每条边在矩阵中描述了两次。

在C 语言中，实现邻接矩阵表示法的类型定义如下所示：

#define MAX_VERTEX_NUM 20typedef struct graph{Elemtypeelem [MAX_VERTEX_NUM][MAX_VERTEX_NUM];int n;}Graph;邻接表

边结点的结构为：

adjvex是该边或弧依附的顶点在数组中的下标，next是指向下一条边或弧结点的指针

elem是顶点内容，firstedge是指向第一条边或弧结点的指针。

在C语言中，实现邻接表表示法的类型定义如下所示：

#defineMAX_VERTEX_NUM30//最大顶点个数typestructEdgeLinklist{//边结点intadjvex;structEdgeLinklist*next;}EdgeLinklist;typedefstructVexLinklist{//顶点结点Elemtypeelem;EdgeLinklist*firstedge;}VexLinklist,AdjList[MAX_VERTEX_NUM];创建有向图邻接表

voidCreate_adj(AdjListadj,intn){for(i=0;iadgvex=j-1;s->next=adj[i-1].firstedge;//将新的弧结点插入到相应的位置adj[i-1].firstegde=s; scanf(&i,&j);//输入下一条弧}}创建无向图的邻接表

voidCreate_adj(AdjListadj,intn){for(i=0;iadgvex=j-1;s2=(EdgeLinklist*)malloc(sizeof(EdgeLinklist));s2->adgvex=i-1;s1->next=adj[i-1].firstedge;adj[i-1].firstegde=s1;s2->next=adj[j-1].firstedge;adj[j-1].firstegde=s2; scanf(&i,&j);}}