数据结构与常用算法二版

第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｝假设干列整数一个学生：学号、姓名、性别、入学成绩。。。一个学生表：假设干条学生记录7.1.2数据结构数据结构：带结构的数据元素的集合。数据元素之间相互有关联例如，3214，6587，9345—a1，a2，a3在a1、a2和a3之间存在“次序〞关系<a1,a2>、<a2、a3>不等于6587,3214,9345—a2,a1,a37.1.2数据结构数据结构主要研究和讨论3个方面的问题：①数据集合中，各种数据元素之间所固有的逻辑关系，即数据的逻辑结构；②在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；③对各种数据结构进行的运算，其中常用的有检索、插入、删除、排序等7.1.2数据结构1.数据的逻辑结构指反映数据元素之间逻辑关系的数据结构。两个要素：一是数据元素的集合，通常记为D；二是D上的二元关系，它反映了D中各数据元素之间的前驱与后继关系，通常记为R。一个数据结构可以表示成B=(D,R)，其中B表示数据结构。通常把数据元素之间的这种固有的关系，简单地用前驱与后继关系来描述。例如家庭成员的数据结构可以表示成B=(D,R)，其中D={父亲，儿子，女儿}，R={<父亲，儿子>，<父亲，女儿>}。7.1.2数据结构1.数据的逻辑结构通常有下面3种根本结构：①线性结构：结构中数据元素之间存在一个对一个的关系。②树形结构：结构中数据元素之间存在一个对多个的关系。③图形结构或网状结构：结构中数据元素之间存在多个对多个的关系。7.1.2数据结构2.数据的存储结构数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构〔也称物理结构〕。在数据的存储结构中，不仅要存放数据元素的信息，还需要存放各数据元素之间的前驱和后继关系的信息。4种常见的存储结构：(1)顺序存储结构(2)链式存储结构(3)索引存储结构(4)散列存储结构7.2线性表及其存储结构7.2.1线性表的根本概念通常，线性表是由n(n≥0)个数据元素a1,a2,…,an组成的一个有限序列。①存在唯一的一个被称为“第一个〞的数据元素；②存在唯一的一个被称为“最后一个〞的数据元素；③除了第一个之外，表中的每个数据元素均只有一个前驱；④除了最后一个之外，表中的每个数据元素均只有一个后继。7.2.1线性表的根本概念线性表的数据元素，通常也称为节点。数据元素在线性表中的位置只取决于它们自己的序号。线性表中节点的个数n称为线性表的长度。当

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

否那么会“下溢〞；所以删除前要检查是否

会“下溢〞。7.2.2线性表的顺序存储及其运算线性表的顺序存储结构的特点具有简单、存储密度大、空间利用率高、对表中任一元素可直接确定其存储地址〔随机存取〕、效率高等优点；但是也有明显的缺乏：在顺序表中进行插入与删除等操作时，需大量移动数据元素，浪费时间。因此，对于大的线性表，特别是元素变动频繁的大线性表，不宜采用顺序存储结构，而是采用链式存储结构。7.2.3线性表的链式存储及其运算1.线性表的链式存储通过每个节点的指针域将n个节点按其逻辑顺序连接在一起而构成的数据存储结构，称为链式存储结构。对线性链表而言，它不要求逻辑上相邻的元素在物理位置上也相邻，其存储单元既可以是连续的，也可以是不连续的，甚至可以零散分布在存储空间中的任何位置上。其中指针域next用于指向该节点的后继节点datanext7.2.3线性表的链式存储及其运算1.线性表的链式存储datanext7.2.3线性表的链式存储及其运算2.单链表的根本运算(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).next7.3栈和队列7.3.1栈及其根本运算1.什么是栈栈是限定在一端进行插入和删除的线性表。在栈中，允许插入和删除的一端称为栈顶，用指针

top来表示栈顶的位置注意，top的指向而不允许插入和删除的另一端称为栈底，用

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

