本笔记整理了同济大学数据结构课程的核心知识点与实践案例，涵盖算法设计、数据存储结构及常用的数据结构操作技巧，适合学生和编程爱好者参考学习。
### 同济大学数据结构笔记知识点汇总
#### 第一章 绪论
1. **数据结构定义**：数据结构主要用于解决非数值计算的问题。
2. **基本单位**：
- 数据元素：构成数据的基本单元；
- 数据项：组成数据的最小单元；
- 数据对象：具有相同性质的数据元素集合，是整体的一部分。
3. **分类方式**：
- 按照特性分为逻辑结构和物理结构；
- 根据存储方法区分为顺序存储结构与非顺序存储结构。
4. **顺序存储的应用范围**：不仅适用于线性数据类型还能够应用于树状等复杂模型中。
5. **算法定义及其特征**：
- 定义：对特定问题求解步骤的描述；
- 特征包括有穷性、确定性、可行性、输入和输出。
6. **算法与数据结构的关系**：设计依赖于逻辑结构，实现基于物理存储方式。
7. **评价标准**：正确性、可读性、健壮性和效率以及低空间需求度。
8. **原地工作定义**：额外使用的内存相对问题规模为固定量级（常数级别）。
9. **时间复杂度**：最坏情况下的运行时间上限。例如，O(n)优于O(n^2)。
#### 第二章 线性表
1. **线性表的形式**：顺序存储与链式结构两种形式。
2. **顺序存储的特性**：支持随机访问、插入和删除等操作。
3. **单链表类型及其基本操作**：
- 带头节点或不带头节点；
- 包括建立列表、输出数据、合并拆分元素以及逆置等功能。
4. **链表插入方法**：头部添加法与尾部追加方式。
5. **排序技术**：利用链式结构进行排序算法的实现。
6. **逆转操作**：改变单向链接顺序以反转原始次序。
7. **循环和双方向列表的基本知识**
#### 第三章 栈和队列
1. **栈定义及类型**：
- 链表形式的链栈与数组表示的顺序栈；
2. **实现机制**：链式结构通过头部插入元素，而顺序存储则使用数组。
3. **空满判断方法**
4. **基本操作**：入栈和出站等。
5. **队列类型及其特点**：
- 单向循环链表与双向链列表；
6. **循环队列状态检测机制**：通过尾指针加1等于头指针判定是否已满，空则两者相等。
7. **基本操作掌握**
#### 第四章 串
1. **存储结构类型**：
- 包括顺序、链接和堆式三种；
2. **堆结构的定义**
3. **密度概念及其影响因素**
#### 第五章 数组与广义表
1. **数组特性及压缩方法**：针对特定矩阵（如对称阵等）采用不同方式。
2. **稀疏矩阵存储技术**：
- 三元组法；
- 十字链式结构。
3. **广义表定义**
4. **长度与深度的确定规则**
以上内容涵盖了同济大学数据结构课程的主要知识点，包括基本概念、线性表操作、栈和队列的应用场景以及数组及广义表的深入理解。这些知识为后续学习高级算法提供了坚实的基础。
5星
