7数据结构与算法(白色背景).ppt

1、数据结构与算法,本章主要内容,7.1 算法 7.2 数据结构的基本概念 7.3 线性表 7.4 栈和队列 7.5 线性表的链式存储结构 7.6 树 7.7 查找技术 7.8 排序技术,学习这章之前需要掌握的基本术语,1.数据,是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。,2.数据元素,数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。,3.数据项,数据项是数据的不可分割的最小单位。,学习这章之前需要掌握的基本术语,4.数据对象,数据对象是性质相同的数据元素的集合，是数据的一个子集。 例如，整数数据对象是集合N=0,1，2，

2、 字母字符数据对象是集合C=A,B,Z,7.1 算法,7.1.1 算法的基本概念 算法的基本特征 算法的基本要素 算法设计基本方法 7.1.2 算法复杂度 算法的时间复杂度 算法的空间复杂度,算法的基本概念,算法是指解决方案的准确而完整的描述。 它是指令的有限序列，其中每一条指令表示一个或多个操作。, 算法的基本特征,可行性,确定性,有穷性,拥有足够的情报,考虑计算工具,明确定义，不允许多义,有限时间内完成,输入数据有效,（2）算法的基本要素,1、对数据的运算和操作,2、算法的控制结构,算术运算,逻辑运算,关系运算,数据传输,顺序,选择,循环,（3）算法设计的基本方法,回溯法,7.1.2 算法

3、复杂度,它是指执行算法所需要的计算工作量。,算法的时间复杂度,算法的工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数，即 算法的工作量=f(n) 其中，n是问题的规模。,例如，两个n阶矩阵相乘所需要的基本运算次数为n3，即计算工作量为n3，也就是时间复杂度为n3。,算法的空间复杂度，一般是指执行这个算法所需要的内存空间。,7.1.2 算法复杂度,算法程序所占的空间,输入的初始数据所占的存储空间,算法执行过程中所需要的额外空间,+,+,算法的空间复杂度,信息社会，在工作中经常要处理大量数据，那么当面对大量的数据元素时又该如何提高数据处理的效率呢？ 两方面 提高数

4、据处理的速度 节省计算机存储空间,数据结构这门课程研究的内容,数据的逻辑结构 数据关系之间的逻辑关系 数据的存储结构 数据的逻辑结构在计算机中的表示 操作算法 插入、删除、修改、查询、排序等,数据结构这门课程研究的内容,集合 线性结构 -表、栈、队列 非线性结构 -树、图,逻 辑 结 构,存 储 结 构,顺序存储结构 -数组 链式存储结构 -指针,7.2.1 数据结构的定义,1.数据的逻辑结构,概念,是指反映数据元素之间逻辑关系的数据结构,B= ( D, R ),一个数据结构可以表示为,2.数据的存储结构,数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构（也称数据的物理结构）。,概

5、念,常用存储结构,顺序,链接,索引,不同的存储结构，数据处理的效率不同!,7.2.2 数据结构的图形表示,集 合,线 性,树,图,数据结构一般分为：线性结构与非线性结构,7.2.3 线性结构,满足条件,特点,（1）有且只有一个根结点； （2）每一个结点最多有一个前件，最多有一个后件。,（1）在数据元素的非空有限集中存在唯一的一个被称做“第一个”的数据元素（即首结点）。 （2）存在唯一的一个被称做“最后一个”的数据元素（即尾结点）。 （3）除第一个之外，集合中的每个数据元素均只有一个前驱（在某元素之前的元素称之为前驱）。 （4）除最后一个之外，集合中每个数据元素均只有一个后继（在某元素之后的元素

6、称之为后继）。,7.3 线性表,7.3.1 线性表的定义 7.3.2 线性表的顺序存储结构 1.定义 2.顺序表的插入操作 3.顺序表的删除操作,7.3.1 线性表的定义,一个线性表是n个数据元素的有限序列。 线性表是一种线性结构。 数据元素在线性表中的位置只取决于其自身的序号，即数据元素之间的相对位置是线性的。 (1)有且只有一个根结点，它无前件； (2)有且只有一个终端结点，它无后件； (3)除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。线性表中结点的个数称为线性表的长度。当n=0时，称为空表。,结构特征,7.3.2 线性表的顺序存储结构,在计算机中用一组地址连续

