大话数据结构

2019-07-08  本文已影响0人  怪客半

大话数据结构

前言

第一章 数据结构绪论

1.1 开场白

1.2 你数据结构怎么学的？

1.3 数据结构起源

1.4 基本概念和术语

1.4.1 数据

数值数据、字符数据（包括声音、视频等）

1.4.2 数据元素

组成数据的、有一定意义的基本单位，也称为记录

1.4.3 数据项

数据不可分割的最小单位

1.4.4 数据对象

性质相同的数据元素的集合，是数据的子集

1.4.5 数据结构

是相互之间存在一种或多种特定关系的数据元素的集合

1.5 逻辑结构与物理结构

1.5.1 逻辑结构

数据对象中数据元素之间的相互关系

1.集合结构

数据元素同属于一个集合，没有其他关系，平等关系

2.线性结构

数据元素是一对一关系

3.树形结构

数据元素之间存在一对多的层次关系

4.图形结构

数据元素是多对多的关系

1.5.2 物理结构

也叫存储结构
是指数据的逻辑结构在计算机中的存储形式
两种形式：顺序存储和链式存储

1.顺序存储结构

把数据元素存放在地址连续的存储单元里
逻辑关系=物理关系

2.链式存储结构

数据元素存放在任意的存储单元
引入指针存放数据元素的位置

逻辑结构是面向问题的，而物理结构就是面向计算机的，其基本的目标就是将数据及其逻辑关系存储到计算机的内存中。

1.6 抽象数据类型

1.6.1 数据类型

指一组数值相同的值的集合及定义在此集合上的一些操作的总称
C语言中数据类型：

抽象是指抽取出事物具有的普遍性的本质。抽象是一种思考问题的方式，它隐藏细节，只保留实现目标所必需的信息。

1.6.2 抽象数据类型

是指一个数学模型及定义在该模型上的一组操作

1.7 总结回顾

1.8 结尾语

第2章 算法

2.1 开场白

2.2 数据结构与算法关系

梁山伯与祝英台、罗密欧与朱丽叶

2.3 两种算法的比较

高斯：求1+2+3+...+100的值的传统算法和高效算法

2.4 算法定义

2.5 算法的特性

输入、输出、有穷性、确定性和可行性

2.5.1 输入输出

2.5.2 有穷性

2.5.3 确定性

无歧义

2.5.4 可行性

2.6 算法设计的要求

2.6.1 正确性

2.6.2 可读性

2.6.3 健壮性

2.6.4 时间效率高和存储量低

2.7 算法效率的度量方法

2.7.1 事后统计方法

缺点很多，不科学，不准确，基本不用

2.7.2 事前分析估算方法

每天打游戏与每天学习的差别

2.8 函数的渐进增长

判断一个算法的效率时，函数中的常数和其他次要项常常可以忽略，而更应该关注主项（最高阶项）的阶数

2.9 算法时间复杂度

2.9.1 算法时间复杂度定义

2.9.2 推导大O阶方法

2.9.3 常数阶

O(1)

2.9.4 线性阶

O(n)

2.9.5 对数阶

O(㏒n)

2.9.6 平方阶

O(n²)

2.10 常见的时间复杂度

2.11 最坏情况与平均情况

2.12 算法空间复杂度

不是讨论重点，时间复杂度才是重点。

2.13 总结回顾

2.14 结尾语

愚公移山固然可敬，但发明炸药和推土机，可能更加实在和聪明。

第3章 线性表

0个或多个数据元素的有限序列

3.1 开场白

幼儿园的小朋友按次序排队一样

3.2 线性表的定义

前驱元素、后继元素
空表

3.3 线性表的抽象数据类型

基本操作：创建、初始化、置空、读表、查表、求长、插入、删除等
及各种基本操作的组合

3.4 线性表的顺序存储结构

3.4.1 顺序存储定义

用一段地址连续的存储单元一次存储线性表的数据元素

3.4.2 顺序存储方式

起始位置、最大长度、当前长度

3.4.3 数据长度与线性表长度区别

3.4.4 地址计算方法

存储单元的编号成为地址
线性表时间复杂度为O(1)
随机存取结构

3.5 顺序存储结构的插入和删除

3.5.1 获得元素操作

3.5.2 插入操作

插入位置之后的元素统一后移一个单位，注意越界问题

3.5.3 删除操作

