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

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

978-7-115-56280-7

计算机及相关专业考研考博课程

计算机等级考试课程

程序员考试课程 编程基础学习数据结构的重要性2提前预习、认真听课、按时完成书面及上机作业先修课程的知识准备离散数学、Python语言着重掌握基本概念、基本思想、基本步骤、算法设计

提高算法设计的能力理解所讲算法、对此多做思考若问题要求不同，

应如何设计有效的算法课程特点内容抽象、概念性强、

内容灵活、不易掌握课程学习指导3•了解数据结构研究的主要内容•

掌握数据结构中涉及的基本概念•

掌握算法、算法的时间复杂度及其分析的简易方法教学目标4第1章

绪论5基础实验综合实验习题解答1.11.2

1.3录目C

O

N

T

E

N

T

S61.1.1

基础实验1

分析算法的时间和空间复杂度1.1.2

基础实验2

设计算法并讨论其时间复杂度1.

1基础实验7考察是否能够正确地理解算法的时间和空间复杂度的概念，

并能否计算出下列给定算法的时间和空间复杂度

。实验内容计算出下列

3

个算法的时间和空间复杂度

。实验代码1

#

#

#

#

#

#

#

#

#

#

#

#

#

#

#

#

#

#

#

#

#

#

#

#

#

#

#

#

2

#

算法

一：

简单输出3

#

#

#

#

#

#

#

#

#

#

#

#

#

#

#

#

#

#

#

#

#

#

#

#

#

#

#

#4

def

Fun

1(

self

):5

i

=

06

pr

in

