附录：所有blog的链接

数据结构学习笔记（1）：基本概念
数据结构学习笔记（2）：线性结构
数据结构学习笔记（3-5）：树
数据结构学习笔记（6-8）：图
数据结构学习笔记（9-10）：排序
数据结构学习笔记（11）：散列查找
数据结构学习笔记（12）：综合习题选讲

第二讲 线性结构

2.1 线性表及其实现

线性表（Linear List）：

由同类型数据元素构成有序序列的线性结构

• 表中元素个数称为线性表的长度
• 线性表没有元素时，称为空表
• 表起始位置称表头，表结束位置称表尾

线性表的抽象数据类型描述：

**类型名称：**线性表（List）数据对象集：线性表是n（e0）个元素构成的有序序列（a1，a2…，an）
**操作集：**线性表L=List，整数i表示位置，元素X= ElementType，线性表基本操作主要有：

• 初始化：List MakeEmpty（）：初始化一个空线性表L；
• 返回位置对应值：ElementType FindKth（int K，ListL）：根据位序K，返回相应元素；
• 查找：int Find（ElementType X，ListL）：在线性表L中查找X的第一次出现位置；
• 插入：void Insert（ElementType X，inti，ListL）：在位序i前插入一个新元素X；
• 删除：void Delete（int i，ListL）：删除指定位序i的元素；
• 求长度：int Length（List L）：返回线性表L的长度n。

数组（线性表）连续存储空间顺序存放，数组求长度简单插入删除较为困难

链表插入删除比较简单 求长度比较困难

广义表（Generalized List）

• 广义表是线性表的推广
• 对于线性表而言，n个元素都是基本的单元素；
• 广义表中，这些元素不仅可以是单元素也可以是另一个广义表。

多重链表：

链表中的节点可能同时隶属于多个链

• 多重链表中结点的指针域会有多个，如前面例子包含了Next和SubList两个指针域；
• 但包含两个指针域的链表并不一定是多重链表，比如在双向链表不是多重链表。
• 多重链表有广泛的用途：基本上如树、图这样相对复杂的数据结构都可以采用多重链表方式实现存储。such as 二维稀疏矩阵（行指针列指针）。

2.2 堆栈

堆栈是一种特殊的线性表

后缀表达式

中缀表达式：运算符号位于两个运算数之间。如$a+b\times c-d÷e$

后缀表达式：运算符号位于两个运算数之后。如$abc\times +de÷-$

后缀表达式求解相对容易，因为看到运算符号的时候已经知道数据了

后缀表达式求值策略：从左向右“扫描”，逐个处理运算数和运算符号
1.遇到运算数怎么办？记住。如何“记住”目前还不未参与运算的数？存入数据结构中。
2.遇到运算符号怎么办？进行计算。对应的运算数是什么？最后两个记住的数据。

需要有种存储方法，能顺序存储运算数，并在需要时“倒序”输出！

62/3-42*+
33-42*+
042*+
08+
8

• 1
• 2
• 3
• 4
• 5

堆栈的抽象数据类型描述：

• 类型名称：堆栈（Stack）（具有一定操作约束的线性表）

• 数据对象集：一个有0个或多个元素的有穷线性表。

• 操作集：长度为 MaxSize 的堆栈S $\in$ Stack，堆栈元素item=ElementType

  • 1、Stack CreateStack（int MaxSize）：生成空堆栈，其最大长度为MaxSize；
  • 2、int IsFull（Stack S，int MaxSize）：判断堆栈S是否己满；
  • 3、void Push（Stack，ElementType item）：将元素item压入堆栈；
  • 4、int IsEmpty（StackS）：判断堆栈S是否为空；
  • 5、ElementType Pop（Stack S）：删除并返回栈顶元素；

堆栈的特点：

• 只在一端（栈顶，Top）做插入、删除
• 插入数据：入栈（Push）
• 删除数据：出栈（Pop）
• 后入先出：Last In First Out（LIFO）

堆栈的顺序存储实现

栈的顺序存储结构通常由一个一维数组和一个记录栈顶元素位置的变量组成。

入栈前判断是否满，出栈前判断是否空。

堆栈的链式存储实现

栈的链式存储结构实际上就是一个单链表，叫做链栈。插入和删除操作只能在链栈的栈顶进行。

栈顶指针Top只能放在链头，因为删除插入都较为方便，如果使用链尾做删除操作的时候删除最后一个节点找不到上一个节点。

删除操作需要释放空间。

堆栈的应用：

中缀表达式的求值：

基本策略：将中缀表达式转换为后缀表达式
中缀表达式和后缀表达式规律：

1.运算数相对顺序不变
2.运算符号顺序发生改变

使用堆栈进行运算

需要存储“等待中”的运算符号

要将当前运算符号与“等待中”的最后一个运算符号比较

左括号存入堆栈前优先级高但是存入之后优先级低

堆栈的其他应用：

• 函数调用及递归实现
• 深度优先搜索
• 回溯算法

2.3 队列

队列(Quene)定义：

具有一定操作约束的线性表

队列的特点：

插入和删除操作：只能在一端插入，而在另一端删除。

数据插入：入队列(AddQ)

数据删除：出队列(DeleteQ)

先来先服务

先进先出：FIFO

队列的抽象数据类型描述：

类型名称：队列（Queue)
数据对象集：一个有0个或多个元素的有穷线性表。
操作集：长度为MaxSize的队列Q=Queue，队列元素item e ElementType

• 1、Queue CreatQueue(int MaxSize)：生成长度为MaxSize的空队列；
• 2、int IsFullQ(Queue Q，int MaxSize)：判断队列Q是否已满；
• 3、void AddQ(Queue Q，Element Type item)：将数据元素item插入队列Q中；
• 4、int IsEmptyQ(Queue Q)：判断队列Q是否为空；
• 5、ElementType DeleteQ(Queue Q)：将队头数据元素从队列中删除并返回。

队列的顺序存储实现

队列的顺序存储结构通常由一个一维数组和一个记录队列头元素位置的变量front以及一个记录队列尾元素位置的变量rear组成。

顺环队列解决的问题：

队列头元素出去后存储空间导致的浪费如下图可见

顺环队列带来的问题：front==rear的时候没有办法区分是满了还是空

顺环队列问题的解决方案：

1)使用额外标记：size（记录个数）或者tag（记录最后一次操作是插入还是删除，以此判断是空还是满）

2)仅使用n-1个数组空间

队列的链式存储实现

队列的链式存储结构通常由一个单链表实现，插入和删除操作分别在链表的头部和尾部进行。front和rear分别在链头和链尾，因为链尾作删除操作就不知道上一个存储单元在哪里了。