同济大学数据结构课程笔记

简介：
本笔记整理了同济大学数据结构课程的核心知识点与实践案例，涵盖算法设计、数据存储结构及常用的数据结构操作技巧，适合学生和编程爱好者参考学习。 ### 同济大学数据结构笔记知识点汇总 #### 第一章 绪论 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. **长度与深度的确定规则** 以上内容涵盖了同济大学数据结构课程的主要知识点，包括基本概念、线性表操作、栈和队列的应用场景以及数组及广义表的深入理解。这些知识为后续学习高级算法提供了坚实的基础。