《数据结构Python 语言描述》 第2章

第2章线性表签到扫码下载文旌课堂APP扫码签到（202X.X.XXXX:00至202X.X.XXXX:10）签到方式教师通过“文旌课堂APP”生成签到二维码，并设置签到时间，学生通过“文旌课堂APP”扫描“签到二维码”进行签到。。线性表本章导读线性表是最简单、最常用的数据结构，可以将其简单理解为“线性结构的表”。本章首先介绍线性表的定义及基本操作，然后介绍线性表的顺序和链式两种存储结构及其基本操作的实现。

第2章线性表知识目标

第2章 理解线性表的定义和特点。 掌握线性表的基本操作。 掌握顺序表的存储结构及其基本操作的实现。 掌握单链表和双链表的结构特点及其基本操作的实现。 理解循环链表的特点。线性表技能目标

第2章 能根据线性表数据的特点选择合适的存储结构。 能使用线性表解决实际问题。线性表素质目标

第2章 增强主动思考、积极寻求问题解决方法的意识。 通过了解“二十四节气”的起源，坚定文化自信。Content第2章线性表的顺序存储线性表概述线性表的链式存储2.1线性表概述第2章线性表2.1线性表概述“春雨惊春清谷天，夏满芒夏暑相连。秋处露秋寒霜降，冬雪雪冬小大寒。”这首仅28个字的“二十四节气歌”蕴含了中华民族千百年来的智慧浓缩。2016年，“二十四节气”入选联合国教科文组织非物质文化遗产名录。在国际气象界，这一已有千年历史的时间认知体系被誉为“中国第五大发明”。“二十四节气”是中国人通过观察太阳周年运动，认知一年中时令、气候、物候等方面变化规律所形成的知识体系和社会实践。2.1线性表概述中国古人将太阳周年运动轨迹划分为24等份，每一等份为一个“节气”，统称“二十四节气”，具体包括立春、雨水、惊蛰、春分、清明、谷雨、立夏、小满、芒种、夏至、小暑、大暑、立秋、处暑、白露、秋分、寒露、霜降、立冬、小雪、大雪、冬至、小寒、大寒。“二十四节气”指导着传统农业生产和日常生活，是中国传统历法体系及其相关实践活动的重要组成部分，深刻影响着人们的思维方式和行为准则，是中华民族文化认同的重要载体。2.1线性表概述2.1.1线性表的定义和特点线性表是由n（n≥0）个特性相同的数据元素组成的有限序列，数据元素之间是一对一的关系。线性表可以表示为(a0,a1,…,ai－1,ai,ai＋1,…,an-1)，其逻辑结构如下图所示。由该图可以看出，线性表中的每个数据元素都有一个确定的位置，a0为首元素，ai为第i（0＜i＜n-1）个元素，an-1为尾元素。通常情况下，用线性表中数据元素的个数n表示线性表的长度。当n=0时，线性表为空表。2.1.2线性表的基本操作线性表基本操作的定义如表2-1所示。2.1线性表概述基本操作说明__init__()初始化线性表，即构造一个空的线性表createList()创建线性表，即构造一个非空的线性表getLength()线性表已存在的前提下，返回表的长度，即表中数据元素的个数insert(i,e)线性表已存在的前提下，在表中第i（0≤i≤getLength()）个位置之前插入新的数据元素e，表长加1delete(i)线性表已存在且非空的前提下，删除表中第i（0≤i≤getLength()-1）个数据元素，表长减1locate(e)线性表已存在的前提下，返回第一个与数据元素e相等的数据元素在线性表中的位置getElem(i)线性表已存在的前提下，返回表中第i（0≤i≤getLength()-1）个数据元素的值traversal()线性表已存在的前提下，对表进行遍历，在遍历过程中对表的每个数据元素均访问一次clearList()线性表已存在的前提下，将其置为空表setElem(i,e)线性表已存在的前提下，将表中第i（0≤i≤getLength()-1）个数据元素的值设置为elistEmpty()线性表已存在的前提下，判断表是否为空表2-1线性表基本操作的定义2.2线性表的顺序存储——顺序表第2章线性表2.2线性表的顺序存储——顺序表假设顺序表中有n（n≥0）个数据元素，每个数据元素占用k个存储单元，且以顺序表中第一个数据元素的存储地址Loc(a0)作为顺序表的起始地址或基地址（用d表示），则可以得到顺序表中第i个数据元素ai的存储地址为