t(

"

hello

wor

ld

！

"

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

目

的81

############################2#算法二：单重循环3

############################4defFun2(self,n)

:5

k=06

fori

inrange(0,n)

:7

k=k+i1

############################2#算法三：双重循环3

############################4def

Function(self,n)

:5

k=06

fori

inrange(1,n)

:7forjinrange(1,i+1)

:8

k=i*j9

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

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

ex010501_

02

.

py

的文件

，

在其中设计多个操作（包括无

循环

、

单重循环和双重循环）

，

体会算法的时间复杂度这一概念

。

通

过以下步骤完成本实验

。1．

实现无循环的方法（

1

）简单地编写一个输出自

己姓名和学号的语句

。（2）

计算该方法的时间复杂度

。2．

实现单重循环的方法（1

）利用单重循环求解正整数

1

～n

的和

。（2）

计算该方法的时间复杂度

。3．

实现双重循环的方法（

1

）利用双重循环输出九九乘法表

。（2）

计算该方法的时间复杂度

。通过设计算法直观感知其时间复杂度

，

从而进一步理解算法

的时间复杂度的概念

，

并能够计算出对应的时间复杂度

。实验内容基础实验2设计算法并讨论其时间复杂度实验

目

的101#########################################2#文件名：

ex010501_02.py3#版本号：0.14#创建时间：2019-1-135#########################################6classLoopCom(object)

:7################################8#实现无循环的方法9################################10

defNoLoop

(self)

:11name="张三"12id="20190113"13

print("\n1.实现无循环的方法")14print("（1）简单地编写一个输出自己姓名和学号的语句。")15print("姓名为{0:}，学号为{1:}".format(name,id))16

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

。")

17

################################18#实现单重循环的方法19

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

defOneLoop

(self)

:21sum=022

n=1023for

i

inrange(1,n+1)

:24sum=sum+i25

print("\n2.实现单重循环的方法")实验代码1126print("（~1

）利用单重循环求解正整数

1~10

的和。")27print("

110

的和为{0:}".format(sum))28print("（2）该算法的时间复杂度为O(n)

。")29################################30#实现双重循环的方法31################################32defDoubleLoop

(self)

:33print("\n3.实现双重循环的方法")34print("（1）利用双重循环输出九九乘法表。")35

for

i

inrange(1,10)

:36for

j

in

range(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

def

PrintOut(self)

:44

self.NoLoop

()45

self.OneLoop

()46self.DoubleLoop

()47

if__name__=='__main__'

:48

LC=

LoopCom()49

LC.PrintOut()12综合实验1综合实验21.2.11.2.21.2综合实验多种方式求素数多种方式求和13同一种环境下运行后的绝对时间

，

深入地体会算法的时间

复杂度

。实验背景以多种方式求解正整数

1

～n

的和

，

通过对比这些方式在综合实验1多种方式求和实验

目

的14综合实验1多种方式求和实验内容1550

def

PrintOut(self)

:51

n=int(input("请输入n

的值：

"))52print("\n（1）编写将正整数1，2，...

，

",n,"逐个进行累加的方法。")53

t2=self.Calculate(n)

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

t4=self.Formula(n)56print("\n（5）

比较（2）和（4）

中的绝对时间。")57self.CompareTime(t2,t4)综合实验1多种方式求和实验代码16我们知道判断一个正整数n

是否为素数的方法是通过计

算该正整数是否只能被

1

和其本身整除

。

当设计如何判

断正整数n

是否为素数的算法时

，

我们可以将n

对正整

数

2

,

3

,

…

,

n

-1

逐个进行取模

，

若结果均不为

0

，

则

n

为素数；

也可以将n

对正整数

2

,

3

,

…

,

2n逐个进行取

模

，

若结果均不为

0

，

则

n

为素数；

也可以将

n

对正整

数

2

,

3

,

…

,

n逐个进行取模

，

若结果均不为

0

，

则

n

为

素数

。

这

3

种方法对素数的判断进行了逐步改进

，

需重

复取模

，

比较的次数也变得越来越少

。以多种方式判断某个正整数

n（n>1）

是否为素数

，

通

过对比这些方式在同一种环境下运行后的绝对时间

，

深

入地体会算法的时间复杂度

。实验背景综合实验2多种方式求素数实验

目

的17创建名为

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多种方式求素数实验内容1858

def

PrintOut(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()66self.three(n)67

t4=time.perf_counter()68print("\n（4）分别执行上述实现的3个方法，并获取各自的运行时间")69print("第1种方法的运行时间为{0:}s".format(t2-t1))70print("第2种方法的运行时间为{0:}s".format(t3-t2))71print("第3种方法的运行时间为{0:}s".format(t4-t3))综合实验2多种方式求素数实验代码19一、选择题1~5

DBCDC【解析】1.数据元素可由若干个数据项组成。

参考主教材P2。2.元素和元素之间可能存在一对一、一对多等关系。

参考主教材P3。3.逻辑结构反映数据元素之间的逻辑关系，线性结构表示数据元素之间

一对一的关系，非线性结构表示数据元素之间一对多或多对一的关系。可参考主教材P4。4.算法最终必须由硬件动作实现；

算法就是为解决某一类问题而编写的

程序；

算法的可行性是算法中执行的任何计算步骤都是可以被分解为基本

的可执行的操作步，

即每个计算步都可以在有限时间内完成。可参考主教材P9。5.

问题的规模和待处理数据的初态都会影响算法的时间复杂度。

可参考主教材P10。1.3

习题解答20二、填空题1．

不可分割。【解析】参考主教材P2数据项的概念。2．集合、线性结构、树形结构、

图状（或网状）结构。【解析】参考主教材P3数据的逻辑结构分类。3．顺序存储结构、链式存储结构、索引存储结构、哈希（或散列）存储结构。~【解析】参考主教材P4

6数据的存储结构。4．有穷性、确定性、可行性、输入、输出。【解析】参考主教材P9。5．

临时变量、形参。【解析】参考主教材P13。1.3

习题解答2115

def

PrintOut(self)

:16

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

"))17

jc=118

for

i

inrange(1,fn+1)

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

print("时间复杂度为O(n)")二、编程题1．

设计算法求解正整数n

的阶乘，并分析其时间复杂度以及空间复杂度，

例如n=10

。（文件名：

ex010603_01.py）。【解析】算法对应的代码仅含一个单重循环，

因此时间复杂度为O(n)，所占用的存储空间为程序本身的空间和变量fn所占用的空间，

即空间复

杂度为O(1)。1.3

习题解答2215

def

PrintOut(self)

:16

a=117

b=218

for

i

in

range(1,18)

:19

c=a+b20

a=b21b=c22print("第20项的值为{0:}".format(c))23

print("时间复杂度为O(n)")二、编程题2．

已知序列1,2,3,5,8,

…

，要求设计算法求第20项的值，并分析其时间和空间复杂度。（文件名：

ex010603_02.py）。【解析】算法对应的代码仅含一个单重循环，

因此时间复杂度为O(n)，所占用的存储空间为程序本身的空间及变量a、变量b和变量c所占用的

空间，

即空间复杂度为O(1)。1.3

习题解答2315

def

PrintOut(self)

:16

n=int(input("请输入n

的值：

"))17

jc=118

sum=019

for

i

inrange(1,n+1)

:20

jc=jc*i21

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

print("时间复杂度为O(n)")二、编程题3．

设计算法求解

1!+2!+3!+…+n!的和，并分析其时间复杂度，例如n=10

（文件名：

ex010603_03.py）。【解析】算法对应的代码仅含一个单重循环，

因此时间复杂度为O(n)。1.3

习题解答241.3

习题解答二、编程题252616

def

PrintOut(self)

:17

n=int(input("请输入n

的值：

"))18

jc=119

sum=020

for

i

inrange(1,n+1)

:21

jc=jc*i22

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

print("时间复杂度为O(n)")二、编程题5．

设计算法求解

1!+2!+3!+…+n!的和，要求仅使用单重循环控制循环的

次数，

同时用于计算当前数的阶乘（记下此值用于计算下一个数的阶乘），

输出最终的结果并计算该算法的时间复杂度，例如n=10（文件名：ex010603_05.py）。【解析】

由于题目要求仅使用单重循环，故算法对应的代码仅含一个单重

循环，

因此时间复杂度为O(n)。1.3

习题解答16

def

PrintOut(self)

:17

n=int(input("请输入n

的值：

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

".format(n))19

num=num.split()20

len=num.__len

()21

for

i

in

range(0,len)

:22

num[i]=int(num[i])23max=num[0]24

for

i

in

range(1,len)

:25

ifmax<num[i]

:26

max=num[i]27print("最大值为{0:}".format(max))二、编程题6．

设计算法获取输入的n个数据中的最大值，要求输入一组数据使时间

复杂度为算法的最好时间复杂度，例如n=10（文件名:ex010603_06.py）。【解析】算法对应的代码包含两个单重循环，第一个单重循环用于获取输

入的n个数据，若输入的数据第一个为最大的，则在第二个单重循环中，就只会执行第25行的if语句，而不会执行第26行的代码，这样可以获得

最好的时间复杂度。1.3

习题解答816

def

PrintOut(self)

:17n=int(input("请输入n

的值：

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

".format(n))19

num=num.split("")20

num_len=num._len_

()21

list=[0for

i

inrange(0,num_len+1)]22

for

i

inrange(0,num_len)

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

for

i

in

range(2,len(list))

:25

list[0]=list[i]26

index=i27while

list[index-1]<list[0]

:28

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

index=index-130

list[index]=list[0]31print("最大值为{0:}".format(list[1]))二、编程题7．

设计算法获取输入的n个数据中的最大值，要求输入一组数据使时间复杂度为

算法的最坏时间复杂度，例如n=10（文件名:ex010603_07.py）。【解析】算法采用插入排序的思路，此时如果输入时将较小的值放在前面，较大的

值放在后面，则需要多次执行第28和第29行代码，从而导致最坏的时间复杂度。1.3

习题解答17

def

PrintOut(self)

:18

n=int(input("请输入n

的值：

"))19

jc=120print("当n=

{0:}时：

\n".format(n))21

for

i

inrange(1,n+1)

:22print("log2

{0:}=

{1:}".format(i,log

(i,2)))23

print("sqrt({0:})=

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

{0:}=

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

print("

{0:}log2

{1:}=

{2:}".format(i,i,i*log

(i,2)))26print("

{0:}²=

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

{0:}³=

{1:}".format(i,i**3))28print("power(2,

{0:})=

{1:}".format(i,2**i))29jc=jc*i30print("

{0:}

!=

{1:}\n".format(i,jc))1.3

习题解答二、编程题defPrintOut(self)

:n=int(input("请输入n

的值：

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

".format(n))

num=num.split("")len=num.

len

()for

i

in

range(0,len)

:num[i]=int(float(num[i]))for

i

in

range(0,len-1)

:for

j

in

range(0,len-1-i)

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

:

print(num)二、编程题9．

设计算法对输入的n个数据从小到大进行排序，要求输入一组数据使时间

复杂度为算法的最好时间复杂度，例如n=10（件名：

ex010603_09.py）

。

【解析】关键看输入的数据是否需要执行第27

29行代码。1.3

习题解答16171819202122232425262728293031

def

PrintOut(self)

:32

n=int(input("请输入n

的值：

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

y=x.split()35arr=

[]36

for

i

in

y:37

arr.append(int(i))38

arr=self.InsertSort(arr)39print("数列按序排列如下：

")40

for

i

in

arr:41

print(i,end='')二、编程题10．

设计算法对输入的n个数据从小到大进行排序，要求输入一组数据使时间

复杂度为算法的最坏时间复杂度，例如n=10（文件名：

ex010603_10.py）。【解析】若输入的数据已经是从小到大的顺序，则时间复杂度最好，反之最坏1.3

习题解答31第二章

线性表32基础实验综合实验习题解答2.12.2

2.3录目C

O

N

T

E

N

T

S332.1.12.1.22.1.32.1.5

基础实验5

循环双链表的基本操作基础实验2单链表的基本操作基础实验3基础实验42.

1基础实验基础实验1循环单链表的基本操作双链表的基本操作顺序表的基本操作2.1.434创建一个名为

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

。理解线性表的顺序存储结构

，

并掌握顺序表基本操作

。实验内容基础实验1顺序表的基本操作实验

目

的351#############################################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)

:21print("---------------------------------------------------")22print("请输入数据后按回车键确认，若想结束输入请按“#

”。")23print("---------------------------------------------------")24Element=input("请输入元素：

")25

whileElement!='#'

:实验代码3626self.SeqList.append(int(Element))27Element=input("请输入元素：

")28print("顺序表SL创建完成")29#####################################30#判断顺序表为空函数31#####################################32def

IsEmpty

(self)

:33

if

len(self.SeqList)==0

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

136else

:37

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

38#####################################39#获取顺序表长度函数40#####################################41defGetLength(self)

:42length=len(self.SeqList)43print("顺序表SL

中元素的个数为",length,"个")

44#####################################45#查找表中某一元素函数46#####################################47defFindElement(self)

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

key

in

self.SeqList

:50ipos=self.SeqList.index(key)3751print("查找成功！值为",self.SeqList[ipos],"的元素，位于当

前顺序表的第",ipos+1,"个位置。")52else

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

54#####################################55#定位插入元素函数56#####################################57

defInsertElement(self)

:58iPos=int(input('请输入待插入元素的位置：'))59Element=int(input('请输入待插入的元素值：'))60

self.SeqList.insert(iPos,Element)61print

("成功插入元素",Element)62#####################################63#删除列表元素函数64#####################################65defDeleteElement(self)

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

ifdElementin

self.SeqList

:68

dPos=self.SeqList.index(dElement)69delself.SeqList[dPos]70print("成功删除元素",dElement)71else

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

73#####################################

74#遍历顺序表函数75#####################################

3876defTraverseElement(self)

:77

SeqListLen=len(self.SeqList)78

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

for

i

inrange(0,SeqListLen)

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

81#####################################82#销毁顺序表函数83#####################################84defDestorySequenceList(self)

:85

del

self.SeqList[:]86print("顺序表已成功销毁！")87#####################################88#输出函数89#####################################90

defPrintOut(self)

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

print("\n（1）初始化顺序表SL：

”,end="")94

try

:95

self.__init__

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

except

:98print("顺序表SL初始化失败")99print("\n（2）判断当前顺序表是否为空：

”,end="")100

self.IsEmpty

()39101

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

try

:103

self.CreateSequenceList()104exceptValueError

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

self.CreateSequenceList()107

print("\n（4）SL

中元素的个数为：

”,end="")108

try

:109

self.GetLength()110except

:111print("获取SL

中元素个数出错！")112

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

try

:114

self.FindElement()115except

:116print("查找元素

5

出错！")117

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

11")118

try

:119self.InsertElement()120except

:121

print("插入元素

11

出错！")122

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

16")123

try

:124

self.DeleteElement()125except

:40126

print("删除元素

16

出错！")127

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

try

:129

self.TraverseElement()130except

:131

print("输出SL

出错！”)132

print("\n（9）销毁线性表SL：

”,end="")133

try

:134

self.DestorySequenceList()135except

:136

print("销毁SL

出错！”)137print("*****************************************************")138

if__name__=='__main__'

:139SL=SequenceList()140

SL.PrintOut()注意：在上述代码中，我们在PrintOut()函数中调用初始化顺序表函数（

init

(self)）、判断顺序表是否为空（IsEmpty

()）和创建顺序表（CreateSequenceList()）时使用了Python提供的异常处理代码（try......except），其目的是为了在发生错误时，及时捕获所产生的异常，

并对其做出调整，

以便程序更为稳定流畅的运行。在之后的例子中，

由于篇

幅的限制，调用其它函数时没有增加异常处理代码，请在实际编写代码时参

照此实例加上。41创建名为

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

中所有结点

。理解单链表的链式存储结构

，

并掌握单链表的基本操作

。实验内容基础实验2单链表的基本操作实验

目

的421##################################################

2#文件名：

ex020501_02.py3#版本号：0.14#创建时间：2019-4-105##################################################

6##################################################7#类名称：Node8#类说明：

定义一个结点9#类释义：创建结点，并对结点进行初始化操作。10#################################################11classNode(object)

:12#####################################

13#初始化结点函数14#####################################15

def__init__

(self,data)

:16self.data=

data17

self.next=None18#################################################

19#类名称：SingleLinkedList20#类说明：

定义一个单链表SLL21#类释义：创建一个单链表SLL，并对其执行相关操作。

22#################################################

23class

SingleLinkedList(object)

:24#####################################

25#初始化头结点函数实验代码4326#####################################27def

__init__

(self)

:28self.head=Node(None)29#####################################30#创建单链表函数31#####################################32

defCreateSingleLinkedList(self)

:33print("---------------------------------------------------")34print("请输入数据后按回车键确认，若想结束输入请按“#

”。")35print("---------------------------------------------------")36

cNode=self.head37Element=

input("请输入当前结点的值：

")38

whileElement!='#'

:39nNode=Node(int(Element))40cNode.next=

nNode41cNode

=

cNode.next42Element=

input("请输入当前结点的值：

")43

print("单链表SLL创建完成！")44#####################################45#判断单链表是否为空46#####################################47defIsEmpty

(self)

:48ifself.GetLength()==0

:49returnTrue50else

:4451

returnFalse52#####################################53#获取单链表长度函数54#####################################55defGetLength(self)

:56

cNode=

self.head57

length=

058

while

cNode.next

!=None

:59

length=

length

+

160cNode

=

cNode.next61return

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

defInsertElement(self)

:66

Pos

=

067

cNode=

self.head68

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

whilePos

<

iPos

:70cNode

=

cNode.next71

Pos

=Pos

+

172Element=

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

nNode=Node(int(Element))74nNode.next=

cNode.next75

cNode.next=

nNode4576print("结点",Element,"插入成功！")77#####################################78#在表中首端插入某一结点79#####################################80defInsertElementInHead(self)

:81Element=

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

"#"

:83

return84

cNode=

self.head85

nNode=Node(int(Element))86

nNode.next=

cNode.next87

cNode.next=

nNode88print("结点",Element,

"插入成功！")89#####################################

90#删除指定位置结点值91#####################################92defDeleteElement(self)

:93

Pos

=

094

cNode=

self.head95

if

self.IsEmpty

()

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

return98

dPos=

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

whilePos

<

dPos

:100

cNode=

cNode.next46101

Pos

=Pos

+

1102

pNode

=

cNode103

cNode=

cNode.next104pNode.next=

cNode.next105

del

cNode106print("成功删除第",dPos,

"个位置的结点！")

107#####################################108#在表中查找某一指定结点109#####################################110defFindElement(self)

:111

Pos

=

0112cNode=

self.head113

sPos=

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

whilePos

<

sPos

:115cNode

=

cNode.next116

Pos

=Pos

+

1117key=

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

119#####################################120#遍历单链表函数121#####################################122defTraverseElement(self)

:123cNode=

self.head124

if

cNode.next==None

:125print("当前单链表为空！")47126return127

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

")128

while

cNode

!=None

:129cNode

=

cNode.next130

self.VisitElement(cNode)131#####################################132#输出单链表某一元素函数133#####################################134

defVisitElement(self,tNode)

:135

if

tNode

!=None

:136

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

else

:138print("None")139#####################################140

#输出函数141#####################################142

defPrintOut(self)

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

print("\n（1）初始化单链表SLL：

”,end="")146

try

:147

self.__init__

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

:150print("单链表SLL初始化失败！")48151print("\n（2）判断当前单链表是否为空：

”,

end="")152

ifself.IsEmpty

()

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

else

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

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

try

:158self.CreateSingleLinkedList()159exceptValueError

:160print("输入有误，请重新输入！”)161self.CreateSingleLinkedList()162

print("\n（4）单链表SLL

中元素的个数为",end="")163

try

:164sum=

self.GetLength()165

print(sum)166except

:167print("获取SLL

中结点个数出错！")168

print("\n（5）将值为

11

的结点插入至SLL

中的第3个位置")169

try

:170self.InsertElement()171except

:172

print("插入结点

18

出错！")173

print("\n（6）在SLL首端插入值为25

的结点")174

try

:175

self.InsertElementInHead()49176except

:177

print("插入结点25

出错！")178

print("\n（7）删除SLL

中第4个位置的结点")179

try

:180

self.DeleteElement()181except

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

print("\n（8）查找SLL

中第3个位置结点的值")184

try

:185

self.FindElement()186except

:187print("查找出错！”)188