（本科）第6章电子教案ppt课件.pptx

《（本科）第6章电子教案ppt课件.pptx》由会员分享，可在线阅读，更多相关《（本科）第6章电子教案ppt课件.pptx（53页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、课程主讲人：（本科）第6章电子教案ppt课件我们毕业啦其实是答辩的标题地方大学计算机基础计算机基础教学系第6章 数据结构数据结构是计算机存储和组织数据的方式。通常情况下，选择合适的数据结构可以带来更高的运行或存储效率。本章内容本章内容6.1 数据结构概述6.2 线性结构6.3 树形结构6.4 查找技术6.5 排序技术p 数据结构是相互之间存在某种特定关系的数据元素的集合。6.1 数据结构概述 数据数据的逻辑结构的逻辑结构 数据数据的存储结构的存储结构 数据数据的运算的运算：线性线性结构结构 非线性非线性结构结构顺序顺序存储存储 链式链式存储存储 线性表线性表栈栈队列队列树形结构树形结构图形结构

2、图形结构数据结构的三个方面数据结构的三个方面 散散列存储列存储 索引存储索引存储遍历、查找、插入、删除、排序遍历、查找、插入、删除、排序等。等。6.2 线性结构p 定义：线性结构是多个数据元素的有序集合，线性结构只有一个根结点，且每个结点最多有一个直接前驱和一个直接后继。p 常用的线性结构有： 线性表，栈，队列等一、 线性表p定义：线性表是由n（n0）个数据元素组成的一个有限序列，表中除了第一个数据元素外，有且只有一个前驱，除了最后一个数据元素外有且只有一个后继。p线性表的分类： 顺序表（顺序存储） 链表 （链式存储）比如：(a1,a2,a3,a4,a5)1. 1.顺序表顺序表p定义：顺序表是

3、用一组地址连续的存储单元依次存储线性表的数据元素，让逻辑上相邻的数据元素在物理位置上也相邻。p顺序表的运算：插入、删除、修改、查找、排序等a1 a2 a3 a4 a51. 1.顺序表顺序表 顺序表的插入运算10 15 20 30 40a【例1】在下列顺序表中插入50，使数据元素仍然有序。807060501. 1.顺序表顺序表 顺序表的删除运算10 15 20 30 40a【例2】在下列顺序表中删除数据元素50807050 60p 小结：顺序表在进行插入和删除运算时可能要移动大量的数据，顺序表仅适用于小线性表和元素不常变动的大线性表。2. 2.链表链表p 定义：链表指的是用一组任意的存储单元（结

4、点）来存储线性表中的数据元素，这些结点可以连续，也可以不连续。p 常用的链表：线性链表（单链表）,循环链表，双向链表。 线性链表的结点由一个数据域和一个指针域组成。 双向链表的结点由一个数据域和两个指针域组成。 data next线性线性链表结点链表结点priornextdata双向链表结点双向链表结点链表链表p 线性链表a1 8HEADa2 1a3 7a4 0p 循环链表a1 8HEADa2 1a3 7a4 4HEAD0 a1 84 a2 18 a3 71 a4 0p 双向链表线性链表线性链表4718a1 8HEADa2 1a3 7a4 0 线性链表的插入运算【例3】在结点a2的后面插入一个

5、结点aa515线性链表线性链表4718a1 8HEADa2 1a3 7a4 0 线性链表的删除运算【例4】删除线性链表中的结点aa 155p 小结：链表的插入和删除操作简单，适用于元素变动频繁的大线性表。二、栈p 定义：栈可以看成是一种只能在一端进行插入与删除操作的线性表。栈是按照“先进后出”或“后进先出”的原则组织数据的，因此，栈也被称为“先进后出”表或“后进先出”表。栈顶栈顶栈底栈底toptopbottombottoman. . . .a2a1栈栈p 栈的分类：顺序栈和链栈二、栈p 栈的常用操作：进栈、出栈。bottombottomtoptopA AB BC CD DA AB B A A、

6、B B、C C、D D进进栈栈C CD Dtoptoptoptoptoptoptoptopbottombottomtoptoptoptop D D、C C出出栈栈toptopp 栈的应用栈的应用 在计算机中，栈常用来进行表达式求值和实现递归过程等。二、二、栈栈p定义：队列可以看成是一种只能在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作的线性表。队列也称“先进先出”表或“后进后出”表。p队列的分类：顺序队列、循环队列和链队列。ABCDfrontfrontrearrear入队入队出队出队三、队列1. 1.顺序队列顺序队列ABCDfrontfrontrearrearrea

7、rrearrearrear rearrear A、B、C、D入队rearrearp 顺序队列是在内存中按顺序存储的队列。1. 1.顺序队列顺序队列ABCDfrontfrontrearrear A、B、C、D出队p 顺序队列是在内存中按顺序存储的队列。frontfront frontfront frontfrontfrontfrontp 小结：顺序队列存在假溢出现象。2. 2.循环队列循环队列p循环队列是把队列设想成一个环形。BCGFEDfront 在执行入队操作时，rear=(rear+1)%maxsize 在执行出队操作时，front=(front+1)%maxsize Hrearrearf

