数据结构与常用算法课件

第7章

数据结构与常用算法7.1数据结构的基本概念7.2线性表及其存储结构7.3栈和队列7.4树与二叉树7.5查找算法7.6排序算法第7章数据结构与常用算法7.1数据结构的基本概念7.1数据结构的基本概念7.1数据结构的基本概念7.1.1基本术语(1)数据：能被计算机识别、存储和加工处理的符号的总称。计算机中可以操作的对象(2)数据元素：数据的基本单位。在计算机中通常作为整体处理，也称为记录(3)数据项：数据元素的最小单位。一个数据元素由若干个数据项组成(4)数据对象：相同性质数据元素的集合。是数据的子集武汉科技大学计算机科学与技术学院7.1.1基本术语(1)数据：能被计算机识别、存储和加工处7.1.1基本术语数据对象、数据元素与数据项一列整数｛2，3，5，-3，8，12｝若干列整数一个学生：学号、姓名、性别、入学成绩。。。一个学生表：若干条学生记录7.1.1基本术语数据对象、数据元素与数据项7.1.2数据结构数据结构：带结构的数据元素的集合。数据元素之间相互有关联例如，3214，6587，9345—a1，a2，a3在a1、a2和a3之间存在“次序”关系<a1,a2>、<a2、a3>不等于

6587,3214,9345—a2,a1,

a37.1.2数据结构数据结构：带结构的数据元素的集合。7.1.2数据结构数据结构主要研究和讨论3个方面的问题：①数据集合中，各种数据元素之间所固有的逻辑关系，即数据的逻辑结构；②在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；③对各种数据结构进行的运算，其中常用的有检索、插入、删除、排序等7.1.2数据结构数据结构主要研究和讨论3个方面的问题：7.1.2数据结构1.数据的逻辑结构指反映数据元素之间逻辑关系的数据结构。两个要素：一是数据元素的集合，通常记为D；二是D上的二元关系，它反映了D中各数据元素之间的前驱与后继关系，通常记为R。一个数据结构可以表示成B=(D,R)，其中B表示数据结构。通常把数据元素之间的这种固有的关系，简单地用前驱与后继关系来描述。例如家庭成员的数据结构可以表示成B=(D,R)，其中D={父亲，儿子，女儿}，R={<父亲，儿子>，<父亲，女儿>}。7.1.2数据结构1.数据的逻辑结构7.1.2数据结构1.数据的逻辑结构通常有下面3种基本结构：①线性结构：结构中数据元素之间存在一个对一个的关系。②树形结构：结构中数据元素之间存在一个对多个的关系。③图形结构或网状结构：结构中数据元素之间存在多个对多个的关系。7.1.2数据结构1.数据的逻辑结构7.1.2数据结构2.数据的存储结构数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构（也称物理结构）。在数据的存储结构中，不仅要存放数据元素的信息，还需要存放各数据元素之间的前驱和后继关系的信息。4种常见的存储结构：(1)顺序存储结构(2)链式存储结构(3)索引存储结构(4)散列存储结构return7.1.2数据结构2.数据的存储结构return7.2线性表及其存储结构7.2线性表及其存储结构7.2.1线性表的基本概念通常，线性表是由n(n≥0)个数据元素

a1,a2,…,an组成的一个有限序列。①存在唯一的一个被称为“第一个”的数据元素；②存在唯一的一个被称为“最后一个”的数据元素；③除了第一个之外，表中的每个数据元素均只有一个前驱；④除了最后一个之外，表中的每个数据元素均只有一个后继。7.2.1线性表的基本概念通常，线性表是由n(n≥0)个数线性表的数据元素，通常也称为节点。数据元素在线性表中的位置只取决于它们自己的序号。线性表中节点的个数n称为线性表的长度。当

