数据结构与算法.ppt

1、李赛红 2011-03,全国计算机等级考试二级公共基础知识（一）,河海大学文天学院教育培训中心,1.数据结构与算法,1.2 数据结构的基本概念 ,1.3 线性表的顺序存储,1.4 栈和队列 ,1.1 算法基本概念及算法评价 ,第一章 数据结构与算法,1.6 树与二叉树 ,1.7 查找与排序 ,1.5 线性表的链式存储,第一章 数据结构与算法,1.1 算法基本概念及算法评价,1.1.1 算法 考点1 算法的定义 算法是用来解决某个特定类型问题的有限运算序列。简单的说：算法就是解决问题的方法. eg.程序是用计算机语言表达的算法; 流程图是图形化的算法,第一章 数据结构与算法,算法特征： （1）有

2、穷性：一个算法（对任何合法的输入）在执行有穷步后能够结束，并且在有限的时间内完成。 （2）确定性：算法中的每一步都有确切的含义。 （3）可行性：算法中的操作能够用已经实现的基本运算执行有限次来实现。 （4）输入：一个算法有零个或者多个输入，零个输入就是算法本身缺定了初始条件。 （5）输出：一个算法有一个或者多个输出，以反映出数据加工的结果。 （拥有足够的情报）,第一章 数据结构与算法,例1. 问题处理方案的正确而完整的描述称为_。 2005年4月 填空第5题 例2. 以下叙述中正确的是(A)用C语言实现的算法必须要有输入和输出操作 (B)用C语言实现的算法可以没有输出但必须要有输入 (C)用C

3、程序实现的算法可以没有输入但必须要有输出 (D)用C程序实现的算法可以既没有输入也没有输出 2005年9月 选择题第13题 例3. 算法具有五个特性,以下选项中不属于算法特性的是 (A)有穷性(B)简洁性(C)可行性(D)确定性 2005年4月 选择题第11题,算法,C,B,第一章 数据结构与算法,第一章 数据结构与算法,算法设计的基本方法 (1)列举法- 根据提出的问题列举所有可能的情况，并用问题中给定的条件检验哪些是需要的而哪些是不需要的； (2)归纳法- 通过列举足够多的特殊情况发现其中一些规律，经过分析最终找出一般的关系； (3)递推法- 从已知的初始条件出发，逐次地推出所要求的各中间

4、结果和最后结果； (4)递归法 - 首先将问题逐层分解最后归结为一些最简单的问题，解决这些最简单问题后再沿着原来分解的逆过程逐步进行综合。 (5)减半递推技术- 工程上常用的分治法，即将问题的规模减半来解，最后重复“减半”的过程； (6)回溯法- 在处理复杂数据结构时，通过对问题的分析找出一 个解决问题的线索，然后沿着次线索逐步试探，若失败就逐步回退并换别的路线再进行试探；,第一章 数据结构与算法,考点2 算法的复杂度 1.算法设计的要求：（一个好的算法要达到的目标） (1)正确性 (2)健壮性 (3)可读性 (4)效率与低存储量的要求 2.算法效率的度量 1)算法的时间复杂度 算法的执行时间

5、=每条语句执行时间之和； 每条语句执行时间=语句执行（频度）次数 * 语句执行一次所需时间； 独立于软硬件系统来分析算法的时间耗费 可以设每条语句执行时间均为一个单位时间 算法的执行时间=所有语句频度之和,第一章 数据结构与算法,算 法 复 杂 度,第一章 数据结构与算法,例1. 算法复杂度主要包括时间复杂度和 【1】 复杂度。 2005年9月 填空第2题 例2. 对长度为N的线性表(一维数组)进行顺序查找,在最坏的情况下所需要的比较次数为 2005年4月 选择第4题 (A)log2n(B)n/2(C)n(D)n+1 。,空间复杂度,C,第二节 数据结构基本概念,1.2 数据结构的基本概念,1

