数据结构与算法（Python版）第2版 课件周元哲 第1-7章 数据结构与算法 -树

数据结构与算法python版

(第二版)周元哲机械工业出版社2程序设计著名计算机科学家沃思提出了一个公式：

程序=数据结构+算法。算法解决“如何操作数据？”的问题。数据结构是指定数据的类型和数据的组织形式，解决了“如何描述数据？”的问题。3程序设计过程分析问题算法与数据结构程序设计语言流程图数据结构数据结构是相互之间存在的一种或多种特定关系的数据元素的集合。数据结构中的“关系”是指数据间的逻辑关系，与数据的物理存储方式无关，同一种逻辑结构可以有多种不同物理存储方式。本章将详细介绍数据结构的几大分类：线形结构、树形结构和图（网状）结构。4数据结构在计算机领域中具有重要地位，是操作系统、人工智能、计算机组成原理、程序设计、软件工程、数据库、编译原理等课程的重要基础5操作系统数据库人工智能计算机组成原理程序设计语言编译原理软件工程数据结构微机原理算法找假币方法一：n-1次612345678910?方法二：n/2次712345679108方法三：log2N次8“算法”就是解决一个问题而采取的方法和步骤，是对解题方案的准确而完整的描述，是一系列解决问题的清晰指令。9五个属性（1）确定性。（2）可行性。（3）有穷性。（4）输入性。（5）输出性。10三个层次层次内容第一层一些基本的算法，如排序、查找、递归法等算法第二层涉及算法的时间复杂度和空间复杂度，如分治法、贪心算法、动态规划法等第三层涉及智能优化算法的学习，如遗传算法、蚁群算法、聚类算法等方法11算法复杂性空间复杂度时间复杂度12

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度，记做S(n)=O(f(n))。（1）算法的输入输出数据所占用的存储空间由要解决的问题决定，是通过参数表由调用函数传递而来的，它不随本算法的不同而改变。（2）算法本身所占用的存储空间与算法书写的长短成正比，要压缩这方面的存储空间，就必须编写出较短的算法。（3）算法在运行过程中临时占用的存储空间随算法的不同而异。13

算法的时间复杂度是一个函数，通常用大O符号表述，用于定量描述了该算法的运行时间。

算法中模块n的基本操作的重复执行次数计为函数f(n)，算法的时间复杂度为T(n)=O(f(n))。

常数阶O(1),对数阶O(log2n),线性阶O(n),线性对数阶O(nlog2n),平方阶O(n^2)，立方阶O(n^3),...，k次方阶O(n^k),指数阶O(2^n)。14算法评价标准1.正确性2.可读性3.健壮性4.高效率与低存储量需求15算法效率减少程序复杂性(圈复杂度V(G))16选用等效的高效率算法例如：鸡兔问题方法1：利用二重循环来实现。方法2：利用一重循环来实现。方法3：17x+y=302x+4y=90X=(4a-b)/2Y=(b-2a)/2算法表示方式程序流程图N-S图伪语言18程序流程图19N-S图20伪语言21伪语言(Pseudocode)也称伪代码，介于自然语言和计算机语言之间，并不是真正存在的编程语言。伪代码综合使用多种编程语言中语法、保留字，甚至会用到自然语言，不采用图形符号，因此书写方便、格式紧凑，便于向计算机编程语言(Pascal,C,Java……)过渡。Python语言概述Python继承于ABC语言，主要受到Modula-3的影响，Modula-3是另一种相当优美且强大的语言，为小型团体所设计，并且结合了Unixshell和C的习惯。

GuidovanRossum“Lifeisshort,youneedPython!”1.Python语言发展Python的特点解释性面向对象第三方库开源，可移植简单易学/jobbole/awesome-python-cn2.Python语言特点Python的程序开发工具1.Python的版本选择

最主流的两个版本是Python2.X和Python3.X2.Python的下载和安装/download3.Python的开发环境第2章异常处理与调试异常

程序中常见的错误分为三种：（1）语法错误（2）编译错误（3）系统错误>>>10*(3/0)Traceback(mostrecentcalllast):File"<pyshell#0>",line1,in<module>10*(3/0)ZeroDivisionError:divisionbyzeroPython中异常处理结构1简单形式的try…except语句一般形式：try:

语句块except:

异常处理语句块例：除数为0的异常处理。numbers=[0.33,2.5,0,100]forxinnumbers:print(x)try:print(1.0/x)exceptZeroDivisionError:print("除数不能为零")运行结果：0.333.03030303030303032.50.40除数不能为零1000.012简单形式的try…except语句一般形式：try:语句块

except异常类型1：异常处理语句块1except异常类型2:异常处理语句块2……except异常类型n:异常处理语句块nexcept:异常处理语句块else:语句块

例：带有多个except的异常处理。try:x=input("请输入被除数:")y=input("请输入除数:")a=int(x)/float(y)*zexceptZeroDivisionError:print("除数不能为零")exceptNameError:print("变量不存在")else:print(x,"/",y,"=",z)运行结果：请输入被除数:3请输入除数:4变量不存在再次运行结果：请输入被除数:3请输入除数:0除数不能为零3try...except...finally语句结构一般形式：try:

语句块：except:

异常处理语句块finally:

语句块断言与上下文管理1断言一般形式：assertexpression[,reason]处理过程：首先判断表达式expression的值，如果为True，什么都不做；如果为False，则断言不通过，则抛出异常。例：判断素数的断言处理。defisPrime(n):assertn>=2frommathimportsqrtforiinrange(2,int(sqrt(n))+1):ifn%i==0:returnFalsereturnTruewhileTrue:n=int(input("请输入一个整数："))flag=isPrime(n)ifflag==True:print("%d是素数"%n)else:print("%d不是素数"%n)2上下文管理一般形式：withcontext_expression[asvar]:

with语句块withopen('test.txt')asf:forlineinf:print(line,end='')例：判断素数的断言处理。defisPrime(n):assertn>=2frommathimportsqrtforiinrange(2,int(sqrt(n))+1):ifn%i==0:returnFalsereturnTruewhileTrue:n=int(input("请输入一个整数："))flag=isPrime(n)ifflag==True:print("%d是素数"%n)else:print("%d不是素数"%n)缩进注释（1）序言性注释:位于每个模块开始处，作为序言性的注解，简要描述模块的功能、主要算法、接口特点、重要数据以及开发简史。（2）功能性注释：插在程序中间，与一段程序代码有关的注解，是针对一些必要的变量，核心的代码进行解释，主要解释包含这段代码的必要性。编码习惯（1）复杂的表达式使用“括号”优先级处理，避免二义性。（2)单个函数的程序行数最好不要超过100行。（3)尽量使用标准库函数和公共函数。（4)不要随意定义全局变量，尽量使用局部变量。

（5)保持注释与代码完全一致，改了代码别忘改注释。编码习惯（6）采用匈牙利命名法，即采用小写前缀加上有特定描述意义的名字方式为变量命名，强调命名应“见名思义”（7）循环、分支层次最好不要超过五层。（8）在编程序前，尽可能化简表达式（9）仔细检查算法中的嵌套的循环，尽可能将某些语句或表达式移到循环外面（10）避免混淆数据类型（11）尽量采用算术表达式和布尔表达式

第3章线性表线性表相关概念线性表是最常用的数据结构之一，它是由n（n≥0）个数据元素（节点）组成的满足如下条件的有限序列（a0，a1…，an-1）：当i=1，...，n-1时，ai有且仅有一个直接前趋ai-1；当i=0，1，...，n-2时，有且仅有一个直接后继ai+1；表中第一个元素a0没有前趋；最后一个元素an-1无后继。数据元素的个数n称为线性表长度，长度为0时称为空表。数据元素可以是单一类型的数据，如整数、字符串等，也可以由若干个数据项组成的结构体，如学生信息（学号，姓名，班级）等。41线性表的存储顺序存储链式存储42顺序存储线性表的节点按逻辑次序依次存放在地址连续的存储单元中，使得逻辑上相邻的元素在物理位置上亦相邻。用这种方法实现的线性表简称为顺序表。Python中list和tuple两种数据类型实现顺序表。43插入算法性能分析：当插入位置为i时，移动次数

f(n)=n–i+1若i=1,需移动全部n个结点

T(n)=O(n)若i=n+1，无需移动结点，直接插入即可

T(n)=O(1)