n=0时，称为空表。线性表的数据元素，通常也称为节点。1.线性表的顺序存储（顺序表）①线性表中的所有元素所占的存储空间是连续的；②线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。高级语言中，常用“一维数组”a(1:m)表示这种存储结构武汉科技大学计算机科学与技术学院7.2.2线性表的顺序存储及其运算1.线性表的顺序存储（顺序表）武汉科技大学计算机科学与技术2.顺序表的基本运算(1)顺序表的插入（ai前插入x）移动元素：从最后一个（即第n个）元素开始，直到第i个元素之间共n-i+1个元素依次向后移动一个位置ajaj+1(j:n~i)插入新元素：将新元素x插入到第i个位置xai更新长度：n+1n当n=m时，不能再插入，否则会“上溢”；所以插入前要检查是否会“上溢”。2.顺序表的基本运算2.顺序表的基本运算(2)顺序表的删除(删除ai)移动元素：从第i+1个元素开始，直到第n个元素之间，共有n

i个元素依次向前移动一个位置。ajaj-1(j:i~n)更新长度：n-1n 当n=0时不能再删除，

否则会“下溢”；所以删除前要检查是否

会“下溢”。2.顺序表的基本运算线性表的顺序存储结构的特点具有简单、存储密度大、空间利用率高、对表中任一元素可直接确定其存储地址（随机存取）、效率高等优点；但是也有明显的不足：在顺序表中进行插入与删除等操作时，需大量移动数据元素，浪费时间。因此，对于大的线性表，特别是元素变动频繁的大线性表，不宜采用顺序存储结构，而是采用链式存储结构。线性表的顺序存储结构的特点1.线性表的链式存储通过每个节点的指针域将n个节点按其逻辑顺序连接在一起而构成的数据存储结构，称为链式存储结构。对线性链表而言，它不要求逻辑上相邻的元素在物理位置上也相邻，其存储单元既可以是连续的，也可以是不连续的，甚至可以零散分布在存储空间中的任何位置上。其中指针域next用于指向该节点的后继节点datanext7.2.3线性表的链式存储及其运算1.线性表的链式存储其中指针域next用于指向该节点的1.线性表的链式存储1.线性表的链式存储datanext2.单链表的基本运算(1)单链表的插入(2)单链表的删除ADR(ai-1)ADR(x)ADR(ai-1)①ADR(ai-1).next

ADR(x).next②ADR(x)ADR(ai-1).next①ADR(ai-1).next.next

ADR(ai-1).next②释放ADR(ai-1).nextreturndatanext2.单链表的基本运算ADR(ai-1)AD7.3栈和队列7.3栈和队列7.3.1栈及其基本运算1.什么是栈栈是限定在一端进行插入和删除的线性表。在栈中，允许插入和删除的一端称为栈顶，用指针top来表示栈顶的位置注意，top的指向而不允许插入和删除的另一端称为栈底，用

bottom指向栈底注意，bottom的指向7.3.1栈及其基本运算1.什么是栈1.什么是栈栈也被称为“先进后出”表或“后进先出”表。因此，栈具有记忆作用。例如：货物堆放子弹夹函数的调用1.什么是栈武汉科技大学计算机科学与技术学院2.栈的顺序存储及其运算在程序设计语言中，用一维数组

S(1:m)作为栈的顺序存储空间，其中m为栈的最大容量。初始状态：bottom=1，top=0武汉科技大学计算机科学与技术学院2.栈的顺序存储及其运算对栈的定义的进一步理解一个栈的入栈序列是a,b,c,d,e，则不可能的出栈序列是（

）。A．edcba B．decbaC．dceab D．abcde对栈的定义的进一步理解一个栈的入栈序列是a,b,c,d2.栈的顺序存储及其运算(1)入栈运算更新栈顶指针：top+1top插入新元素：xStop当top=m时，说明栈空间已满，不能再进行入栈操作。否则出现“上溢”错误。所以入栈之前，要检查是否会“上溢”top-->x2.栈的顺序存储及其运算top-->x2.栈的顺序存储及其运算(2)退栈运算读栈顶元素：Stop

x更新栈顶指针：top-1top当

top=0时，说明栈空，不能再进行退栈运算。否则会出现“下溢”错误；所以退栈之前，要检查是否会“下溢”top-->-->x2.栈的顺序存储及其运算top-->-->x2.栈的顺序存储及其运算(3)读栈顶元素读数：Stop

x栈顶指针保持不变当

top=0

