数据结构实验指导与习题解答-Python语言描述全套课件

数据结构Python语言描述实验指导与习题解答

编程基础计算机及相关专业考研考博课程计算机等级考试课程程序员考试课程学习数据结构的重要性2

课程学习指导1.提前预习、认真听课、按时完成书面及上机作业2.先修课程的知识准备离散数学、Python语言3.着重掌握基本概念、基本思想、基本步骤、算法设计4.提高算法设计的能力理解所讲算法、对此多做思考若问题要求不同，应如何设计有效的算法课程特点：内容抽象、概念性强、内容灵活、不易掌握3

了解数据结构研究的主要内容掌握数据结构中涉及的基本概念掌握算法、算法的时间复杂度及其分析的简易方法

教学目标4第1章绪论5目录1.1基础实验1.2综合实验1.3习题解答61.1基础实验1.1.1基础实验1分析算法的时间和空间复杂度1.1.2基础实验2设计算法并讨论其时间复杂度71.1.1基础实验1分析算法的时间和空间复杂度82、实验内容1、实验目的3、实验代码1.1.2基础实验2设计算法并讨论其时间复杂度92、实验内容1、实验目的3、实验代码1.2综合实验1.2.1综合实验1多种方式求和1.2.2综合实验2多种方式求素数101.2.1综合实验1多种方式求和113、实验内容1、实验目的4、实验代码2、实验背景1.2.2综合实验2多种方式求素数123、实验内容1、实验目的4、实验代码2、实验背景1.3习题解答一、选择题二、填空题三、编程题13数据结构实验指导与习题解答——Python语言描述张光河

主编guanghezhang@163.com人民邮电出版社2022年09月14ISBN：978-7-115-56280-7ISBN：978-7-115-56280-7ISBN：978-7-115-48577-9配套教材主教材主教材与配套教材15

学习数据结构的重要性编程基础计算机及相关专业考研考博课程计算机等级考试课程程序员考试课程16

课程学习指导提前预习、认真听课、按时完成书面及上机作业先修课程的知识准备

离散数学、Python语言着重掌握

基本概念、基本思想、基本步骤、算法设计提高算法设计的能力

理解所讲算法、对此多做思考

若问题要求不同，应如何设计有效的算法课程特点内容抽象、概念性强、内容灵活、不易掌握17

了解数据结构研究的主要内容掌握数据结构中涉及的基本概念掌握算法、算法的时间复杂度及其分析的简易方法

教学目标18第1章绪论19习题解答1.3综合实验1.2基础实验1.1目录CONTENTS201.1基础实验211.1.1分析算法的时间和空间复杂度基础实验11.1.2设计算法并讨论其时间复杂度基础实验2

基础实验1分析算法的时间和空间复杂度221############################2#算法一：简单输出3############################4defFun1(self):5

i=06

print("helloworld！")考察是否能够正确地理解算法的时间和空间复杂度的概念，并能否计算出下列给定算法的时间和空间复杂度。实验目的实验内容计算出下列3个算法的时间和空间复杂度。实验代码231############################2#算法二：单重循环3############################4defFun2(self,n):5

k=06

foriinrange(0,n):7

k=k+i1############################2#算法三：双重循环3############################4defFunction(self,n):5

k=06

foriinrange(1,n):7

forjinrange(1,i+1):8

k=i*j9

print(i,"*",j,"=",k)10

print()基础实验1分析算法的时间和空间复杂度

基础实验2设计算法并讨论其时间复杂度24实验目的通过设计算法直观感知其时间复杂度，从而进一步理解算法的时间复杂度的概念，并能够计算出对应的时间复杂度。创建名为ex010501_02.py的文件，在其中设计多个操作（包括无循环、单重循环和双重循环），体会算法的时间复杂度这一概念。通过以下步骤完成本实验。1．实现无循环的方法（1）简单地编写一个输出自己姓名和学号的语句。（2）计算该方法的时间复杂度。2．实现单重循环的方法（1）利用单重循环求解正整数1～n的和。（2）计算该方法的时间复杂度。3．实现双重循环的方法（1）利用双重循环输出九九乘法表。（2）计算该方法的时间复杂度。实验内容251#########################################2#文件名：ex010501_02.py3#版本号：0.14#创建时间：2019-1-135#########################################6classLoopCom(object):7

################################8

#实现无循环的方法9

################################10

defNoLoop(self):11

