数据结构（Python版）PPT完整全套教学课件

绪论第1章数据结构（Python版）第1章绪论.ppt第2章线性表.ppt第3章栈和队列.ppt第4章串、数组和广义表.ppt第5章树和2叉树.ppt第6章图.ppt第7章查找.ppt第8章排序.ppt全套PPT课件编程基础为什么要学习数据结构计算机及相关专业考研考博课程计算机等级考试课程程序员考试课程课程学习指导提前预习、认真听课、按时完成书面及上机作业课程特点：内容抽象、概念性强、内容灵活、不易掌握01020304注意先修课程的知识准备离散数学、Python语言注意循序渐进：基本概念、基本思想、基本步骤、算法设计注意培养算法设计的能力理解所讲算法、对此多做思考：若问题要求不同，应如何选择数据结构，设计有效的算法平时成绩:40%考核方式12期末成绩:60%(闭卷笔试)了解数据结构研究的主要内容掌握算法的时间、空间复杂度及其分析的简易方法01OPTION02OPTION03OPTIONtarget目标掌握数据结构中涉及的基本概念目录导航1.11.21.31.4数据结构的研究内容基本概念和术语抽象数据类型的表示与实现算法与算法分析Contents

N.沃思（NiklausWirth)教授提出：数据结构的研究内容程序=算法+数据结构

电子计算机的主要用途：早期：主要用于数值计算后来：处理逐渐扩大到非数值计算领域，能处理多种复杂的具有一定结构关系的数据书目自动检索系统登录号：书名：作者名：分类号：出版单位：出版时间：价格：书目卡片书目文件按书名按作者名按分类号索引表线性表人机对奕问题树……..……..…...…...…...….../(root)binlibuseretcmathdsswyintaoxieStack.cppQueue.cppTree.cpp文件系统的系统结构图树多叉路口交通灯管理问题CEDABABACADBABCBDDADBDCEAEBECED图顶点：一条通路连线：不能同时通行染色：有连线的两个顶点不能具有相同颜色设计出合适的数据结构及相应的算法即：首先要考虑对相关的各种信息如何表示、组织和存储？求解非数值计算的问题：数据结构的研究内容为：研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作。形成阶段：60年代初期，“数据结构”有关的内容散见于操作系统、编译原理和表处理语言等课程。1968年，“数据结构”被列入美国一些大学计算机科学系的教学计划。数据结构课程的形成和发展：发展阶段：数据结构的概念不断扩充，包括了网络、集合代数论、关系等“离散数学结构”的内容。70年代后期，我国高校陆续开设该课程。介于数学、计算机硬件和计算机软件三者之间的一门核心课程《数据结构》所处的地位：数据结构在计算机学科中的地位能够分析研究计算机加工的对象的特性，获得其逻辑结构，根据需求，选择合适存贮结构及其相应的算法；课程目的学习一些常用的算法；复杂程序设计的训练过程，要求编写的程序结构清楚和正确易读；初步掌握算法的时间分析和空间分析技术目录导航1.11.21.31.4数据结构的研究内容基本概念和术语抽象数据类型的表示与实现算法与算法分析Contents三者之间的关系：数据>数据元素>数据项例：学生表>个人记录>学号、姓名……基本概念和术语所有能输入到计算机中去的描述客观事物的符号。数值性数据非数值性数据（多媒体信息处理）有独立含义的数据最小单位，也称域(field)数据的基本单位，也称结点（node）或记录（record）1.数据（data)3、数据项（dataitem）2、数据元素

（dataelement）整数数据对象N={0,1,2,…}基本概念和术语学生数据对象学生记录的集合4、数据对象(DataObject)：相同特性数据元素的集合，是数据的一个子集数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。5、数据结构（DataStructure）是相互之间存在一种或多种特定关系的数据元素的集合。数据结构的两个层次：基本概念和术语逻辑结构存储结构（物理结构）划分方法一逻辑结构

线性结构----有且仅有一个开始和一个终端结点

，并且所有结点都最多只有一个直

接前趋和一个后继。例如：线性表、栈、队列、串

非线性结构----

一个结点可能有多个直接前趋和直

接后继。例如：树、图02OPTION01OPTION线性结构一个对一个，如线性表、栈、队列树形结构一个对多个，如树集合数据元素间除“同属于一个集合”外，无其它关系图形结构多个对多个，如图逻辑结构划分方法二存储结构顺序存储结构借助元素在存储器中的相对位置来表示数据元素间的逻辑关系。1链式存储结构借助指示元素存储地址的指针表示数据元素间的逻辑关系。3存储结构分为：元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储内容Loc(元素i)=Lo+（i-1)*m顺序存储1536元素21400元素11346元素3∧元素41345h

链式存储h存储地址存储内容指针1345

元素114001346

元素4∧…….……..…….

1400

元素2

1536…….……..…….1536

元素31346逻辑结构和存储结构都相同,但运算不同,则数据结构不同.例如,栈与队列数据的运算1234插入查找删除修改排序5对于一种数据结构,常见的运算

数据的逻辑结构

数据的存储结构数据的运算：插入、删除、修改、查找、排序

线性结构

