线性结构概念相关

前言

罗列一些基本概念，供后续文章使用，后续系列文章中不再过多阐述。

结构特点

在数据元素的有限集中：

1. 存在唯一的一个被称作“第一个”的数据元素
2. 存在唯一的一个被称作“最后一个”的数据元素
3. 除第一个之外，集合中的每个数据元素均只有一个前驱
4. 除最后一个之外，集合中每个数据元素均只有一个后继[^1]

常用的线性结构

线性表

基本定义：具有相同类型的有限多个数据元素组成的一个有序序列。
线性表存储结构事例

线性表顺序存储

基本定义：用一组地址连续的存储单元一次存储线性表的数据元素。常见的便是一维数组类型

线性表链式(linked)存储

基本定义：用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。常见的便是单链表或线性链表结构，双向链表，单向循环链表，双向循环链表等。
其它概念：数据域、指针域，其中指针域中存储的信息称之为指针或链。数据域与指针域共同组成一个节点（node）

栈(stack)

基本定义： 限定 **仅在 标尾进行插入或删除操作的线性表。表尾称之为栈顶（top），表头称之为栈底（bottom）

队列(queue /kyo͞o/)

基本定义：是一种 先进先出 (first in first out，缩写为FIFO)的线性表。只允许在表的一端进行插入，而在另一端删除元素。

串(string)

就是通常意义上的字符串。
基本定义：由零个或多个字符组成的有限序列，一般记为[^2]
$$
s = ‘a_1a_2···a_n’ (a\geq0)
$$
其它概念：

• 称两个串相等，当且仅当这两个串的值相等，即：两个串长度相等的同时，两者各个位置对应的字符也相等。
• 串的三种存储方式：
  • 定长顺序存储：类似于线性表的顺序存储结构，用一组地址连续的存储单元存储串值的字符序列。
  • 堆(heap)分配存储表示：任以一组地址连续的存储单元放串值字符序列，但它们的存储空间是在程序执行过程中冬天分配而得。
  • 块链存储表示：与线性表的链式存储类似，串的块链是每个节点存放固定长度的字符，除基本设定头指针外，还需有相应的尾指针来指示当前块链表中的最后结点，与此同时需要给出当前串的长度。用的不多

引用链接

[1] 严蔚敏，吴伟民.数据结构：C语言版[M].北京：北京大学出版社，2007: 18.
[2] 严蔚敏，吴伟民.数据结构：C语言版[M].北京：北京大学出版社，2007: 70.