name="张三"12

id="20190113"13

print("\n1.实现无循环的方法")14

print("（1）简单地编写一个输出自己姓名和学号的语句。")15

print("姓名为{0:}，学号为{1:}".format(name,id))16

print("（2）该方法的时间复杂度为O(1)。")17

################################18

#实现单重循环的方法19

################################20

defOneLoop(self):21

sum=022

n=1023

foriinrange(1,n+1):24

sum=sum+i25

print("\n2.实现单重循环的方法")实验代码2630

#实现双重循环的方法31

################################32

defDoubleLoop(self):33

print("\n3.实现双重循环的方法")34

print("（1）利用双重循环输出九九乘法表。")35

foriinrange(1,10):36

forjinrange(1,i+1):37

print("{0:}*{1:}={2:}".format(i,j,i*j),end="")38

print()39

print("（2）该算法的时间复杂度为O(n^2)。")40

################################41

#输出函数42

################################43

defPrintOut(self):44

self.NoLoop()45

self.OneLoop()46

self.DoubleLoop()47if__name__=='__main__':48

LC=LoopCom()49

LC.PrintOut()26

print("（1）利用单重循环求解正整数1~10的和。")27

print("1~10的和为{0:}".format(sum))28

print("（2）该算法的时间复杂度为O(n)。")29

################################1.2综合实验271.2.1多种方式求和综合实验11.2.2多种方式求素数综合实验2

综合实验1多种方式求和28以多种方式求解正整数1～n的和，通过对比这些方式在同一种环境下运行后的绝对时间，深入地体会算法的时间复杂度。实验目的实验背景

综合实验1多种方式求和29

实验内容

综合实验1多种方式求和30实验代码50

defPrintOut(self):51

n=int(input("请输入n的值："))52

print("\n（1）编写将正整数1，2，...，",n,"逐个进行累加的方法。")53

t2=self.Calculate(n)54

print("\n（3）编写使用(n*(n+1))/2求解1~",n,"的和的方法。")55

t4=self.Formula(n)56

print("\n（5）比较（2）和（4）中的绝对时间。")57

self.CompareTime(t2,t4)

综合实验2多种方式求素数31实验目的以多种方式判断某个正整数n（n>1）是否为素数，通过对比这些方式在同一种环境下运行后的绝对时间，深入地体会算法的时间复杂度。实验背景我们知道判断一个正整数n是否为素数的方法是通过计算该正整数是否只能被1和其本身整除。当设计如何判断正整数n是否为素数的算法时，我们可以将n对正整数2,3,…,n-1逐个进行取模，若结果均不为0，则n为素数；也可以将n对正整数2,3,…,2n逐个进行取模，若结果均不为0，则n为素数；也可以将n对正整数2,3,…,n逐个进行取模，若结果均不为0，则n为素数。这3种方法对素数的判断进行了逐步改进，需重复取模，比较的次数也变得越来越少。

综合实验2多种方式求素数32创建名为ex010502_02.py的文件，在其中编写判断正整数n是否为素数的程序，具体如下。（1）编写通过将正整数n对2,3,…,n-1逐个取模，判断其是否为素数的方法。（2）编写通过将正整数n对2,3,…,2n逐个取模，判断其是否为素数的方法。（3）编写通过将正整数n对2,3,…,n逐个取模，判断其是否为素数的方法。（4）输入待判断的正整数n。（5）分别执行上述实现的3个方法，并获取各自的运行时间。（6）改变n的规模（n=100、10000和1000000），并重复执行上述3个方法，分析每次的运行时间，计算算法的时间复杂度。实验内容

综合实验2多种方式求素数33实验代码58

defPrintOut(self):59

n=input("请输入待判断的正整数n：")60

n=int(n)61

t1=time.perf_counter()62

self.one(n)63

t2=time.perf_counter()64

self.two(n)65

t3=time.perf_counter()66

self.three(n)67

t4=time.perf_counter()68

print("\n（4）分别执行上述实现的3个方法，并获取各自的运行时间")69

print("第1种方法的运行时间为{0:}s".format(t2-t1))70

print("第2种方法的运行时间为{0:}s".format(t3-t2))71