Loc(ai)=d+i×k（0≤i≤n-1）相邻两个数据元素ai和ai＋1的存储地址之间的关系为

Loc(ai＋1)=Loc(ai)+k（0≤i＜n-1）因此，顺序表的存储结构如下图所示。2.2.1顺序表的存储结构2.2线性表的顺序存储——顺序表由右图可以看出，在顺序表中，逻辑结构相邻的数据元素在物理存储单元中也是相邻的。只要确定顺序表的起始地址（基地址）和表中每个数据元素所占存储单元的大小，就可以计算出顺序表中任意一个数据元素的存储地址。也就是说，顺序表中任一数据元素都是可以随机存取的，这种存取元素的方法称为随机存取法。因此，线性表的顺序存储结构是一种随机存取的存储结构。2.2线性表的顺序存储——顺序表2.2.2顺序表中基本操作的实现1．初始化顺序表初始化顺序表是为顺序表动态分配存储空间，并将其长度设置为0，其具体步骤如下。（1）设置顺序表的最大容量。（2）设置顺序表的存储空间。（3）将顺序表的长度设置为0。2.2线性表的顺序存储——顺序表2．在顺序表中插入数据元素顺序表的插入操作是指在长度为n的顺序表的第i（0≤i≤n）个位置之前插入一个数据元素e。例如，顺序表为(a0,a1,…,ai－1,ai,ai＋1,…,an-1)，插入数据元素e后为(a0,a1,…,ai－1,e,ai,ai＋1,…,an-1)。此时，顺序表的长度变为n+1，如下图所示。2.2线性表的顺序存储——顺序表由上图可以看出，当在第i（0≤i≤n）个位置插入一个数据元素时，须从最后一个数据元素（an-1）开始到第i个数据元素（ai）结束，依次向后移动一个位置。当i=0时，表示在表头插入；当i=n时，表示在表尾插入，此时无须移动其他数据元素。因此，在顺序表中插入数据元素的具体步骤如下。（1）判断顺序表的存储空间是否已满，若已满，则抛出异常。（2）判断插入数据元素的位置i是否满足条件0≤i≤n，若不满足，则抛出异常。（3）将插入位置及其之后的所有数据元素依次向后移动一个位置，空出存放新数据元素的位置。（4）将新的数据元素插入到第i个位置。（5）顺序表的表长加1。2.2线性表的顺序存储——顺序表definsert(self,i,e):ifself.length==self.max: #如果表长等于最大容量，抛出异常

raiseException('顺序表已满，无法插入数据！')ifi<0ori>self.length: #如果插入位置不合理，抛出异常

raiseException('插入位置不合理！')forjinrange(self.length,i-1,-1): #移动数据元素

self.data[j]=self.data[j-1]self.data[i]=e #插入数据元素

self.length+=1 #表长加1【算法描述】2.2线性表的顺序存储——顺序表

【算法分析】2.2线性表的顺序存储——顺序表提示最坏时间复杂度是算法在最坏情况下的时间复杂度，表示算法的计算量可能达到的最大值。最好时间复杂度是算法在最好情况下的时间复杂度，表示算法的计算量可能达到的最小值。平均时间复杂度是算法在所有可能情况下，按照输入实例以等概率出现时，算法计算量的加权平均值，一般用于表示该算法的时间复杂度。2.2线性表的顺序存储——顺序表3．在顺序表中删除数据元素顺序表的删除操作是指将顺序表中第i（0≤i≤n-1）个数据元素从顺序表中删除。例如，顺序表为(a0,a1,…,ai－1,ai,ai＋1,…,an-1)，删除数据元素ai后为(a0,a1,…,ai－1,ai＋1,…,an-1)。此时，顺序表的长度变为n-1，如下图所示。2.2线性表的顺序存储——顺序表由上图可以看出，删除顺序表中第i（0≤i≤n-1）个数据元素，须从第i+1个数据元素（ai＋1）开始到第n-1个数据元素（an-1）结束，依次向前移动一个位置。当i=0时，表示删除表头的数据元素；当i=n-1时，表示删除表尾的数据元素，此时无须移动其他数据元素。因此，在顺序表中删除数据元素的具体步骤如下。（1）判断删除数据元素的位置i是否满足条件0≤i≤n-1，若不满足，则抛出异常。（2）将第i个数据元素之后的数据元素都向前移动一个位置。（3）顺序表的表长减1。2.2线性表的顺序存储——顺序表defdelete(self,i):ifi<0ori>self.length-1:#如果删除位置不合理，抛出异常