插入和删除操作的时间复杂度都是O(n)

3.5.4 线性表顺序存储结构的优缺点

3.6 线性表的链式存储结构

3.6.1 顺序存储结构不足的解决办法

3.6.2 线性表链式存储结构定义

任意的存储单元
数据域、指针域组成一个结点
单链表：结点中只有一个指针域
头结点

3.6.3 头指针和头结点的异同

头结点不一定会有
头指针一定会有

3.6.4 线性表链式存储结构代码描述

3.7 单链表的读取

必须从头开始找

3.8 单链表的插入与删除

3.8.1 单链表的插入

事先判断插入位置是否存在

3.8.2 单链表的删除

事先判断删除位置是否存在
插入和删除的时间复杂度均为O(n)

3.9 单链表的整表创建

头插法、尾插法

3.10 单链表的整表删除

3.11 单链表结构与顺序存储结构优缺点

3.12 静态链表

用数组描述的链表叫做静态链表
应用场景：为没有指针的高级语言设计的一种单链表能力

3.12.1 静态链表的插入操作

3.12.2 静态链表的删除操作

3.12.3 静态链表的优缺点

3.13 循环链表

3.14 双向链表

新增指向前驱结点的指针域
用空间来换时间

3.15 总结回顾

线性表的顺序结构和链式存储结构是其他数据结构的基础，很重要

3.16 结尾语

第4章 栈与队列

栈：仅在表尾进行插入和删除操作
队列：只允许在一端进行插入，另一端进行删除

4.1 开场白

左轮手枪与弹夹式手枪

4.2 栈的定义

4.2.1栈的定义

栈顶：允许插入和删除的一端
栈底
后进先出 LIFO结构

4.2.2 进栈出栈变化形式

4.3 栈的抽象数据类型

4.4 栈的顺序存储结构及实现

4.4.1 栈的顺序存储结构

栈底：下标为0的一端
类比游标卡尺

4.4.2 栈的顺序存储结构--进栈操作

4.4.3 栈的顺序存储结构--出栈操作

4.5 两栈共享空间

4.6 栈的链式存储结构及实现

4.6.1 栈的链式存储结构

链栈

4.6.2 栈的链式存储结构--进栈操作

4.6.2 栈的链式存储结构--出栈操作

进栈、出栈的时间复杂度均为O(1)

4.7 栈的作用

简化程序设计
类比用脚走路和乘坐交通工具
很多高级语言都有对栈结构的封装

4.8 栈的应用--递归

4.8.1 斐波那契数列实现

兔子繁殖问题
数学模型

4.8.2 递归定义

直接调用自己或通过一系列的调用语句间接地调用自己的函数
递归会建立函数副本，消耗时间和内存

4.9 栈的应用--四则运算表达式求值

4.9.1 后缀（逆波兰）表示法定义

四则运算表达式的一种新的显示方式，巧妙地解决了程序四则运算的难题，所有的符号都是在要运算数字的后面出现

4.9.2 后缀表达式计算结果

遇到数字就进栈，遇到符号，就将处于栈顶的两个数字出栈进行运算，运算结果进栈

4.9.3 中缀表达式转后缀表达式

标准四则运算表达式即中缀表达式

4.10 队列的定义

先进先出的线性表，FIFO
队尾：允许插入
队头：允许删除

4.11 队列的抽象数据类型

是一种特殊的线性表

4.12 循环队列

4.12.1 队列顺序存储的不足

入队列操作，时间复杂度为O(1)
出队列操作，时间复杂度为O(n)
假溢出：内存利用率不高
front指针：指向队头元素
rear指针：指向队尾元素的下一个位置

4.12.2 循环队列定义

头尾相接的顺序存储结构的队列

4.13 队列的链式存储结构及实现

简称链队列

4.13.1 队列的链式存储结构--入队操作

入队：链表尾部插入结点

4.13.2 队列的链式存储结构--出队操作

出队：头结点的后续结点出队，将头结点的后继改为它后面的结点

4.14 总结回顾

栈和队列都是特殊的线性表，只不过对插入和删除操作做了限制。
栈：

4.15 结尾语

第5章 串

由零个或多个字符组成的有限序列，又叫字符串

5.1 开场白

5.2 串的定义

早期计算机主要做一些计算工作，后来在计算机上作非数值处理的工作越来越多，就不得不引入对字符的处理。
空串用“”或希腊字母Φ表示
空格串、子串与主串

