内容纲要

目录

一、数据结构绪论

二、线性表

三、栈和队列

四、

五、数组矩阵与广义表

六、树与二叉树

七、

八、查找

九、排序


数据结构总结

1、具备学科基础:

离散数学程序设计语言

2、数据结构研究的主要内容:

计算机的操作对象的关系更加复杂,不再是单纯的数值计算,而更多地是非数值性处理。数据结 构描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中的表示和实现。
重点分析数据之间的抽象的相互关系,而不涉及数据的具体内容。
数据结构是一门研究非数值计算的程序设计中计算机的操作对象以及它们之间的关系和操作等的学科 。

3、数据结构的发展

起源于程序设计的发展,程序设计经历三个阶段:无结构阶段;结构化程序设计阶段;面向对象阶段。
“数据结构”作为一门独立的课程在 1968 年才开始设立。美国唐.欧.克努特教授开创了“数据结构” 的最初体系。

1、当今计算机应用(数据处理,科学计算,实时控制)的特点:

所处理的数据量大且具有一定的关系;
对其操作不再是单纯的数值计算,而更多地是需要对其进行组织、管理和检索。

数据结构大纲:

数据结构

排序算法分析:

时间复杂度
最好情况最坏情况平均情况空间复杂度稳定性
直接插入排序O(n)O(n2)O(n2)O(1)稳定
折半插入排序O(n)O(n2)O(n2)O(1)稳定
希尔排序O(n3/2)O(1)不稳定
冒泡排序O(n)O(n2)O(n2)O(1)稳定
快速排序O(nlog2n)O(n2)O(nlog2n)O(log2n)不稳定
简单选择排序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)稳定

最后修改日期:2020年4月11日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。