主要时间消耗在移动数据元素上，因此作为基本操作对插入算法进行时间复杂度估计。顺序存储结构的优缺点分析优点：缺点：1.无需为表示结点间的逻辑关系而增加额外的存储空间；2.可方便地随机存取表中的任一元素。1.插入或删除平均需要移动一半的结点；2.存储分配只能预先进行静态分配过大浪费过小溢出链式存储链式存储通过一组含有指针的存储单元来存储线性表的数据及其逻辑关系。采用链式存储的线性表通常称为单链表。单链表节点的结构，除存放元素的数据域（data）外，还有存放后继元素地址的指针域（next）46特点：链表中结点的逻辑次序和物理次序不一定相同。即：逻辑上相邻未必在物理上相邻。定义：采用链式存储结构的线性表称为链表，其采用一组任意的存储单元来存放线性表的数据元素（可零散的分布于内存单元的任何位置上）。链式存储节点数据类型可表示为：classSingleNode(object):"""单链表的结点"""def__init__(self,item):self.item=item#item存放数据元素self.next=None#next是下一个结点的标识48（1）创建单链表：包括判断链表是否为空；求链表的长度；遍历整个链表。（2）线性表的查找：查找节点是否存在。（3）线性表的插入：包括在链表头部、链表尾部添加元素和在指定位置添加元素。（4）线性表的删除：删除节点单链表基本操作——建单链表(1)尾插法算法思路：从一个空表开始，每读入一个数据，生成新结点，将读入数据存放在新结点的数据域中，然后将新结点插入到当前链表的最后一个结点之后，依此类推，直到处理完所有数据。ABC^Head例:(A,B,C,D,···,Z)^rDrNew生成的结点次序和输入的顺序相同建立链表就是根据需要一个一个地开辟新结点，在结点中存放数据并建立结点之间的链接关系。6.单链表基本操作——建单链表(2)头插法算法思路：从一个空表开始，每读入一个数据，生成新结点，将读入数据存放在新结点的数据域中，然后将新结点插入到当前链表的第一个结点之前，依此类推，直到处理完所有数据。A^BC例:(A,B,C,D,···,Z)HDNew生成的结点次序和输入的顺序相反'''遍历整个列表'''deftravel(self):'''遍历整个列表'''cur=self.__headwhilecur!=None:print(cur.elem,end='')cur=cur.nextprint("\n")‘’‘查找节点是否存在'defsearch(self,item):'''查找节点是否存在'''cur=self.__headwhilenotcur:ifcur.elem==item:returnTrueelse:cur=cur.nextreturnFalse'''链表头部添加元素'''defadd(self,item):node=Node(item)node.next=self.__headself.__head=nodeheaditemnodenode.next=headhead‘’‘链表尾部添加元素'''defappend(self,item):'''链表尾部添加元素'''node=Node(item)#由于特殊情况当链表为空时没有next，所以在前面要做个判断ifself.is_empty():self.__head=nodeelse:cur=self.__headwhilecur.next!=None:cur=cur.nextcur.next=nodepabxs在线性表两个数据元素a和b间插入x，已知p指向as.next=p.nextp.next=s‘’‘指定位置添加元素'''definsert(self,pos,item):'''指定位置添加元素'''ifpos<=0:#如果pos位置在0，当做头插法self.add(item)elifpos>self.length()-1:#如果pos位置比原链表长，那么都当做尾插法来做self.append(item)else:per=self.__headcount=0whilecount<pos-1:count+=1per=per.next#当循环退出后，pre指向pos-1位置node=Node(item)node.next=per.nextper.next=nodeai-1aiai+1算法思路：········ep①③④q②New单链表基本操作——删除结点ai-1aiai+1算法思路：········p①q②③④‘’‘删除节点'''defremove(self,item):'''删除节点'''cur=self.__headpre=Nonewhilecur!=None:ifcur.elem==item:#先判断该节点是否是头结点ifcur==self.__head:self.__head=cur.nextelse:pre.next=cur.nextbreakelse:pre=curcur=cur.next

改进链表的设置：单链表的表长是一个隐含的值；在单链表的最后一个元素之后插入元素时，需遍历整个链表；在链表中，元素的“位序”概念淡化，结点的“位置”概念加强。增加“表长”、“表尾指针”和“当前位置的指针”三个数据域；将基本操作中的“位序i”改变为“指针p”。存在的问题及解决方案

存在的问题：循环链表基本操作同线性链表，区别在于判别链表中最后一个结点的条件是“后继是否为头结点”特点：最后一个结点的指针指向头结点，整个链表构成了一个封闭的环。a1a2an····空表：Head非空表：Head双向链表特点：每个结点的指针域里包含两个指针，其中一个指向前驱结点，另外一个指向后继结点。a1a2^an^····空表：^^Head非空表：Head顺序表与链表的比较顺序是用数组实现的，而链表是用指针或“游标”来实现的。顺序表的存储空间是静态分配的，而算法的执行前必须明确的规定其存储规模；链表的存储空间是动态分配的。当线性表的长度变化较大或问题规模难以确定时，采用动态链表较好。对于顺序表，可随机访问任一个元素，而在单链表中,需要顺着链逐个进行查找，因此单链表适合于在成批地,顺序地处理线性表中的元素时采用。在单链表里进行插入、删除运算比在顺序表里容易得多。双链表predatanext双链表（DoublyLinkedList）比单链表增加了一个指针域。双链表的每个节点元素包含三个部分：数据域（用于存储节点的数据）、前驱指针（指向前一个节点）和后继指针（指向后一个节点），

一元多项式的加法一元多项式anxn+an-1xn-1+…+a1x+a0的数据结构的实现具有如下3种方法：方法1：采用顺序存储结构，第i个位置存储指数为i的系数ai；方法2：采用顺序存储结构存储一元多项式的所有系数非零项及其指数(ai,i)；方法3：采用链式存储结构存储一元多项式的所有系数非零项及其指数。本题采用单链表存储一元多项式的系数和指数，并且将指数按照递减顺序排列，实现一元多项式的初始化，判空，插入，显示和加法操作。舞蹈链

舞蹈链（DancingLinks）是一种数据结构，用于解决精确覆盖问题。精确覆盖问题是指在一个矩阵中选出一些行，使得这些行的并集恰好等于一个全集，且每列恰好被选中一次。采用十字链表存储舞蹈链的数据，完成舞蹈链的快速删除矩阵的某一行的功能。最大子序列和在整数数组中寻找一个具有最大和的连续子数组（至少包含一个元素），返回其最大和。输入格式：第一行输入一个整数n，表示数组的长度。第二行输入n个整数，表示数组中的元素。输出格式：输出一个整数，表示最大子数组的和。输入样例：6-23-83-12输出样例：7样例解释：最大子数组为[6-23]，和为7。链表合并