raiseException('删除位置不合理！')forjinrange(i,self.length): #移动数据元素

self.data[j]=self.data[j+1]self.length-=1 #表长减1【算法描述】2.2线性表的顺序存储——顺序表

【算法分析】2.2线性表的顺序存储——顺序表4．在顺序表中查找数据元素在顺序表中查找数据元素的过程是从第一个数据元素（a0）开始，依次将表中的数据元素与要查找的数据元素进行比较，若相等，则返回该数据元素在表中的位置；否则，查找失败，过程如下图所示。2.2线性表的顺序存储——顺序表在顺序表中查找数据元素的具体步骤如下。（1）从顺序表中第一个数据元素（a0）开始，依次和要查找的数据元素e比较，若找到与e相等的数据元素ai，则查找成功，并返回该数据元素的位置i。（2）若顺序表查找完成后依然没有找到数据元素e，则查找失败，返回-1。deflocate(self,e):foriinrange(self.length):ifself.data[i]==e:returnireturn-1【算法描述】2.2线性表的顺序存储——顺序表

【算法分析】2.2线性表的顺序存储——顺序表5．在顺序表中取指定数据元素由于顺序表具有随机存取的特点，因此可以通过数据元素的下标直接获取数据元素，如下图所示。在顺序表中取指定数据元素的具体步骤如下。（1）判断指定的位置i是否满足条件0≤i≤n-1，若不满足，则返回-1。（2）若i满足条件，将直接返回第i个数据元素。2.2线性表的顺序存储——顺序表defgetElem(self,i):ifi<0ori>self.length-1:return-1returnself.data[i]【算法描述】【算法分析】该算法的时间复杂度为O(1)。2.2线性表的顺序存储——顺序表6．求顺序表的长度defgetLength(self):returnself.length【算法描述】【算法分析】该算法的时间复杂度为O(1)。求顺序表的长度就是返回顺序表中数据元素的个数。2.2线性表的顺序存储——顺序表7．遍历顺序表deftraversal(self):foriinrange(self.length):returnself.data[i]【算法描述】【算法分析】该算法的时间复杂度为O(n)。遍历顺序表就是依次访问顺序表中的各个数据元素。当线性表的长度变化不大，且易于事先确定其大小时，为了节省存储空间，应使用顺序存储结构。此外，若线性表的主要操作是查找数据元素，且很少插入或删除数据元素，也应使用顺序存储结构。高手点拨2.2线性表的顺序存储——顺序表同步训练利用顺序表存储学生成绩【问题描述】设计算法创建一个学生成绩表（其中每个学生的成绩信息包括学号、姓名、《语文》成绩、《数学》成绩、《英语》成绩、总成绩），实现学生成绩的录入、总成绩的计算，以及学生成绩的查询和删除。【问题分析】创建一个顺序表存储学生的成绩信息，首先输入学生人数确定要创建的顺序表长度，然后依次录入每个学生的成绩信息并提示“成绩录入成功！”，最后计算学生个人总成绩。查询学生的成绩信息时，首先输入要查询学生的学号，然后将顺序表中每个学生的学号与给定学号进行比较，若相等则提示“成绩查询成功！”并输出该学生的成绩信息，否则提示“无此学生！”。同步训练利用顺序表存储学生成绩删除学生的成绩信息时，首先输入要删除学生的学号，然后将顺序表中每个学生的学号与给定学号进行比较，若相等则删除该学生的成绩信息并提示“成绩删除成功！”，否则提示“无此学生！”。【代码实现】L=[]defadd(): #录入学生的成绩信息

