11-07 08:06 阅读 102

数据结构学习笔记(二) - 线性结构

第二章、线性结构

2.1 线性表

1. 线性表及其实现

线性结构是数据结构中最基础，也是最简单的一种数据结构类型，其中典型的一种叫线性表，那么什么是线性表？通过下面这个例子来理解：

用程序设计语言来表示一元多项式以及实现相加、相减和相乘等运算
分析：一元多项式的关键数据
多项式项数 $nn n$
各项系数 $aia_{i}ai$ 和指数 $ii i$
实现：
利用顺序存储结构直接表示
数组中的分量a[i]对应多项式中 $xix^{i}xi$ 的系数 $aia_{i}ai$
例如： $f(x)=4x5−3x2+1f(x) = 4x^{5} - 3x^{2} + 1f(x)=4x5−3x2+1$ 表示成
const a: Array<number> = [1, 0, -3, 0, 0, 4] 复制代码
实现简单但是当多项式中指数跨度较大时会造成空间的巨大浪费
利用顺序存储结构存储非零项
元祖数组中的分量a[i]对应多项式中 $xix^{i}xi$ 的系数 $aia_{i}ai$ 和指数 $ii i$ 组成的元祖
例如： $P(x)=9x12+15x8+3x2P(x) = 9x^{12} + 15x^{8} + 3x^{2}P(x)=9x12+15x8+3x2$ 表示成
const a: Array<[number, number]> = [[9, 12], [15, 8], [3, 2]] 复制代码
为了使运算方便，将元祖数组中的分量按照指数 $ii i$ 的大小进行存储
利用链表存储结构存储非零项
链表中的每个结点存储多项式中的一个非零项，包括系数 $aia_{i}ai$ 和指数 $ii i$ 两个数据域以及一个用于保存指向下一结点指针的指针域，为了使运算方便，依然将链表中的结点按照指数 $ii i$ 的大小进行存储
例如： $P(x)=9x12+15x8+3x2P(x) = 9x^{12} + 15x^{8} + 3x^{2}P(x)=9x12+15x8+3x2$ 表示成
interface LinkedNode {   a: number   i: number   next?: LinkedNode }         const a: LinkedNode = {   a: 9,   i: 12,   next: {     a: 15,     i: 8,     next: {       a: 3,       i: 2     }   } } 复制代码

结论：表示多项式的不同方法解决的是一个共性问题：有序线性序列的组织和管理

1. 线性表

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

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

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

类型名称：线性表（List）

数据对象集：线性表是由 $NN N$ （ $N≥0N \geq 0N≥0$ ）个元素构成的有序序列

操作集：线性表L $∈\in∈$ List，整数 $ii i$ 表示位置，元素x $∈\in∈$ ElementType，线性表的基本操作主要有：

create(): List：返回一个空线性表L
findKth(k: number, l: List): ElementType：根据位序 $KK K$ 返回相应的元素
find(x: ElementType, l: List): number：在线性表L中查找元素x第一次出现的位置
insert(x: ElementType, i: number, l: List): void：在位序 $ii i$ 之前插入一个新的元素x
delete(i: number, l: List): void：删除指定位序 $ii i$ 的元素
getLength(l: List): number：返回线性表L的长度

3. 线性表的实现方式

顺序存储：利用数组存放线性表的各元素，线性表中的两个相邻元素在逻辑上和物理上都是相邻的
```
interface ArrayList<T> {     data: Array<T>     last: number } 复制代码
```

按值查找、插入元素和删除元素的平均时间复杂度均为 $O(n)O(n) O (n)$

链式存储：利用链表存放线性表的各元素，线性表中的两个相邻元素在逻辑上是相邻的，在物理上不是

interface ListNode<T> {   data: T   next: ListNode<T> } interface LinkedList<T> {   head: ListNode<T> } 复制代码