给定两个升序链表，将它们合并为一个新的升序链表。新链表通过拼接给定的两个链表的结点来完成。线性表在AI中应用（1）数据预处理在AI中，线性表可以用于存储和处理原始数据。例如，在图像识别中，图像的像素值可以存储在一个线性表。这些像素值需要进行预处理，如归一化处理，线性表方便对每个像素值进行遍历和修改操作。（2）模型训练数据管理在机器学习和深度学习的模型训练过程中，训练数据集通常可以用线性表的结构来管理。例如，监督学习中的样本数据集可以看作是一个线性表，其中每个元素是一个样本，样本又包含特征向量（可以看作是一个子线性表）和对应的标签。像线性回归模型的训练数据，这里的数据集就是一个线性表结构，方便对样本进行批量处理或者随机访问，以进行梯度下降等优化算法。（3）算法实现辅助结构许多AI算法在实现过程中会用到线性表作为辅助的数据结构。例如，在搜索算法（如广度优先搜索）中，用于存储待搜索的节点队列。广度优先搜索算法在图数据结构中搜索从起始节点到目标节点的最短路径，通过队列来存储待扩展的节点，按照层次依次搜索，其中队列这种线性表结构保证了搜索的顺序性。

AI对线性表的影响

（1）新的数据处理需求促使线性表优化随着AI处理的数据量越来越大、数据类型越来越复杂，对线性表的存储和操作效率提出了更高的要求。例如，在处理大规模文本数据时，需要高效地存储和检索文本中的单词序列（可以用线性表表示），这促使了对线性表存储结构的优化，如采用更紧凑的存储方式或者分布式存储来适应大数据场景。（2）启发新的线性表相关算法AI中的一些算法思想也启发了线性表相关的新算法。例如，借鉴神经网络中的梯度下降思想，可以用于优化线性表上某些操作的性能。假设要在一个很长的线性表中找到某个满足特定条件的元素，并且每次比较元素都有一定的“成本”，可以通过类似梯度下降的策略，根据比较结果来动态调整搜索的“步长”，以更快地找到目标元素。

队列

周元哲

队列是一种操作受限制的特殊线性表，特殊性只允许在线性表的一端(队尾)进行插入(入队列)，而在另一端(队头)进行删除(出队列)

。1.基本概念

元素入队列的顺序与出队列的顺序相同，即先进先出(FIFO)。a1a2a3…an入队列出队列队头队尾队列类型的实现链队列——链式映象循环队列——顺序映象a1∧an…Q.frontQ.rearQ.frontQ.rear∧空队列LinkedQueueQ链队列逻辑结构示意图1）入队将值为X的元素插入队尾。

2）出队删去队头元素并返回该元素。

2.链队列的插入和删除运算classQueue(object):def__init__(self):self.items=[]defis_empty(self):#判断队列是否为空returnself.items==[]defenqueue(self,item):#入队列self.items.insert(0,item)defdequeue(self):#出队列returnself.items.pop()defsize(self):#队列元素个数returnlen(self.items)77队空条件：rear=front队满：rear-front=maxsize012345ABCrearDEGrearfrontrearfrontfrontrearfront01234567ABCDEFGH队满条件：rear=front队空条件：rear=front如何区分队空与队满呢？循环队列的队空和队满判断问题循环队列的元素个数为：

(q.rear-q.front+maxsize)%maxsize队满条件：（rear+1)mod

maxsize=front队空条件：

rear=front循环队列的队空和队满判断问题01234567ABCDEFGrear解决方法1：少用一个存储单元队满条件：

rear==front&&tag==1队空条件：

rear==front&&tag==0解决方法2：设置一个标志位假设标志位tag，初值＝0

当入队列操作成功，tag=1;当出队列操作成功，tag=0;队满条件：

count==maxsize队空条件：

count==0解决方法3：设置一个计数器假设计数器count，初值＝0

当入队列操作成功，count+1;当出队列操作成功，count-1;这样，count不仅具有计数功能，而且可以起到标识作用周元哲栈栈与队列的逻辑特征：

从数据结构角度讲，栈与队列也是线性表，不同之处在于其操作的特殊性（栈为LIFO，队列为FIFO），为操作受限的线性表。

从数据类型角度讲，栈与队列是与线性表不同的重要抽象数据类型，广泛的应用于各类软件系统中。1.基本概念定义：栈(Stack)是限定仅在表尾进行插入或删除操作的线性表。an...a2a1

栈顶

Top

栈底

Bottom栈顶（Top）—表尾元素，允许插入和删除的一端。栈底（Bottom)—表头元素，不允许插入和删除的一端。空栈—表中没有元素。2.栈的基本特征栈——后进先出(LIFO，LastInFirstOut)。故栈又称为后进先出的线性表。an...a2a1入栈出栈栈顶栈底入栈(PUSH)---最先插入的元素放在栈的底部。出栈(POP)---最后插入的元素最先出栈。

栈的实现——顺序栈

——链栈2.顺序栈：栈顶指针与栈中元素间关系3210BAtopC出栈top=-1，B、A出栈32103210空栈top=-13210AA进栈top3210CBAtopB,C依次进栈〖例〗设有一个空栈，栈顶指针为1000H，现有输入序列为12345,PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH后,输出序列为___,栈顶指针为______〖例〗在一个n个单元的顺序栈中，假定以地址高端(下标为n的单元)作为栈底，以top作为栈顶指针，则向栈中压入一个元素时，top的变化是______top不变top=ntop=top-1 top=top+1〖例〗若一个栈的输入序列是1，2，…，n，输出序列的第一个元素是n，则第i个输出元素是______n-i n-i+1 i n-i-12,31003H3.顺序栈的基本操作特点下溢：栈空时再做退栈运算将产生溢出。1）栈底位置固定在向量的低端，即S->elem[0]----表示栈底元素2）入栈：S->top++

