内容纲要
目录
一、数据结构绪论
二、线性表
三、栈和队列
四、串
五、数组矩阵与广义表
六、树与二叉树
七、图
八、查找
九、排序
数据结构总结
2、数据结构研究的主要内容： 计算机的操作对象的关系更加复杂，不再是单纯的数值计算，而更多地是非数值性处理。数据结 构描述现实世界实体的数学模型（非数值计算）及其上的操作在计算机中的表示和实现。重点分析数据之间的抽象的相互关系，而不涉及数据的具体内容。数据结构是一门研究非数值计算的程序设计中计算机的操作对象以及它们之间的关系和操作等的学科 。
3、数据结构的发展： 起源于程序设计的发展，程序设计经历三个阶段：无结构阶段；结构化程序设计阶段；面向对象阶段。“数据结构”作为一门独立的课程在 1968 年才开始设立。美国唐.欧.克努特教授开创了“数据结构” 的最初体系。
4、当今计算机应用(数据处理，科学计算，实时控制)的特点： 所处理的数据量大且具有一定的关系;对其操作不再是单纯的数值计算，而更多地是需要对其进行组织、管理和检索。
数据结构大纲：
排序算法分析：
| 时间复杂度 | |||||
|---|---|---|---|---|---|
| 最好情况 | 最坏情况 | 平均情况 | 空间复杂度 | 稳定性 | |
| 快速排序 | O(nlog2n) | O(n2) | O(nlog2n) | O(log2n) | 不稳定 |
| 直接插入排序 | O(n) | O(n2) | O(n2) | O(1) | 稳定 |
| 折半插入排序 | O(n) | O(n2) | O(n2) | O(1) | 稳定 |
| 希尔排序 | O(n2/3) | O(1) | 不稳定 | ||
| 冒泡排序 | O(n) | O(n2) | O(n2) | O(1) | 稳定 |
| 简单选择排序 | O(n2) | O(n2) | O(n2) | O(1) | 不稳定 |
| 堆排序 | O(nlog2n) | O(nlog2n) | O(nlog2n) | O(1) | 不稳定 |
| 归并排序 | O(nlog2n) | O(nlog2n) | O(nlog2n) | O(n) | 稳定 |
| 基数排序 | O(d(n+rd)) | O(d(n+rd)) | O(d(n+rd)) | O(rd) | 稳定 |
留言