获取线性表长度的时间复杂度为 $O(n)O(n) O (n)$
按位序查找、按值查找、插入元素和删除元素的平均时间复杂度均为 $O(n)O(n) O (n)$

2. 广义表

通过下面这个例子来理解广义表：

用程序设计语言来表示二元多项式
分析：将二元多项式看成关于其中一个元的一元多项式，每一项的系数是关于另一个元的一元多项式或者常数
例如： $P(x,y)=9x12y2+4x12+15x8y3−x8y+3x2P(x,y) = 9x^{12}y^{2} + 4x^{12} + 15x^{8}y^{3} - x^{8}y + 3x^{2}P(x,y)=9x12y2+4x12+15x8y3−x8y+3x2$ 可以改写成 $P(x,y)=(9y2+4)x12+(15y3−y)x8+3x2P(x,y) = (9y^{2} + 4)x^{12} + (15y^{3} - y)x^{8} + 3x^{2}P(x,y)=(9y2+4)x12+(15y3−y)x8+3x2$
仍然用链表实现表示以上改写后的一元多项式，链表中的每个结点存储多项中的一个非零项，不同的是，包括指数 $ii i$ 数据域和一个用于保存指向下一结点指针指针域，以及一个系数数据域或者一个用于保存指向关于另一个元的一元多项式的链表的指针域

广义表：

广义表是线性表的推广
在线性表中，每个元素都是基本的单元素，而广义表中的元素是单元素或另一个广义表

3. 多重链表

多重链表：链表中的结点可能同时隶属于多个链表

多重链表中的结点包含多个指针域，之前的广义表就属于多重链表
但包含两个指针域的链表并不一定就是多重链表，例如双向链表就不属于多重链表

多重链表有广泛的用途，例如树和图这样相对复杂的数据结构都可以利用多重链表存储方式实现

通过下面的例子来理解多重链表：

用程序设计语言来表示矩阵
分析：
可以用二维数组来表示矩阵，但二维数组的实现有两个缺陷：
数组的大小需要事先预知
对于稀疏矩阵，将造成大量的存储空间浪费
采用一种典型的多重链表——十字链表来存储矩阵中的非零项
每一行和每一列都用一个循环链表来存储
每个结点包含三个数据域：行坐标、列坐标和数值
每个结点还包含行指针和列指针两个指针域，分别用来把同行和同列串起来
入口元素的行坐标、列坐标和数值数据域分别保存稀疏矩阵的行数、列数和非零项个数

2.2 堆栈

堆栈是一种数据结构，也是一种特殊的线性表，堆栈在计算机学科中有广泛的用途，例如在函数调用、递归和表达式求值都需要用到堆栈，通过下面的例子来理解堆栈：

用程序设计语言求算术表达式的值
例如：求算术表达式 $5+6÷2−3×45 + 6 \div 2 - 3 \times 45+6÷2−3×4$
分析：
$5+6÷2−3×4=5+3−3×4=5+3−12=8−12=−45 + 6 \div 2 - 3 \times 4 = 5 + 3 - 3 \times 4 = 5 + 3 - 12 = 8 - 12 = -45+6÷2−3×4=5+3−3×4=5+3−12=8−12=−4$
算术表达式由两类对象构成：运算数（5、6、3和4）和运算符号（ $+++$ 、 $---$ 、 $×\times×$ 、 $÷\div÷$ ）\
不同运算符号的优先级不同
平时使用的算术表达式称为中缀表达式，即表达式中运算符号位于两个运算数中间，而用程序求中缀表达式的值较为困难，因此可以考虑将中缀表达式改写为后缀表达式，即表达式中运算符号位于两个运算数之后，例如将 $5+6÷2−3×45 + 6 \div 2 - 3 \times 45+6÷2−3×4$ 改写为后缀表达式可以得到 $5 6 2÷+ 3 4×−5 \ 6 \ 2 \div + \ 3 \ 4 \times -5 6 2÷+ 3 4×−$
后缀表达式的求值策略：从左向右对表达式进行扫描，若遇到运算数则先记住，若遇到运算符号则对之前记住的倒数两个运算数进行运算