print("第3种方法的运行时间为{0:}s".format(t4-t3))1.3习题解答34一、选择题1~5DBCDC【解析】1.数据元素可由若干个数据项组成。参考主教材P2。2.元素和元素之间可能存在一对一、一对多等关系。参考主教材P3。3.逻辑结构反映数据元素之间的逻辑关系，线性结构表示数据元素之间一对一的关系，非线性结构表示数据元素之间一对多或多对一的关系。可参考主教材P4。4.算法最终必须由硬件动作实现；算法就是为解决某一类问题而编写的程序；算法的可行性是算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步，即每个计算步都可以在有限时间内完成。可参考主教材P9。5.问题的规模和待处理数据的初态都会影响算法的时间复杂度。可参考主教材P10。1.3习题解答35二、填空题1．不可分割。【解析】参考主教材P2数据项的概念。2．集合、线性结构、树形结构、图状（或网状）结构。【解析】参考主教材P3数据的逻辑结构分类。3．顺序存储结构、链式存储结构、索引存储结构、哈希（或散列）存储结构。【解析】参考主教材P4~6数据的存储结构。4．有穷性、确定性、可行性、输入、输出。【解析】参考主教材P9。

5．临时变量、形参。【解析】参考主教材P13。1.3习题解答36二、编程题1．设计算法求解正整数n的阶乘，并分析其时间复杂度以及空间复杂度，例如n=10。（文件名：ex010603_01.py）。【解析】算法对应的代码仅含一个单重循环，因此时间复杂度为O(n)，所占用的存储空间为程序本身的空间和变量fn所占用的空间，即空间复杂度为O(1)。15

defPrintOut(self):16

fn=int(input("请输入需要求解阶乘的数n："))17

jc=118

foriinrange(1,fn+1):19

jc=jc*i20

print("n=",fn,"的阶乘为{0:}".format(jc))21

print("时间复杂度为O(n)")1.3习题解答37二、编程题2．已知序列1,2,3,5,8,…，要求设计算法求第20项的值，并分析其时间和空间复杂度。（文件名：ex010603_02.py）。【解析】算法对应的代码仅含一个单重循环，因此时间复杂度为O(n)，所占用的存储空间为程序本身的空间及变量a、变量b和变量c所占用的空间，即空间复杂度为O(1)。15

defPrintOut(self):16

a=117

b=218

foriinrange(1,18):19

c=a+b20

a=b21

b=c22

print("第20项的值为{0:}".format(c))23

print("时间复杂度为O(n)")1.3习题解答38二、编程题3．设计算法求解1!+2!+3!+…+n!的和，并分析其时间复杂度，例如n=10（文件名：ex010603_03.py）。【解析】算法对应的代码仅含一个单重循环，因此时间复杂度为O(n)。15

defPrintOut(self):16

n=int(input("请输入n的值："))17

jc=118

sum=019

foriinrange(1,n+1):20

jc=jc*i21

sum=sum+jc22

print("1!+...+{:0}！={:1}".format(n,sum))23

print("时间复杂度为O(n)")1.3习题解答39二、编程题

1.3习题解答40二、编程题5．设计算法求解1!+2!+3!+…+n!的和，要求仅使用单重循环控制循环的次数，同时用于计算当前数的阶乘（记下此值用于计算下一个数的阶乘），输出最终的结果并计算该算法的时间复杂度，例如n=10（文件名：ex010603_05.py）。【解析】由于题目要求仅使用单重循环，故算法对应的代码仅含一个单重循环，因此时间复杂度为O(n)。16

defPrintOut(self):17

n=int(input("请输入n的值："))18

jc=119

sum=020

foriinrange(1,n+1):21

jc=jc*i22

sum=sum+jc23

print("1!+...+{:0}！={:1}".format(n,sum))24

print("时间复杂度为O(n)")1.3习题解答41二、编程题6．设计算法获取输入的n个数据中的最大值，要求输入一组数据使时间复杂度为算法的最好时间复杂度，例如n=10（文件名:ex010603_06.py）。【解析】算法对应的代码包含两个单重循环，第一个单重循环用于获取输入的n个数据，若输入的数据第一个为最大的，则在第二个单重循环中，就只会执行第25行的if语句，而不会执行第26行的代码，这样可以获得最好的时间复杂度。16

defPrintOut(self):17

n=int(input("请输入n的值："))18

num=input("请输入{0:}个整数，每个数字以空格分隔：".format(n))19

num=num.split()20

len=num.__len()21

foriinrange(0,len):22

num[i]=int(num[i])23

max=num[0]24