非线性结构

顺序存储

链式存储线性表树形结构图形结构逻辑结构唯一存储结构不唯一运算的实现依赖于存储结构栈、队列串、数组抽象数据类型(ADTs:AbstractDataTypes)更高层次的数据抽象。由用户定义，用以表示应用问题的数据模型。由基本的数据类型组成,并包括一组相关的操作。抽象数据类型抽象数据类型可以用以下的三元组来表示：

ADT=（D，S，P）数据对象D上的关系集D上的操作集ADT抽象数据类型名：

数据对象：<数据对象的定义>

数据关系：<数据关系的定义>

基本操作：<基本操作的定义>ADT常用定义格式抽象数据类型抽象数据类型查找插入删除修改线性表接口或用户界面数据类型的物理实现封装信息隐蔽和数据封装，使用与实现相分离目录导航1.11.21.31.4数据结构的研究内容基本概念和术语抽象数据类型的表示与实现算法与算法分析Contents（4）内存的动态分配与释放

（5）赋值语句（6）选择语句（7）循环语句抽象数据类型的表示与实现（8）使用的结束语句形式有：函数结束语句return循环结束语句break（9）输入输出语句形式有：输入语句input()输出语句output()（10）扩展函数有：求最大值max求最小值min抽象数据类型的表示与实现目录导航1.11.21.31.4数据结构的研究内容基本概念和术语抽象数据类型的表示与实现算法与算法分析Contents算法和算法分析0102一个有穷的指令集，这些指令为解决某一特定任务规定了一个运算序列算法定义算法的描述自然语言流程图程序设计语言伪码算法的特性：算法和算法分析12345输入

有0个或多个输入输出有一个或多个输出(处理结果)确定性每步定义都是确切、无歧义的有穷性算法应在执行有穷步后结束有效性每一条运算应足够基本算法的评价:正确性算法和算法分析可读性健壮性高效性（时间代价和空间代价）算法的效率的度量算法效率：用依据该算法编制的程序在计算机上执行所消耗

的时间来度量 算法和算法分析事后统计事前分析估计算法和算法分析1.事后统计：利用计算机内的计时功能，不同算法的程序可以用一组或多组相同的统计数据区分缺点必须先运行依据算法编制的程序所得时间统计量依赖于硬件、软件等环境因素，掩盖算法本身的优劣2.事前分析估计：一个高级语言程序在计算机上运行所消耗的时间取决于：依据的算法选用何种策略问题的规模程序语言编译程序产生机器代码质量机器执行指令速度同一个算法用不同的语言、不同的编译程序、在不同的计算机上运行，效率均不同，———使用绝对时间单位衡量算法效率不合适算法和算法分析算法中基本语句重复执行的次数是问题规模n的某个函数f(n),算法的时间量度记作：T(n)=O(f(n))

时间复杂度的渐进表示法数学符号“O”的定义为：若T(n)和f(n)是定义在正整数集合上的两个函数，则T(n)

=

O(f(n))表示存在正的常数C和n0，使得当n≥n0时都满足0≤T(n)≤Cf(n)。表示随着n的增大，算法执行的时间的增长率和f(n)的增长率相同，称渐近时间复杂度。n越大算法的执行时间越长排序：n为记录数矩阵：n为矩阵的阶数多项式：n为多项式的项数集合：n为元素个数树：n为树的结点个数图：n为图的顶点数或边数算法中重复执行次数和算法的执行时间成正比的语句对算法运行时间的贡献最大n*n阶矩阵加法：foriinrange(n): forjinrange(n): c[i][j]=a[i][j]+b[i][j];

语句的频度（FrequencyCount):重复执行的次数：n*n; T(n)=O(n2)即：矩阵加法的运算量和问题的规模n的平方是同一个量级时间复杂度的渐进表示法找出语句频度最大的那条语句作为基本语句计算基本语句的频度得到问题规模n的某个函数f(n)取其数量级用符号“O”表示分析算法时间复杂度的基本方法f(n)=n2T(n)=O(n2)例1：N×N矩阵相乘foriinrange(n):forjinrange(n):c[i][j]=0; forkinrange(n):c[i][j]=c[i][j]+a[i][k]*b[k][j] 算法中的基本操作语句为c[i][j]=c[i][j]+a[i][k]*b[k][j];时间复杂度是由嵌套最深层语句的频度决定的例2：for

i

in

range(n):forjinrange(i):forkinrange(j):

x=x+1语句频度=定理1.1若f(n)=amnm+am-1nm-1++a1n+a0是m次多项式，则T(n)=O(nm)。忽略所有低次幂项和最高次幂系数，体现出增长率的含义时间复杂度是由嵌套最深层语句的频度决定的例3：分析以下程序段的时间复杂度

i=1①whilei<=n:

i=i*2②即f(n)≤log2n，取最大值f(n)=log2n所以该程序段的时间复杂度T(n)=O(log2n)时间复杂度是由嵌套最深层语句的频度决定的例4：顺序查找，在数组a[i]中查找值等于e的元素，返回其所在位置。

