1、数据结构的定义
我们如何把现实中大量而复杂的问题,以特定的数据类型和特定的存储结构保存到主存储器(内存)中。
以及在此基础上为实现某个功能而执行的相应操作,这个相应的操作叫做算法。
- 特定的数据类型:个体如何存储。
- 特定的存储结构:个体与个体之间的关系如何来存储。
数据的存储包含两方面:个体的存储 + 个体关系的存储。
当这两方面解决后,数据的存储问题就解决了。
从某个角度而言,数据的存储最核心的就是个体关系的存储;个体的存储可以忽略不计。
- 狭义:数据结构是专门研究数据存储的问题。
- 广义:数据结构既包含数据的存储也包含数据的操作(算法)。
2、数据结构的地位
数据结构是软件中最核心的课程。
程序 = 数据的存储 + 数据的操作 + 可以被计算机执行的语言
3、数据的存储结构
- 线性结构:把所有的结点用一根直线串起来。
- 栈(堆栈)应用:函数调用、内存分配。
- 队列 应用:操作系统中所有和时间有关的操作。
注意:数据结构中没有堆的概念,堆是内存分配的一种方式,不属于存储数据的一种结构。
4、算法
- 某个功能:查找某个元素、删除某个元素、对所有元素进行排序等。
数据结构解决存储的问题,算法解决操作的问题。
算法:解题的方法和步骤。
- 狭义:与存储有关。存储方式不同,执行操作的算法也不同。
- 广义:与存储没关系。
泛型:利用某种技术达到的效果就是:不同的存储方式,执行的操作是一样的。(Java的泛型已经不伦不类了)
通过模板、运算符的重载、指针可以达到这种效果。
泛型只是一种假象。
泛型深入:同一种逻辑结构,无论该逻辑结构物理存储是什么样的,我们都可以对它执行相同的操作。
衡量算法的标准:
- 时间复杂度:程序大概要执行的次数(而非执行的时间,因为不同的机器执行速度不一样)。
- 空间复杂度:算法执行过程中大概所占用的最大内存。
- 难易程度:别人易理解,算法易实现。
- 健壮性