S(1:m)作为栈的顺序存储空间，其中m为栈的最大容量。初始状态：bottom=1，top=0对栈的定义的进一步理解一个栈的入栈序列是a,b,c,d,e，那么不可能的出栈序列是〔〕。A．edcba B．decbaC．dceab D．abcde7.3.1栈及其根本运算2.栈的顺序存储及其运算(1)入栈运算更新栈顶指针：top+1top插入新元素：xStop当top=m时，说明栈空间已满，不能再进行入栈操作。否那么出现“上溢〞错误。所以入栈之前，要检查是否会“上溢〞top-->x7.3.1栈及其根本运算2.栈的顺序存储及其运算(2)退栈运算读栈顶元素：Stopx更新栈顶指针：top-1top当top=0时，说明栈空，不能再进行退栈运算。否那么会出现“下溢〞错误；所以退栈之前，要检查是否会“下溢〞top-->-->x7.3.1栈及其根本运算2.栈的顺序存储及其运算(3)读栈顶元素读数：Stop

x栈顶指针保持不变当

top=0

时，说明栈空，读不到栈顶元素；所以读数之前，要检查是否为空栈。7.3.2队列及其根本运算1.什么是队列指允许在一端进行插入，而在另一端进行删除的线性表。允许插入的一端称为队尾，通常用一个称为队尾指针〔rear〕的指针指向队尾元素的下一个位置注意，rear的指向允许删除的一端称为队首，通常用一个称为队首指针〔front〕的指针指向队首元素的位置注意，front的指向7.3.2队列及其根本运算1.什么是队列队列又称为“先进先出〞或“后进后出〞的线性表，它表达了“先来先效劳〞的原那么。例如：排队等候现象7.3.2队列及其根本运算1.什么是队列在程序设计语言中，用一维数组

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

m为队列的最大容量初始状态：front=rear=17.3.2队列及其根本运算1.什么是队列入队运算插入新元素：xSrear更新队尾指针：rear+1rear当rear=m+1时，说明栈队列满，不能再入队。否那么会出现“上溢〞错误；所以入队之前，要检查是否会“上溢〞观察：此时队首前面可能还有空位置。rear-->x7.3.2队列及其根本运算1.什么是队列出队运算读队首元素：Sfrontx更新队首指针：front+1front当front=rear时，不能再出队了。否那么会出现“下溢〞错误；所以出队之前，要检查是否会“下溢〞观察：出队后会留下空位置，但已不能继续使用了——空间的浪费！front-->--->x7.3.2队列及其根本运算2.循环队列及其运算将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。当队尾指针rear=m+1时，那么置rear=1。当队首指针front=m+1时，那么置front=1。7.3.2队列及其根本运算2.循环队列及其运算7.3.2队列及其根本运算2.循环队列及其运算循环队列队满时，有front=rear；而当循环队列空时，也有front=rear。解决方法：增加一个标志s循环队列初始状态：front=rear=1，且s=07.3.2队列及其根本运算2.循环队列及其运算(1)入队运算插入新元素：xSrear更新队尾指针和空否标志：rear+1rear，当rear=m+1时置rear=1，且如果此时s=0，那么置s=1，表示队列非空。防止“上溢〞：入队之前要检查，是否s=1且font=rear7.3.2队列及其根本运算2.循环队列及其运算(2)出队运算读队首元素：Sfrontx更新队首指针和空否标志：front+1front，当front=m+1时置front=1，且如果此时front=rear，那么说明队空，应置s=0。防止“下溢〞：出队之前要检查，是否s=0且font=rear7.4树与二叉树7.4.1树的根本概念1.树的定义树是n(n

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

≥0)个互不相交的子集T1,T2,…,Tm，其中每个子集本身又是一颗树，并称其为根的子树。这是一个递归定义，是表达“一对多〞的逻辑关系7.4.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⑧兄弟和堂兄弟⑨祖先和子孙⑩有序树和无序树森林度的概念的进一步理解9．设树T的度为4，其中度为1,2,3,4的结点数分别为4,2,1,1。那么T中的叶子结点数为〔〕。A．8 B．7 C．6D．5设树的节点总数为n,度为0〔即叶子〕、1、2、3、4的结点个数分别设为n0,n1,n2,n3,n4.