7、的存储单元依次存储线性表的各个数据元素，称做线性表的顺序存储结构，简称顺序表。,定义,7.3.2 线性表的顺序存储结构,顺序表的插入操作,7.3.2 线性表的顺序存储结构,顺序表的删除操作,7.4.1 栈,栈（Stack）是一种只允许在一端进行插入和删除的线性表 ，它是一种操作受限的线性表。,栈的定义,栈顶和栈底,在表中只允许进行插入和删除的这一端称为栈顶（top），另一端称为栈底（bottom）。,入栈和出栈,栈的插入操作叫入栈（push）；栈的删除操作叫出栈（pop）。,栈在生活中的例子,举例1 家里吃饭的碗，通常在洗干净后一个一个地落在一起存放，在使用时，若一个一个地拿，一定最先拿走最上

8、面的那只碗，而最后拿出最下面的那只碗。 举例2 在建筑工地上，使用的砖块从底往上一层一层地码放，在使用时，将从最上面一层一层地拿取。,7.4.1 栈,利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。 栈底的位置通常设置成数组的0单元 栈顶的当前位置是动态的，随着插入与删除而变化 对栈顶当前位置的标记称为栈顶指针,栈的顺序存储结构,顺序栈,栈为后进先出（Last In First Out）的线性表，简称为LIFO表。 栈的修改是按后进先出的原则进行。每次删除（退栈）的总是当前栈中最新的元素，即最后插入（进栈）的元素，而最先插入的是被放在栈的底部，要到最后才能删除。,7.4.1 栈,顺序

9、栈插入删除操作示意图,空栈,插入元素A,插入BCDE,删除E,D,栈顶,栈底,7.4.2 队列,定 义,队列（Queue）是一种只允许在一端进行插入，而在另一端进行删除的线性表，它也是一种操作受限的线性表。,队尾,队头,队列在生活中的例子,举例1 到医院看病，首先需要到挂号处挂号，然后，按号码顺序救诊。 举例2 乘坐公共汽车，应该在车站排队，车来后，按顺序上车 举例3 在Windows这类多任务的操作系统环境中，每个应用程序响应一系列的消息，像用户点击鼠标；拖动窗口这些操作都会导致向应用程序发送消息。为此，系统将为每个应用程序创建一个队列，用来存放发送给该应用程序的所有消息，应用程序的处理过程

10、就是不断地从队列中读取消息，并依次给予响应。,7.4.2 队列,（1）允许删除的一端称为队头（Front）。 （2）允许插入的一端称为队尾（Rear）。 （3）当队列中没有元素时称为空队列。 （4）队列亦称作先进先出（First In First Out）的线性表，简称为FIFO表。 （5）队列的修改是依先进先出的原则进行的。 新来的成员总是加入队尾（即不允许加塞），每次离开的成员总是队列头上的（不允许中途离队），即当前最老的成员离队。,顺序队列,7.5 线性表的链式存储结构,链接方式存储的线性表简称为链表（Linked List）,链式存储方法, 用一组任意的存储单元来存放线性表的结点 （这

11、组存储单元既可以是连续的，也可以是不连续的） 链表中结点的逻辑次序和物理次序不一定相同。 为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息（称为指针（pointer）,不仅可用来表示线性表，而且可用来表示各种非线性的数据结构。,7.5.1 线性单链表,线性链表是线性表的链式存储结构，是一种物理存储单元上非连续、非顺序的存储结构。 数据元素的逻辑顺序是通过链表中的指针链接次序实现的。 将每一个存储结点分为两部分：一部分用于存储数据元素的值，称为数据域；另一部分用于存放下一个数据元素的存储结点的地址，即指向后继结点，称为指针域。,7.5.1 线性

12、单链表,（1）空线性链表,（2）非空线性链表,指针域为空,对于链表的各种操作必须从头指针开始,7.5.2 循环链表,循环链表是将单链表的表中最后一个结点指针指向链表的表头结点，整个链表形成一个环，这样从表中任一结点出发都可找到表中其他的结点。,（1）带头结点的循环单链表的空表形式,（2）带头结点的循环单链表的一般形式,7.5.3 双向链表,在双向链表中，每一个结点除了数据域外，还包含两个指针域，一个指针（prior）指向该结点的后继结点，另一个指针（next）指向它的前驱结点。 双向链表也可以有循环表。让表头结点的前驱指针指向链表的最后的一个结点，让最后一个结点的后继指针指向头结点。,（1）空