foriinrange(n):ifa[i]==e: returni+1return0有的情况下，算法中基本操作重复执行的次数还随问题的输入数据集不同而不同最好情况：1次时间复杂度是由嵌套最深层语句的频度决定的123最坏情况：n平均时间复杂度为:O(n)时间复杂度T(n)按数量级递增顺序为：复杂度高复杂度低当n取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊时间复杂度是由嵌套最深层语句的频度决定的空间复杂度:算法所需存储空间的度量，记作:S(n)=O(f(n))其中n为问题的规模(或大小)渐进空间复杂度算法要占据的空间算法本身要占据的空间，输入/输出，指令，常数，变量等算法要使用的辅助空间【算法1】

foriinrange(n/2):

t=a[i]a[i]=a[n-i-1]a[n-i-1]=t

【算法2】

foriinrange(n):b[i]=a[n-i-1]foriinrange(n):a[i]=b[i]

例5：将一维数组a中的n个数逆序存放到原数组中。S(n)=O(n)S(n)=O(1)原地工作渐进空间复杂度1、数据、数据元素、数据项、数据结构等基本概念2、对数据结构的两个层次的理解逻辑结构存储结构3、抽象数据类型的表示方法4、算法、算法的时间复杂度及其分析的简易方法小结互助互利共同进步数据结构（Python版）

线性表第2章数据结构（Python版）第2章线性表第3章栈和队列第4章串、数组和广义表

若结构是非空有限集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。可表示为：（a1,a2,……,an）线性结构的定义：近3周上课内容线性结构（逻辑、存储和运算）线性结构的特点：①只有一个首结点和尾结点；②除首尾结点外，其他结点只有一个直接前驱和一个直接后继。线性结构表达式：（a1,a2,……,an）线性结构包括线性表、堆栈、队列、字符串、数组等等，其中，最典型、最常用的是线性表简言之，线性结构反映结点间的逻辑关系是

一对一的近3周上课内容了解线性结构的特点掌握顺序表的定义、查找、插入和删除掌握链表的定义、创建、查找、插入和删除能够从时间和空间复杂度的角度比较两种存储结构的不同特点及其适用场合01OPTION02OPTION03OPTION04OPTIONtarget目标目录导航2.12.22.32.42.52.62.72.82.9线性表的定义和特点案例引入线性的类型定义线性表的顺序表示和实现线性表的链式表示和实现顺序表和链表的比较线性表的应用案例分析与实现Python标准库中的线性表Contents（a1,a2,…ai-1，ai,ai＋1

，…,an）线性表的定义：用数据元素的有限序列表示n=0时称为数据元素线性起点ai的直接前趋ai的直接后继空表线性终点线性表的定义和特点下标，是元素的序号，表示元素在表中的位置n为元素总个数，即表长分析26个英文字母组成的英文表（A,B,C,D,……,Z）例2分析学生情况登记表数据元素都是记录;元素间关系是线性数据元素都是字母;元素间关系是线性同一线性表中的元素必定具有相同特性学号姓名性别年龄班级041810205于春梅女1804级计算机1班041810260何仕鹏男2004级计算机2班041810284王爽女1904级计算机3班041810360王亚武男1804级计算机4班：：：

：：目录导航2.12.22.32.42.52.62.72.82.9线性表的定义和特点案例引入线性的类型定义线性表的顺序表示和实现线性表的链式表示和实现顺序表和链表的比较线性表的应用案例分析与实现Python标准库中的线性表Contents2.2案例引入案例2.1：一元多项式的运算案例2.2：稀疏多项式的运算案例2.3：表达式求值案例2.4：舞伴问题指数（下标i）01234系数p[i]105-432案例2.1：一元多项式的运算Pn(x)

=

p0

+

p1x

+

p2x2

+

…

+

pnxn线性表P

=

(p0,p1,p2,…,pn)P(x)

=

10

+

5x

-

4x2

+

3x3

+

2x4数组表示（每一项的指数i隐含在其系数pi的序号中）Rn(x)

=

Pn(x)

+

Qm(x)线性表R

=

(p0

+

q0,p1

+

q1,p2

+

q2,…,pm

+

qm,pm+1,…,pn)稀疏多项式S(x)

=

1

+

3x10000

+

2x20000案例2.1：一元多项式的运算下标i0123下标i012系数a[i]7395系数b[i]822-9指数01817指数178多项式非零项的数组表示线性表P

=((p1,e1),(p2,e2),…,(pm,em))案例2.2：稀疏多项式的运算（a）A(x)

=

7

+

3x

+

9x8

+

5x17

（b）(x)

=

8x

+

22x7

−

