《数据结构与常用算法课件.ppt》由会员分享，可在线阅读，更多相关《数据结构与常用算法课件.ppt（60页珍藏版）》请在三一办公上搜索。
1、第7章 数据结构与常用算法,7.1 数据结构的基本概念7.2 线性表及其存储结构7.3 栈和队列7.4 树与二叉树7.5 查找算法7.6 排序算法,7.1 数据结构的基本概念,7.1.1 基本术语,(1)数据：能被计算机识别、存储和加工处理的符号的总称。计算机中可以操作的对象(2)数据元素：数据的基本单位。在计算机中通常作为整体处理，也称为记录(3)数据项：数据元素的最小单位。一个数据元素由若干个数据项组成(4)数据对象：相同性质数据元素的集合。是数据的子集,武汉科技大学计算机科学与技术学院,7.1.1 基本术语,数据对象、数据元素与数据项一列整数2，3，5，-3，8，12若干列整数一个学生：
2、学号、姓名、性别、入学成绩。一个学生表：若干条学生记录,7.1.2 数据结构,数据结构：带结构的数据元素的集合。数据元素之间相互有关联例如，3214，6587，9345 a1，a2，a3在a1、a2和a3之间存在“次序”关系、不等于 6587,3214,9345 a2,a1,a3,7.1.2 数据结构,数据结构主要研究和讨论3个方面的问题：数据集合中，各种数据元素之间所固有的逻辑关系，即数据的逻辑结构；在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；对各种数据结构进行的运算，其中常用的有检索、插入、删除、排序等,7.1.2 数据结构,1.数据的逻辑结构指反映数据元素之间逻
3、辑关系的数据结构。两个要素：一是数据元素的集合，通常记为D；二是D上的二元关系，它反映了D中各数据元素之间的前驱与后继关系，通常记为R。一个数据结构可以表示成B=(D,R)，其中B表示数据结构。通常把数据元素之间的这种固有的关系，简单地用前驱与后继关系来描述。例如家庭成员的数据结构可以表示成B=(D,R)，其中D=父亲，儿子，女儿，R=，。,7.1.2 数据结构,1.数据的逻辑结构通常有下面3种基本结构：线性结构：结构中数据元素之间存在一个对一个的关系。树形结构：结构中数据元素之间存在一个对多个的关系。图形结构或网状结构：结构中数据元素之间存在多个对多个的关系。,7.1.2 数据结构,2.数据
4、的存储结构数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构（也称物理结构）。在数据的存储结构中，不仅要存放数据元素的信息，还需要存放各数据元素之间的前驱和后继关系的信息。4种常见的存储结构：(1)顺序存储结构(2)链式存储结构(3)索引存储结构(4)散列存储结构,return,7.2 线性表及其存储结构,7.2.1 线性表的基本概念,通常，线性表是由n(n0)个数据元素 a1,a2,an组成的一个有限序列。存在唯一的一个被称为“第一个”的数据元素；存在唯一的一个被称为“最后一个”的数据元素；除了第一个之外，表中的每个数据元素均只有一个前驱；除了最后一个之外，表中的每个数据元素均只有
5、一个后继。,线性表的数据元素，通常也称为节点。数据元素在线性表中的位置只取决于它们自己的序号。线性表中节点的个数 n 称为线性表的长度。当 n=0 时，称为空表。,1.线性表的顺序存储（顺序表）线性表中的所有元素所占的存储空间是连续的；线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。高级语言中，常用“一维数组”a(1:m)表示这种存储结构,武汉科技大学计算机科学与技术学院,7.2.2 线性表的顺序存储及其运算,2.顺序表的基本运算(1)顺序表的插入（ai 前插入 x）移动元素：从最后一个（即第 n个）元素开始，直到第 i 个元素之间共 n-i+1 个元素依次向后移动一个位置aj aj+1
6、(j:ni)插入新元素：将新元素 x 插入到第 i 个位置x ai更新长度：n+1n当 n=m 时，不能再插入，否则会“上溢”；所以插入前要检查是否会“上溢”。,2.顺序表的基本运算(2)顺序表的删除(删除ai)移动元素：从第 i+1 个元素开始，直到第 n 个元素之间，共有 ni 个元素依次向前移动一个位置。aj aj-1(j:in)更新长度：n-1n当 n=0 时不能再删除，否则会“下溢”；所以删除前要检查是否会“下溢”。,线性表的顺序存储结构的特点具有简单、存储密度大、空间利用率高、对表中任一元素可直接确定其存储地址（随机存取）、效率高等优点；但是也有明显的不足：在顺序表中进行插入与删除
7、等操作时，需大量移动数据元素，浪费时间。因此，对于大的线性表，特别是元素变动频繁的大线性表，不宜采用顺序存储结构，而是采用链式存储结构。,1.线性表的链式存储通过每个节点的指针域将n个节点按其逻辑顺序连接在一起而构成的数据存储结构，称为链式存储结构。对线性链表而言，它不要求逻辑上相邻的元素在物理位置上也相邻，其存储单元既可以是连续的，也可以是不连续的，甚至可以零散分布在存储空间中的任何位置上。,其中指针域 next 用于指向该节点的后继节点,7.2.3 线性表的链式存储及其运算,1.线性表的链式存储,2.单链表的基本运算(1)单链表的插入(2)单链表的删除,ADR(ai-1),ADR(ai-1
8、).next ADR(x).next ADR(x)ADR(ai-1).next,ADR(ai-1).next.next ADR(ai-1).next 释放 ADR(ai-1).next,return,7.3 栈和队列,7.3.1 栈及其基本运算,1.什么是栈栈是限定在一端进行插入和删除的线性表。在栈中，允许插入和删除的一端称为栈顶，用指针 top 来表示栈顶的位置注意，top的指向而不允许插入和删除的另一端称为栈底，用 bottom 指向栈底注意，bottom的指向,1.什么是栈栈也被称为“先进后出”表或“后进先出”表。因此，栈具有记忆作用。例如：货物堆放子弹夹函数的调用,武汉科技大学计算机科
9、学与技术学院,2.栈的顺序存储及其运算在程序设计语言中，用一维数组 S(1:m)作为栈的顺序存储空间，其中m为栈的最大容量。初始状态：bottom=1，top=0,对栈的定义的进一步理解,一个栈的入栈序列是a,b,c,d,e，则不可能的出栈序列是（）。AedcbaBdecbaCdceabDabcde,2.栈的顺序存储及其运算(1)入栈运算更新栈顶指针：top+1 top插入新元素：x Stop当 top=m 时，说明栈空间已满，不能再进行入栈操作。否则出现“上溢”错误。所以入栈之前，要检查是否会“上溢”,top-,x,2.栈的顺序存储及其运算(2)退栈运算读栈顶元素：Stop x更新栈顶指针：
10、top-1 top当 top=0 时，说明栈空，不能再进行退栈运算。否则会出现“下溢”错误；所以退栈之前，要检查是否会“下溢”,top-,-x,2.栈的顺序存储及其运算(3)读栈顶元素读数：Stop x栈顶指针保持不变当 top=0 时，说明栈空，读不到栈顶元素；所以读数之前，要检查是否为空栈。,7.3.2 队列及其基本运算,武汉科技大学计算机科学与技术学院,1.什么是队列指允许在一端进行插入，而在另一端进行删除的线性表。允许插入的一端称为队尾，通常用一个称为队尾指针（rear）的指针指向队尾元素的下一个位置注意，rear 的指向允许删除的一端称为队首，通常用一个称为队首指针（front）的指
11、针指向队首元素的位置注意，front 的指向,1.什么是队列队列又称为“先进先出”或“后进后出”的线性表，它体现了“先来先服务”的原则。例如：排队等候现象,武汉科技大学计算机科学与技术学院,1.什么是队列在程序设计语言中，用一维数组 S(1:m)作为队列的顺序存储空间，其中 m 为队列的最大容量初始状态：front=rear=1,1.什么是队列入队运算插入新元素：x Srear更新队尾指针：rear+1 rear当 rear=m+1 时，说明栈队列满，不能再入队。否则会出现“上溢”错误；所以入队之前，要检查是否会“上溢”观察：此时队首前面可能还有空位置。,rear-,x,1.什么是队列出队运算
12、读队首元素：S front x更新队首指针：front+1 front当 front=rear 时，不能再出队了。否则会出现“下溢”错误；所以出队之前，要检查是否会“下溢”观察：出队后会留下空位置，但已不能继续使用了空间的浪费！,front-,-x,2.循环队列及其运算将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。当队尾指针 rear=m+1时，则置rear=1。当队首指针 front=m+1时，则置 front=1。,2.循环队列及其运算,武汉科技大学计算机科学与技术学院,2.循环队列及其运算循环队列队满时，有 front=rear；而当循环队列空时，也有
13、front=rear。解决办法：增加一个标志 s循环队列初始状态：front=rear=1，且 s=0,2.循环队列及其运算(1)入队运算插入新元素：x Srear更新队尾指针和空否标志：rear+1 rear，当 rear=m+1 时置rear=1，且如果此时 s=0，则置 s=1，表示队列非空。防止“上溢”：入队之前要检查，是否 s=1且 font=rear,2.循环队列及其运算(2)出队运算读队首元素：Sfront x更新队首指针和空否标志：front+1 front，当 front=m+1时置 front=1，且如果此时 front=rear，则说明队空，应置 s=0。防止“下溢”：出
14、队之前要检查，是否 s=0且 font=rear,7.4 树与二叉树,7.4.1 树的基本概念,1.树的定义树是n(n 0)个节点的有限集T。当n=0时，称为空树；当n 0时，该集合满足如下条件：有且仅有一个根节点；其余的节点可分为m(m 0)个互不相交的子集T1,T2,Tm，其中每个子集本身又是一颗树，并称其为根的子树。,这是一个递归定义，是表达“一对多”的逻辑关系,2.树的基本术语节点的度，例如：节点A的度为3，节点C的度为1树的度，例如：树的度为3叶子，例如：节点E，G，H，J，K，L，M分支节点，例如：节点A，B，C，D，F，I双亲和孩子，例如：节点A是B、C、D的双亲节点的层，例如：
15、节点E、F、G、H、I、J的层均为3树的深度，例如：图中树的深度为4兄弟和堂兄弟祖先和子孙有序树和无序树森林,度的概念的进一步理解,9设树T的度为4，其中度为1,2,3,4的结点数分别为4,2,1,1。则T中的叶子结点数为（）。A8 B7 C6 D5,7.4.2 二叉树及其基本性质,1.二叉树的定义二叉树是n(n 0)个节点的有限集，它或者是空集(n=0)，或者是由一个根节点和两颗互不相交且分别称为根的左子树和右子树的二叉树组成。在二叉树中，每一个节点的度最大为2。二叉树和度为2的树是两个不同的概念。,一颗野生的二叉树,2.二叉树的基本性质【性质1】在二叉树的第 i 层至多有 2i-1 个节点
16、(i1)。【性质2】深度为k的二叉树至多有 2k1个节点(k1)。【性质3】对任何一颗二叉树T，如果其叶子节点数为n0，度为2的节点数为n2，则 n0=n2+1。【性质4】具有n(n1)个节点的完全二叉树的深度为log n+1（其中log n表示取log n的整数部分）。,2.二叉树的基本性质满二叉树完全二叉树非完全二叉树,完全二叉树的深入理解,10设一棵完全二叉树共有700个节点，则该二叉树中有_个叶子节点。,7.4.3 二叉树的存储结构,1.顺序存储结构完全二叉树的顺序存储结构非完全二叉树的顺序存储结构,2.链式存储结构,7.4.4 二叉树的遍历,遍历一棵二叉树就是按照某种规则去访问二叉树
17、的每个节点，而且每个节点仅被访问一次。在先左后右的约定下，根据访问根节点的次序，二叉树的遍历可以分为:(1)先根遍历例如：ABDFCE(2)中根遍历例如：BFDACE(3)后根遍历例如：FDBECA,武汉科技大学计算机科学与技术学院,练习：先根遍历序列：+a*bcd/ef中根遍历序列：a+b*cde/f后根遍历序列：abcd*+ef/,二叉树遍历练习,11设一棵二叉树的中序遍历结果为DBEAFC，先序遍历结果为ABDECF，则该二叉树的后序遍历结果为_。,return,7.5 查找算法,7.5 查找算法,1定义查找就是根据给定的值，在一组数据中确定一个其数值等于给定值的数据元素，若存在这样的数
18、据元素说明查找是成功的，否则查找是不成功的。查找某个数据元素取决于数据中数据元素的组织方式。衡量查找算法好坏的标准是以平均查找比较的次数来定。,2查找方法顺序查找顺序查找方法的平均查找比较次数为(n+1)/2。折半查找只能用于顺序存储的数据元素且各数据元素按关键字有序排列的序列。其基本思想是：假设查找表中的数据元素按关键字递增有序排列，则首先与“中间位置”的元素比较，若相等则查找成功；若给定值大于“中间位置”的元素值，则在后半部继续进行折半查找；否则在前半部分进行折半查找。当在长度为n的表中使用折半查找时，最坏情况下的查找长度不超过log2 n+1,2查找方法如果采用顺序查找方法来查找21，需
19、要比较4次；如果采用折半查找方法来查找21，需要比较3次,return,7.6 排序算法,7.6 排序算法,1选择排序（从小到大）,原始序列 89 21 56 48 85 16 19 47第1遍 16 21 56 48 85 89 19 47第2遍 16 19 56 48 85 89 21 47第3遍 16 19 21 48 85 89 56 47第4遍 16 19 21 47 85 89 56 48第5遍 16 19 21 47 48 89 56 85第6遍 16 19 21 47 48 56 89 85第7遍 16 19 21 47 48 56 85 89,与“固定位”比较，后大则互换，使
20、“最小者”出现在“最前面”。,武汉科技大学计算机科学与技术学院,2交换排序（冒泡排序，从小到大）,原始序列 89 21 56 48 85 16 19 47第1遍 21 89 56 48 85 16 19 47 21 56 89 48 85 16 19 47 21 56 48 89 85 16 19 47 21 56 48 85 89 16 19 47 21 56 48 85 16 89 19 47 21 56 48 85 16 19 89 47 结果 21 56 48 85 16 19 47 89第2遍 21 56 48 85 16 19 47 89 结果 21 48 56 16 19 47
21、85 89第3遍 21 48 56 16 19 47 85 89 结果 21 48 16 19 47 56 85 89第4遍 21 48 16 19 47 56 85 89 结果 21 16 19 47 48 56 85 89,相邻比较两个元素，前大则互换，使“最大者”移动至“最后”。,武汉科技大学计算机科学与技术学院,原始序列 89 21 56 48 85 16 19 47第4遍 21 48 16 19 47 56 85 89 结果 21 16 19 47 48 56 85 89第5遍 21 16 19 47 48 56 85 89 结果 16 19 21 47 48 56 85 89第6遍
22、 16 19 21 47 48 56 85 89 结果 16 19 21 47 48 56 85 89第7遍 16 19 21 47 48 56 85 89 结果 16 19 21 47 48 56 85 89,3插入排序,原始序列 89 21 56 48 85 16 19 47 第1遍 21 89 56 48 85 16 19 47 第2遍 21 56 89 48 85 16 19 47 第3遍 21 48 56 89 85 16 19 47 第4遍 21 48 56 85 89 16 19 47 第5遍 16 21 48 56 85 89 19 47 第6遍 16 19 21 48 56 85 89 47 第7遍 16 19 21 47 48 56 85 89,return,