j=eval(input('输入学生人数:'))foriinrange(0,j): #按输入的学生人数遍历顺序表

print('----输入第%d个学生的成绩信息----'%(i+1))sNumber=eval(input('学号：')) #定义学生学号同步训练利用顺序表存储学生成绩sName=input('姓名：') #定义学生姓名

chinese=eval(input('请输入《语文》成绩：'))

#定义《语文》成绩

math=eval(input('请输入《数学》成绩：'))

#定义《数学》成绩

english=eval(input('请输入《英语》成绩：'))

#定义《英语》成绩

dict1={} #定义一个字典存储学生的成绩信息

dict1['sNumber']=sNumber #存储学生学号

dict1['name']=sName #存储学生姓名

dict1['chinese']=chinese #存储《语文》成绩同步训练利用顺序表存储学生成绩dict1['math']=math #存储《数学》成绩

dict1['english']=english #存储《英语》成绩

dict1['sum']=(math+chinese+english)#存储总成绩

L.append(dict1) #将学生的成绩信息加入列表中

print('成绩录入成功！')defsearch(): #查询学生的成绩信息

num=eval(input('请输入要查询学生的学号：'))index1=-1fori,dictinenumerate(L): #将顺序表组成索引序列进行遍历

#如果顺序表中存储的学号与输入的学号相等

ifdict.get('sNumber')==num:

同步训练利用顺序表存储学生成绩index1=i #index1重新赋值

breakifindex1!=-1: #如果index1不等于-1，输出学生信息

print('成绩查询成功！')print('学号：%d，姓名：%s，《语文》成绩：%d，《数学》成绩：%d，《英语》成绩：%d，总成绩：%d'%(L[index1]['sNumber'],L[index1]['name'],L[index1]['chinese'],L[index1]['math'],L[index1]['english'],L[index1]['sum']))else:print('无此学生！')

同步训练利用顺序表存储学生成绩defdelete(): #删除学生的成绩信息

num=eval(input('请输入要删除学生的学号：'))index1=-1fori,dictinenumerate(L): #将顺序表组成索引序列进行遍历

#如果顺序表中存储的学号与输入的学号相等

ifdict.get('sNumber')==num:index1=i #index1重新赋值

breakifindex1!=-1: #如果index1不等于-1，删除学生的成绩信息

delL[index1]print('成绩删除成功！')同步训练利用顺序表存储学生成绩

else:print('无此学生！')defdisplay(): #显示学生的成绩信息

iflen(L)==0: #确认存储学生成绩信息的顺序表是否为空

print('无学生！')else:fordict1inL: #遍历存储学生信息的顺序表并输出学生的成绩信息

print('学号：%d，姓名：%s，《语文》成绩：%d，《数学》成绩：%d，《英语》成绩：%d，总成绩：%d'%(dict1['sNumber'],dict1['name'],dict1['chinese'],dict1['math'],dict1['english'],dict1['sum']))同步训练利用顺序表存储学生成绩defmain(): #定义main()函数并调用定义的方法

add() #调用add()函数录入学生的成绩信息

display() #调用display()函数显示学生的成绩信息

search() #调用search()函数查询学生的成绩信息

delete() #调用delete()函数删除学生的成绩信息

display() #调用display()函数显示学生的成绩信息

