[Data Structures] 数据结构基础

用计算机解决一个具体问题时，一般要经过下列几个步骤：首先要从具体问题抽象出一个适当的数学模型，然后设计一个解此数学模型的算法，最后编出程序、进行测试、调整直至得到最终解答。寻求数学模型的实质是分析问题、从中提取操作的对象，并找出这些操作对象之间含有的关系，这实际上就是分析数据结构。数据结构是研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科。

　　数据结构是一门综合的专业基础课。数据结构的研究不仅涉及到计算机硬件(特别是编码理论、存储装置和存取方法)，而且和计算机软件的研究有着更密切的关系，无论是编译程序还是操作系统，都涉及到数据元素在存储器中的分配问题。有搜索引擎开发经验的朋友更清楚，良好的数据组织形式，对查找和存取数据元素非常有利。由此可见，数据结构是介于数学计算机硬件和软件三者之间的一门核心课程。数据结构不仅是程序设计(特别是非数值计算的程序设计)的基础，而且是设计和实现编译程序、操作系统、数据库系统及其它系统程序和大型应用程序的重要基础。

　　数据(Data)：是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。
数据元素(Data Element)：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。有时一个数据元素有若干个数据项(Data Item)组成。数据项是数据的不可分割的最小单位。
　　数据结构(Data Structure): 是相互之间存在一种或多种特定关系的数据元素的集合。元素之间的关系称为结构。

四类基本结构：

集合：结构中的数据元素之间除了“同属于一个集合”的关系外，别无其他关系。
结性结构：结构中的数据元素之间存在一个对一个的关系。
树形结构：结构中的数据元素之间存在一个对多个的关系。
图形结构或网状结构：结构中的数据元素之间存在多外对多个的关系。

数据结构中元素之间的关系描述的是数据元素之间的逻辑关系，称为数据的逻辑结构。
数据结构在计算机中的映象称为数据的物理结构，又称存储结构。它包括数据元素的表示和关系的表示。

数据元素之间的关系在计算机中有两种不同的映象：顺序映象和非顺序映象，由此得出两种不同的存储结构：顺序存储结构和链式存储结构。

顺序映象的特点是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。非顺序映象的特点是借助指示元素存储地址的指针(Pointer)表示数据元素之间的逻辑关系。

常用的数据结构有：线性表、栈和队列、串、数组和广义表、树、图等。

线性表
线性结构的特点是：
在数据元素的非空有限集合中，

存在唯一的一个被称做“第一个”的数据元素；
存在唯一的一个被称做“最后”一个的数据元素；
除第一个外，集合中的每个数据元素均只有一个前驱；
除最后一个之外，集合的每个数据元素均只有一个后继。

　　线性表是最常用且最简单的一种数据结构。简言之，一个线性表是n个数据元素的有限序列，它的长度可以根据需要增长或缩短，即对线性表的数据元素不仅可以进行访问，还可进行插入和删除等。
1.   线性表的顺序表示
线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。
假设线性表的每个元素占用l个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表的第i+1个数据元素的存储位置和第i个数据元素的存储位置之间满足如下关系：（i+1）的位置= i 位置+l. 也就是说线性表的顺序表示用存储位置相临表示了元素之间的关系，因此可以随机存取任一元素。缺点是：在插入或删除时要移动大量元素。
高级程序设计语言中数据类型具有随机存取的特性，因此通常都用数据来描述数据结构中的顺序存储结构。由于线性表长度可变，且所需最大存储空间随问题不同而不同，C语言中可用动态分配的一维数组描述。

2.   线性表的链式表示
1.   单链表
　　线性表的链式存储结构特点是用一组任意的存储单元存储线性表的数据元素(不一定是连续存储单元)，为了表示每个数据元素与其前驱或后继的逻辑关系，元素除要保存本身信息外，还要存储一个指示其直接前驱或后继的关系，这两部分信息组成元素的存储映象，称为结点(Node)。存储数据元素信息的域称为数据域；存储直接后继存储位置的域为指针域。指针域中存储的信息称做指针或链。N个结点链结成一个链表，即为线性表的链式存储结构。由于只有一个指针域，又称为线性链表或单链表。单链表用指针表示了元素之间的关系，指针为数据元素的逻辑关系的映象。
优点：在插入或删除元素时只要改变指针即可。
缺点：只有一个指示后继的指针，查找比较元素要从表头开始，不能随机存取。
2.   循环链表
　　循环链表特点是最后一个结点的指针域指向头结点，整个链表形成一个环。从表中任何一个结果出发均可以找到表中的其它结点。
3.   双向链表
      在双向链表的结点中有两个指针域，其一指向直接后继，另一指向直接前驱。解决单链表只能单向比较查找

栈和队列
　　栈和队列都是线性结构，都是线性表，但栈和队列的基本操作是线性表的子集，是操作受限的线性表。
栈
　　栈(Stack)是限定仅在表尾进行插入或删除操作的线性表。对栈来说，表尾有其特殊含义，称为栈顶(Top), 表头端称为栈底(Bottom)。不含元素的空表称为空栈。
　　栈的修改是按后进先出的原则进行的，因此栈又称为后进先出(Last In First Out)的线性表。
　　栈的典型应用是实现递归子方法调用。别外还有括号匹配的检验、行编辑程序、迷宫求解等等。
队列
　　队列(Queue)是一种先进先出(First In First Out 缩写FIFO) 线性表，它只允许在表的一端进行插入，而在另一端删除元素。最早进入队列的元素最早离开，允许插入的一端叫做队尾(Rear), 允许删除的一端则称为队头(Front)。队列的一个典型应用是操作系统中的作业排队。

字符串

数组和广义表

树和二叉树
　　树型结构是一类重要的非线性数据结构。
　　树(Tree)是n(N>=0)个结点的有限集合。在任意一棵非空树中：有且仅有一个特定的称为树的结点；当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,…Tm,　其中每个集合本身又是一查树，并且称为根的子树。
　　树的结点包含一个数据元素及若干指向其子树的分支。结点拥有的子树数称为结点的度。
度为０的结点称为叶子或终端结点。度不为０的结点称为非终端结点或分支结点。除根结点外，分支结点也称为内站结点。结的度是树内各结点的度的最大值。结点的子树称为该结点的孩子(Child)。相应地，该结点称为孩子的双亲(Parent)。同一个双亲的孩子之间互称兄弟(Sibling)。结点的祖先是从根到该结点所经分支上的所有结点。反之，以某结点为根的子树中的任一结点都称为该结点的子孙。
　　结点的层次从根开始定义起，根为第一层，根的孩子为第二层。若某结点在第l层，则其子树的根就在第l+1层。其双亲在同一层的结点互为堂兄弟。树中结点的最大层次为结的深度(Depth)或高度。
　　如果将树中结点的各子树看成从左至右是有次序的(即不能互换),则称该树为有序树，否则称为无序树。在有序树中最左边的子树的根称为第一个孩子，最右边的称为最后的一个孩子。
　　森林(Forest)是m(m>=0)棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。
　　在树型结构中，数据元素之间有着明显的层次关系，并且每一层上的数据元素可能和下一层中多个元素相关，但只能和上一层中一个元素相关。
图

－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－

[Data Structures] 线性表

参考《数据结构》