9x8创建一个新数组c案例2.2：稀疏多项式的运算分别从头遍历比较a和b的每一项指数相同，对应系数相加，若其和不为零，则在c中增加一个新项。指数不相同，则将指数较小的项复制到c中。一个多项式已遍历完毕时，将另一个剩余项依次复制到c中即可A17(x)=7+3x+9x8+5x17B8(x)=8x+22x7-9x8-1703198517-181227-98ABpapb顺序存储结构存在问题存储空间分配不灵活运算的空间复杂度高链式存储结构案例2.2：稀疏多项式的运算多项式相加A17(x)=7+3x+9x8+5x17B8(x)=8x+22x7-9x8-1703198517-181227-98ABpapbA17(x)=7+3x+9x8+5x17B8(x)=8x+22x7-9x8181227-98ABpapb多项式相加A17(x)=7+3x+9x8+5x17B8(x)=8x+22x7-9x8181227-98ABpapb多项式相加A17(x)=7+3x+9x8+5x17B8(x)=8x+22x7-9x8181227-98ABpapb多项式相加（1）查找（2）插入（3）删除（4）修改（5）排序（6）计数案例2.3：图书信息管理系统图书顺序表图书链表案例2.3：图书信息管理系统线性表中数据元素的类型可以为简单类型，也可以为复杂类型。许多实际应用问题所涉的基本操作有很大相似性，不应为每个具体应用单独编写一个程序。从具体应用中抽象出共性的逻辑结构和基本操作（抽象数据类型），然后实现其存储结构和基本操作。总结030102目录导航2.12.22.32.42.52.62.72.82.9线性表的定义和特点案例引入线性的类型定义线性表的顺序表示和实现线性表的链式表示和实现顺序表和链表的比较线性表的应用案例分析与实现Python标准库中的线性表Contents线性表的重要基本操作线性表的类型定义基本操作初始化查找插入取值删除15432目录导航2.12.22.32.42.52.62.72.82.9线性表的定义和特点案例引入线性的类型定义线性表的顺序表示和实现线性表的链式表示和实现顺序表和链表的比较线性表的应用案例分析与实现Python标准库中的线性表Contents线性表的顺序表示又称为顺序存储结构或顺序映像。线性表的顺序表示和实现0102顺序存储定义把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。简言之，逻辑上相邻，物理上也相邻顺序存储方法用一组地址连续的存储单元依次存储线性表的元素，可通过定义数组来实现。max_size=100 #图书表可能达到的最大长度book= #图书信息定义{‘no’:None, #图书ISBN‘name’:None, #图书名字‘price’:None #图书价格}classSqList:

def__init__(self):

self.elem=[None]*max_size

#为顺序表分配一个大小为

max_size的数组空间

self.length=0#空表长度为0图书表的顺序存储结构类型定义线性表的重要基本操作基本操作初始化查找插入取值删除15432初始化线性表classSqList:

def__init__(self):

self.elem=[None]*max_size

#为顺序表分配一个大小为max_size的数组空间

self.length=0#空表长度为0defclear_list(self):

self.length=0补充：几个简单基本操作的算法实现

销毁线性表清空线性表def__len__(self):

returnself.length

销毁线性表求线性表的长度deflist_empty(self):

returnself.length==0判断线性表是否为空线性表的重要基本操作基本操作初始化查找插入取值删除15432def

get_elem(self,i):

#返回顺序表self中的第i个元素

if1<=i<=self.length:

returnself.elem[i-1]

raiseException('位置不合法')取值（根据位置i获取相应位置数据元素的内容）随机存取获取线性表L中的某个数据元素的内容查找（根据指定数据获取数据所在的位置）顺序查找图示253457164809012345data查找

16i253457164809i253457164809i253457164809i查找成功253457164801234data查找50i2534571648i2534571648i2534571648i2534571648i查找失败查找（根据指定数据获取数据所在的位置）查找算法时间效率分析？？？在线性表L中查找值为e的数据元素deflocate_elem(self,e):

#在顺序表中查找值为e的数据元素，返回其序号

fori,eleminenumerate(self.elem[:self.length]):

ifelem==e:

returni+1#查找成功，返回序号i+1

raiseException('元素不存在')查找（根据指定数据获取数据所在的位置）2512478936141234567892512479989361499插入251247893614251247893614251247893614插第4个结点之前，移动6－4+1

次插在第i个结点之前，移动n-i+1

次插入（插在第i个结点之前）判断插入位置i

是否合法。【算法步骤】0102030405判断顺序表的存储空间是否已满。将第n至第i位的元素依次向后移动一个位置，空出第i个位置。将要插入的新元素e放入第i个位置。表长加1，插入成功返回OK。deflist_insert(self,i,e):

#在顺序表中第i个位置插入新的元素e，i值的合法范围是1≤i≤self.length+1

ifi>len(self.elem):#存储空间已满

raiseException('空间已满')

ifi<1ori>self.length+1:

raiseException('位置不合法')

foridxinrange(self.length-1,i-2,-1):

self.elem[idx+1]=self.elem[idx]#插入位置及之后的元素后移

self.elem[i-1]=e#将新元素e放入第i个位置

self.length+=1#表长加1【算法描述】在线性表L中第i个数据元素之前插入数据元素e若插入在尾结点之后，则根本无需移动（特别快）；若元素全部后移（特别慢）；若要考虑在各种位置插入（共n+1种可能）的平均移动次数，该如何计算？算法时间主要耗费在移动元素的操作上【算法分析】251247893614123456789251247361425124736142512473614删除删除（删除第i个结点）删除第4个结点，移动6－4

次删除第i个结点，移动n-i