foriinrange(1,len):25

ifmax<num[i]:26

max=num[i]27

print("最大值为{0:}".format(max))1.3习题解答42二、编程题7．设计算法获取输入的n个数据中的最大值，要求输入一组数据使时间复杂度为算法的最坏时间复杂度，例如n=10（文件名:ex010603_07.py）。【解析】算法采用插入排序的思路，此时如果输入时将较小的值放在前面，较大的值放在后面，则需要多次执行第28和第29行代码，从而导致最坏的时间复杂度。16

defPrintOut(self):17

n=int(input("请输入n的值："))18

num=input("请输入{0:}个整数，每个数字以空格分隔：".format(n))19

num=num.split("")20

num_len=num._len_()21

list=[0foriinrange(0,num_len+1)]22

foriinrange(0,num_len):23

list[i+1]=int(num[i])#list[0]空出用于存放哨兵(插入排序算法)24

foriinrange(2,len(list)):25

list[0]=list[i]26

index=i27

whilelist[index-1]<list[0]:28

list[index]=list[index-1]29

index=index-130

list[index]=list[0]31

print("最大值为{0:}".format(list[1]))1.3习题解答43二、编程题

17

defPrintOut(self):18

n=int(input("请输入n的值："))19

jc=120

print("当n={0:}时：\n".format(n))21

foriinrange(1,n+1):22

print("log2{0:}={1:}".format(i,log(i,2)))23

print("sqrt({0:})={1:}".format(i,sqrt(i)))24

print("{0:}={1:}".format(i,i))25

print("{0:}log2{1:}={2:}".format(i,i,i*log(i,2)))26

print("{0:}²={1:}".format(i,i**2))27

print("{0:}³={1:}".format(i,i**3))28

print("power(2,{0:})={1:}".format(i,2**i))29

jc=jc*i30

print("{0:}!={1:}\n".format(i,jc))1.3习题解答44二、编程题9．设计算法对输入的n个数据从小到大进行排序，要求输入一组数据使时间复杂度为算法的最好时间复杂度，例如n=10（文件名：ex010603_09.py）。【解析】关键看输入的数据是否需要执行第27~29行代码。16

defPrintOut(self):17

n=int(input("请输入n的值："))18

temp=019

num=input("请输入{0:}个整数，每个数字以空格分隔：".format(n))20

num=num.split("")21

len=num.__len__()22

foriinrange(0,len):23

num[i]=int(float(num[i]))24

foriinrange(0,len-1):25

forjinrange(0,len-1-i):26

if(num[j]>num[j+1]):27

temp=num[j+1]28

num[j+1]=num[j]29

num[j]=temp30

print(num)1.3习题解答45二、编程题10．设计算法对输入的n个数据从小到大进行排序，要求输入一组数据使时间复杂度为算法的最坏时间复杂度，例如n=10（文件名：ex010603_10.py）。【解析】若输入的数据已经是从小到大的顺序，则时间复杂度最好，反之最坏31

defPrintOut(self):32

n=int(input("请输入n的值："))33

x=input("请输入{0:}个待排序整数，每个数字以空格分隔".format(n))34

y=x.split()35

arr=[]36

foriiny:37

arr.append(int(i))38

arr=self.InsertSort(arr)39

print("数列按序排列如下：")40

foriinarr:41

print(i,end='')ThankYou！人民邮电出版社2022年09月张光河guanghezhang@163.com46ISBN：978-7-115-56280-7数据结构实验指导与习题解答——Python语言描述张光河

主编guanghezhang@163.com人民邮电出版社2022年09月47ISBN：978-7-115-56280-7ISBN：978-7-115-56280-7ISBN：978-7-115-48577-9配套教材主教材主教材与配套教材48第二章线性表49习题解答2.3综合实验2.2基础实验2.1目录CONTENTS502.1基础实验512.1.1顺序表的基本操作基础实验1基础实验22.1.22.1.32.1.42.1.5单链表的基本操作循环单链表的基本操作双链表的基本操作循环双链表的基本操作基础实验3基础实验4基础实验5

