数据结构复习课

《数据结构复习课》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、《数据结构》复习课第一章基本概念与算法基础一、学习要求：理解关于数据结构的名词术语；理解算法描述方式；掌握算法时间复杂度和辅助空间的概念；掌握时间复杂度的计算。二、数据结构概念：1、数据：数据是指能够输入到计算机中，并被计算机识别和处理的符号的集合。2、数据结构：是存在一种或多种特定关系的数据元素间的逻辑结构和存储结构关系以及在其上的运算的集合。3、数据结构的三个方面：数据的逻辑结构，数据的存贮结构和对数据所施加的运算。这三个方面的关系为：（1）数据的逻辑结构独立于计算机，是数据本身所固有的。（2）存贮结构是逻辑结构在计算机存贮器中的映像，必须依赖于计算

2、机。（3）运算是指所施加的一组操作总称。运算的定义直接依赖于逻辑结构，但运算的实现必依赖于存贮结构。4、从逻辑结构划分数据结构数据结构从逻辑结构划分为：（1）线性结构（线性表、栈、队列、字串，数组……）元素之间为一对一的线性关系，第一个元素无直接前驱，最后一个元素无直接后继，其余元素都有一个直接前驱和直接后继。（2）非线性结构（树、堆、图（网络），……）元素之间为一对多或多对多的非线性关系，每个元素有多个直接前驱或多个直接后继。5．从存贮结构划分数据结构数据结构从存贮结构划分为：(1)顺序存贮（向量存贮）所有元素存放在一片连续的存贮单元中，逻辑上相邻的元素存放到

3、计算机内存仍然相邻。(2)链式存贮所有元素存放在可以不连续的存贮单元中，但元素之间的关系可以通过地址确定，逻辑上相邻的元素存放到计算机内存后不一定是相邻的。(3)索引存贮使用该方存放元素的同时，还建立附加的索引表，索引表中的每一项称为索引项，索引项的一般形式是：（关键字，地址），其中的关键字是能唯一标识一个结点的那些数据项。(4)散列存贮通过构造散列函数，用函数的值来确定元素存放的地址。6、抽象数据类型：用户在数据类型基础上自己定义和实现的数据类型。在更高一级的抽象程度上实现了信息的隐藏和封装。三、算法：1、算法的概念（algorithm）通俗地讲，算法就是一种

4、解题的方法。更严格地说，算法是由若干条指令组成的有穷序列，它必须满足下述条件（也称为算法的五大特性）：（1）输入：具有0个或多个输入的外界量（算法开始前的初始量）（2）输出：至少产生一个输出，它们是算法执行完后的结果。（3有穷性：算法的执行步骤必须是有限的。（4)确定性：每条指令的含义都必须明确，无二义性。（5)有效性：每条指令必须是可执行的。2．算法和程序的关系算法的含义与程序十分相似，但二者是有区别的。一个程序不一定满足有穷性（死循环），另外，程序中的指令必须是机器可执行的，而算法中的指令则无此限制。一个算法若用计算机语言来书写，则它就可以是一个程序。3、算

5、法描述（1）用流程图描述算法一个算法可以用流程图的方式来描述，输入输出、判断、处理分别用不同的框图表示，用箭头表示流程的流向。这是一种描述算法的较好方法，目前在一些高级语言程序设计中仍然采用。（2）用自然语言描述算法用我们日常生活中的自然语言（可以是中文形式，也可以是英形式）也可以描述算法。（3）用其它方式描述算法我们还可以用数学语言或约定的符号语言来描述算法。（4）用C++描述算法在本教材中，我们将采用C＋＋或类C++来描述算法。函数类型函数名（形参及类型说明）{函数语句部分return(表达式值)；}4、算法分析（1）时间复杂度一个算法花费的时间与算法中

6、语句的执行次数成正比例，一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)，n称为问题的规模，当n不断变化时，时间频度T(n)也会不断变化。设T(n)的一个辅助函数为g(n),定义为当n大于等于某一足够大的正整数n0时，存在两个正的常数A和B（其中A≤B），使得A≤T(n)/g(n)≤B均成立，则称g(n)是T(n)的同数量级函数。把T(n)表示成数量级的形式为：T(n)=Ｏ(g(n)),其中大写字母Ｏ为英文Order（即数量级）一词的第一个字母。在各种不同算法中，若算法中语句执行次数为一个常数，则时间复杂度为O(1),另外，在时间频度不相同时，时间复

7、杂度有可能相同，如T(n)=n2+3n+4与T(n)=4n2+2n+1它们的频度不同，但时间复杂度相同，都为O(n2)。按数量级递增排列，常见的时间复杂度有：常数阶O(1),对数阶O(log2n),线性阶O(n),线性对数阶O(nlog2n),平方阶O(n2)，立方阶O(n3),...，k次方阶O(nk),指数阶O(2n)。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。算法的时间复杂度应是数据元素最坏情况下取值的时间复杂度或数据元素等概率取值情况下的平均（或称期望）时间复杂度。（2）空间复杂度一个算法在执行时所占有的内存开销，称为空间频度

8、，但我们一般是讨论算法占