，保存元素；3）出栈：取元素，S->top--；4）空栈：S->top=-1；5）栈满：S->top=Stack_Size-1；上溢：栈满时再做进栈运算（一种出错状态，应设法避免）。classStack(object):def__init__(self):#初始化self.items=[]defis_empty(self):#判断栈是否为空returnself.items==[]defpush(self,item):#加入元素self.items.append(item)defpop(self):#弹出元素returnself.items.pop()defpeek(self):#返回栈顶元素returnself.items[len(self.items)-1]defsize(self):#返回栈的大小returnlen(self.items)注意:链栈中指针的方向8.链栈的基本概念anan-1^a1····栈顶指针链栈的特点插入和删除（进栈/退栈）仅能在表头位置上（栈顶）进行。链栈中的结点是动态产生的，可不考虑上溢问题。不需附加头结点，栈顶指针就是链表（即链栈）的头指针。11.链栈的基本操作特点栈底位置固定链表的末尾p->next=NULL----表示栈底元素入栈：用入栈元素建立新结点，并将其插入到链表的第一个结点之前（头插法）；出栈：取出链表第一个结点的元素，并将其第一个结点从链表中删除；空栈：S=NULL；假设在表达式中 （［］（））或［（［］［］）］等为正确的格式， ［（］）或（［（））或（（）］)均为不正确的格式。则检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。例.括号匹配的检验分析可能出现的不匹配的情况:到来的右括弧并非是所“期待”的；到来的是“不速之客”；直到结束，也没有到来所“期待”的括弧。例如：考虑下列括号序列：

[([][])]12345678栈与递归过程2.递归应用：1)阶乘函数2)斐波纳契数列(Fibonacci函数)递归算法的两个基本特征递推归纳将问题转化为比原问题小的同类规模，归纳出一般递推公式.

故所处理的对象要有规律地递增或递减递归终止当规模小到一定的程度应该结束递归调用,逐层返回常用条件语句来控制何时结束递归例求递归方法求n的阶乘总结执行过程（两个阶段）第一阶段：逐层调用，调用函数自身第二阶段：逐层返回，返回到调用该层的位置继续执行后递归调用是多重嵌套调用的一种特殊情况调用的深度：调用的层数设计递归算法的方法前提：原问题可以层层分解为类似的子问题，且子问题比原问题规模更小规模最小的问题具有直接解方法：寻找分解方法：将原问题转化为子问题求解，例：n!=n*(n-1)!设计递归出口：根据规模最小的子问题确定递归终止条件，例：求解n!，当n＝0时，n!＝1；2.递归应用示例——汉诺(hanoi)问题n阶Hanoi塔问题：假设有三个分别命名为X,Y,Z的塔座，在塔座X上插有n个直径大小各不相同、依小到大的编号为1,2,3,…,n的圆盘。现要求将X轴上的n个盘移到至塔座Z上并保持同样顺序叠排，移动圆盘时必须遵守以下规则：（1）每次只能移动一个圆盘；（2）圆盘可以插在X,Y,Z任意一个塔座上；（3）任何时候都不能将一个较大的圆盘放到较小的圆盘之上。

将A塔上的红、黄两盘移动到B上蓝盘放到C上将红、黄两盘从B移动到C盘上。（完成）ABC问题分析：n=1时，直接将其从A－>C；n>1时，只要先将前n-1个借助C从A－>B,那么可以把第n个直接从A－>C;3.如何将剩下的n-1个圆盘遵守规则借助A从B－>C，问题性质同（2）;问题性质相同，因此适合采用递归过程！若将n个盘片按规定从A塔移至C塔，移动步骤可分为三步：把A塔上的n-1个盘片借助C移动到B塔把第n个盘片从A塔移至C塔把B塔上的n-1个盘片借助A塔移至C塔算法用函数hanoi(n,x,y,z)以递归算法实现盘片数源塔借用塔目标塔

递归终止：当递归调用到盘片数为1时算法描述：1)递归调用hanoi(n-1,a,c,b);2)将n号盘片从a塔移动到c塔；3)递归调用hanoi(n-1,b,a,c)。将所有的实在参数、返回地址等信息传递给被调用函数保存；为被调用函数的局部变量分配存储区；将控制转移到被调用函数的入口。3.函数调用实现内幕

