天津滨海汽车工程职业技术学院 伊森
2025-04-16 18:34:26 0 举报AI智能生成
天津滨海汽车工程职业技术学院
作者其他创作
大纲/内容
绪论
数据结构的重要性
计算机相关专业的必修课
程序设计的基础：“算法 + 数据结构 = 程序”
应用场景：图论、排序、检索、计算机网络、数据库等
数据结构的基本知识
定义：数据元素的集合，元素间存在特定关系
数据结构表示：\text{data_structure} = (D, S)
元素的逻辑关系和物理关系
数据结构的分类：集合、线性结构、树形结构、图（网）状结构
抽象数据类型（ADT）
定义：数据类型及其操作的集合
ADT的描述：数据元素、数据逻辑结构、基本操作
面向对象中的类和对象
线性表和数组
线性表
定义：n个数据元素组成的有限序列
基本操作：初始化、取元素、求长度、定位、插入、删除
合并线性表：抽象描述和实现
线性表的顺序存储
存储方式：连续存储单元
特点：随机存取
插入和删除操作的时间复杂度：O(n)
线性表的链式存储
单链表：结点由数据域和指针域组成
基本操作：查找、插入、删除
时间复杂度：O(n)
循环链表和双向链表的特点和操作
数组
定义：下标和值的集合
存储方式：顺序存储结构
特殊矩阵的压缩存储：对称矩阵、三角矩阵、三对角矩阵
稀疏矩阵的转置：三元组表示法、快速转置算法
栈和队列
栈（Stack）
定义：后进先出（LIFO）的线性表
基本操作：初始化、判空、进栈、出栈、取栈顶元素
应用：表达式处理、括号匹配
顺序存储结构和链式存储结构
队列（Queue）
定义：先进先出（FIFO）的线性表
基本操作：初始化、入队、出队、判空、取队头元素
应用：消息加密解密、表达式求值
顺序存储结构和链式存储结构
循环队列的实现和操作
树和二叉数
树的基本概念
定义：n个结点的有限集，结点间有特定关系
结点的度、叶子、孩子、双亲、兄弟、层数、树的高度
树的表示方法：集合包含关系、广义表法、凹入法
二叉树
定义：每个结点最多有两个子树的树
特殊二叉树：满二叉树、完全二叉树
二叉树的性质：层数、结点数、叶子结点
存储结构：顺序存储、链式存储
二叉树的遍历
先根遍历、中根遍历、后根遍历
递归算法和非递归算法
线索二叉树的概念和实现
树和森林
树的存储结构：双亲数组、孩子链表、孩子兄弟链表
树与二叉树的转换
树的遍历：先根遍历、后根遍历
森林的遍历：先序遍历、中序遍历
哈夫曼树及其应用
哈夫曼树的定义和构造
哈夫曼编码的实现
排序
排序的基本概念
内排序和外排序
排序的时间开销和附加存储
稳定性：相同关键字记录的相对位置
插入排序
直接插入排序
折半插入排序
希尔排序
交换排序
冒泡排序
快速排序
选择排序
简单选择排序
堆排序
归并排序
两路归并排序
归并排序算法
基数排序
分配和收集
最高位优先（MSD）和最低位优先（LSD）
内部排序总结
各排序方法的时间复杂度、稳定性、辅助空间
李怡森202368040518
收藏
0 条评论
下一页
为你推荐
查看更多