5.3 串的比较

通过组成串的字符之间的编码来进行的，而字符的编码指的是字符在对应字符集中的序号。
标准ASCII编码：7位二进制数表示一个字符，总共128个，后来拓展到8位二进制数，可以表示256个字符。
Unicode编码：常用的是由16位二进制数表示一个字符，约65万多个字符，足够表示世界上所有语言的所有字符，为了和ASCII兼容，前256个字符和ASCII码完全相同。
类比查字典

5.4 串的抽象数据类型

串的基本操作和线性表的基本操作有很大区别，线性表关注的是单个元素的操作，串更多的是查找子串位子、得到指定位置子串、替换子串等操作。

5.5 串的存储结构

5.5.1 串的顺序存储结构

容易越界

5.5.2 串的链式存储结构

为了避免浪费内存空间，可以在一个结点存放多个字符

5.6 朴素的模式匹配算法

子串的定位操作通常称做串的模式匹配。
对主串的每一个字符作为子串开头，与要匹配的字符串进行匹配，对子串做大循环，每个字符开头做T的长度的小循环，直到匹配成功或全部遍历完成为止。
太过低效。

5.7 KMP模式匹配算法

以三个研究过该算法的前辈的名字缩写命名。

5.7.1 KMP模式匹配算法原理

5.7.2 next数组值推导

5.7.3 KMP模式匹配算法实现

KMP算法仅当模式与子串之间存在许多“部分匹配”的情况下才体现出它的优势，否则两者差异并不明显。

KMP模式匹配算法改进

5.7.4 KMP模式匹配算法改进

5.7.5 nextval数组值推导

5.8 总结回顾

5.9 结尾语

第6章 树

空树
根
根的子树

6.1 开场白

6.2 树的定义

线性结构：一对一
树形结构：一对多
根节点是唯一的
子树个数没有限制，但它们一定是互不相交的

6.2.1 结点分类

结点的度：结点拥有的子树数
叶结点或终端结点：度为0
非终端结点或分支结点：度不为0
内部结点：除根节点之外的分支结点
树的度：树内各结点的度的最大值

6.2.2 结点间的关系

孩子
双亲
兄弟
祖先
子孙

6.2.3 树的其他相关概念

结点的层次
堂兄弟
树的深度或高度
森林：m棵互不相交的树的集合

6.3 树的抽象数据类型

6.4 树的存储结构

6.4.1 双亲表示法

每个结点中，附设一个指示器指示其双亲结点到链表中的位置

6.4.2 孩子表示法

每个结点有多个指针域，其中每个指针指向一棵子树的根结点，也叫做多重链表表示法。

6.4.3 孩子兄弟表示法

6.5 二叉树的定义

左子树和右子树

6.5.1 二叉树的特点

6.5.2 特殊二叉树

1.斜树：左斜树、右斜树
2.满二叉树：最完美、最平衡的二叉树
3.完全二叉树：满二叉树一定是一棵完全二叉树，但完全二叉树不一定是满二叉树

6.6 二叉树的性质

6.6.1 二叉树性质1

6.6.2 二叉树性质2

6.6.3 二叉树性质3

6.6.4 二叉树性质4

6.6.5 二叉树性质5

6.7 二叉树的存储结构

6.7.1 二叉树顺序存储结构

顺序存储结构一般只用于完全二叉树

6.7.2 二叉链表

data：数据域
lchild：左孩子指针域
rchild：右孩子指针域

6.8 遍历二叉树

6.8.1 二叉树遍历原理

访问
次序

6.8.2 二叉树遍历方法

1.前序遍历
2.中序遍历
3.后序遍历
4.层序遍历

6.8.3 前序遍历算法

6.8.4 中序遍历算法

6.8.5 后序遍历算法

6.8.6 推导遍历结果

6.9 二叉树的建立

扩展二叉树

6.10 线索二叉树

6.10.1 线索二叉树原理

指向前驱和后继的指针称为线索，加上线索的二叉链表称为线索链表，相应的二叉树就称为线索二叉树。
线索二叉树等于是把一棵二叉树转变成了一个双向链表。
对二叉树以某种次序遍历使其变为线索二叉树的过程称作是线索化。
ltag、rtag区分是指向孩子还是指向前驱或后继的。

6.10.2 线索二叉树结构实现