当在一个函数的运行期间调用另一个函数时，在运行该被调用函数之前，需先完成三项任务：保存被调函数的计算结果；释放被调函数的数据区；依照被调函数保存的返回地址将控制转移到调用函数。从被调用函数返回调用函数之前，应该完成下列三项任务：递归工作栈：递归过程执行过程中占用的数据区。递归工作记录：每一层的递归参数合成一个记录。当前活动记录：栈顶记录指示当前层的执行情况。当前环境指针：递归工作栈的栈顶指针。递归函数执行的过程可视为同一函数进行嵌套调用，例如：栈小结栈是一种操作受限制的特殊线性表，特殊性在于插入(入栈)和删除(出栈)操作只能在线性表的一端进行(栈顶)，线性表的另外一端固定不变(栈底)。操作的特殊性造就了元素入栈的顺序与出栈的顺序相反，即后进先出(LIFO)。同线性表一样，栈也有两种存储方式：顺序栈与链栈。顺序栈有发生上溢的可能，而链栈通常不会发生栈满（除非整个空间均被占满）只要满足LIFO原则，均可采用栈结构。第5章串串串是由零个或多个字符组成的有限序列 s=“a1a2…an”(n

0，串长度)子串：串中任意个连续的字符组成的子序列。主串：包含子串的串相应地称为主串。位置：字符在序列中的序号。子串在主串中的位置则以子串的第一个字符在主串中的位置来表示。相等：两个串的长度相等，并且对应位置的字符都相等。长度：字符个数空串：string=""，长度为0空格串：stringBlank="",仅含一个空格，长度为1字串：串中任何连续字符组成主串：包含子串b的串，称为b的主串真子串：串的所有字串，除了自身以外字串的位置：子串中第一个字符的位置串相等：长度和位置相等110创建串

defCreateString(self):#创建串stringSH=input("请输入字符串：")iflen(stringSH)>self.MaxStringSize:print("溢出，超过的部分无法保存")self.chars=stringSH[:self.MaxStringSize]else:self.chars=stringSH111串连接defStringConcat(self,strSrc):#串连接lengthSrc=len(strSrc)stringSrc=strSrciflengthSrc+len(self.chars)<=self.MaxStringSize:self.chars=self.chars+stringSrcelse:print("两个字符的长度之和溢出，超过的部分无法显示")size=self.MaxStringSize-len(self.chars)self.chars=self.chars+stringSrc[:size]print("连接后字符串为：",self.chars)112取长度为length的子串defSubString(self,iPos,length):#从iPos位置开始，取长度为length的子串ifiPos>len(self.chars)-1oriPos<0orlength<1or(length+iPos)>len(self.chars):print("无法获取")else:substr=self.chars[iPos:iPos+length]print("获取的字串为：",substr)113说明：串的逻辑结构和线性表极为相似，区别仅在于串的数据对象约束为字符集。串的基本操作和线性表有很大差别。在线性表的基本操作中，大多以“单个元素”作为操作对象；在串的基本操作中，通常以“串的整体”作为操作对象。

串的模式匹配算法串匹配(查找)的定义:StrInex(S,pos,T)初始条件：主串S和T存在，T是非空串并且1≤pos≤Length(S)。

操作结果：若主串S中存在和串T值相同的子串,则返回它在主串S中从第

pos个字符开始第一次出现的位置；

否则函数值为0。

一、简单匹配算法（Brute-Force）二、首尾匹配算法三、KMP(D.E.Knuth,V.R.Pratt,J.H.Morris)算法1.简单匹配算法的思路：依次将主串S中长度和模式t相同的子串与模式进行比较，直到找到相同的子串为止。如果存在相同的子串，则匹配成功，返回子串在主串S中的位置pos。 否则匹配不成功。子串与模式的比较策略：从前到后依次进行比较。第一趟匹配ababcabcacbababcac第二趟匹配ababcabcacbababcac第三趟匹配ababcabcacbababcac第四趟匹配ababcabcacbababcac第五趟匹配ababcabcacbababcac第六趟匹配ababcabcacbababcac1.简单匹配算法的匹配实例：首尾匹配算法的思路：1)依次将主串S中长度和模式t相同的子串与模式进行比较，直到找到相同的子串为止。2)如果存在相同的子串，则匹配成功，返回子串在主串S中的位置pos。 否则匹配不成功。3)子串与模式的比较策略：先比较模式串的第一个字符,再比较模式串的最后一个字符，最后比较模式串中从第二个到第n-1个字符。

KMP为(D.E.Knuth与V.R.Pratt和J.H.Morris)同时发现的算法，因此人们称之为克努特－莫里斯－普拉特算法。

特点是在匹配的过程中，不需要回溯主串的指针i，且时间复杂度可以达到O(m+n)。3.KMP算法基本概念：前缀与后缀设A为字母表，X=x1...xn，是在A上的长度为n的一个字符串。

X的前缀(prefix)是一个子串uu

=

x1...xb|

这里

b

{1,

...,n}就是说x开始于u。

X的后缀(suffix)是一个子串uu

=

xn-b...xn|

这里

b

{1,

...,

n}就是说x结束于u。若b<n，则相应u分别称为真前缀（真后缀）

设X=abacab。X的真前缀是

,a,ab,aba,abac,abacaX的真后缀是

