数据结构基本概念
什么是数据结构？
- 数据
数据即信息的载体，是能够输入到计算机中并且能被计算机识别、存储和处理的符号总称。
- 数据元素
数据元素是数据的基本单位，又称之为记录（Record）。一般，数据元素由若干基本项（或称字段、域、属性）组成。
- 数据结构
数据结构指的是数据元素及数据元素之间的相互关系，或组织数据的形式。
数据之间的结构关系
表示数据之间的抽象关系（如邻接关系、从属关系等），按每个元素可能具有的直接前趋数和直接后继数将逻辑结构分为“线性结构”和“非线性结构”两大类。
存储结构
逻辑结构在计算机中的具体实现方法，分为顺序存储方法、链接存储方法、索引存储方法、散列存储方法。
逻辑结构
- 特点：
- 只是描述数据结构中数据元素之间的联系规律
- 是从具体问题中抽象出来的数学模型，是独立于计算机存储器的（与机器无关）
2.逻辑结构的分类
线性结构
树形结构（层次结构）
图状结构（网状结构）
其他结构
线性结构
对于数据结构课程而言，简单地说，线性结构是n个数据元素的有序（次序）集合。
- 集合中必存在唯一的一个”第一个元素”；
- 集合中必存在唯一的一个”最后的元素”；
- 除最后元素之外，其它数据元素均有唯一的”后继”；
- 除第一元素之外，其它数据元素均有唯一的”前驱”。
树形结构（层次结构）
树形结构指的是数据元素之间存在着“一对多”的树形关系的数据结构，是一类重要的非线性数据结构。在树形结构中，树根结点没有前驱结点，其余每个结点有且只有一个前驱结点。叶子结点没有后续结点，其余每个结点的后续节点数可以是一个也可以是多个。
图状结构（网状结构）
图是一种比较复杂的数据结构。在图结构中任意两个元素之间都可能有关系，也就是说这是一种多对多的关系。
其他结构
除了以上几种常见的逻辑结构外，数据结构中还包含其他的结构，比如集合等。有时根据实际情况抽象的模型不止是简单的某一种，也可能拥有更多的特征。
存储结构
- 特点：
- 是数据的逻辑结构在计算机存储器中的映象（或表示）
- 存储结构是通过计算机程序来实现的，因而是依赖于具体的计算机语言的。
2.存储结构分类
顺序存储
链式存储
索引存储
散列存储
顺序存储
顺序存储（Sequential Storage）：将数据结构中各元素按照其逻辑顺序存放于存储器一片连续的存储空间中。
链式存储
链式存储（Linked Storage）：将数据结构中各元素分布到存储器的不同点，用记录下一个结点位置的方式建立它们之间的联系，由此得到的存储结构为链式存储结构。
索引存储
索引存储（Indexed Storage）：在存储数据的同时，建立一个附加的索引表，即索引存储结构=数据文件+索引表。
散列存储
散列存储(Hash Structure)： 根据数据元素的特殊字段(称为关键字key)，计算数据元素的存放地址，然后数据元素按地址存放，所得到的存储结构为散列存储结构(或Hash结构)。
线性表
线性表的定义是描述其逻辑结构，而通常会在线性表上进行的查找、插入、删除等操作。
线性表作为一种基本的数据结构类型，在计算机存储器中的映象（或表示）一般有两种形式，一种是顺序映象，一种是链式映象。
线性表的顺序存储
线性表的顺序存储
- 定义
若将线性表L=(a0,a1, ……,an-1)中的各元素依次存储于计算机一片连续的存储空间，这种机制表示为线性表的顺序存储结构。
- 特点
- 逻辑上相邻的元素 ai, ai+1，其存储位置也是相邻的；
- 存储密度高，方便对数据的遍历查找。
- 对表的插入和删除等运算的效率较差。
线性表的链式存储
- 定义
将线性表L=(a0,a1,……,an-1)中各元素分布在存储器的不同存储块，称为结点，每个结点（尾节点除外）中都持有一个指向下一个节点的引用，这样所得到的存储结构为链表结构。
- 特点
- 逻辑上相邻的元素 ai, ai+1，其存储位置也不一定相邻；
- 存储稀疏，不必开辟整块存储空间。
- 对表的插入和删除等运算的效率较高。
- 逻辑结构复杂，不利于遍历。