main() 同步训练利用顺序表存储学生成绩【程序测试】程序运行结果如右图所示。2.3线性表的链式存储——链表第2章线性表2.3线性表的链式存储——链表2.3.1单链表1．单链表的结构特点在线性表的链式存储结构中，为了表示每个元素与其后继元素之间的逻辑关系，除了需要存储元素本身的数据信息外，还要存储一个指示其后继元素地址的信息，这两部分信息共同构成了一个数据元素的存储结构，称为结点（node），如下图所示。2.3线性表的链式存储——链表其中，存储元素本身数据信息的部分称为数据域（data），存储其后继元素地址信息的部分称为指针域（next）。单链表（也称线性链表）是指将n个数据元素通过其对应结点的指针域按其逻辑关系链接成的链表，其中每个结点只包含一个数据域和一个指针域，一般形式如下图所示。其中，head称为头指针，用于指向单链表的第一个结点（也称首元结点）。由于单链表的最后一个结点没有后继元素，所以其指针域为“空”（None），用符号“^”表示。2.3线性表的链式存储——链表提示在Python中并不存在指针的概念，此处的指针属性实际上存放的是后继结点的引用，但为了表述方便仍然采用“指针”一词。为避免读者对首元结点、头结点和头指针的概念产生混淆，下面分别对其进行解释说明。（1）首元结点是指链表中存储第一个数据元素的结点。（2）头结点是在首元结点之前增加的一个结点，其指针域指向首元结点。增加头结点是为了便于处理首元结点，即对链表的首元结点的操作与其他结点相同，无须做特殊处理。（3）头指针是指向链表中第一个结点的指针。若单链表中增加了头结点，则头指针指向头结点；若单链表中没有增加头结点，则头指针指向首元结点。高手点拨2.3线性表的链式存储——链表2.3线性表的链式存储——链表2．单链表中基本操作的实现1）初始化单链表初始化单链表就是构造一个空表，如右图所示。classSLinkList:def__init__(self):self.head=Node(None)self.head.next=None【算法描述】2.3线性表的链式存储——链表2）建立单链表建立单链表是在一个空表中一次性创建多个结点。建立单链表的常用方法有头插法和尾插法两种，下面分别介绍。（1）头插法是通过将新结点逐个插入单链表中的头结点之后来建立单链表，具体过程如下图所示。2.3线性表的链式存储——链表由上图可以看出，使用头插法建立单链表可分为如下6步。①建立只有头结点的空表。②生成第一个结点s。其中，新结点的数据域存储数据元素的数据信息，指针域为None。③将第一个结点插入头结点之后。④生成新结点s。⑤将新结点的指针指向第一个结点（s.next=head.next），然后将头结点的指针指向新结点s（head.next=s）。⑥重复步骤④和⑤，直到单链表生成完毕。2.3线性表的链式存储——链表defcreateList_head(self,a):self.head=Node(None) #生成头结点

foriinrange(len(a)):s=Node(a[i]) #生成一个新结点ss.next=self.head.next #修改新结点的指针域

self.head.next=s #将新结点s插入头结点之后【算法描述】2.3线性表的链式存储——链表提示上述算法中的语句s.next=head.next和head.next=s的顺序不能颠倒。若先执行语句head.next=s，再执行语句s.next=head.next，会找不到结点a0，此时相当于执行语句s.next=s，插入操作将出现错误。2.3线性表的链式存储——链表（2）尾插法是通过将新结点逐个插入单链表的尾部来建立单链表，具体过程如下图所示。由上图看出，使用尾插法建立单链表可分为如下3步。①建立只有头结点的空表，并增加指针t，使其指向头结点。②从线性表的第一个数据元素开始依次获取表中数据元素，并生成一个新结点s。其中，新结点的数据域存储数据元素的数据信息，指针域为None。③将新结点插入当前链表的表尾，并使指针t始终指向当前链表的尾结点。2.3线性表的链式存储——链表defcreateList_tail(self,a):self.head=Node(None) #生成头结点

t=self.head #创建一个尾指针t指向头结点

foriinrange(len(a)):s=Node(a[i]) #生成一个新结点ss.next=None #将新结点的指针域置为空

t.next=s #将新结点s插入尾结点t之后

t=s #尾指针t指向尾结点【算法描述】【算法分析】该算法的时间复杂度为O(n)。2.3线性表的链式存储——链表3）在单链表中取指定结点的值若要在单链表中取指定结点的值，须从单链表的首元结点出发，然后顺着指针域向后依次访问各个结点，其具体步骤如下。（1）使用指针p指向首元结点，使用变量j做计时器并赋初值0。（2）从首元结点开始依次向后访问，只要当前结点的指针p不为空，且没有到达第i（0≤i≤n-1）个结点，就循环执行p指向下一个结点及j+1的操作。（3）退出循环后，判断指定结点的位置i是否满足条件0≤i≤n-1，若满足，则取值成功，此时j=i，即p所指的结点就是要取出的第i个结点，最后保存该结点的数据域。若不满足，则返回-1。2.3线性表的链式存储——链表deflistGetElem(self,i):p=self.head.next #p指向首元结点