基础实验1顺序表的基本操作52理解线性表的顺序存储结构，并掌握顺序表基本操作。实验目的实验内容创建一个名为ex020501_01.py的文件，在其中编写一个顺序表的类，该类必须包含顺序表的定义及基本操作，并通过以下步骤测试基本操作的实现是否正确。（1）初始化一个顺序表SL。（2）判断SL是否为空。（3）将元素2，5，16，55，8依次存入SL中。（4）输出SL中元素的个数。（5）获取SL中元素5的位置。（6）在元素5之后插入元素11。（7）删除值为16的元素。（8）将SL中元素依次输出。（9）销毁SL。531#############################################2#文件名：ex020501_01.py3#版本号：0.14#创建时间：2019-1-45#############################################6#############################################7#类名称：SequenceList8#类说明：定义一个顺序表SL9#类释义：创建一个顺序表SL，并对其执行相关操作。10############################################11classSequenceList(object):12

#####################################13

#初始化顺序表函数14

#####################################15

def__init__(self):16

self.SeqList=[]17

#####################################18

#创建顺序表函数19

#####################################20

defCreateSequenceList(self):21

print("---------------------------------------------------")22

print("请输入数据后按回车键确认，若想结束输入请按“#”。")23

print("---------------------------------------------------")24

Element=input("请输入元素：")25

whileElement!='#':实验代码5426

self.SeqList.append(int(Element))27

Element=input("请输入元素：")28

print("顺序表SL创建完成")29

#####################################30

#判断顺序表为空函数31

#####################################32

defIsEmpty(self):33

iflen(self.SeqList)==0:34

print("顺序表SL为空！")35

return136

else:37

print("顺序表SL不为空！",self.SeqList)38

#####################################39

#获取顺序表长度函数40

#####################################41

defGetLength(self):42

length=len(self.SeqList)43

print("顺序表SL中元素的个数为",length,"个")44

#####################################45

#查找表中某一元素函数46

#####################################47

defFindElement(self):48

key=int(input('请输入想要查找的元素值：'))49

ifkeyinself.SeqList:50

ipos=self.SeqList.index(key)5551

print("查找成功！值为",self.SeqList[ipos],"的元素，位于当前顺序表的第",ipos+1,"个位置。")52

else:53

print("查找失败！当前顺序表中不存在值为",key,"的元素")54

#####################################55

#定位插入元素函数56

#####################################57

defInsertElement(self):58

iPos=int(input('请输入待插入元素的位置：'))59

Element=int(input('请输入待插入的元素值：'))60

self.SeqList.insert(iPos,Element)61

print("成功插入元素",Element)62

#####################################63

#删除列表元素函数64

#####################################65

defDeleteElement(self):66

dElement=int(input('请输入需要删除元素的值：'))67

ifdElementinself.SeqList:68

dPos=self.SeqList.index(dElement)69

delself.SeqList[dPos]70

print("成功删除元素",dElement)71

else:72

print("顺序表中不存在该元素")73

#####################################74

#遍历顺序表函数75

#####################################5676

defTraverseElement(self):77

SeqListLen=len(self.SeqList)78

print("------------------遍历顺序表中元素------------------")79

foriinrange(0,SeqListLen):80

print("第",i+1,"个元素的值为",self.SeqList[i])81

#####################################82

#销毁顺序表函数83

#####################################84

defDestorySequenceList(self):85

delself.SeqList[:]86

print("顺序表已成功销毁！")87

#####################################88

#输出函数89

#####################################90

defPrintOut(self):91

print("*****************************************************")92

print("*******基础实验1实现顺序表的基本操作*******")93