时，说明栈空，读不到栈顶元素；所以读数之前，要检查是否为空栈。2.栈的顺序存储及其运算7.3.2队列及其基本运算武汉科技大学计算机科学与技术学院1.什么是队列指允许在一端进行插入，而在另一端进行删除的线性表。允许插入的一端称为队尾，通常用一个称为队尾指针（rear）的指针指向队尾元素的下一个位置注意，rear的指向允许删除的一端称为队首，通常用一个称为队首指针（front）的指针指向队首元素的位置注意，front的指向7.3.2队列及其基本运算武汉科技大学计算机科学与技术学院1.什么是队列队列又称为“先进先出”或“后进后出”的线性表，它体现了“先来先服务”的原则。例如：排队等候现象1.什么是队列武汉科技大学计算机科学与技术学院1.什么是队列在程序设计语言中，用一维数组

S(1:m)作为队列的顺序存储空间，其中

m为队列的最大容量初始状态：front=rear=1武汉科技大学计算机科学与技术学院1.什么是队列1.什么是队列入队运算插入新元素：xSrear更新队尾指针：rear+1rear当

rear=m+1时，说明栈队列满，不能再入队。否则会出现“上溢”错误；所以入队之前，要检查是否会“上溢”观察：此时队首前面可能还有空位置。rear-->x1.什么是队列rear-->x1.什么是队列出队运算读队首元素：Sfrontx更新队首指针：front+1front当

front=rear时，不能再出队了。否则会出现“下溢”错误；所以出队之前，要检查是否会“下溢”观察：出队后会留下空位置，但已不能继续使用了——空间的浪费！front-->--->x1.什么是队列front-->--->x2.循环队列及其运算将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。当队尾指针

rear=m+1时，则置rear=1。当队首指针

front=m+1时，则置

front=1。2.循环队列及其运算2.循环队列及其运算2.循环队列及其运算武汉科技大学计算机科学与技术学院2.循环队列及其运算循环队列队满时，有front=rear；而当循环队列空时，也有front=rear。解决办法：增加一个标志

s循环队列初始状态：front=rear=1，且s=0武汉科技大学计算机科学与技术学院2.循环队列及其运算2.循环队列及其运算(1)入队运算插入新元素：xSrear更新队尾指针和空否标志：rear+1rear，当rear=m+1时置rear=1，且如果此时s=0，则置

s=1，表示队列非空。防止“上溢”：入队之前要检查，是否s=1且font=rear2.循环队列及其运算2.循环队列及其运算(2)出队运算读队首元素：Sfront

x更新队首指针和空否标志：front+1front，当front=m+1时置front=1，且如果此时front=rear，则说明队空，应置s=0。防止“下溢”：出队之前要检查，是否s=0且font=rear2.循环队列及其运算7.4树与二叉树7.4树与二叉树7.4.1树的基本概念1.树的定义树是n(n

≥0)个节点的有限集T。当n=0时，称为空树；当n>0时，该集合满足如下条件：①有且仅有一个根节点；②其余的节点可分为m(m

≥0)个互不相交的子集T1,T2,…,Tm，其中每个子集本身又是一颗树，并称其为根的子树。这是一个递归定义，是表达“一对多”的逻辑关系7.4.1树的基本概念1.树的定义这是一个递归定义，是表2.树的基本术语①节点的度，例如：节点A的度为3，节点C的度为1②树的度，例如：树的度为3③叶子，例如：节点E，G，H，J，K，L，M④分支节点，例如：节点A，B，C，D，F，I⑤双亲和孩子，例如：节点A是B、C、D的双亲⑥节点的层，例如：节点E、F、G、H、I、J的层均为3⑦树的深度，例如：图中树的深度为4⑧兄弟和堂兄弟⑨祖先和子孙⑩有序树和无序树森林2.树的基本术语度的概念的进一步理解9．设树T的度为4，其中度为1,2,3,4的结点数分别为4,2,1,1。则T中的叶子结点数为（

）。A．8 B．7 C．6D．5度的概念的进一步理解9．设树T的度为4，其中度为1,2,7.4.2二叉树及其基本性质1.二叉树的定义二叉树是n(n

≥0)个节点的有限集，它或者是空集(n=0)，或者是由一个根节点和两颗互不相交且分别称为根的左子树和右子树的二叉树组成。在二叉树中，每一个节点的度最大为2。二叉树和度为2的树是两个不同的概念。7.4.2二叉树及其基本性质1.二叉树的定义一颗野生的二叉树一颗野生的二叉树2.二叉树的基本性质【性质1】在二叉树的第i层至多有