j=0 #查找第i个结点并由p指向该结点

whilepisnotNoneandj<i:p=p.nextj+=1ifpisNoneorj>i: #判断指定结点的位置是否满足条件

return-1e=p.data #保存结点的数据域

returne【算法描述】【算法分析】该算法的时间复杂度为O(n)。2.3线性表的链式存储——链表4）在单链表中插入结点单链表的插入操作是指在长度为n的单链表的第i（0≤i≤n）个位置插入一个值为e的结点，因此，须首先找到插入位置的前驱结点，然后修改该结点的指针域，具体过程如下图所示。当i=0时，表示在链表头部插入；当i=n时，表示在链表尾部插入。2.3线性表的链式存储——链表由上图可以看出，在单链表中插入结点可分为如下4步。（1）找到单链表的第i-1个结点，并增加一个指针p指向该结点。（2）生成一个新结点s，并设置其数据域为e。（3）使新结点s的指针域指向第i个结点。（4）修改第i-1个结点的指针域，使其指向新结点。deflistInsert(self,i,e):p=self.head #p指向头结点

j=-1 #查找第i-1个结点并由p指向该结点

whilepisnotNoneandj<i-1:【算法描述】2.3线性表的链式存储——链表p=p.nextj+=1ifpisNoneorj>i-1: #判断插入的位置是否满足条件

return-1s=Node(e) #生成新结点

s.next=p.next #修改指针域

p.next=s【算法分析】该算法的时间复杂度为O(n)。2.3线性表的链式存储——链表5）在单链表中删除结点删除单链表中的结点与插入结点类似，也须首先找到删除结点的前驱结点，然后修改该结点的指针域，具体过程如下图所示。2.3线性表的链式存储——链表由上图可以看出，在单链表中删除结点可分为如下两步。（1）找到单链表中ai的前驱结点，并增加一个指针p指向该结点。（2）修改ai的前驱结点的指针域，使其指向ai的后继结点。deflistDelete(self,i):p=self.head #p指向头结点

j=-1

#查找第i-1个结点并由p指向该结点【算法描述】2.3线性表的链式存储——链表whilepisnotNoneandj<i-1:p=p.nextj+=1ifpisNoneorj>i-1: #判断插入的位置是否满足条件

return-1p.next=p.next.next

#修改指针域【算法分析】该算法的时间复杂度为O(n)。2.3线性表的链式存储——链表6）在单链表中查找结点要查找单链表中值为e的结点，需从单链表的首元结点开始，逐个将结点的值与e进行比较。当两者相等时，则当前指针指向的就是要查找的结点，其具体步骤如下。（1）使用指针p指向首元结点。（2）从首元结点开始顺着指针域依次向后查找，只要当前结点的指针p不为空，且p所指结点的数据域与要查找的值e不相等，就循环执行p指向下一个结点的操作。（3）查找成功后，返回p。2.3线性表的链式存储——链表deflistLocate(self,e):p=self.head.next #p指向首元结点

#查找值为e的结点并由p指向该结点

whilepisnotNoneandp.data!=e:p=p.nextreturnp【算法描述】【算法分析】该算法的时间复杂度为O(n)。2.3线性表的链式存储——链表7）遍历单链表遍历单链表就是依次访问单链表中的各个结点，并输出各个结点的值。deftraversal(self):p=self.head.next #p指向首元结点

whilepisnotNone: #判断当前指针是否指向尾结点

print(p.data,end='')p=p.next【算法描述】【算法分析】该算法的时间复杂度为O(n)。2.3线性表的链式存储——链表2.3.2双链表1．双链表的结构特点在单链表中，每个结点只设置了一个指针域用于指示该结点的后继结点。因此，从单链表的任意结点出发，都只能顺着指针方向向后查找其他结点。若要查找其前驱结点，必须从单链表的头结点出发，从前向后依次查找。为此，在单链表的每个结点中增加一个指向其前驱结点的指针域，这样的链表称为双链表。双链表中的每个结点有一个数据域（data）和两个指针域（prior和next），一个指针域（prior）指向该结点的前驱结点，另一个指针域（next）指向该结点的后继结点，如下图所示。2.3线性表的链式存储——链表双链表的一般形式如下图所示。在双链表中，假设每个结点为DNode类对象，则结点的定义如下。classDNode: #双链表结点类

