第二章 线性结构
2.1 线性表（list）
数据对象集：线性表是n（≥0）个元素构成的有序序列（
）
-
操作集：线性表L
- 初始化空
- 根据位序k查找值
- 查找元素x第一次出现的位置
- 删除指定位序的元素
- 返回线性表长度
-
主要操作代码实现(顺序存储)
初始化
查找
插入
删除
-
链式存储实现
初始化
查找
插入
删除
-
广义表
- 线性表的一种推广，在线性表中，n个基本元素都是基本的单元素；但是在广义表中，元素不仅可以是单元素也可以是另一个广义表。
- 问题：有时候一个域是一个不能分解的单元，也有可能是一个指针。
- C语言中可以用union解决，union可以把不同类型的数据组合在一起，不同类型的类型共用一处空间，另外再使用标记去区分。
- 线性表的一种推广，在线性表中，n个基本元素都是基本的单元素；但是在广义表中，元素不仅可以是单元素也可以是另一个广义表。
-
多重链表
-
多重链表中节点可能同时隶属于多个链
- 多重链表中节点的指针域会有多个，但是一个链表包含多个指针不一定是多重链表（比如双向链表，但其实该链表串联起来的链表实际上是同一个，只不过是指向了链表的不同方向。）
-
用途：
- 树和图等相对复杂的数据结构都可以采用多重链表的方式实现存储。
栗子1：矩阵存储
用二维数组方式存储
缺点：数组大小需要事先确定，稀疏矩阵会造成大量空间浪费
方法
结点数据域：行坐标Row、列坐标Col、数值Value
-
结点指针域：行指针（Right）、列指针（Down）、入口节点Term项
多重链表.png
多重链表存储节点统一表示.png
-
2.2 堆栈（Stack）
- 堆栈是一种线性结构，也是一个特殊的线性表
- 常见用途：函数调用、递归、（表达式求值）、深度优先搜索、回溯算法
栗子2：算数表达式求值
- 两类对象
- 运算数
- 运算符号
- 不同运算符号优先级不一样
- 前缀、中缀、后缀表达式
- 后缀表达式求值策略：从左向右扫描，逐个处理运算数和运算符号
- 要求：1 顺序存储结构（存储运算数） 2 返回最后存储两个运算数
- 堆栈：具有一定操作约束的线性表
- 只能在一端（栈顶，Top）做插入、删除
- 插入数据：入栈（Pus）
- 删除数据：出栈（Remove）
- 后入先出：LIFO
- 堆栈抽象数据类型描述
- 数据对象集：一个由0个或者多个元素的有穷线性表
- 操作集：长度为MaxSize的堆栈S
Stack,堆栈元素item
- 初始化（生成空堆栈，最大长度为MaxSize）
- 判断满栈
- 插入
- 判断空栈
- 删除
- 栈的顺序存储实现
- 栈的顺序结构通常是由一个一维数组和一个记录栈顶元素位置的变量组成
- 堆栈的链式存储实现
- 栈的链式存储结构实际上是一个单链表，叫做链栈。插入和删除操作只能在链栈的栈顶进行。
2.3 队列(Queue)
队列也是一种受限的线性表
插入和删除操作：只能在一端插入，而在另一端删除。
先入先出：FIFO
-
队列的顺序存储实现
- 用一维数组和一个记录队列头元素位置的变量front以及记录队尾位置的变量rear组成
- 循环队列，形成一个环
- 循环队列.png
-
链式存储
- 队列的链式存储结构可以用单链表实现。插入和删除操作分别在链表两头，front要做删除操作，在表头。rear做插入操作，在表尾。