,b,ab,cab,acab,bacab基本概念：前缀与后缀举例第一趟匹配ababcabcacbababcac第二趟匹配ababcabcacbababcac第三趟匹配ababcabcacbababcac第四趟匹配ababcabcacbababcac第五趟匹配ababcabcacbababcac第六趟匹配ababcabcacbababcac简单匹配算法的情况：第一趟匹配第二趟匹配第三趟匹配ababcabcacbabababcabcacbabababcabcacbababcacabcac(a)bcac改进后的匹配情况：123456789123456789123456789词法分析表达式“3+4*2“看作一个字符串。通过遍历这个字符串，当遇到数字字符时，使用一个内部循环来提取完整的数字（操作数）作为一个单词存入tokens列表中；当遇到非数字字符（操作符）时，直接将其作为一个单词存入tokens列表。最终，tokens列表包含了这个表达式的所有单词，类似于编译器词法分析的结果。126字串统计字串统计:给定一个长度为n的字符串S，还有一个数字L，统计长度大于等于L的出现次数最多的子串（不同的出现可以相交），如果有多个，输出最长的，如果仍然有多个，输出第一次出现最早的。输入格式第一行一个数字L。

第二行是字符串S。（L大于0，且不超过S的长度。）输出格式一行，题目要求的字符串。数据规模和约定n<=60

S中所有字符都是小写英文字母。

127串在AI中应用（1）串在自然语言处理（NLP）领域有如下应用：1)文本预处理：在NLP的几乎所有任务开始之前，都需要对文本进行预处理。串的操作在这里起到关键作用。例如，将文本分割成单词（或词素）的过程，其实就是把一个长串按照空格或其他分隔符拆分成多个子串。以句子为例，通过串的分割操作可以得到单词串。2）文本特征提取：串可以用于提取文本的一些基本特征。比如，统计某个单词（串）在一篇文档中的出现频率，这对于文本分类等任务很有帮助。将一篇新闻文章看作是一个长串，统计其中关键词的出现次数，可以作为判断文章所属领域的一个依据。3）文本相似度计算：在信息检索、问答系统等应用中，需要计算文本之间的相似度。串的比较操作可以作为基础来构建更复杂的相似度计算方法。例如，通过比较两篇文章中相同单词（串）的比例，或者使用编辑距离（一种衡量两个串差异程度的度量）来判断它们的相似程度。编辑距离是指将一个串转换成另一个串所需的最少插入、删除和替换操作的次数。例如，“kitten”和“sitting”的编辑距离是3。

128串在AI中应用（2）知识图谱构建与维护在知识图谱中，实体和关系通常以字符串的形式表示。例如，“爱因斯坦”是一个实体串，“发现相对论”是一个关系串。对这些串进行处理，包括实体识别（从文本中识别出代表实体的串）、关系抽取（从文本中抽取表示关系的串）等操作，是构建和维护知识图谱的重要步骤。在知识图谱的查询过程中，串的匹配操作用于查找相关的实体和关系，比如用户输入一个查询串“爱因斯坦的科学成就”，系统需要在知识图谱中找到与这个串匹配的实体和关系，以提供准确的答案。129

第7章树和二叉树树非线性结构是指至少存在一个数据元素有两个或两个以上的直接后继（或直接前驱）的数据结构，例如树和图。树中的每个节点有唯一的直接前驱，但可以有多个直接后继，而图中的每个节点可以有多个直接前驱，也可以有多个直接后继。树通常用于描述一对多的逻辑关系，而图通常用于描述多对多的逻辑关系为了简便起见，给树定义了下列相关术语节点(Node)：表示树中的数据元素，由数据项和数据元素之间的关系组成。节点的度(DegreeofNode)：节点拥有子树的个数树的度(DegreeofTree)：树中各节点度的最大值。131树叶子节点(LeafNode)：度为0的节点。孩子(Child)：节点子树的根。双亲(Parent)：节点的上层节点叫该节点的双亲。兄弟(Brother)：同一双亲的孩子。节点的层次(LevelofNode)：从根节点到树中某节点所经路径上的分支数称为该节点的层次。根节点的层次规定为1，其余节点的层次等于其双亲节点的层次加1。树的深度(DepthofTree)：树中节点的最大层次数。无序树(UnorderedTree)：树中任意一个节点的各孩子节点之间的次序构成无关紧要的树。通常树指无序树。有序树(OrderedTree)：树中任意一个节点的各孩子节点有严格排列次序的树。二叉树是有序树，因为二叉树中每个孩子节点都确切定义为该节点的左孩子或者右孩子。森林(Forest)：m(m≥0)棵树的集合。自然界中的树和森林的概念差别很大，但在数据结构中树和森林的概念差别很小。从定义可知，一棵树有根节点和m个子树构成，若把树的根节点删除，则树变成了包含m棵树的森林。根据定义，一棵树也可以称为森林。132二叉树所谓二叉树（BinaryTree）是一种有限元素的集合，该集合或者为空、或者由一个称为根(root)的元素及两个不相交的左子树和右子树的二叉树组成当集合为空时，称该二叉树为空二叉树。在非空情况下二叉树的左右子树是有序的，即若将其左、右子树颠倒，就成为另一棵不同的二叉树，即使树中节点只有一棵子树，也要区分它是左子树还是右子树。归纳来讲，二叉树具有四种基本形态，分别是：空树、只有左子树、只有右子树、同时有左右子树133满二叉树和完全二叉树在二叉树中，有两种较为特殊的二叉树：满二叉树：在一棵二叉树中，如果所有分支节点都存在左子树和右子树，并且所有叶子节点都在同一层上，这样的一棵二叉树称作满二叉树。完全二叉树。一棵深度为k的有n个节点的二叉树，对树中的节点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的节点与满二叉树中编号为i的节点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。在完全二叉树中，叶子节点只能出现在最下层和次下层，且最下层的叶子节点集中在树的左部。一棵满二叉树必定是一棵完全二叉树，而完全二叉树未必是满二叉树。134二叉树的性质性质1