def__init__(self,data): #构造方法

self.data=data #data属性

self.next=None #next属性

self.prior=None #prior属性2.3线性表的链式存储——链表2．双链表中基本操作的实现1）初始化双链表初始化双链表就是构造一个空表，如右图所示。classDLinkList:def__init__(self):self.head=DNode(None)self.head.next=None

self.head.prior=None【算法描述】2.3线性表的链式存储——链表2）在双链表中插入结点在长度为n的双链表的第i（0≤i≤n）个位置插入一个值为e的结点，首先需要找到第i-1个结点，然后修改4个指针属性，其实现过程如下图所示。2.3线性表的链式存储——链表由上图可以看出，在双链表中插入结点可分为如下3步。（1）找到双链表的第i-1个结点，并增加一个指针p指向该结点。（2）生成一个新结点s，并令其数据域为e。（3）修改第i-1个结点、第i个结点和新结点s的next和prior属性（共4个指针属性）。defdlistInsert(self,i,e):p=self.head #p指向头结点

j=-1 #查找第i-1个结点，并由p指向该结点

whilepisnotNoneandj<i-1: p=p.next【算法描述】2.3线性表的链式存储——链表 j+=1ifpisNoneorj>i-1: #判断插入的位置是否满足条件

return-1s=DNode(e) #生成新结点

s.next=p.nextifp.next!=None: #判断p是否为尾结点

p.next.prior=ss.prior=pp.next=s【算法分析】该算法的时间复杂度为O(n)。2.3线性表的链式存储——链表提示以上算法是在双链表中先找到第i-1个结点，然后在该结点之后插入新结点，还可以在双链表中先找到第i个结点，然后在该结点之前插入新结点。2.3线性表的链式存储——链表3）在双链表中删除结点删除长度为n的双链表的第i（0≤i≤n-1）个结点，首先需要找到该结点，然后修改其前驱结点和后继结点的指针属性，具体过程如下图所示。defdlistDelete(self,i):p=self.head #p指向头结点

j=-1 #查找第i个结点并由p指向该结点【算法描述】2.3线性表的链式存储——链表whilepisnotNoneandj<i:p=p.nextj+=1ifpisNoneorj>i: #判断删除的位置是否满足条件

return-1ifp.prior!=None: #不是第一个结点时执行的操作

p.prior.next=p.nextifp.next!=None: #不是最后一个结点时执行的操作

p.next.prior=p.prior【算法分析】该算法的时间复杂度为O(n)。2.3线性表的链式存储——链表提示以上算法是在双链表中先找到第i个结点，然后通过其前驱结点和后继结点删除该结点，还可以在双链表中先找到第i1个结点，然后再删除其后继结点。2.3线性表的链式存储——链表2.3.3循环链表将链表中最后一个结点的指针域指向头结点，从而形成一个首尾相接的链表，这样的链表称为循环链表。在循环链表中，所有结点链接在环上，从循环链表中任一结点出发均可找到其他结点。循环链表又可以分为循环单链表和循环双链表。带头结点的循环单链表和循环双链表分别如下图所示。2.3线性表的链式存储——链表循环链表的操作与普通链表基本一致，不同的是，在循环链表中判断某个结点为尾结点的条件不是其后继结点为空，而是其后继结点为头结点。在循环单链表中，找到第一个结点a0只需要一步操作，即a0=head.next，其时间复杂度为O(1)；然而要找到最后一个结点an-1则要遍历整个链表，其时间复杂度为O(n)。为使操作简化，通常在循环单链表中设立尾指针rear，如下图所示。这样，当查找第一个结点和最后一个结点时，都只需一步操作就可以完成，即a0=rear.next.next，an-1=rear，其时间复杂度均为O(1)。当线性表的长度变化较大，难以事先确定其大小时，应使用链式存储结构。此外，若线性表的主要操作是插入或删除，也应使用链式存储结构。高手点拨2.3线性表的链式存储——链表同步训练利用单链表实现多项式相加【问题描述】已知有两个一元n阶多项式a(x)=a0+a1x+a2x2+a3x3+…+anxn和b(x)=b0+b1x+b2x2+b3x3+…+bnxn，设计算法求它们的和c(x)。【问题分析】多项式中的每一项由其系数和指数来确定，