次【算法步骤】（1）判断删除位置i是否合法（合法值为1≤i≤n）。（2）将欲删除的元素保留在e中。（3）将第i+1至第n位的元素依次向前移动一个位置。（4）表长减1。deflist_delete(self,i):

#删除顺序表中第i个元素

ifi<1ori>self.length:

raiseException('位置不合法')

foridxinrange(i,self.length):

self.elem[idx-1]=self.elem[idx]#被删除元素之后的元素前移

self.length-=1#表长减1【算法描述】将线性表L中第i个数据元素删除若删除尾结点，则根本无需移动（特别快）；若删除首结点，则表中n-1个元素全部前移（特别慢）；若要考虑在各种位置删除（共n种可能）的平均移动次数，该如何计算？算法时间主要耗费在移动元素的操作上【算法分析】123显然，顺序表的空间复杂度S(n)=O(1)（没有占用辅助空间）查找、插入、删除算法的平均时间复杂度为：O(n)顺序表（顺序存储结构）的特点这种存取元素的方法被称为随机存取法利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系，即线性表的逻辑结构与存储结构一致在访问线性表时，可以快速地计算出任何一个数据元素的存储地址。因此可以粗略地认为，访问每个元素所花时间相等

（1）（2）顺序表的优缺点链表为克服这一缺点存储密度大（结点本身所占存储量/结点结构所占存

储量）可以随机存取表中任一元素优点：在插入、删除某一元素时，需要移动大量元素浪费存储空间属于静态存储形式，数据元素的个数不能自由扩充缺点：目录导航2.12.22.32.42.52.62.72.82.9线性表的定义和特点案例引入线性的类型定义线性表的顺序表示和实现线性表的链式表示和实现顺序表和链表的比较线性表的应用案例分析与实现Python标准库中的线性表Contents线性表的链式表示和实现链式存储结构结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻线性表的链式表示又称为非顺序映像或链式映像。如何实现？通过“指针（Python变量）”来实现单链表的存储映像free(a)可利用存储空间a0a2a1a3freefirst(b)经过一段运行后的单链表结构线性表的链式表示和实现各结点由两个域组成：数据域：存储元素数值数据指针域：存储直接后继结点的存储位置指针数据例画出26个英文字母表的链式存储结构aheadb/\z……链式存储结构：逻辑结构：（a,b,…,y,z）与链式存储有关的术语1、结点：数据元素的存储映像。由数据域和指针域两部分组成2、链表：

n个结点由指针链组成一个链表。它是线性表的链式存储映像，称为线性表的链式存储结构43216785a1heada2an……head循环链表示意图：3、单链表、双链表、循环链表：

结点只有一个指针域的链表，称为单链表或线性链表有两个指针域的链表，称为双链表首尾相接的链表称为循环链表与链式存储有关的术语4、头指针、头结点和首元结点头指针是指向链表中第一个结点的指针首元结点是指链表中存储第一个数据元素a1的结点头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息与链式存储有关的术语头指针头结点首元结点a1heada2…infoan^上例链表的逻辑结构示意图有以下两种形式：①ZHAOQIANLISUNZHOUWUZHENG/\WANGH②ZHAOQIANLISUNZHOUWUZHENG/\WANGH区别：①

无头结点②有头结点与链式存储有关的术语讨论1.如何表示空表？有头结点时，当头结点的指针域为空时表示空表非空表 空表0ana0headhead^表头结点第一个结点与链式存储有关的术语讨论2.在链表中设置头结点有什么好处？⒈便于首元结点的处理首元结点的地址保存在头结点的指针域中,所以在链表的第一个位置上的操作和其它位置一致，无须进行特殊处理;⒉便于空表和非空表的统一处理无论链表是否为空，头指针都是指向头结点的非空指针，因此空表和非空表的处理也就统一了。与链式存储有关的术语讨论3.头结点的数据域内装的是什么？

头结点的数据域可以为空，也可存放线性表长度等附加信息，但此结点不能计入链表长度值。头结点的数据域H与链式存储有关的术语结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻链表（链式存储结构）的特点访问时只能通过头指针进入链表，并通过每个结点的指针域向后扫描其余结点，所以寻找第一个结点和最后一个结点所花费的时间不等

这种存取元素的方法被称为顺序存取法01OPTION02OPTION链表的优缺点优点数据元素的个数可以自由扩充插入、删除等操作不必移动数据，只需修改链接指针，修改效率较高缺点存储密度小存取效率不高，必须采用顺序存取，即存取数据元素时，只能按链表的顺序进行访问（顺藤摸瓜）链表的优缺点练习1.链表的每个结点中都恰好包含一个指针。2.顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。3.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。4.线性表若采用链式存储时，结点之间和结点内部的存储空间都是可以不连续的。5.线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型×

单链表的定义和实现非空表空表单链表是由表头唯一确定classLNode:

def__init__(self,data=None):

self.data=data#结点的数据域

self.next=None#结点的指针域

def__str__(self):

returnstr(self.data)单链表的存储结构定义单链表基本操作的实现初始化0102030405取值查找

插入删除基本操作的实现【算法步骤】【算法描述】初始化(构造一个空表)classLinkList:

def__init__(self):