13、双向链表,（2）非空双向循环链表,7.6 树,7.6.1 树的基本概念 7.6.2 二叉树 7.6.3 遍历二叉树,7.6.1 树的基本概念,树形结构是一类重要的非线性数据结构。 族谱和各种社会组织结构都可以用树形结构表示。,7.6.1 树的基本概念,1定义 树是由n（n0）个结点组成的有限集合。 若n=0，称为空树； 若n0，则：（1）有一个特定的称为根（root）的结点。它只有直接后继，但没有直接前驱；（2）除根结点以外的其它结点可以划分为m（m0）个互不相交的有限集合T0，T1，Tm-1，每个集合Ti（i=0,1,m-1）又是一棵树，称为根的子树，每棵子树的根结点有且仅有一个直接前驱，但

14、可以有0个或多个直接后继。,树的示意图,树的根结点为A，该树还可以分为三个互不相交子集T0，T1，T2 T0=B，E，F，J，K，L T1=C，G T2=D，H，I，M,如T0可以分为： T00 , T01 T00= E，J，K，L T01= F,树的常用术语,1.结点指树中的一个数据元素，包含数据项及若干指向其子树的分支，一般用一个字母表示。 2.结点的度 一个结点包含子树的数目，称为该结点的度。 3.树的度 树内各结点的度的最大值。 4.树叶（叶子） 度为0的结点，称为叶子结点或树叶，也叫终端结点。 5.分支结点 度不为0的结点，又称非终端结点。 6.孩子结点的子树的根称为该结点的孩子,树

15、的常用术语,7.双亲 孩子结点的上层结点即为这些结点的双亲。 8.兄弟 同一双亲的孩子之间互为兄弟。 9.堂兄弟 其双亲在同一层的结点互为堂兄弟。 10.结点的祖先 从根到该结点所经分支上的所有结点。 11.结点的子孙 以某结点为根的子树中的任一结点都称为该结点的子孙。,树的常用术语,12.结点的层次 从根开始定义，根为第一层，根的孩子为第二层；若某结点在m层，则该结点的子树的根在m+1层。 13.深度 树中结点的最大层次数。 14.森林 是m(m0)棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。 15.有序树和无序树 如果各子树依次从左到右排列，不可对换，则称该子树为有序树

16、，且把各子树分别称为第一子树，第二子树；反之，称为无序树。,7.6.2 二叉树,1.定义 二叉树是一种度不大于2的有序树。 每个结点至多只有两棵子树（即二叉树中不存在度大于2的结点），并且二叉树的子树有左右之分，其次序不能任意颠倒。 递归定义 二叉树是n(n0)个结点的有限集，它或者为空树(n=0)，或者由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树所构成。,完全二叉树,除叶子结点外，所有的结点的度都为2的二叉树称为完全二叉树,非完全二叉树,完全二叉树,满二叉树,满二叉树是完全二叉树的特例。 每层的结点数都满足2n-1。,满二叉树,二叉树的存储,将一棵二叉树按完全二叉树顺序存放到一

17、个一维数组中，若该二叉树为非完全二叉树，则必须将相应位置空出来，使存放的结果符合完全二叉树形状。,顺序存储结构,浪费了大量的存储空间,二叉树的存储,树形结构是非线性结构，采用顺序存储有一定的困难。 (浪费了大量的存储空间) 通常用具有两个指针域的链表作为二叉树的存储结构，其中，每个结点由数据域Data、左指针域LChild和右指针域RChild组成。 两个指针域分别指向该结点的左、右孩子。 若某结点没有左孩子或右孩子，则对应的指针域为空。,7.6.3 遍历二叉树,遍历（Traversing）是指循着某条搜索路线查找某数据结构中的结点，而且每个结点只被访问一次。 遍历操作让二叉树中各结点按指定的

18、顺序线性排列，使得非线性的二叉树线性化。,遍历,7.6.3 遍历二叉树,表示访问根结点,D,L,R,表示遍历左子树,表示遍历右子树,DLR、LDR、LRD、DRL、RDL、RLD 若规定先左后右，则可归并为以下三种形式。 DLR：前序（根）遍历。 LDR：中序（根）遍历。 LRD：后序（根）遍历。, 前序遍历,1）访问根结点； 2）按前序遍历规则遍历左子树； 3）按前序遍历规则遍历右子树。,规则:,A B D E C F G, 中序遍历,1）按中序遍历规则遍历左子树； 2）访问根结点； 3）按中序遍历规则遍历右子树。,规则:,D B E A F G C, 后序遍历,1）按后序遍历规则遍历左子树