线索化的实质就是将二叉树链表中的空指针改为指向前驱或后继的线索。所以线索化的过程就是在遍历的过程中修改空指针的过程。
如果所用的二叉树需经常遍历或查找结点时需要某种遍历序列中的前驱和后继，那么采用线索二叉链表的存储结构是很不错的。

6.11 树、森林与二叉树的转换

6.11.1 树转换为二叉树

6.11.2 森林转换为二叉树

6.11.3 二叉树转换为树

6.11.4 二叉树转换为森林

判断一棵二叉树能够转换成一棵树还是森林的标准：只要看这棵二叉树的根节点有没有右孩子，有就是森林，没有就是一棵树。

6.11.5 树与森林的遍历

6.12 赫夫曼树及其应用

6.12.1 赫夫曼树

压缩文件：重新编码
赫夫曼编码
成绩评级算法的优化

6.12.2 赫夫曼树定义与原理

路径：从树中一个结点到另一个结点之间的分支
路径长度：路径上的分支数目
树的路径长度：从树根到每一结点的路径长度之和
赫夫曼树：带权路径长度WPL最小的二叉树称为赫夫曼树，也称为最优二叉树。
寻找最优二叉树的步骤。

6.12.3 赫夫曼编码

解决远距离通信（主要是电报）的数据传输的最优化问题

6.13 总结回顾

需要在理解的基础上去记忆。
二叉树的遍历，前序、中序、后序以及层序遍历都是需要熟练掌握的。

6.14 结尾语

第7章 图

7.1 开场白

7.2 图的定义

线性表：线性关系
树形结构：类比人类族谱，一对多
图：更复杂，结点之间的关系可以是任意的

元素：线性表中的单位
结点：树中的数据元素
顶点：图中的数据元素

线性关系：线性表中相邻元素之间的关系
层次关系：树结构中，相邻两层结点的关系
边：图中任意两个顶点之间都可能有关系，顶点之间的逻辑关系用边表示

7.2.1 各种图的定义

无向边：顶点之间的边没有方向
无序偶对
无向图
无向完全图

有向边：也称为弧
弧头、弧尾
有向图
有向完全图
简单图

稀疏图、稠密图

权：与图或弧相关的数
网：带权的图

子图

7.2.2 图的顶点与边间关系

互为邻接点（有向图）
邻接到、邻接自（无向图）

顶点的度：和顶点相关联的边的数目（有向图）
入度、出度、度=入度+出度（有向图）

顶点序列：一个顶点到另一个顶点的所有路径
路径长度：边或弧的数目

回路或环：首尾顶点相同的路径
简单路径、简单回路、简单环

7.2.3 连通图相关术语

连通图（无向图）
连通分量（无向图）

强连通图（有向图）
强连通分量（有向图）

有向树

7.2.4 图的定义与术语总结

7.3 图的抽象数据类型

7.4 图的存储结构

图的存储结构更复杂。不能用顺序存储结构来表示，也不推荐多重链表的方式，会造成很多存储单元的浪费，或者操作的不便。

7.4.1 邻接矩阵

顶点：一维数组存储
边或弧：二维数组存储
邻接矩阵：一维+二维

无向图的边数组是一个对称矩阵。

网的邻接矩阵，需要包含权值信息。

7.4.2 邻接表

邻接矩阵的缺点：边数较少（稀疏图）时，会极大浪费存储空间。
邻接表：数组和链表相结合的存储方式称为邻接表。

边表（无向图）
弧尾的出边表（有向图）

统计顶点的出度：邻接表很清晰
统计顶点的入度：逆邻接表

网的邻接表：边表结点中新增weight数据域

7.4.3 十字链表

正向思维、逆向思维、整合思维
同时统计出度和入度：邻接表+逆邻接表=十字链表

7.4.4 邻接多重表

为了简化无向图的边操作

7.4.5 边集数组

关注的是边的集合，查找度效率太低。

7.5 图的遍历

7.5.1 深度优先遍历

也称深度优先搜索，简称DFS.
走迷宫策略。

7.5.2 广度优先遍历

也称广度优先搜索，简称BFS.

深度与广度算法在时间复杂度上是一样的，不同之处在于对顶点访问的顺序不同。

7.6 最小生成树

构造连通网的最小代价生成树称为最小生成树。

7.6.1 普里姆算法

7.6.2 克鲁斯卡尔算法