self.head=LNode(None)（1）生成新结点作为头结点并初始化指针域和数据区域为None，头指针head指向头节点pLa1a2…...^pi01p2pn

is

Nonean求表长补充：几个简单基本操作的算法实现“数”结点：指针p依次指向各个结点从第一个元素开始“数”一直“数”到最后一个结点求表长def__iter__(self):

p=self.head

whilepisnotNone:

yieldp

p=p.nextdef__len__(self):

cnt=0

forpinself:

cnt+=1

returncnt–1“数”结点：指针p依次指向各个结点从第一个元素开始“数”一直“数”到最后一个结点补充：几个简单基本操作的算法实现判断表是否为空def

list_empty(self):#若是空表，则返回True，否则返回Falseifself.head.nextisnotNone:

#非空returnFalseelsereturnTrue补充：几个简单基本操作的算法实现线性表的重要基本操作初始化0102030405取值查找

插入删除基本操作的实现思考：顺序表里如何找到第i个元素？链表的查找：要从链表的头指针出发，顺着链域next逐个结点往下搜索，直至搜索到第i个结点为止。因此，链表不是随机存取结构取值（根据位置i获取相应位置数据元素的内容）head211830754256∧pppj123p1i=3i=156p7例：分别取出表中i=3和i=15的元素从第1个结点（head.next）顺链扫描，用指针p指向当前扫描到的结点，p初值p

=

head.next。j做计数器，累计当前扫描过的结点数，j初值为1。当p指向扫描到的下一结点时，计数器j加1。当j

=

i时，p所指的结点就是要找的第i个结点。【算法步骤】线性表的重要基本操作pdefget_elem(self,i):

#在带头结点的单链表中根据序号i获取元素的值

foridx,iteminenumerate(self):#遍历链表

ifidx==i:#当索引等于i时，返回该数据元素

returnitem

raiseException('位置不合法')取值（根据位置i获取相应位置数据元素的内容）查找（根据指定数据获取数据所在的位置）head211830753056∧pj1x=30p2p3找到，返回ix=51p1p6p7未找到，返回0从第一个结点起，依次和e相比较。如果找到一个其值与e相等的数据元素，则返回其在链表中

的“位置”；如果查遍整个链表都没有找到其值和e相等的元素，则返回“None”。#在线性表L中查找值为e的数据元素deflocate_elem(self,e):

#单链表的按值查找，查找成功返回第一个符合的元素，查找失败返回None

forpinself:#遍历当前链表

ifp.data==e:

returnp#当p的值等于e,返回p

returnNone#未找到返回None【算法描述】线性表的重要基本操作将值为x的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间

s.next=p.next;p.next=s思考：步骤1和2能互换么？插入（插在第i个结点之前）

16:39

【算法步骤】找到ai-1存储位置p线性表的重要基本操作01OPTION02OPTION03OPTION新结点s的指针域指向结点ai令结点p的指针域指向新结点s将新结点s的数据域置为x生成一个新结点s04OPTION05OPTION#在L中第i个元素之前插入数据元素e

deflist_insert(self,i,e):

#在带头结点的单链表中第i个位置插入值为e的新结点

foridx,pinenumerate(self):#遍历链表

ifidx+1==i:

s=LNode(e)#生成新结点s并将s的数据域设置为e

s.next=p.next#将结点s的指针域指向结点ai

p.next=s#将结点p的指针域指向结点s

return

raiseException('位置不合法')【算法描述】线性表的重要基本操作（1）找到ai-1存储位置p（2）保存要删除的结点的值（3）令p.next指向ai的直接后继结点（4）释放结点ai的空间删除（删除第i个结点）将表的第i个结点删去步骤：删除（删除第i个结点）p.next=p.next.next???ai-1ai-1aiaiai+1ai+1pq删除前删除后删除（删除第i个结点）【算法步骤】（1）找到ai-1存储位置p（2）临时保存结点ai的地址在q中，以备释放（3）令p.next指向ai的直接后继结点（4）将ai的值保留在e中（5）释放ai的空间删除（删除第i个结点）#将线性表L中第i个数据元素删除deflist_delete(self,i):

#删除单链表中的第i个结点

foridx,pinenumerate(self):#查找第i−1个结点，p指向该结点

ifidx+1==iandp.nextisnotNone:

p.next=p.next.next#改变删除结点前驱结点的指针域

return

raiseException('位置不合法')【算法描述】删除（删除第i个结点）但是，如果要在单链表中进行前插或删除操作，由于要从头查找前驱结点，所耗时间复杂度为O(n)。链表的运算时间效率分析1.查找:

因线性链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为

O(n)。2.插入和删除:

因线性链表不需要移动元素，只要修改指针，一般情况下时间复杂度为

O(1)。从一个空表开始，重复读入数据：生成新结点将读入数据存放到新结点的数据域中将该新结点插入到链表的前端单链表的建立（前插法）p.data=anp.data=an-1L.next=pp.next=L.next单链表的建立（前插法）defcreate_list_h(self,l_data:list):

#前插法，根据l_data数据列表创建链表

fordatainl_data:

p=LNode(data)#生成新结点p，并将p结点的数据域赋值为data

