数据结构课程重点、知识点 时时补充

第一周

1操作对象以及操作对象间的关系----数据结构

随着发展，计算机更多的用来进行非数值计算的处理：

存储中的增删改查（线性关系）

人机对弈 井字棋 （非线性关系 树形）

2.png

文件系统结构 ：目录-》子目录 ...（非线性关系 树形）

地图导航 求最短路径、最快路径（网状结构）

3.png

逻辑结构---》线性：线性表、栈、队列、串；非线性：树、图
存储结构---》顺序存储、链式存储（存数据本身同时还存储了下一个元素地址）、索引存储（有一个索引表：通讯录--》详情）、散列存储（根据节点关键字，直接计算数据存储地址）

4.png

2抽象数据类型

5.png 6.png

抽象数据类型ADT定义举例：Circle定义

模板

8.png 7.png

抽象数据类型ADT定义举例：复数定义

9.png

小结

10.png

3抽象数据类型表示与实现

例如上面复数 例子的实现

11.png

4算法和算法分析

对特定问题的求解方法和步骤的一种描述，他是指令的有限序列，其中每个指令表示一个或多个操作。
算法的描述：自然语言；流程图：传统流程图、NS图；伪代码
特性：有穷性、确定性、可行性、0或多输入、1或多输出
设计要求：正确性、可读性、健壮性、高效性

算法的效率：时间效率、空间效率

12.png

执行时间由机器决定，所以假设每条语句所需时间均为单位时间

13.png 14.png 15.png

只考虑最坏时间复杂度

16.png 17.png