19、； 2）按后序遍历规则遍历右子树； 3）访问根结点。,规则:,D E B G F C A,7.7 查找技术,所谓查找是指在一个给定的数据结构中查找某个指定的元素。 不同的数据结构采用不同的查找方法。 本节课，我们讨论最常用的两种查找方式: 1)顺序查找 2)二分法查找,7.7.1 顺序查找,从线性表的第一个元素开始，依次将线性表中的元素与被查元素进行比较。 若相等则表示找到（即查找成功); 若线性表中所有的元素都与被查元素进行了比较但都不相等，则表示线性表中没有要找的元素（即查找失败）。,基本原理,7.7.1 顺序查找,两种情况下也只能采用顺序查找： 1)如果线性表为无序表（即表中元素的排列是

20、无序的)，则不管是顺序存储结构还是链式存储结构，都只能用顺序查找。 2)即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。,7.7.2 二分法查找,二分法查找只适用于顺序存储的有序表。,基本原理,设有序线性表的长度为n，被查元素为x,查找步骤如下: 1)将x与线性表的中间项进行比较； 若中间项的值等于x，则说明查到，查找结束； 2)若x小于中间项的值，则在线性表的前半部分（即中间项以前的部分）以相同的方法进行查找； 3)若x大于中间项的值，则在线性表的后半部分（即中间项以后的部分）以相同的方法进行查找。 4)这个过程一直进行到查找成功或子表长度为0（说明线性表中没有这个元素）为止。,7

21、.8 排序技术,1.交换类排序,2.插入类排序,3.选择类排序,冒泡排序法,快速排序法,简单插入排序法,希尔排序法,简单选择排序法,堆排序法,7.8.1 交换类排序法,所谓交换类排序法是指借助数据元素之间的互相交换进行排序的一种方法。 本门课介绍冒泡排序法和快速排序法,1.冒泡排序法,基本原理,5个数7、5、6、3、2的排序过程如下：,第1轮比较4次,第2轮比较3次,第3轮比较2次,第4轮比较1次,2.快速排序法,从线性表中选取一个元素设为T，将线性表后面小于T的元素移到前面，而前面大于T的元素移到后面，结果就将线性表分成了两部分（称为两个子表），T插入到其分界线的位置处，这个过程称为线性表的

22、分割。 如果对分割后的各子表再按上述原则进行分割，并且，这种分割过程可以一直做下去，直到所有子表为空为止，则此时的线性表就变成了有序表。 在表的第一，中间和最后一个元素取中项，设为P（K）并把它移动到表的第一个位置上。,2.快速排序法,2.快速排序法,用快速排序法为以下7个数排序： 49，38，65，97，76，13，27,（1）令 P（K）= 49,2.快速排序法,49，38，65，97，76，13，27,27，38，65，97，76，13，49 i=1，j=7,1,2,27，38，49，97，76，13，65 i=3，j=7,3,4,i=1,j=7,原,27，38，13，97，76，49，

23、65 i=3，j=6,27，38，13，49，76，97，65 i=4，j=6,2.快速排序法,经过几次交换，此时i=j，交换结束。 此时，比P(k)小的数（27，38，13）都在它的前面，而比P(k)大的数（76，97，65）都在它的后面。 与此同时，第一次分割结束。 下面应该进行的是子表1（27，38，13）和子表2（76，97，65）的分割，方法同上。,27，38，13，49，76，97，65 i=5，j=5 无变化,7.8.2 插入类排序,假设线性表中前j-1个元素已经有序，现在要将第j个元素插入到前面的有序子表中的方法如下： 将第j个元素放到一个变量T中 从有序子表的最后一个元素（即

24、线性表中第j-1个元素）开始，往前逐个与T进行比较，将大于T的元素均依次向后移动一个位置，直到发现一个元素不大于T为止 将T（即原线性表中的第j个元素）插入到刚移出的空位置上 此时有序子表的长度就变为j了。,1.简单插入排序,简单插入排序举例,3 5 8 10 15 19 24 38 49 57,22,3 5 8 10 15 19 22 24 38 49 57,1922,7.8.2 插入类排序,先取一个小于n的整数h1作为第一个增量，把文件的全部记录分成h1个组。 所有距离为h1的倍数的记录放在同一个组中。先在各组内进行直接插人排序 取第二个增量h2h1重复上述的分组和排序，直至所取的增量ht=1(dtdt-ld2d1)，即所有记录放在同一组中进行直接插入排序为止。 增量序列一般取ht=n/2k(k=1，2，1og2n)，