2i-1

个节点(i≥1)。【性质2】深度为k的二叉树至多有2k

1个节点(k≥1)。【性质3】对任何一颗二叉树T，如果其叶子节点数为n0，度为2的节点数为n2，则n0=n2+1。【性质4】具有n(n≥1)个节点的完全二叉树的深度为[logn]+1（其中[logn]表示取logn的整数部分）。2.二叉树的基本性质2.二叉树的基本性质满二叉树完全二叉树非完全二叉树2.二叉树的基本性质完全二叉树的深入理解10．设一棵完全二叉树共有700个节点，则该二叉树中有_________________个叶子节点。完全二叉树的深入理解10．设一棵完全二叉树共有700个节点，7.4.3二叉树的存储结构1.顺序存储结构完全二叉树的顺序存储结构非完全二叉树的顺序存储结构7.4.3二叉树的存储结构1.顺序存储结构2.链式存储结构2.链式存储结构7.4.4二叉树的遍历遍历一棵二叉树就是按照某种规则去访问二叉树的每个节点，而且每个节点仅被访问一次。在先左后右的约定下，根据访问根节点的次序，二叉树的遍历可以分为:(1)先根遍历例如：ABDFCE(2)中根遍历例如：BFDACE(3)后根遍历例如：FDBECA7.4.4二叉树的遍历遍历一棵二叉树就是按照某种规则去访问武汉科技大学计算机科学与技术学院练习：先根遍历序列：

+a*b

cd/ef中根遍历序列：a+b*c

d

e/f后根遍历序列：abcd

*+ef/

武汉科技大学计算机科学与技术学院练习：二叉树遍历练习11．设一棵二叉树的中序遍历结果为DBEAFC，先序遍历结果为ABDECF，则该二叉树的后序遍历结果为_________________。return二叉树遍历练习11．设一棵二叉树的中序遍历结果为DBEAFC7.5查找算法7.5查找算法7.5查找算法1．定义查找就是根据给定的值，在一组数据中确定一个其数值等于给定值的数据元素，若存在这样的数据元素说明查找是成功的，否则查找是不成功的。查找某个数据元素取决于数据中数据元素的组织方式。衡量查找算法好坏的标准是以平均查找比较的次数来定。7.5查找算法1．定义2．查找方法顺序查找顺序查找方法的平均查找比较次数为(n+1)/2。折半查找只能用于顺序存储的数据元素且各数据元素按关键字有序排列的序列。其基本思想是：假设查找表中的数据元素按关键字递增有序排列，则首先与“中间位置”的元素比较，若相等则查找成功；若给定值大于“中间位置”的元素值，则在后半部继续进行折半查找；否则在前半部分进行折半查找。当在长度为n的表中使用折半查找时，最坏情况下的查找长度不超过log2n+12．查找方法2．查找方法如果采用顺序查找方法来查找21，需要比较4次；如果采用折半查找方法来查找21，需要比较3次序号1234567891011数据513192137566475808892return2．查找方法序号1234567891011数据51319217.6排序算法7.6排序算法7.6排序算法1．选择排序（从小到大）原始序列8921564885161947第1遍1621564885891947第2遍1619564885892147第3遍1619214885895647第4遍1619214785895648第5遍1619214748895685第6遍161921474856

8985第7遍16192147485685

89与“固定位”比较，后大则互换，使“最小者”出现在“最前面”。7.6排序算法1．选择排序（从小到大）原始序列武汉科技大学计算机科学与技术学院2．交换排序（冒泡排序，从小到大）原始序列8921564885161947第1遍218956488516194721568948851619472156488985161947215648858916194721564885168919472156488516198947

结果2156488516194789第2遍2156↔4885↔16↔19↔4789

结果2148561619478589第3遍214856↔16↔19↔478589

结果2148161947568589第4遍2148↔16↔19↔47568589

结果2116194748568589

相邻比较两个元素，前大则互换，使“最大者”移动至“最后”。武汉科技大学计算机科学与技术学院2．交换排序（冒泡排序，从小武汉科技大学计算机科学与技术学院原始序列8921564885161947第4遍