p.next=self.head.next#将新结点p插入到头结点之后

self.head.next=p【算法描述】单链表的建立（前插法）从一个空表L开始，将新结点逐个插入到链表的尾部，尾指针r指向链表的尾结点。初始时，r同L均指向头结点。每读入一个数据元素则申请一个新结点，将新结点插入到尾结点后，r指向新结点。单链表的建立（尾插法）defcreate_list_r(self,l_data:list):

#后插法，根据l_data数据列表创建链表

r=self.head#尾指针r指向头结点

fordatainl_data:

p=LNode(data)#生成新结点，并初始化p的数据域为data

r.next=p#将新结点p插入尾结点r之后

r=r.next#r指向新的尾结点p【算法描述】单链表的建立（尾插法）循环链表L.next=L(a)非空单循环链表L(b)空表L说明从循环链表中的任何一个结点的位置都可以找到其他所有结点，而单链表做不到；循环条件：pisnotNoneandp!=Lp.nextisnotNoneandp.next!=L循环链表中没有明显的尾端如何避免死循环循环链表对循环链表，有时不给出头指针，而给出尾指针可以更方便的找到第一个和最后一个结点rear

a1

ai-1

an

ai如何查找开始结点和终端结点？开始结点：rear.next.next终端结点：rear说明循环链表Taa1anTbb1bn循环链表的合并a1anb1bn①p②③④TaTb示例循环链表著名犹太历史学家

Josephus约瑟夫问题在罗马人占领乔塔帕特后39个犹太人与Josephus及他的朋友躲到一个洞中39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止然而Josephus和他的朋友并不想遵从，Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏例如n=8m=3约瑟夫问题classLNode:

def__init__(self,data=None):

self.data=data

self.next=None

self.prior=None双向链表(a)空双向循环链表(b)双向循环链表d.next.prior=d.prior.next=dL.next=L双向链表双向链表的插入双向链表的插入abx......1ps1.s.prior=p.prior2.p.prior.next=sabx......12ps双向链表的插入1.s.prior=p.prior双向链表的插入032.p.prior.next=s1.s.prior=p.prior3.s.next.p4.p.prior=sabx......1234ps双向链表的插入2.p.prior.next=s1.s.prior=p.prior3.s.next=pdeflist_insert_dul(self,i,e):

#在第i个位置插入节点e

foridx,pinenumerate(self):

ifidx==i:

s=LNode(e)#生成新结点s,并将数据域置为e

s.prior=p#将结点s插入双向链表

s.next=p.next

p.next=s

ifs.nextisnotNone:

s.next.prior=s

return

raiseException('位置不合法')双向链表的插入双向链表的删除1.p.prior.next=p.next双向链表的删除1.p.prior.next=p.next2.p.next.prior=p.priordeflist_delete_dul(self,i):

#删除双向链表中的第i个元素

foridx,pinenumerate(self):

ifidx==i:

p.prior.next=p.next

#修改被删结点的前驱结点的后继指针

ifp.nextisnotNone:

p.next.prior=p.prior

#修改被删结点的后继结点的前驱指针

return

raiseException('位置不合法')双向链表的删除目录导航2.12.22.32.42.52.62.72.82.9线性表的定义和特点案例引入线性的类型定义线性表的顺序表示和实现线性表的链式表示和实现顺序表和链表的比较线性表的应用案例分析与实现Python标准库中的线性表Contents顺序表和链表的比较

存储结构

比较项目顺序表链表空间存储空间预先分配，会导致空间闲置或溢出现象动态分配，不会出现存储空间闲置或溢出现象存储密度不用为表示结点间的逻辑关系而增加额外的存储开销，存储密度等于1需要借助指针来体现元素间的逻辑关系，存储密度小于1时间存取元素随机存取，按位置访问元素的时间复杂度为O(1)顺序存取，按位置访问元素时间复杂度为O(n)插入、删除平均移动约表中一半元素，时间复杂度为O(n)不需移动元素，确定插入、删除位置后，时间复杂度为O(1)适用情况①表长变化不大，且能事先确定变化的范围②很少进行插入或删除操作，经常按元素位置序号访问数据元素①长度变化较大②频繁进行插入或删除操作目录导航2.12.22.32.42.52.62.72.82.9线性表的定义和特点案例引入线性的类型定义线性表的顺序表示和实现线性表的链式表示和实现顺序表和链表的比较线性表的应用案例分析与实现Python标准库中的线性表Contents线性表的应用有序表的合并线性表的合并线性表的合并

问题描述：假设利用两个线性表la和lb分别表示两个集合

A和B,现要求一个新的集合

A=A∪Bla=(7,5,3,11)

lb=(2,6,3)la=(7,5,3,11,2,6)依次取出lb中的每个元素，执行以下操作：【算法步骤】

1.在la中查找该元素

2.如果找不到，则将其插入la的最后defmerge_list(la,lb):

m=len(la)#求线性表la的长度

forpinlb:#用p遍历lb中的数据元素

ifla.locate_elem(p.data)isNone:

#la中不存在和p相同的数据元素

m+=1#la的长度加1

la.list_insert(m,p.data)

#将p.data插在la最后

