5
《数据结构》必须掌握的知识点与算法
第一章 绪论
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、线性表的归并排序:
5、掌握线性表的顺序表示法定义代码,各元素的含义;
7、顺序线性表的元素的查找。
8、顺序线性表的元素的插入算法,注意其对于
9
10
11、链表的定义代码,各元素的含义,并能用图形象地表示出来,以利分析;
12、链表中元素的查找
13、链表的元素插入,算法与图解,
14、链表的元素的删除,算法与图解,
15、链表
18、循环链表的定义,意义
19、循环链表的构造算法〔其与单链表的区别是在创建时确定的〕、图解