6、.2.1 数据结构 考点3 数据结构的定义 ： 数据结构(data structure)是指相互之间存在一种或多种特定关系的数据元素的集合，即数据的组织形式。 数据+关系 数据结构学科，主要研究和讨论以下三个方面： (l)数据集合中个数据元素之间所固有的逻辑关系，即数据的逻辑结构； (2)在对数据元素进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构； (3)对各种数据结构进行的运算。,第二节 数据结构基本概念,基本概念： （1）数据(data)：是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 （2）数据元素(data element)

7、：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 （3）数据对象(data object)：是性质相同的数据元素的集合。（数据元素是数据对象的一个实例） 例如：所有书的书目信息为数据对象，每一条书目信息为数据元素。,第二节 数据结构基本概念,（4）数据的逻辑结构 ： 对数据元素之间逻辑关系的描述。一个数据结构应该包含两方面的信息：数据元素的集合和定义在这个集合上的关系来表示.,（5）数据的存储结构 (物理结构) 数据的逻辑结构在计算机中存储空间中的存放形式称为数据的存储结构（物理结构）。,1）顺序存储方式（向量存储）,2）链式存储方式,3）索引存储方式,第二节 数据结构基本概

8、念,考点4 数据结构的图形表示 例如：一年四季的图形表示： 例如：反映家庭成员辈分关系的图形表示,第二节 数据结构基本概念,1.2.3 线性结构与非线性结构 考点5 线性结构与非线性结构 如果在一个数据结构中一个数据元素都没有，则称该数据结构为空的数据结构。 根据数据结构中各数据元素之间逻辑关系，一般将数据结构分为两大类型：线性结构与非线性结构。 非空数据结构满足： (l)有且只有一个没有前件的结点； (2)每一个结点最多有一个前件（直接前驱），也最多有一个后件（直接后继）。 则称该数据结构为线性结构。,1.3 线性表的顺序存储结构及链式存储 1.3.1 线性表的基本概念 考点6 1.线性表(

9、逻辑)的定义 线性表是n(n0)个元素构成的有限序列(a1，a2，an)。n=0时称为空表 2.线性表的特性： (1) 当1in时，ai的直接前驱为ai-1, ai的直接后继为ai+1 (2) 除了第一个元素与最后一个元素,序列中任何一个元素有且仅有一个直接前驱元素,有且仅有一个直接后继元素。,第三节 线性表,1.3.2 考点7 线性表的顺序存储结构 用一组地址连续的存储单元依次存储线性表中的数据元素，数据元素之间的逻辑关系通过元素的存储位置直接反映。,第三节 线性表,线性表的顺序存储结构特点： (1)线性表中所有元素所占的存储空间是连续的; (2)线性表中各数据元素在存储空间中是按逻辑顺序依

10、次存放的。 在程序设计语言中用一维数组来表示线性表的顺序存储空间。,第三节 线性表,1.可以随机存取,2.空间利用率高,3.结构简单,考点8 线性表的插入运算 在长度为n的线性表L的第i个位置上插入一个新的数据元素X,第三节 线性表,1.将第i到n个元素依次后移一个位置,2.将新元素x放到线性表的第i个位置,3.将线性表的表长由n修改为n+1,插入运算时间复杂度分析:,第三节 线性表,(1) 在计算机中，算法是指_。 A. 查询方法B. 加工方法C. 解题方案的准确而完整的描述D. 排序方法 (2) 算法一般都可以用哪几种控制结构组合而成_。 A. 循环、分支、递归B. 顺序、循环、嵌套C.

11、循环、递归、选择D. 顺序、选择、循环,复习题,C,D,(3) 一个算法应该具有“确定性”等5个特性，下面对另外4个特性的描述中错误的是A) 有零个或多个输入 B) 有零个或多个输出 C) 有穷性 D) 可行性 (4) 算法分析的目的是_。 A. 找出数据结构的合理性B. 找出算法中输入和输出之间的关系C. 分析算法的易懂性和可靠性D. 分析算法的效率以求改进,D,B,(5) 算法的时间复杂度是指_。 A. 执行算法程序所需要的时间B. 算法程序的长度C. 算法执行过程中所需要的基本运算次数D. 算法程序中的指令条数 (6) 算法的空间复杂度是指_。 A. 算法程序的长度B. 算法程序中的指令