7.7 最短路径

网图最短路径：权值之和最少的路径，源点、终点。
人脑是用来创造而不是做枯燥复杂的计算的。

7.7.1 迪杰斯特拉算法

解决了从某个源头到其余各顶点的最短路径问题。

7.7.2 弗洛伊德算法

所有顶点至所有顶点的最短路径问题可以选择弗洛伊德算法。

7.8 拓扑排序

7.8.1 拓扑排序介绍

AOV网：表示工程，用顶点表示活动，用弧表示活动之间的优先关系的有向图。
对一个有向图构造拓扑序列的过程。

7.8.2 拓扑排序算法

入度域

7.9 关键路径

AOE网：表示工程，用顶点表示事件，用有向边表示活动，用边上的权值表示活动的持续时间的带权有向图。
路径长度
关键路径、关键活动

7.9.1 关键路径算法原理

7.9.2 关键路径算法

存在多条关键路径的有向无环图，只提高一条关键路径上的关键活动的速度并不能导致整个工程缩短工期，而必须同时在几条关键路径上提高活动的速度。
就像仅仅有事业的成功，而没有健康的身体以及快乐的生活，压根谈不上幸福的人生。

7.10 总结回顾

7.11 结尾语

第8章 查找

8.1 开场白

搜索引擎：网络蜘蛛
关键字的云端之旅

8.2 查找概论

8.3 顺序表查找

顺序查找（线性查找）

8.3.1 顺序表查找算法

循环查找

8.3.2 顺序表查找优化

哨兵
参考：顺序表查找优化（哨兵元素的重要作用）

8.4 有序表查找

有序排序
时间复杂度:O(n)

8.4.1 折半查找

8.4.2 插值查找

8.4.3 斐波那契查找

8.5 线性索引查找

8.5.1 稠密索引

8.5.2 分块索引

8.5.3 倒排索引

8.6 二叉排序树

8.6.1 二叉排序树查找操作

8.6.2 二叉排序树插入操作

8.6.3 二叉排序树删除操作

8.6.4 二叉排序树总结

8.7 平衡二叉树(AVL树)

8.7.1 平衡二叉树实现原理

8.7.2 平衡二叉树实现算法

8.8 多路查找树（B树）

8.8.1 2-3树

8.8.2 2-3-4树

8.8.3 B树

8.8.4 B+树

8.9 散列表查找(哈希表)概述

8.9.1 散列表查找定义

8.9.2 散列表查找步骤

8.10 散列函数的构造方法

8.10.1 直接定址法

8.10.2 数字分析法

8.10.3 平方取中法

8.10.4 折叠法

8.10.5 除留余数法

8.10.6 随机数法

8.11 处理散列冲突的方法

8.11.1 开放定址法

8.11.2 再散列函数法

8.11.3 链地址法

8.11.4 公共溢出区法

8.12 散列表查找实现

8.12.1 散列表查找算法实现

8.12.2 散列表查找性能分析

8.13 总结回顾

8.14 结尾语

第9章 排序

9.1 开场白

9.2 排序的基本概念与分类

9.2.1 排序的稳定性

9.2.2 内排序与外排序

内排序算法的性能：

内排序常用方法：

简单算法：

改进算法：

9.2.3 排序用到的结构与函数

9.3 冒泡排序

9.3.1 最简单排序实现

9.3.2 冒泡排序算法

9.3.3 冒泡算法优化

9.3.4 冒泡排序复杂度分析

9.4 简单选择排序

9.4.1 简单选择排序算法

9.4.2 简单选择排序复杂度分析

9.5 直接插入排序

9.5.1 直接插入排序算法

9.5.2 直接插入排序复杂度分析

9.6 希尔排序

Ⅸ变6的几种方法

9.6.1 希尔排序原理

9.6.2 希尔排序算法

9.6.3 希尔排序复杂度分析

9.7 堆排序

9.7.1 堆排序算法

9.7.2 堆排序复杂度分析

9.8 归并排序

9.8.1 归并排序算法

9.8.2 归并排序复杂度分析

9.8.3 非递归实现归并排序

9.9 快速排序

9.9.1 快速排序算法

9.9.2 快速排序复杂度分析

9.9.3 快速排序优化

1.优化选取枢轴

9.10 总结回顾

9.11 结尾语

上一篇 下一篇

猜你喜欢

热点阅读