结论：需要有一种存储方法，能够按顺序存储运算数，并在需要时倒序输出

1. 堆栈

只能在栈顶做插入和删除操作的线性表

插入数据称为入栈
删除数据称为出栈
后入先出：Last In First Out（LIFO）

2. 堆栈的抽象数据类型描述

类型名称：堆栈（Stack）

数据对象集：堆栈是一个有零个或多个元素的有穷线性表

操作集：长度为maxSize的堆栈S $∈\in∈$ Stack，元素x $∈\in∈$ ElementType，堆栈的基本操作主要有：

create(maxSize: number): Stack：返回一个空的堆栈，其最大长度为maxSize
isFull(maxSize: number, s: Stack): boolean：判断堆栈S是否已满
isEmpty(s: Stack): boolean：判断堆栈S是否为空
push(x: ElementType, s: Stack): void：将元素x压入堆栈S
pop(s: Stack): ElementType：删除并返回堆栈S栈顶元素

3. 堆栈的实现方式

顺序存储：利用数组存储堆栈中的各元素

interface ArrayStack<T> {   data: Array<T> } 复制代码

链式存储：利用链表存储堆栈中的各元素，将链表的头作为堆栈的栈顶

interface ListNode<T> {   data: T   next: ListNode<T> } interface LinkedStack<T> {   // 链表头结点，便于操作   hair: ListNode<T> } 复制代码

4. 堆栈应用：表达式求值

将中缀表达式转换为后缀表达式的流程

从左向右读取中缀表达式中的每个对象，对不同对象采取不同的处理方法：

若优先级大于栈顶运算符，则将其压入堆栈
若优先级小于等于栈顶运算符，则不断将栈顶运算符弹出并输出，直到该运算符大于栈顶运算符的优先级为止，之后将该运算符压入堆栈

运算数：将其直接输出
左括号：将其压入堆栈
右括号：将栈顶运算符弹出并输出，直到遇到左括号（弹出但不输出）
运算符：

表达式中的对象全部处理完成后，将堆栈中的运算符一并输出

5. 堆栈的其他应用

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

2.3 队列

1. 队列

只能在队尾插入而在队首删除的线性表

插入数据称为入队
删除数据称为出队
先入先出：First In First Out（FIFO）

2. 队列的抽象数据类型描述

类型名称：队列（Queue）

数据对象集：队列是一个有零个或多个元素额有穷线性表

操作集：长度为maxSize的队列Q $∈\in∈$ Queue，元素x $∈\in∈$ ElementType，队列的基本操作主要有：

create(maxSize: number): Queue：返回一个空的队列，其最大长度为maxSize
isFull(maxSize: number, q: Queue): boolean：判断队列S是否已满
isEmpty(q: Queue): boolean：判断队列S是否为空
enQueue(x: ElementType, q: Queue): void：将元素x插入到队列S
deQueue(q: Queue): ElementType：删除并返回队列S队首元素

3. 队列的实现方式

顺序存储：利用数组存储堆栈中的各元素
```
interface ArrayQueue<T> {   data: Array<T> } 复制代码
```
对队列进行几次操作后，可能会出现数组前几位没有值而后几位有值的情况，导致空间的浪费，可以采用循环队列解决这一问题。

链式存储：利用链表存储堆栈中的各元素，将链表的头作为队列的队尾，而将链表的尾作为队列的队首

interface ListNode<T> {   data: T   next: ListNode<T> } interface LinkedQueue<T> {   // 链表头结点   front: ListNode<T>   // 链表尾结点   rear: ListNode<T> } 复制代码

2.4 实例：多项式乘法与加法运算

作者：Stan9726
链接：https://juejin.cn/post/7027750954711646239