12、条数C. 算法程序所占的存储空间D. 算法执行过程中所需要的存储空间,C,D,(7)下列对于线性表的描述中正确的是 A)存储空间不一定是连续,且各元素的存储顺序是任意的 B)存储空间不一定是连续,且前件元素一定存储在后件元素的前面 C)存储空间必须连续,且各前件元素一定存储在后件元素的前面 D)存储空间必须连续,且各元素的存储顺序是任意的,A,（8）数据结构中，与所使用的计算机无关的是数据的 A）存储结构 B）物理结构 C）逻辑结构 D）物理和存储结构,C,（1）数据结构分为逻辑结构与存储结构，线性链表属于 【1】 。,1.存储结构 解析： 数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构

13、；数据的存储结构是指数据的逻辑结构在计算机存储空间中的存放形式。在数据的存储结构中，不仅要存放各数据元素的信息，还需要存放各数据元素之间的前后件关系的信息。,Pi ( i = 1 , 2 , , n , n+1 ) (其中pi=1/(n+1)） T= Pi(n-i+1) = (n-i+1)/(n+1) = n/2,对于长度为n的顺序存储的线性表，当随机插入和删除一个元素时，需要平均移动元素的个数为多少？,考点9 线性表的删除运算 线性表的删除运算是指将表的第i(1in)个结点删除,第三节 线性表,1.将第i+1到n个元素依次前移一个位置,2.将线性表的表长由n修改为n-1,删除时间复杂度分析:

14、,第三节 线性表,线性表的顺序存储结构的缺点（补充）,1. 缺点：,2. 解决方案,(1) 需要一片地址连续的存储空间;,(2)插入和删除元素时不方便，大量的时间用在元素的搬家;,(1)对线性表的插入和删除运算进行限定,(2) 采用其它的存储结构(链式存储),(3)在预分配存储空间时，可能造成空间的浪费;,(4)表的容量难以扩充。,第四节 栈和队列,1.4 栈和队列,1.4.1 考点10 栈及其基本运算 1. 栈的定义 ： 限定在一端进行插入与删除的线性表。 允许进行插入和删除操作的一端叫栈顶，不允许插入（入栈）和删除（出栈）的一端叫栈底。没有元素的栈叫空栈。,若给定栈S=(a1,a2, ,a

15、n),则a1是栈底元素，an是栈顶元素，表中元素按a1,a2, ,an顺序进栈，按an, ,a2,a1顺序出栈。通常把栈称为先进后出的线性表。因此栈中数据元素的逻辑关系是先进后出(FILO)或后进先出。,第四节 栈和队列,2. 栈的顺序存储及其运算 ： 在程序设计语言中，用一维数组作为栈的顺序存储空间。,第四节 栈和队列,(l)入栈运算： 入栈运算是指在栈顶位置插入一个新元素。首先将栈顶指针加一(即top加1)，然后将元素插入到栈顶指针指向的位置。当栈顶指针已经指向存储空间的最后一个位置时，说明栈空间已满，不可能再进行入栈操作。这种情况称为栈“上溢”错误。 (2)退栈运算： 退栈是指取出栈顶元

16、素并赋给一个指定的变量。首先将栈顶元素(栈顶指针指向的元素)赋给一个指定的变量，然后将栈顶指针减一(即top减1)。当栈顶指针为0时，说明栈空，不可进行退栈操作。这种情况称为栈的“下溢”错误。 时间复杂度均为O(1)，压栈和退栈时不需移动元素,(3)读栈顶元素 读栈顶元素是指将栈顶元素赋给一个指定的变量。当栈顶指针为0时（空栈），读不到栈顶元素。 注意：这个运算不能删除栈顶元素。 栈的考题举例： 例1.下列关于栈的描述中错误的是05年4月 选择题2 (A)栈是先进后出的线性表 (B)栈只能顺序存储 (C)栈具有记忆作用 (D)对栈的插入和删除操作中，不需要改变栈底指针 例2.下列关于栈的描述正

17、确的是 05年9月 选择题3 (A)在栈中只能插入元素而不能删除元素 (B)在栈中只能删除元素而不能插入元素 (C)栈是特殊的线性表，只能在一端插入或删除元素 (D)栈是特殊的线性表，只能在一端插入元素，而在另一端删除元素,B,C,第四节 栈和队列,1.4.2 考点11 队列及其基本运算 1. 队列的定义 ： 所有的插入在表的一端进行，所有的删除在表的另一端进行的线性表。允许插入的一端称队尾，允许删除的一端称为队头。队列是一种先进先出(FIFO)的线性表。,2. 队列的顺序存储 可用一维数组q0.m-1存储队列中的元素，队列所允许的最大容量是m,如图：,第四节 栈和队列,数组q:表示队列 头指

18、针front:总是指向队头的前一个位置 尾指针rear:总是指向队列的最后一个元素 队空：front=rear (下溢) 队满：rear=m-1 (上溢),下面我们举一个例子实际做一下：m=5（入队，出队）,0,1,2,3,4,初始状态,rear=fornt=,0,1,2,3,4,加入A元素,rear,front,A,0,1,2,3,4,加入B元素,rear,front,A,B,0,1,2,3,D,4,加入E元素,rear,front,B,C,E,A,0,1,2,3,D,4,加入D元素,rear,front,A,B,C,0,1,2,3,4,删除ABC元素,rear,front,A,B,C,0,

19、1,2,3,4,加入C元素,rear,front,A,B,C,此时，再想加入一个元素也加不进去了，我们说队列已经满了，rear=m-1。这里存在一个问题，实际上在前页的图中，队列并不是真正的溢出，但rear=m-1，又说明队列满，新元素插不进去，这种情况称作假溢出，真正的队满是元素占满队列的所有空间,即rear-front=m。 解决方法： 采用循环队列。我们把q0和qm-1首尾相连，就形成了一个循环队列。 初始状态： 头指针：在顺时针方向上落后于队列中第一个元素一个位置。 尾指针：指向最后加入的元素的位置。,3. 循环队列及其运算 可用一维数组q0.m-1存储队列中的元素，队列所允许的最大容

20、量是m,如图：,第四节 栈和队列,头指针：在顺时针方向上落后于队列中第一 个元素一个位置。 尾指针：指向最后加入的元素的位置。,North China Electric Power University,q0,qm-1,rear,front,0,1,2,3,4,初态r=f,队空,0,1,2,3,4,rear,front,加入A,A,0,1,2,3,4,rear,front,A,B,A,B,C,0,1,2,3,4,rear,front,加入B,加入C,A,B,C,0,1,2,3,4,rear,front,删除ABC,D,0,1,2,3,4,rear,front,加入D,front,rear,0,

21、1,2,3,4,D,E,加入E,0,1,2,3,4,rear,front,D,E,F,加入F,0,1,2,3,4,rear,front,D,E,F,G,H,加入G、H,r=f 队满,从以上分析可以看出，循环队列的队空与队满条件相同，都是front=rear,这样我们区分不出队列到底是空还是满，对此解决方法: 设一个标志位(s)区分队列是空还是满。(队空置0，队满置1)。 由此可以得出队空与队满的条件如下： 判队空的条件：s=0 ; 判队满的条件：s=1 且 front=rear ;,第四节 栈和队列,(1)循环队列的入队 循环队列的入队是指在队尾加入一新元素。 基本操作：rear=rear+1

22、,且当rear=m-1时置rear=1; qrear=x; 当队列非空（s=1）且rear=front 时，队列满不能入队，上溢。 (2)循环队列的出队 循环队列的出队是指在队头指向的元素退出。 基本操作：front=front+1,且当front=m-1时置front=0; y=qfront; 当队列为空（s=0）不能出队，称为下溢。,第四节 栈和队列,例1. 数据结构分为_和存储结构，循环队列属于 【5】 结构。2005年9月 填空题 5 例2. 下列关于队列的叙述中正确的是_。A. 在队列中只能插入数据B. 在队列中只能删除数据C. 队列是先进先出的线性表D. 队列是先进后出的线性表 例

23、3. 栈和队列的共同点是_。A. 都是先进后出B. 都是先进先出C. 只允许在端点处插入和删除元素D. 没有共同点,逻辑结构,C,C,1.5 线性链表,假定上图为当前内存的使用情况，阴影部分为已用内存，现有一线性表L=(A,B,C,D,E,F,G,H),假若采用顺序存储的话，则在当前内存中不能分配一块长度为7的连续的存储空间。但实际上，系统的可用内存远大于该线性表所要求的内存空间，应采用其它的存储结构链式存储。,North China Electric Power University,G,F,B,C,E,D,H,A,可以采用上面的存储结构，每一个数据元素占用两个存 储单元，其中一个用来存放数

24、据元素的值，另外一个存 放下一个数据元素存储单元的地址，这种结构称为链式 存储结构。在这种结构中，数据元素存放是不连续的。,Head,第五节 线性链表,1.5 线性链表,1.5.1 考点12 线性链表的基本概念 1. 线性链表的定义 ： 线性表的链式存储结构称为线性链表。 用一组地址任意的存储单元存放线性表中的数据元素。（如下页图） 结点(表示数据元素)=元素(数据元素的映象) + 指针(指示后继元素存储位置),第五节 线性链表,头指针（head）：指向链表中第一个结点的指针。,第五节 线性链表,对于线性链表，可以从头指针开始，沿各结点的指针扫描到链表中的所有结点，只能顺着指针向链尾方向进行扫

25、描，所以会带来不便，当从某一结点出发，只能找到他的后继，为了找到他的前驱，必须从头指针开始重新寻找。 为了解决以上问题，采用双向链表的存储结构： 链表的每一个结点中除了数据域以外设置两个指针域，其中之一指向结点的直接前驱结点，另外一个指向结点的直接后继结点。,第五节 线性链表,2. 链栈 ： 栈也是线性表，也可以用单链表实现其存储结构。 设置一个指针变量( 这里不妨仍用 top表示)指出当前栈顶元素所在链结点的位置。当栈为空时，有top=null。 在一个初始为空的链接堆栈中依次插入数据元素 A, B, C, D 以后, 堆栈的状态为,第五节 线性链表,2. 链队 ： 队列也是线性表，也可以用

26、单链表实现其存储结构。 指针：front指向实际队头元素所在的链结点 rear指向实际队尾元素所在的链结点。,链队,在链队中插入p,在链队中删除a1,第五节 线性链表,考点13 线性链表的基本运算 （主要是插入、删除、查找） 1. 线性链表中查找指定元素 ： 2. 线性链表的插入 插入运算是将值为X的新结点插入到表的第i个结点的位置上 线性链表在插入过程中不发生数据元素移动的现象，只要改变有关结点的指针即可，从而提高了插入的效率。,p,第五节 线性链表,3.线性链表的删除 删除运算是指在链式存储结构下的线性链表中删除包含指定元素的结点。 从线性链表中删除一个元素后，不需要移动表中的数据元素，只

27、要改变被删除元素所在结点的前一个结点的指针域即可。,第五节 线性链表,考点14 循环链表及其运算 头结点：单链表的第一个结点之前附设的一个结点，它 的数据域不存放信息、或存放如线性的长度等附加信息。 循环链表 是指链表中最后那个链结点的指针域存放指向链表最前面那个结点的指针，整个链表形成一个环。,线性链表,第五节 线性链表,循环链表的特点： 只要给出表中任何一个结点的位置，则由此出发就可以访问表中其他所有结点。 对循环链表，若在它的第一个结点之前设立一个特殊的称为表头的结点，它的数据域可以按需要设定。使这样的链表中任何时候都至少有一个结点存在，这样就可以把对空表和非空表的处理统一起来。,例如：下列对于线性表的描述中正确的是 2005年4月 选择题5 A)存储空间不一定是连续,