：二叉树第i层上的节点数目最多为2i-1(i≥1)。【证明】：数学归纳法证明。归纳基础：i=1时，有2i-1=20=1。因为第1层上只有一个根节点，所以命题成立。归纳假设：假设对所有的j(1≤j<i)命题成立，即第j层上至多有2j-1个节点，证明j=i时命题亦成立。归纳步骤：根据归纳假设，第i-1层上至多有2i-2个节点。由于二叉树的每个节点至多有两个孩子，故第i层上的节点数至多是第i-1层上的最大节点数的2倍。即j=i时，该层上至多有2×2i-2=2i-1个节点，故命题成立。135二叉树的性质性质2：

深度为k的二叉树至多有2k-1个节点(k≥1)。【证明】：在具有相同深度的二叉树中，仅当每一层都含有最大节点数时，其树中节点数最多。因此利用性质1可得，深度为k的二叉树的节点数至多为：

20+21+…+2k-1=2k-1

故命题正确。136二叉树的性质性质3：

在任意-棵二叉树中，若终端节点的个数为n0，度为2的节点数为n2，则no=n2+1。【证明】：因为二叉树中所有节点的度数均不大于2，所以节点总数(记为n)应等于0度节点数、1度节点(记为n1)和2度节点数之和：

n=no+n1+n2

另一方面，1度节点有一个孩子，2度节点有两个孩子，故二叉树中孩子节点总数是：

nl+2n2树中只有根节点不是任何节点的孩子，故二叉树中的节点总数又可表示为：

n=n1+2n2+1由式子1和式子2得到：no=n2+1137二叉树存储1．顺序存储二叉树的顺序存储是使用一维数组存储二叉树中的节点。通过节点的存储位置，也就是数组的下标体现节点之间的逻辑关系，比如双亲与孩子的关系，左右兄弟的关系等。由于顺序存储会导致大量的空间浪费，例如一棵深度为k的右斜树，它只有k个节点，却需要分配2k-1个存储单元空间，所以，顺序存储结构往往只适用于完全二叉树。138二叉树存储2．链式存储根据二叉树每个节点最多有两个孩子的特性，链式存储采用一个数据域和两个指针域的节点形式来存储二叉树。data是数据域，lchild和rchild分别是指向左孩子和右孩子的指针域。链式存储的二叉树又称为二叉链表139二叉树遍历1．遍历的类型遍历是对树的所有节点进行访问且仅访问一次。按照访问时根节点出现的顺序，遍历分为先序遍历、中序遍历和后序遍历三种形式，遍历顺序如下：前序遍历：根节点->左子树->右子树中序遍历：左子树->根节点->右子树后序遍历：左子树->右子树->根节点各种遍历算法的结果为：

先序遍历：abdefgc；中序遍历：debgfac；后序遍历：edgfbca。140二叉树遍历2.遍历的递归实现a)先序遍历基本流程为：若二叉树为空，则空操作，否则，访问根节点；先序访问左子树；先序访问右子树。【先序遍历递归代码】defPreOrder(self,root):ifroot==None:returnprintroot.elemself.PreOrder(root.lchild)#先序遍历左子树self.PreOrder(root.rchild)#先序遍历右子树

141二叉树遍历b)中序遍历基本流程为：若二叉树为空，则空操作，否则，中序访问左子树；访问根节点；中序访问右子树。【中序遍历递归代码】defInOrder(self,root):ifroot==None:returnself.InOrder(root.lchild)#先序遍历左子树printroot.elemself.InOrder(root.rchild)#先序遍历右子树142

二叉树遍历

c)后序遍历基本流程为：若二叉树为空，则空操作，否则，后序访问左子树；访问根节点；后序访问右子树。【后序遍历递归代码】defPostOrder(self,root):ifroot==None:returnself.PostOrder(root.lchild)#先序遍历左子树self.PostOrder(root.rchild)#先序遍历右子树printroot.elem143二叉树创建【二叉树创建代码】defcreateBiTree(self,root):data=input()ifdatais“#”:#如果当前元素为‘#’,则认为其为NonereturnNoneelse:root.data=dataroot.lchild=self.createBiTree(root.lchild)

//构造左子树

root.rchild=self.createBiTree(root.rchild)

//构造右子树returnroot144哈夫曼编码哈夫曼树

在电文传输中，需要将电文中出现的每个字符进行二进制编码和译码。编码是指用不同的0/1序列代表不同的字符。译码是指将已编了码的信息还原成原来的形式。

在设计编码时需要遵守两个原则：（1）要能唯一地译码。（2）编码长度要尽量短。146

编码

等长编码不等长编码。147等长编码假设字符集只