侯庭璞 天汽职院
2025-04-16 18:43:26 0 举报AI智能生成
计算机复习材料
作者其他创作
大纲/内容
├─ 第2章 线性表
│ ├─ 2.1 线性表定义
│ │ ├─ 顺序存储（随机存取）
│ │ └─ 链式存储（单链表/双向链表）
│ ├─ 2.2 基本操作
│ │ ├─ 插入/删除（时间复杂度O(n)）
│ │ └─ 合并算法
│ └─ 2.3 特殊结构
│ ├─ 循环链表
│ └─ 双向循环链表
2.1 线性表定义
顺序存储（随机存取）
顺序表的基本概念
元素连续存储
随机访问特性
空间利用率与扩容机制
预分配与动态扩容
链式存储（单链表/双向链表）
单链表结构
节点定义与指针
头节点与尾节点
双向链表结构
前向指针与后向指针
节点访问与遍历
链式存储的优势与局限
动态调整长度
内存碎片化问题
2.2 基本操作
插入/删除（时间复杂度O(n)）
顺序表中的插入操作
定位插入位置
元素移动与插入
顺序表中的删除操作
定位删除位置
元素移动与删除
链式表中的插入操作
定位插入节点
指针调整与插入
链式表中的删除操作
定位删除节点
指针调整与删除
合并算法
两个有序顺序表的合并
创建新表并复制元素
合并后的有序性保持
两个有序链表的合并
创建哑节点辅助合并
指针调整与链表连接
合并算法的时间复杂度分析
顺序表合并的时间复杂度
链表合并的时间复杂度
2.3 特殊结构
循环链表
循环链表的基本概念
尾节点指向头节点
循环遍历特性
循环链表的插入操作
定位插入位置与指针调整
循环链表的删除操作
定位删除位置与指针调整
循环链表的应用场景
环形缓冲区
约瑟夫环问题
双向循环链表
双向循环链表的结构
前向指针与后向指针的循环
双向遍历特性
双向循环链表的插入操作
双向指针的调整与插入
双向循环链表的删除操作
双向指针的调整与删除
双向循环链表的优势与应用
更灵活的遍历与操作
图的邻接表表示
├─ 第3章 栈和队列
│ ├─ 3.1 栈
│ │ ├─ LIFO特性
│ │ ├─ 顺序栈（数组实现）
│ │ └─ 链栈（链表实现）
│ ├─ 3.2 队列
│ │ ├─ FIFO特性
│ │ ├─ 循环队列（解决假溢出）
│ │ └─ 链队列
│ └─ 3.3 应用
│ ├─ 表达式括号匹配
│ └─ 加密算法（凯撒密码）
3.1 栈
LIFO特性
后进先出原理说明
示例分析
应用场景介绍
函数调用栈
实现方式对比
软件实现与硬件实现
顺序栈（数组实现）
顺序栈结构定义
数组与栈顶指针
基本操作实现
入栈与出栈
空间复杂度分析
固定大小与动态扩展
栈满与栈空判断
条件检测与异常处理
链栈（链表实现）
链栈结构定义
节点结构与链表头指针
基本操作实现
链式入栈与出栈
内存管理
节点分配与释放
遍历与搜索
链栈元素遍历
3.2 队列
FIFO特性
先进先出原理说明
示例分析
应用场景介绍
任务调度与打印队列
实现方式对比
数组实现与链表实现
循环队列（解决假溢出）
循环队列结构定义
数组与前后指针
基本操作实现
入队与出队
队列满与队列空判断
条件检测与循环逻辑
空间利用率分析
循环队列的优势
链队列
链队列结构定义
节点结构与队列头尾指针
基本操作实现
链式入队与出队
内存管理
节点分配与释放
遍历与搜索
链队列元素遍历
3.3 应用
表达式括号匹配
括号匹配原理
括号类型与配对规则
算法实现
栈的应用与匹配过程
错误检测与处理
不匹配情况处理
性能分析
时间复杂度与空间复杂度
加密算法（凯撒密码）
凯撒密码原理
字母移位与加密规则
算法实现
栈与队列在加密中的应用
解密过程
逆向移位与解密算法
安全性分析
简单加密的局限性
├─ 第4章 树和二叉树
│ ├─ 4.1 树基础
│ │ ├─ 术语（度/层次/深度）
│ │ └─ 存储结构（双亲表示法/孩子兄弟法）
│ ├─ 4.2 二叉树
│ │ ├─ 性质（n0=n2+1）
│ │ ├─ 遍历（先序/中序/后序）
│ │ └─ 线索二叉树
│ └─ 4.3 哈夫曼树
│ ├─ 带权路径最小（WPL）
│ └─ 哈夫曼编码（前缀编码）
4.1 树基础
术语
度：节点的子节点数量
层次：节点在树中的深度层级
深度：树的最大层次
路径：连接两个节点的边和节点序列
存储结构
双亲表示法：通过数组存储节点及其父节点信息
孩子兄弟法：使用两个指针分别指向第一个孩子和最右兄弟
链式存储：通过链表结构存储节点及其子节点关系
图表示法：使用图结构表示树，节点为图的顶点，边为父子关系
4.2 二叉树
性质
n0=n2+1：二叉树中叶子节点数等于度为2的节点数加1
满二叉树：所有节点要么有2个子节点，要么没有子节点
完全二叉树：按层序编号，除最后一层外节点均满，且最后一层节点连续
二叉搜索树：左子树节点值小于根节点，右子树节点值大于根节点
遍历
先序遍历：根节点-左子树-右子树
中序遍历：左子树-根节点-右子树
后序遍历：左子树-右子树-根节点
层次遍历：按层次从上到下，从左到右遍历节点
线索二叉树
线索：指向前驱或后继的空指针
中序线索二叉树：中序遍历形成的线索二叉树
先序线索二叉树：先序遍历形成的线索二叉树
后序线索二叉树：后序遍历形成的线索二叉树
线索化过程：将空指针改为线索的过程
4.3 哈夫曼树
带权路径最小（WPL）
WPL定义：所有叶子节点权值与其路径长度的乘积之和
构造过程：根据权值构建哈夫曼树
最优性证明：哈夫曼树是WPL最小的二叉树
应用实例：文件压缩、字符编码优化
哈夫曼编码
前缀编码：任意字符的编码不是其他字符编码的前缀
构造方法：根据字符权值构建哈夫曼树，生成编码
解码过程：根据哈夫曼树和编码还原字符
应用场景：数据压缩、通信协议
├─ 第6章 排序
│ ├─ 6.1 排序分类
│ │ ├─ 稳定性
│ │ └─ 时间复杂度对比
│ ├─ 6.2 插入排序
│ │ ├─ 直接插入（O(n²)）
│ │ └─ 希尔排序（O(n^1.3)）
│ ├─ 6.3 交换排序
│ │ ├─ 冒泡排序（O(n²)）
│ │ └─ 快速排序（O(nlogn)）
│ ├─ 6.4 选择排序
│ │ ├─ 简单选择（O(n²)）
│ │ └─ 堆排序（O(nlogn)）
│ └─ 6.5 其他排序
│ ├─ 归并排序（分治思想）
│ └─ 基数排序（LSD/MSD）
排序分类
稳定性
稳定排序与非稳定排序的定义
稳定排序的特点与应用场景
非稳定排序的影响与解决方案
稳定性在排序算法中的重要性
稳定性测试方法与工具
时间复杂度对比
常见排序算法时间复杂度概览
O(n)复杂度算法特点
O(nlogn)复杂度算法优势
不同规模数据下的时间复杂度表现
小规模数据排序效率对比
大规模数据排序性能评估
插入排序
直接插入（O(n²)）
直接插入排序的基本思想
从后向前扫描插入位置
元素移动与插入操作
直接插入排序的实现步骤
初始化与边界条件处理
循环遍历与插入逻辑
直接插入排序的优化策略
二分查找优化插入位置
元素交换减少移动次数
希尔排序（O(n^1.3)）
希尔排序的基本原理
增量序列的选择与设计
分组插入排序与整体优化
希尔排序的实现细节
增量递减与分组策略
循环遍历与插入操作
希尔排序的性能分析
时间复杂度与空间复杂度
希尔排序的适用场景与限制
交换排序
冒泡排序（O(n²)）
冒泡排序的基本流程
相邻元素比较与交换
冒泡过程的终止条件
冒泡排序的实现方式
原地排序与额外空间使用
优化冒泡排序的策略
冒泡排序的应用场景与限制
简单排序任务中的适用性
复杂排序需求下的局限性
快速排序（O(nlogn)）
快速排序的核心思想
选取基准元素与分区操作
递归排序子数组
快速排序的实现步骤
基准元素的选择方法
分区逻辑与递归调用
快速排序的性能优化
三数取中优化基准选择
尾递归消除与迭代实现
快速排序的适用场景分析
大规模数据排序的优势
特定数据分布下的效率
选择排序
简单选择（O(n²)）
简单选择排序的基本原理
未排序部分最小（大）值查找
元素交换与排序完成
简单选择排序的实现细节
初始化与边界条件处理
循环遍历与选择操作
简单选择排序的优化方向
减少不必要的元素比较
元素交换的替代方案
堆排序（O(nlogn)）
堆排序的基本概念
堆的定义与性质
堆的构建与维护
堆排序的实现步骤
构建最大（小）堆
堆顶元素与末尾元素交换并调整堆
堆排序的性能分析
时间复杂度与空间复杂度
堆排序的稳定性与适用场景
其他排序
归并排序（分治思想）
归并排序的基本原理
分治策略与递归实现
合并两个有序数组
归并排序的实现细节
递归基准条件与终止
合并操作的优化技巧
归并排序的性能评估
时间复杂度与稳定性分析
归并排序的空间复杂度与改进
归并排序的应用实例
外部排序中的归并算法
归并排序在数据库中的应用
基数排序（LSD/MSD）
基数排序的基本概念
LSD（最低有效位）排序流程
MSD（最高有效位）排序原理
基数排序的实现步骤
基数确定与桶分配
桶内排序与收集元素
基数排序的性能特点
时间复杂度与稳定性分析
基数排序的空间复杂度与适用场景
基数排序的应用实例
字符串排序中的基数算法
基数排序在图像处理中的应用
第1章 绪论
1.1 数据结构意义
程序=算法+数据结构（N.Wirth）
数据结构在程序设计中的核心地位
算法与数据结构的关系
数据结构对程序性能的影响
数据结构的发展与应用
逻辑结构
集合结构的特点与应用
线性结构（数组、链表）
树形结构（二叉树、平衡树）
图形结构（有向图、无向图）
物理结构
顺序存储结构的原理与特点
链式存储结构的原理与类型
索引存储结构与散列存储结构
物理结构与算法性能的关系
1.2 算法评价
时间复杂度（O符号）
时间复杂度的定义与计算方法
常见时间复杂度类型（常数、线性、对数、多项式）
时间复杂度与算法效率的关系
时间复杂度的优化策略
空间复杂度
空间复杂度的定义与计算方法
空间复杂度与时间复杂度的权衡
空间复杂度优化策略
算法在有限内存下的实现
1.3 抽象数据类型（ADT）
数据+操作
抽象数据类型的定义与特点
数据类型的抽象层次与封装
操作的定义与实现
抽象数据类型在程序设计中的应用
类图表示（UML）
UML类图的基本元素与符号
抽象数据类型在UML类图中的表示
UML类图在数据结构设计中的应用
UML类图与代码实现的对应关系
0 条评论
下一页