return【算法描述】O(m*n)问题描述：la=(1,7,8)lb=(2,4,6,8,10,11)lc=(1,2,4,6,7,8,8,10,11)有序表的合并已知线性表la和lb中的数据元素按值非递减有序排列,现要求将La和lb归并为一个新的线性表lc,且lc中的数据元素仍按值非递减有序排列。【算法步骤】－有序的顺序表合并依次从la或lb中“摘取”元素值较小的结点插入到lc表的最后，直至其中一个表变空为止0201创建一个空表lc继续将la或lb其中一个表的剩余结点插入在lc表的最后03defmerge_list_sq(la,lb):

lc=Sqlbist()

i,j,k=1,1,1

whilei<=len(la)andj<=len(lb):#la和lb均未到达表尾

ifla.get_elem(i)<=lb.get_elem(j):

#依次“摘取”两表中值较小的结点插入到lc的最后

lc.list_insert(k,la.get_elem(i))

i+=1

else:

lc.list_insert(k,lb.get_elem(j))

j+=1

k+=1

whilei<=len(la):

#lb已到达表尾，依次将la的剩余元素插入lc的最后

lc.list_insert(k,la.get_elem(i))

i+=1

k+=1

whilej<=len(lb):

#la已到达表尾，依次将lb的剩余元素插入lc的最后

lc.list_insert(k,lb.get_elem(j))

j+=1

k+=1

returnlcT(n)=O(m+n)S(n)=O(m+n)【算法描述】－有序的顺序表合并将这两个有序链表合并成一个有序的单链表。有序链表合并－－重点掌握要求结果链表仍使用原来两个链表的存储空间,不另外占用其它的存储空间。表中允许有重复的数据。lbla12467881011合并后有序链表合并－－重点掌握lc指向la【算法步骤】－有序的链表合并1依次从la或lb中“摘取”元素值较小的结点插入到lc表的最后，直至其中一个表变空为止。2继续将la或lb其中一个表的剩余结点插入在lc表的最后。3释放lb表的表头结点4有序链表合并（初始化）palbpblc=pcpala(lc,pcbpb有序链表合并(pa.data<＝pb.data)pc.next=papala(lcbpb有序链表合并(pa.data<＝pb.data)pc.next=papc=pa1pcla(lcbpb有序链表合并(pa.data<＝pb.data)pc.next=papc=pa1pcpa=pa.nextpala(lcbpb有序链表合并(pa.data>pb.data)pc.next=pb1pcpala(lcbpb有序链表合并(pa.data>pb.data)pc.next=pb1papcpc=pb2la(lcb有序链表合并(pa.data>pb.data)pc.next=pb1papcpc=pb2pb=pb.nextpbla(lc)12467881011有序链表合并paifpc.next==paelsepbpa(None)pbpcla(lc)12467881011合并后有序链表合并defmerge_list_l(la,lb):

#已知单链表la和lb的元素按值非递减排列

#归并la和lb得到新的单链表lc，lc的元素也按值非递减排列

pa,pb=la.head.next,lb.head.next#pa和pb的初值分别指向两个表的第一个结点

lc=la#la的头结点作为lc的头结点

pc=lc.head#pc的初值指向lc的头结点

whilepaisnotNoneandpbisnotNone:

ifpa.data<=pb.data:#“摘取”pa所指结点

pc.next=pa#将pa所指结点链接到pc所指结点之后

pc=pa#pc指向pa

pa=pa.next#pa指向下一结点

else:#“摘取”pb所指结点

pc.next=pb#将pb所指结点链接到pc所指结点之后

pc=pb#pc指向pb

pb=pb.next#pb指向下一结点

pc.next=paifpaisnotNoneelsepb

returnlc#返回合并后的链表lcT(n)=O(m+n)S(n)=O(1)【算法描述】－有序的链表合并思考1：要求合并后的表无重复数据，如何实现？提示：要单独考虑

pa.data==pb.data

la(lc)12467881011要求结果链表仍使用原来两个链表的存储空间,不另外占用其它的存储空间。表中允许有重复的数据。思考2：将两个非递减的有序链表合并为一个非递增的有序链表，如何实现？（1）lc指向la（2）依次从la或lb中“摘取”元素值较小的结点插入到lc表的表头结点之后，直至其中一个表变空为止（3）继续将la或lb其中一个表的剩余结点插入在lc表的表头结点之后（4）释放lb表的表头结点【算法步骤】目录导航2.12.22.32.42.52.62.72.82.9线性表的定义和特点案例引入线性的类型定义线性表的顺序表示和实现线性表的链式表示和实现顺序表和链表的比较线性表的应用案例分析与实现Python标准库中的线性表Contents案例2.1：一元多项式的运算指数（下标i）01234系数p[i]105-432P(x)

=

10

+

5x

-

4x2

+

3x3

+

2x4数组表示（每一项的指数i隐含在其系数pi的序号中）Rn(x)

=

Pn(x)

+

Qm(x)线性表R

=

(p0

+

q0,p1

+

q1,p2

+

q2,…,pm

+

qm,pm+1,…,pn)下标i0123下标i012系数a[i]7395系数b[i]822-9指数