8、rontH进队，A出队A3. 3.链队列链队列fronta1 a2 a3 0rear 队头指针front始终指向第一个元素结点 队尾指针rear始终指向最后一个元素结点a4 0rearfront队列的应用队列的应用 在计算机中，队列常用来解决主机与外部设备之间速度不匹配的问题，以及解决由多用户引起的资源竞争问题等。6.3 树形结构p 树树的定义：的定义： 树树是是由由n（n0）个有限结点）个有限结点组成组成的的一一个具有层次个具有层次关系的集合关系的集合。集合集合为空的树称为空树。为空的树称为空树。p 树的相关术语树的相关术语 结点结点树树中的元素中的元素 父结点父结点结点的直接前驱结点结点的

9、直接前驱结点 子子结点结点结点的直接后继结点结点的直接后继结点 根结点根结点没有父结点的结点没有父结点的结点 叶子结点叶子结点没有没有子结点子结点的结点的结点 结点的度结点的度结点的子结点数结点的子结点数ABCDEHFGIJ6.3 树形结构p 树树的相关术语的相关术语 结点的层次从根结点到该结点的层数（根结点是第1层） 树的度所有结点的度的最大值 树的层次所有结点的最大层数 子树以子结点为根构成的树 ABCDEHFGIJ计算机的文件系统是一种典型的树形结构。p 树的应用树的应用6.3 树形结构p 二叉二叉树树的定义：的定义：二叉树二叉树的每个的每个结点最多结点最多有两棵子树，并且二叉有两棵子树

10、，并且二叉树的子树有左右之分树的子树有左右之分，即顺序，即顺序不能颠倒不能颠倒。ABCDEFHGI 第第k k层上最多有层上最多有2 2k-1k-1个个结点。结点。 深度为深度为m m的二叉树最多有的二叉树最多有2 2m m-1-1个个结结点。点。 若度若度2 2的结点数的结点数有有n1n1个个，叶子结点，叶子结点数数为为n1+1n1+1。 具有具有n n个结点的二叉树，其深度至个结点的二叉树，其深度至少少为为 loglog2 2n n + +1 1。p 二叉二叉树树的性质：的性质：6.3 树形结构p满二叉满二叉树树的定义：的定义：满二叉树是指除最后一满二叉树是指除最后一层层的叶子结的叶子结点

11、点外，其他结点都有外，其他结点都有两个子结点的二叉树两个子结点的二叉树。ABCDEHF6.3 树形结构p完全二叉完全二叉树树的定义的定义：完全二叉树是指除最后一层外，完全二叉树是指除最后一层外，每一层上的结点数均达到最大值，但在最后一层上只每一层上的结点数均达到最大值，但在最后一层上只缺少缺少右边若干右边若干结点的二叉树结点的二叉树。完全二叉树完全二叉树第第k k层上有层上有2 2k-1k-1个个结点结点深度为深度为m m的完全二叉树有的完全二叉树有2 2m m-1-1个个结点结点若度若度2 2的结点数有的结点数有n1n1个，叶子结点个，叶子结点数为数为n1+1n1+1具有具有n n个结点的完

12、全二叉树的个结点的完全二叉树的深度深度 一定是一定是p完全二叉完全二叉树树的性质：的性质：ABCDEHIFGJ6.3 树形结构 如果如果对一棵有对一棵有n个结点的完全个结点的完全二叉树的二叉树的结结点按层序编号，则对任点按层序编号，则对任一一编号编号为为i结点结点（1in），有：），有：（1）若k=1，则该结点为根结点，它没有父结点；若k1，则该结点的父结点编号为 k/2 ；（2）若2kn，则编号为k的结点的左子结点编号为2k；否则该结点无左子结点；（3）若2k+1n，则编号为k的结点的右子结点编号为2k+1；否则该结点无右子结点。p完全二叉完全二叉树树的性质：的性质：ABCDEHIFGJ12

13、345678910二叉树的存储结构二叉树的存储结构p顺序存储结构ABCDEHIFGJ12345678910ABCDEFGHIJ二叉树的存储结构二叉树的存储结构p链式存储结构 每个结点每个结点由由1个数据域和个数据域和2个指针域组成。个指针域组成。lchild data rchildAB0 C0 D 0 E 0 0 H 0F0 G 00 I 0HEADABCDEFHGI二叉树的遍历二叉树的遍历p二叉树的遍历指不重复地访问二叉树的所有结点。DHIFGBCA 先序遍历A BD CFGH I访问根结点访问根结点先序遍历左子树先序遍历左子树先序遍历右子树先序遍历右子树二叉树的遍历二叉树的遍历DHIFGB