print("\n（1）初始化顺序表SL：”,end="")94

try:95

self.__init__()96

print("顺序表SL初始化成功")97

except:98

print("顺序表SL初始化失败")99

print("\n（2）判断当前顺序表是否为空：”,end="")100

self.IsEmpty()57101

print("\n（3）创建顺序表SL")102

try:103

self.CreateSequenceList()104

exceptValueError:105

print("输入有误，请重新输入！")106

self.CreateSequenceList()107

print("\n（4）SL中元素的个数为：”,end="")108

try:109

self.GetLength()110

except:111

print("获取SL中元素个数出错！")112

print("\n（5）查找元素5所在位置")113

try:114

self.FindElement()115

except:116

print("查找元素5出错！")117

print("\n（6）在元素5后插入元素11")118

try:119

self.InsertElement()120

except:121

print("插入元素11出错！")122

print("\n（7）删除元素16")123

try:124

self.DeleteElement()125

except:58126

print("删除元素16出错！")127

print("\n（8）输出顺序表SL")128

try:129

self.TraverseElement()130

except:131

print("输出SL出错！”)132

print("\n（9）销毁线性表SL：”,end="")133

try:134

self.DestorySequenceList()135

except:136

print("销毁SL出错！”)137

print("*****************************************************")138if__name__=='__main__':139

SL=SequenceList()140

SL.PrintOut()注意：在上述代码中，我们在PrintOut()函数中调用初始化顺序表函数（__init__(self)）、判断顺序表是否为空（IsEmpty()）和创建顺序表（CreateSequenceList()）时使用了Python提供的异常处理代码（try......except），其目的是为了在发生错误时，及时捕获所产生的异常，并对其做出调整，以便程序更为稳定流畅的运行。在之后的例子中，由于篇幅的限制，调用其它函数时没有增加异常处理代码，请在实际编写代码时参照此实例加上。

基础实验2单链表的基本操作59理解单链表的链式存储结构，并掌握单链表的基本操作。实验目的实验内容创建名为ex020501_02.py的文件，在其中编写一个结点类，该类中必须包含结点的定义及初始化操作，再编写一个单链表类，该类中包含单链表的定义及基本操作。请通过以下步骤测试基本操作的实现是否正确（假定头结点所处位置为第0个位置）。（1）初始化一个单链表SLL。（2）判断SLL是否为空。（3）将值为33，24，231，3，11的结点依次链入SLL中。（4）获取SLL的长度。（5）将值为11的结点插入至SLL中第3个位置。（6）在SLL首端插入值为25的结点。（7）删除SLL中第4个位置的结点。（8）查找SLL中第3个位置结点的值。（9）遍历SLL中所有结点。601##################################################2#文件名：ex020501_02.py3#版本号：0.14#创建时间：2019-4-105##################################################6##################################################7#类名称：Node8#类说明：定义一个结点9#类释义：创建结点，并对结点进行初始化操作。10#################################################11classNode(object):12

#####################################13

#初始化结点函数14

#####################################15

def__init__(self,data):16

self.data=data17

self.next=None18#################################################19#类名称：SingleLinkedList20#类说明：定义一个单链表SLL21#类释义：创建一个单链表SLL，并对其执行相关操作。22#################################################23classSingleLinkedList(object):24

#####################################25

#初始化头结点函数实验代码6126

#####################################27

def__init__(self):28

self.head=Node(None)29

#####################################30

#创建单链表函数31

#####################################32

defCreateSingleLinkedList(self):33

print("---------------------------------------------------")34

print("请输入数据后按回车键确认，若想结束输入请按“#”。")35

print("---------------------------------------------------")36

cNode=self.head37

Element=input("请输入当前结点的值：")38

whileElement!='#':39

nNode=Node(int(Element))40

cNode.next=nNode41

cNode=cNode.next42

Element=input("请输入当前结点的值：")43

print("单链表SLL创建完成！")44

#####################################45

#判断单链表是否为空46

#####################################47

defIsEmpty(self):48

ifself.GetLength()==0:49

returnTrue50

else:6251

returnFalse52

#####################################53

#获取单链表长度函数54

#####################################55

defGetLength(self):56

cNode=self.head57

length=058

whilecNode.next!=None:59

length=length+160

cNode=cNode.next61

returnlength62

#####################################63

#在表中指定位置插入结点64

#####################################65

defInsertElement(self):66

Pos=067

cNode=self.head68

iPos=int(input('请输入待插入结点的位置：'))69

whilePos<iPos:70

cNode=cNode.next71

Pos=Pos+172

Element=int(input('请输入待插入结点的值：'))73

nNode=Node(int(Element))74

nNode.next=cNode.next75

cNode.next=nNode6376

print("结点",Element,"插入成功！")77

#####################################78

#在表中首端插入某一结点79

#####################################80

defInsertElementInHead(self):81

Element=int(input('请输入待插入结点的值：'))82

ifElement=="#":83

return84

cNode=self.head85

nNode=Node(int(Element))86

nNode.next=cNode.next87

cNode.next=nNode88

print("结点",Element,"插入成功！")89

#####################################90

#删除指定位置结点值91

#####################################92

defDeleteElement(self):93

Pos=094

cNode=self.head95

ifself.IsEmpty():96

print("当前单链表为空！")97

return98

dPos=int(input('请输入待删除结点的位置：'))99

whilePos<dPos:100

cNode=cNode.next64101

Pos=Pos+1102

pNode=cNode103

cNode=cNode.next104

pNode.next=cNode.next105

delcNode106

print("成功删除第",dPos,"个位置的结点！")107

#####################################108

#在表中查找某一指定结点109

#####################################110

defFindElement(self):111

Pos=0112

cNode=self.head113

sPos=int(input('请输入想要查找的结点位置：'))114

whilePos<sPos:115

cNode=cNode.next116

Pos=Pos+1117

key=cNode.data118

print("查找成功！第",Pos,"个位置的结点值为",key)119

#####################################120

#遍历单链表函数121

#####################################122

defTraverseElement(self):123

cNode=self.head124

ifcNode.next==None:125

print("当前单链表为空！")65126

return127

print("您当前的单链表为：")128

whilecNode!=None:129

cNode=cNode.next130

self.VisitElement(cNode)131

#####################################132

#输出单链表某一元素函数133

#####################################134

defVisitElement(self,tNode):135

iftNode!=None:136

print(tNode.data,"->",end="")137

else:138

print("None")139

#####################################140

#输出函数141

#####################################142

defPrintOut(self):143

print("*****************************************************")144

print("*********基础实验2实现单链表的基本操作*********")145

print("\n（1）初始化单链表SLL：”,end="")146

try:147

self.__init__()148

print("单链表SLL初始化成功！")149

except:150

print("单链表SLL初始化失败！")66151

print("\n（2）判断当前单链表是否为空：”,end="")152

ifself.IsEmpty():153

print("当前链表为空！")154

else:155

print("当前链表不为空！")156

print("\n（3）创建单链表SLL")157

try:158

self.CreateSingleLinkedList()159

exceptValueError:160

print("输入有误，请重新输入！”)161

self.CreateSingleLinkedList()162

print("\n（4）单链表SLL中元素的个数为",end="")163

try:164

sum=self.GetLength()165

print(sum)166

except:167

print("获取SLL中结点个数出错！")168

print("\n（5）将值为11的结点插入至SLL中的第3个位置")169

try:170

self.InsertElement()171

except:172

print("插入结点18出错！")173

print("\n（6）在SLL首端插入值为25的结点")174

try:175

self.InsertElementInHead()67176

except:177

print("插入结点25出错！")178

print("\n（7）删除SLL中第4个位置的结点")179

try:180

self.DeleteElement()181

except:182

print("删除结点出错！")183

print("\n（8）查找SLL中第3个位置结点的值")184

try:185

self.FindElement()186

except:187

print("查找出错！”)188

print("\n（9）遍历SLL中的所有结点：”)189

try:190

self.TraverseElement()191

except:192

print("遍历SLL出错！”)193

print("*****************************************************")194if__name__=='__main__':195

SLL=SingleLinkedList()196

SLL.PrintOut()

基础实验3循环单链表的基本操作68理解循环单链表的链式存储结构，并掌握循环单链表的基本操作。实验目的实验内容创建名为ex020501_03.py的文件，在其中编写一个结点类，该类中必须包含结点的定义及初始化操作，再编写一个循环单链表类，该类中包含循环单链表的定义及基本操作。请通过以下步骤测试基本操作的实现是否正确（假定头结点所处位置为第0个位置）。（1）初始化一个循环单链表CSLL。（2）判断CSLL是否为空。（3）将值为60，41，43，78，85的结点依次链入CSLL中。（4）将值为49的结点插入至CSLL中第3个位置。（5）在CSLL末端插入值为66的结点。（6）删除CSLL中值为78的结点。（7）查找值为66的结点的位置。（8）遍历CSLL中所有结点。691##################################################2#文件名：ex020501_03.py3#版本号：0.14#创建时间：2019-4-105##################################################6##################################################7#类名称：Node8#类说明：定义一个结点9#类释义：创建结点，并对结点进行初始化操作。10#################################################11classNode(object):12

#####################################13

#初始化结点函数14

#####################################15

def__init__(self,data):16

self.data=data17

self.next=None18#################################################19#类名称：CircularSingleLinkedList20#类说明：定义一个循环单链表CSLL21#类释义：创建一个循环单链表CSLL，并对其执行相关操作。22#################################################23classCircularSingleLinkedList(object):24

#####################################25

#初始化头结点函数实验代码7026

#####################################27

def__init__(self):28

self.head=Node(None)29

#####################################30

#创建循环单链表函数31

############