《数据结构》必须掌握的知识点与算法
第一章 绪论
1、算法的五个重要特性（有穷性、确定性、可行性、输入、输出）
2、算法设计的要求（正确性、可读性、健壮性、效率与低存储量需求）
3、算法与程序的关系：
（1）一个程序不一定满足有穷性。例操作系统，只要整个系统不遭破
坏，它将永远不会停止，即使没有作业需要处理，它仍处于动态等待中。因此，
操作系统不是一个算法。
（2）程序中的指令必须是机器可执行的，而算法中的指令则无此限制。
算法代表了对问题的解，而程序则是算法在计算机上的特定的实现。
（3）一个算法若用程序设计语言来描述，则它就是一个程序。
4、算法的时间复杂度的表示与计算（这个比较复杂，具体看算法本身，一
般关心其循环的次数与 N 的关系、函数递归的计算）
第二章 线性表
1、线性表的特点：
（1）存在唯一的第一个元素；（这一点决定了图不是线性表）
（2）存在唯一的最后一个元素；
（3）除第一个元素外，其它均只有一个前驱（这一点决定了树不是线
性表）
（4）除最后一个元素外，其它均只有一个后继。
2、线性表有两种表示：顺序表示（数组）、链式表示（链表），栈、队列
都是线性表，他们都可以用数组、链表来实现。
3、顺序表示的线性表（数组）地址计算方法：
（ 1 ） 一 维 数 组 ， 设 DataType a[N] 的 首 地 址 为 A
0
， 每 一 个 数 据
（DataType 类型）占 m 个字节，则 a[k]的地址为：A
a[k]
＝A
0
+m*k（其直接意义
就是求在数据 a[k]的前面有多少个元素，每个元素占 m 个字节）
（2）多维数组，以三维数组为例，设 DataType a[M][N][P]的首地址为
A
000
，每一个数据（DataType 类型）占 m 个字节，则在元素 a[i][j][k]的前面共有
元素个数为：M*N*i+N*j+k，其其地址为：
A
a[i][j][k]
＝A
000
+m*(M*N*i+N*j+k)；
4、线性表的归并排序：
设两个线性表均已经按非递减顺序排好序，现要将两者合并为一个线性
表，并仍然接非递减顺序。可见算法 2.2
5、掌握线性表的顺序表示法定义代码，各元素的含义；
6、顺序线性表的初始化过程，可见算法 2.3
7、顺序线性表的元素的查找。
8、顺序线性表的元素的插入算法，注意其对于当原来的存储空间满了后，
追加存储空间（就是每次增加若干个空间，一般为 10 个）的处理过程，可见算
法 2.4
9、顺序线性表的删除元素过程，可见算法 2.5
10、顺序线性表的归并算法，可见算法 2.7
评论0