源代码:C:\迅雷下载\2021072816023491335\59e95a4689eeb92f380f4ab2\202107\29976aaa-ef7a-11eb-aba5-00163e0a088c
PPT:C:\迅雷下载\2021072816023491335\59e95a4689eeb92f380f4ab2\202009\942a5ce8-fe34-11ea-a6a1-00163e0396a1
参考文献:C:\迅雷下载\2021072816023491335\59e95a4689eeb92f380f4ab2\202009\c53b3bcc-fe34-11ea-97a4-00163e0a088c
2.5 算法的特性
- 输入
- 输出
- 有穷性
- 确定性
- 可行性
2.6 算法设计的要求
- 正确性
- 可读性
- 健壮性
- 时间效率高和存储量低
2.9
推导大 O 阶方法
1)用常数 1 取代运行时间中的所有加法常数。
即,不论算法函数运行多少次,只要是通过加法得到的,就改为 1。
2)在修改后的运行次数函数中,只保留最高阶项
3)如果最高阶项存在且其系数不是 1,则去除与这个项相乘的系数。
得到的结果就是大 O 阶。
2.9.5 对数阶
2 x Count >= n 退出循环
由 2Count = n 得到 x = log2n,时间复杂度是 O(logn)
2.10 常见的时间复杂度
常数阶
12
O(1)
线性阶
2n + 3
O(n)
平方阶
3n2 + 2n + 1
O(n2)
对数阶
5log2n + 20
O(logn)
nlogn阶
2n + 3nlog2n + 19
O(nlogn)
立方阶
6n3 + 2n2 + 3n + 4
O(n3)
指数阶
2n
O(2n)
时间复杂度耗费的时间从小到大排:
O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn)
第3章,线性表
线性表:(List) 零个或多个元素的有限序列。
数组长度:存放线性表的存储空间的长度,存储分配后这个量一般是不变的。
线性表的长度:线性表中数据元素的个数,随着线性表插入和删除操作的进行,这个量是变化的。
任意时刻,线性表的长度应该小于等于数组的长度。
3.5 顺序存储结构的插入与删除
优点:
- 无须为表示表中元素之间的逻辑关系而增加额外的存储空间。
- 可以快速地存取表中任一位置的元素。
缺点: - 插入和删除操作需要移动大量元素。
- 当线性表长度变化较大时,难以确定存储空间的容量。
- 造成存储空间的“碎片”
3.6 线性表的链式存储结构
节点:
- 节点数据
- 下一节点地址
3.7 单链表的读取
要通过循环的移动下标,判断,才能读取到指定下标的数据。
3.8 单链表的插入与删除
3.9 单链表的整表创建
1)声明一指针 p 和计数器变量 l
2)初始化一空链表 L。
3)让 L 的头结点的指针指向 NULL,即建立一个带头结点的单链表。
4)循环:
(1)生成一新结点赋值给 p
(2)随机生成一数字赋值给 p 的数据域 p->data
(3)将 p 插入到头结点与前一新结点之间。
3.10 单链表的整表删除
3.12 静态链表
3.13 循环链表
3.14 双向链表
第4章,栈与队列
4.6 栈的链式存储结构及实现
4.8 栈的应用 —— 递归
4.9 栈的应用 —— 四则运算表达式求值
后缀表达式:叫后缀的原因,在于所有的符号都是在要运算数字的后面出现。
一种不需要括号的后缀表达法,称为逆波兰表示(Reverse Polish Notation, RPN)。
4.10 队列的定义
4.12 循环队列
第5章,串(字符串)
5.6 朴素的模式匹配算法
110页,
5.7 KMP 模式匹配算法
第6章,树
6.8.2 二叉树的遍历方法
[[二叉树的遍历方法]]
书中规则的描述认为不清晰。
6.9 二叉树的建立
6.11 树、森林与二叉树的转换
第7章,图
7.6 最小生成树
普里姆( Prim )算法
克鲁斯卡尔( Kruskal )算法文章来源:https://www.toymoban.com/news/detail-611548.html
7.7 最短路径
迪杰斯特拉( Dijkstra )算法
弗洛伊德( Floyd )算法文章来源地址https://www.toymoban.com/news/detail-611548.html
7.8 拓扑排序
7.9 关键路径
第8章,查找
8.3 顺序表查找
8.4 有序表查找
8.5 线性索引查找
8.6 二叉排序树
8.7 平衡二叉树(AVL 树)
8.8 多路查找树(B树)
8.9 散列表查找(哈希表)概述
8.10 散列函数的构造方法
- 直接定址法:取关键字的某个线性函数值为散列地址
- 数字分析法
- 平方取中法
- 折叠法
- 除留余数法
- 随机数法
8.11 处理散列冲突的方法
- 开放定址法
- 再散列函数法
- 链地址法
- 公共溢出区法
第9章,排序
9.3 冒泡排序
9.4 简单选择排序
9.5 直接插入排序
9.6 希尔排序
9.7 堆排序
9.8 归并排序
9.9 快速排序
到了这里,关于读《大话数据结构》溢彩加强版的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!