如a2x2中的a2是系数，x2中的2是指数。多项式相加的规则是指数相同的项，指数不变，系数相加；指数不同的项，指数小的项在前，指数大的项在后，最后合并两项即可。由一元n阶多项式的表示形式可以看出，它由n+1个系数唯一确定。因此，为节省存储空间，通常采用链式存储结构来存储多项式。多项式中的每个系数非零项对应着链表中的一个结点，其存储结构如下图所示。同步训练利用单链表实现多项式相加其中，coef域用于存放多项式某一项的系数；index域用于存放该项的指数；next域用于存放指向下一个系数非零项结点的指针。【代码实现】'''结点为Node类对象，结点的定义'''classNode:def__init__(self,coef,index):self.coef=coef #多项式的系数

self.index=index #多项式的指数

self.next=None #指向后继元素的指针同步训练利用单链表实现多项式相加

'''单链表为polyLinkList类对象，单链表的定义'''classpolyLinkList():def__init__(self,items):self.head=Noneself.items=items #存放系数和指数的数组

foriteminself.items:coef,index=item[0],item[1]node=Node(coef,index)self.insertSort(node)同步训练利用单链表实现多项式相加 '''将结点插入单链表中，并按指数大小升序排列'''definsertSort(self,node): pre=Nonecur=self.head #指针cur指向头结点

whilecurisnotNoneandcur.index<=node.index:ifcur.index==node.index:cur.coef+=node.coefreturnpre=curcur=cur.next #移动指针cur同步训练利用单链表实现多项式相加node.next=curifpreisnotNone:pre.next=nodeelse:self.head=nodedefdisplay(self): #打印多项式

cur=self.headwhilecurisnotNone:ifcur.coef!=0:print('%d%s%d'%(cur.coef,'x^',cur.index),end='')cur=cur.next同步训练利用单链表实现多项式相加'''多项式相加类polynomialAdd的定义'''classpolynomialAdd:def__init__(self,p1,p2):self.p1=p1 #第一个多项式

self.p2=p2 #第二个多项式

self.sum=[] #存储两个多项式相加得到的系数和指数的数组

self.__polynomialAdd() #两个多项式相加

p3=polyLinkList(self.sum) #创建存储两个多项式的和同步训练利用单链表实现多项式相加

p3.display()

def__polynomialAdd(self):l1=self.p1.head #第一个多项式的表头

l2=self.p2.head #第二个多项式的表头

'''两个多项式都不为空时，将其合并'''whilel1isnotNoneandl2isnotNone:ifl1.index>l2.index:self.sum.append([l2.coef,l2.index])l2=l2.nextelifl1.index<l2.index:同步训练利用单链表实现多项式相加self.sum.append([l1.coef,l1.index])

l1=l1.nextelse:self.sum.append([l1.coef+l2.coef,l2.index])l1=l1.nextl2=l2.next '''如果第一个多项式为空，但第二个多项式不为空，则将第二个多项式中的其余结点添加到新的多项式中'''whilel1isNoneandl2isnotNone:self.sum.append([l2.coef,l2.index])l2=l2.next同步训练利用单链表实现多项式相加 '''如果第一个多项式不为空，但第二个多项式为空，则将第一个多项式中的其余结点添加到新的多项式中'''whilel1isnotNoneandl2isNone:self.sum.append([l1.coef,l1.index])l1=l1.nextexp1=[[7,1],[4,3],[2,5],[3,6]] #第一个多项式表达式

exp2=[[10,1],[-6,2],[1,3],[8,5]] #第二个多项式表达式

p1=polyLinkList(exp1) #创建对象

p2=polyLinkList(exp2)print('a(x)=',end='')p1.display()同步训练利用单链表实现多项式相加