数据结构基础——线性表、栈、队列、串

**C语言版本 

 

• 数据结构

逻辑结构：集合（集合关系）；线性（一对一）；树（一对多）；图（多对多）

存储结构：顺序存储；链式存储

 

• 线性表（linear_list）

线性表是n个数据元素的有限序列（有一个头、一个尾、一个前驱、一个后继）。根据存储结构的不同，可分为：

顺序表：顺序存储结构实现

线性链表/单链表：链式存储结构实现

**线性表插入/删除元素的时间复杂度为O(n)

 

• 线性链表/单链表

链表中的一个节点a(i)存储两部分信息：

数据域：存储数据元素本身的信息

指针域：直接后继存储位置

 

• 静态链表

静态链表是用结构数据描述的链表，举例说明如下：

s[i].cur：指示i+1个节点在数组中的位置

s[i].data：存储线性表的第i个元素

 

• 循环链表与双向链表

循环链表：表中最后一个节点后继存储位置不为null，而是指向头节点

双向链表：节点中有两个指针域，直接后继和直接前驱

---

 

• 栈

限定仅在表尾进行插入或删除操作的线性表。表尾长称为栈顶；表头称为栈底。后进先出（LIFO）

作为线性表的一种，根据存储方式，可分为：顺序栈和链栈

• 队列

限定只能在一端插入，另一端删除的线性表。插入端称为对尾；删除端称为对头。先进先出（FIFO）

作为线性表的一种，根据存储方式，可分为：顺序队列和链队列

“假上溢”：顺序队列由于入队和出队操作中，头尾指针只增加不减小，致使被删元素的空间永远无法重新利用。 

循环队列：将顺序队列假想为一个环状的空间，以解决“假上溢”，充分利用存储空间。

**使用循环队列必须设定一个最大队列长度，如果不能确定所需的长度，采用链对。 

---

 

• 串/字符串

串/字符串：由零个或多个字符组成的有限序列

空串：零个字符的串

 

• 串的表示和存储

定长顺序存储：类似线性表的顺序存储，用一组地址连续的存储单元存储串值的字符序列

堆分配存储：存储地址连续，程序执行时动态分配

块链存储：类似线性表的链式存储结构

---

 

• 数据类型

定义：数据类型是一个值的集合和定义在这个值集上的一组操作的总称。

种类：按“值”的不同特性，可分为两类，一是非结构的原子类型，另一类是结构类型。原子类型的值是不可再分解的（如基本数据类型：整形、字符型等）。结构类型的值是由若干成分按照某种结构组成的。

上述几种线性结构中的数据都是非结构的原子类型，元素的值不可再分解。数组和广义表是两种结构类型的线性结构。

 

• 数组

数组一旦被定义，其维数和维界不能再改变。所以数组的操作除了初始化和销毁之外，只有存取元素和修改元素值的操作。

由于存储单元是一维结构，多维数组的存储有两种方式：以列序为主序；以行序为主序。

 

• 广义表/列表

广义表是线性表的推广

由于广义表中的数据元素可以具有不同的结构（原子或者广义表类型）不宜采用顺序存储结构，通常采用链式存储结构。根据数据元素的类型将存储结构中的节点分为两种：

表节点：表示列表。包括3个域，标志域、指示表头的指针域、指示表尾的指针域

原子节点：表示原子。包括2个域，标志域和值域