那么n=n0+n1+n2+n3+n4=n0+4+2+1+1=n0+8;树中结点总数也可以由树中分支数B求得,度为1的结点就是有1个分支,度为2的结点就是有2个分支,度为3的结点就是有3个分支,度为4的结点就是有4个分支,度为0的叶子没有分支,所以B＝1*n1+2*n2+3*n3+4*n4=15.从下向上看,除了根结点,每个结点都有一个分支连着,所以n=B+1=16.所以叶子数n0为87.4.2二叉树及其根本性质1.二叉树的定义二叉树是n(n

≥0)个节点的有限集，它或者是空集(n=0)，或者是由一个根节点和两颗互不相交且分别称为根的左子树和右子树的二叉树组成。在二叉树中，每一个节点的度最大为2。二叉树和度为2的树是两个不同的概念。一颗野生的二叉树7.4.2二叉树及其根本性质2.二叉树的根本性质【性质1】在二叉树的第i层至多有2i-1个节点(i≥1)。【性质2】深度为k的二叉树至多有2k1个节点(k≥1)。【性质3】对任何一颗二叉树T，如果其叶子节点数为n0，度为2的节点数为n2，那么n0=n2+1。【性质4】具有n(n≥1)个节点的完全二叉树的深度为[logn]+1〔其中[logn]表示取logn的整数局部〕。7.4.2二叉树及其根本性质2.二叉树的根本性质满二叉树完全二叉树非完全二叉树完全二叉树的深入理解10．设一棵完全二叉树共有700个节点，那么该二叉树中有_________________个叶子节点。7.4.3二叉树的存储结构1.顺序存储结构完全二叉树的顺序存储结构非完全二叉树的顺序存储结构7.4.3二叉树的存储结构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，那么该二叉树的后序遍历结果为_________________。7.5查找算法7.5查找算法1．定义查找就是根据给定的值，在一组数据中确定一个其数值等于给定值的数据元素，假设存在这样的数据元素说明查找是成功的，否那么查找是不成功的。查找某个数据元素取决于数据中数据元素的组织方式。衡量查找算法好坏的标准是以平均查找比较的次数来定。7.5查找算法2．查找方法顺序查找顺序查找方法的平均查找比较次数为(n+1)/2。折半查找只能用于顺序存储的数据元素且各数据元素按关键字有序排列的序列。其根本思想是：假设查找表中的数据元素按关键字递增有序排列，那么首先与“中间位置〞的元素比较，假设相等那么查找成功；假设给定值大于“中间位置〞的元素值，那么在后半部继续进行折半查找；否那么在前半局部进行折半查找。当在长度为n的表中使用折半查找时，最坏情况下的查找长度不超过log2n+17.5查找算法2．查找方法如果采用顺序查找方法来查找21，需要比较4次；如果采用折半查找方法来查找21，需要比较3次序号1234567891011数据5131921375664758088927.6排序算法7.6排序算法1．选择排序原始序列8921564885161947第1遍1621564885891947第2遍1619564885892147第3遍1619214885895647第4遍16192147

85895648第5遍1619214748895685第6遍161921474856

89

85第7遍16192147485685

897.6排序算法2．交换排序〔冒泡排序〕原始序列8921564885161947第1遍

218956488516194721568948851619472156488985161947215648858916194721564885168919472156488516198947

结果

2156488516194789第2遍

2156↔4885↔16↔19↔4789

结果

2148561619478589第3遍

214856↔16↔19↔478589

结果

2148161947568589第4遍

2148↔16↔19↔47568589

结果

2116194748568589

7.6排序算法2．交换排序〔冒泡排序〕原始序列8921564885161947第4遍

2148↔16↔19↔47568589

结果

2116194748568589第5遍

21↔16↔