14、CA 中序遍历 后序遍历中序遍历左子树中序遍历左子树访问根结点访问根结点中序遍历右子树中序遍历右子树DB A FCHGI后序遍历左子树后序遍历左子树后序遍历右子树后序遍历右子树访问根结点访问根结点DB FHGCAI构造二叉树构造二叉树已知中序遍历：已知中序遍历：B D C E A F H G已知后序遍历：已知后序遍历：D E C B H G F A B D C E F H G A D C E BHFGCD EAABCBCFF H GGG6.4 6.4 查找查找技术技术p定义：查找是指在一个给定的数据结构中查找某个指定的元素，是数据处理领域中一个重要的内容，查找的效率将直接影响到数据处理的效率。

15、p查找技术分类：顺序查找：无序顺序表和链表二分查找：有序顺序表6.5 6.5 排序技术排序技术p定义：排序是指将一个无序序列整理成按值递增或递减排列的有序序列。p排序类别：交换类排序：冒泡排序、快速排序法插入类排序：简单插入排序法、希尔排序法选择类排序：简单选择排序法、堆排序法冒泡排序法冒泡排序法p基本思想：以升序排序为例，从表头开始扫描线性表，在扫描的过程中依次比较相邻两个元素的大小，若前面的元素大于后面的元素，则交换它们的位置。冒泡排序法冒泡排序法93576原始数据96573第1轮979693第2轮97356 7673第3轮7965336第4轮67935 35快速快速排序法排序法p基本思想

16、：以升序排序为例，在线性表中任意选取一个元素作为基准数T，接下来把比T大的元素放在它的右边，比T小的元素放在它的左边，T放到分界线的位置，将线性表分为两个子表，这个过程称为线性表的分割。按照这个原则对子表继续进行分割，直到所有子表的元素个数为0或1时结束。快速排序法第1次分割40103050702060ijj4020iii5040jj40第2次分割201030ijj1020i20705060iji6070i70第3次分割第4次分割6050ij i506060简单简单插入插入排序排序法法p基本思想：在线性表中，把只包含第1个元素的子表看成是一个有序表，然后从线性表的第2个元素开始直到最后一个元素

17、，依次插入到前面有序的子表中。简单插入排序法简单插入排序法70 10 60 50 4010 70第1次插入10 70 60 50 40第2次插入706010 60 70 50 40第3次插入706010 50 60 70 40第4次插入7060504050希尔希尔排序法排序法p基本思想：是把线性表分割成若干个子表分别进行简单插入排序。p线性表分割的方法：把相隔增量h的元素构成一个子表进行简单插入排序，在排序过程中逐次减小增量h，最后当h减到1时，再进行最后一次简单插入排序。希尔排序法希尔排序法70 10 80 60 40 20 30 50h=n/2=440708030 506040 10 30

18、 50 70 20 80 60h=h/2=23040 205030 10 40 20 70 50 80 60h=h/2=110 20 30 40 50 6070 80简单选择排序法简单选择排序法p基本思想：以升序排序为例，扫描整个线性表，从中选择最小的元素，把它与最前面的元素交换，使得最小元素就位；然后再对剩下的元素使用相同的方法，依次使得第二小的元素、第三小的元素，以及最大的元素就位。简单选择排序法简单选择排序法57396kk5337596kkk573579635697kk767第1轮第2轮第3轮第4轮9k堆排序法堆排序法p堆的定义：堆是满足某种特性的完全二叉树。p堆的分类：最大堆、最小堆。

19、p最大堆满足性质：任何一个父结点的值都大于等于它的左右子结点的值。p最小堆满足性质：任何一个父结点的值都小于等于它的左右子结点的值。p最大堆用来进行升序排序，最小堆用来进行降序排序。堆排序法堆排序法p最大堆升序排序的基本思想：以n个元素为例，首先将n个元素构造成一个最大堆，然后将根结点与末尾元素进行交换，此时末尾元素为最大值。然后将剩余的n-1个元素重新构造成一个最大堆，可以得到n-1个元素的最大值。如此反复执行，最后就能得到一个升序序列。堆排序法堆排序法30605010402030 60 50 10 40 20第1步： 用全部元素构建最大堆。从最后一个非叶子结点开始，自下向上，自右向左进行调

20、整。 交换堆顶元素和完全二叉树中最后1个元素的位置。505060603030306030603040304060206020堆排序法堆排序法204050103020 40 50 10 30 60第2步： 用剩余的5个元素构建最大堆。 交换堆顶元素和完全二叉树中最后1个元素的位置。404020202050505020305030堆排序法堆排序法3040201030 40 20 10 50 60第3步： 用剩余的4个元素构建最大堆。 交换堆顶元素和完全二叉树中最后1个元素的位置。404030304040403040 301010堆排序法堆排序法10302010 30 20 40 50 60第4步： 用剩余的3个元素构建最大堆。 交换堆顶元素和完全二叉树中最后1个元素的位置。10101030103020303020堆排序法堆排序法201020 10 30 40 50 60第5步： 用剩余的2个元素构建最大堆。 交换堆顶元素和完全二叉树中最后1个元素的位置。202020102010