數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)與習(xí)題解答-python語(yǔ)言描述

數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)與習(xí)題解答——Python語(yǔ)言描述1ISBN：

978-7-115-56280-7

計(jì)算機(jī)及相關(guān)專(zhuān)業(yè)考研考博課程

計(jì)算機(jī)等級(jí)考試課程

程序員考試課程 編程基礎(chǔ)學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的重要性2提前預(yù)習(xí)、認(rèn)真聽(tīng)課、按時(shí)完成書(shū)面及上機(jī)作業(yè)先修課程的知識(shí)準(zhǔn)備離散數(shù)學(xué)、Python語(yǔ)言著重掌握基本概念、基本思想、基本步驟、算法設(shè)計(jì)

提高算法設(shè)計(jì)的能力理解所講算法、對(duì)此多做思考若問(wèn)題要求不同，

應(yīng)如何設(shè)計(jì)有效的算法課程特點(diǎn)內(nèi)容抽象、概念性強(qiáng)、

內(nèi)容靈活、不易掌握課程學(xué)習(xí)指導(dǎo)3?了解數(shù)據(jù)結(jié)構(gòu)研究的主要內(nèi)容?

掌握數(shù)據(jù)結(jié)構(gòu)中涉及的基本概念?

掌握算法、算法的時(shí)間復(fù)雜度及其分析的簡(jiǎn)易方法教學(xué)目標(biāo)4第1章

緒論5基礎(chǔ)實(shí)驗(yàn)綜合實(shí)驗(yàn)習(xí)題解答1.11.2

1.3錄目C

O

N

T

E

N

T

S61.1.1

基礎(chǔ)實(shí)驗(yàn)1

分析算法的時(shí)間和空間復(fù)雜度1.1.2

基礎(chǔ)實(shí)驗(yàn)2

設(shè)計(jì)算法并討論其時(shí)間復(fù)雜度1.

1基礎(chǔ)實(shí)驗(yàn)7考察是否能夠正確地理解算法的時(shí)間和空間復(fù)雜度的概念，

并能否計(jì)算出下列給定算法的時(shí)間和空間復(fù)雜度

。實(shí)驗(yàn)內(nèi)容計(jì)算出下列

3

個(gè)算法的時(shí)間和空間復(fù)雜度

。實(shí)驗(yàn)代碼1

#

#

#

#

#

#

#

#

#

#

#

#

#

#

#

#

#

#

#

#

#

#

#

#

#

#

#

#

2

#

算法

一：

簡(jiǎn)單輸出3

#

#

#

#

#

#

#

#

#

#

#

#

#

#

#

#

#

#

#

#

#

#

#

#

#

#

#

#4

def

Fun

1(

self

):5

i

=

06

pr

in

t(

"

hello

wor

ld

！

"

)基礎(chǔ)實(shí)驗(yàn)1分析算法的時(shí)間和空間復(fù)雜度實(shí)驗(yàn)

目

的81

############################2#算法二：?jiǎn)沃匮h(huán)3

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

:5

k=06

fori

inrange(0,n)

:7

k=k+i1

############################2#算法三：雙重循環(huán)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()基礎(chǔ)實(shí)驗(yàn)1分析算法的時(shí)間和空間復(fù)雜度9創(chuàng)建名為

ex010501_

02

.

py

的文件

，

在其中設(shè)計(jì)多個(gè)操作（包括無(wú)

循環(huán)

、

單重循環(huán)和雙重循環(huán)）

，

體會(huì)算法的時(shí)間復(fù)雜度這一概念

。

通

過(guò)以下步驟完成本實(shí)驗(yàn)

。1．

實(shí)現(xiàn)無(wú)循環(huán)的方法（

1

）簡(jiǎn)單地編寫(xiě)一個(gè)輸出自

己姓名和學(xué)號(hào)的語(yǔ)句

。（2）

計(jì)算該方法的時(shí)間復(fù)雜度

。2．

實(shí)現(xiàn)單重循環(huán)的方法（1

）利用單重循環(huán)求解正整數(shù)

1

～n

的和

。（2）

計(jì)算該方法的時(shí)間復(fù)雜度

。3．

實(shí)現(xiàn)雙重循環(huán)的方法（

1

）利用雙重循環(huán)輸出九九乘法表

。（2）

計(jì)算該方法的時(shí)間復(fù)雜度

。通過(guò)設(shè)計(jì)算法直觀感知其時(shí)間復(fù)雜度

，

從而進(jìn)一步理解算法

的時(shí)間復(fù)雜度的概念

，

并能夠計(jì)算出對(duì)應(yīng)的時(shí)間復(fù)雜度

。實(shí)驗(yàn)內(nèi)容基礎(chǔ)實(shí)驗(yàn)2設(shè)計(jì)算法并討論其時(shí)間復(fù)雜度實(shí)驗(yàn)

目

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

ex010501_02.py3#版本號(hào)：0.14#創(chuàng)建時(shí)間：2019-1-135#########################################6classLoopCom(object)

:7################################8#實(shí)現(xiàn)無(wú)循環(huán)的方法9################################10

defNoLoop

(self)

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

print("\n1.實(shí)現(xiàn)無(wú)循環(huán)的方法")14print("（1）簡(jiǎn)單地編寫(xiě)一個(gè)輸出自己姓名和學(xué)號(hào)的語(yǔ)句。")15print("姓名為{0:}，學(xué)號(hào)為{1:}".format(name,id))16

print("（2）該方法的時(shí)間復(fù)雜度為O(1)

。")

17

################################18#實(shí)現(xiàn)單重循環(huán)的方法19

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

defOneLoop

(self)

:21sum=022

n=1023for

i

inrange(1,n+1)

:24sum=sum+i25

print("\n2.實(shí)現(xiàn)單重循環(huán)的方法")實(shí)驗(yàn)代碼1126print("（~1

）利用單重循環(huán)求解正整數(shù)

1~10

的和。")27print("

110

的和為{0:}".format(sum))28print("（2）該算法的時(shí)間復(fù)雜度為O(n)

。")29################################30#實(shí)現(xiàn)雙重循環(huán)的方法31################################32defDoubleLoop

(self)

:33print("\n3.實(shí)現(xiàn)雙重循環(huán)的方法")34print("（1）利用雙重循環(huán)輸出九九乘法表。")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）該算法的時(shí)間復(fù)雜度為O(n^2)

。")

40################################41#輸出函數(shù)42################################43

def

PrintOut(self)

:44

self.NoLoop

()45

self.OneLoop

()46self.DoubleLoop

()47

if__name__=='__main__'

:48

LC=

LoopCom()49

LC.PrintOut()12綜合實(shí)驗(yàn)1綜合實(shí)驗(yàn)21.2.11.2.21.2綜合實(shí)驗(yàn)多種方式求素?cái)?shù)多種方式求和13同一種環(huán)境下運(yùn)行后的絕對(duì)時(shí)間

，

深入地體會(huì)算法的時(shí)間

復(fù)雜度

。實(shí)驗(yàn)背景以多種方式求解正整數(shù)

1

～n

的和

，

通過(guò)對(duì)比這些方式在綜合實(shí)驗(yàn)1多種方式求和實(shí)驗(yàn)

目

的14綜合實(shí)驗(yàn)1多種方式求和實(shí)驗(yàn)內(nèi)容1550

def

PrintOut(self)

:51

n=int(input("請(qǐng)輸入n

的值：

"))52print("\n（1）編寫(xiě)將正整數(shù)1，2，...

，

",n,"逐個(gè)進(jìn)行累加的方法。")53

t2=self.Calculate(n)

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

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

比較（2）和（4）

中的絕對(duì)時(shí)間。")57self.CompareTime(t2,t4)綜合實(shí)驗(yàn)1多種方式求和實(shí)驗(yàn)代碼16我們知道判斷一個(gè)正整數(shù)n

是否為素?cái)?shù)的方法是通過(guò)計(jì)

算該正整數(shù)是否只能被

1

和其本身整除

。

當(dāng)設(shè)計(jì)如何判

斷正整數(shù)n

是否為素?cái)?shù)的算法時(shí)

，

我們可以將n

對(duì)正整

數(shù)

2

,

3

,

…

,

n

-1

逐個(gè)進(jìn)行取模

，

若結(jié)果均不為

0

，

則

n

為素?cái)?shù)；

也可以將n

對(duì)正整數(shù)

2

,

3

,

…

,

2n逐個(gè)進(jìn)行取

模

，

若結(jié)果均不為

0

，

則

n

為素?cái)?shù)；

也可以將

n

對(duì)正整

數(shù)

2

,

3

,

…

,

n逐個(gè)進(jìn)行取模

，

若結(jié)果均不為

0

，

則

n

為

素?cái)?shù)

。

這

3

種方法對(duì)素?cái)?shù)的判斷進(jìn)行了逐步改進(jìn)

，

需重

復(fù)取模

，

比較的次數(shù)也變得越來(lái)越少

。以多種方式判斷某個(gè)正整數(shù)

n（n>1）

是否為素?cái)?shù)

，

通

過(guò)對(duì)比這些方式在同一種環(huán)境下運(yùn)行后的絕對(duì)時(shí)間

，

深

入地體會(huì)算法的時(shí)間復(fù)雜度

。實(shí)驗(yàn)背景綜合實(shí)驗(yàn)2多種方式求素?cái)?shù)實(shí)驗(yàn)

目

的17創(chuàng)建名為

ex010502_

02

.py

的文件

，

在其中編寫(xiě)判斷正整數(shù)n是否為素?cái)?shù)的程序

，

具體如下

。（1）

編寫(xiě)通過(guò)將正整數(shù)

n

對(duì)

2

,

3

,

…

,

n

-1

逐個(gè)取模

，

判斷其

是否為素?cái)?shù)的方法

。（2）

編寫(xiě)通過(guò)將正整數(shù)

n

對(duì)

2

,

3

,

…

,

2n逐個(gè)取模

，

判斷其是

否為素?cái)?shù)的方法

。（3）

編寫(xiě)通過(guò)將正整數(shù)

n

對(duì)

2

,

3

,

…

,

n逐個(gè)取模

，

判斷其是

否為素?cái)?shù)的方法

。（4）

輸入待判斷的正整數(shù)

n

。（5）

分別執(zhí)行上述實(shí)現(xiàn)的

3

個(gè)方法

，

并獲取各自的運(yùn)行時(shí)間

。（6）改變

n

的規(guī)模（n=100

、

10000

和

1000000）

，

并重復(fù)

執(zhí)行上述

3

個(gè)方法

，

分析每次的運(yùn)行時(shí)間

，

計(jì)算算法的時(shí)間復(fù)

雜度

。綜合實(shí)驗(yàn)2多種方式求素?cái)?shù)實(shí)驗(yàn)內(nèi)容1858

def

PrintOut(self)

:59

n=input("請(qǐng)輸入待判斷的正整數(shù)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）分別執(zhí)行上述實(shí)現(xiàn)的3個(gè)方法，并獲取各自的運(yùn)行時(shí)間")69print("第1種方法的運(yùn)行時(shí)間為{0:}s".format(t2-t1))70print("第2種方法的運(yùn)行時(shí)間為{0:}s".format(t3-t2))71print("第3種方法的運(yùn)行時(shí)間為{0:}s".format(t4-t3))綜合實(shí)驗(yàn)2多種方式求素?cái)?shù)實(shí)驗(yàn)代碼19一、選擇題1~5

DBCDC【解析】1.數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)項(xiàng)組成。

參考主教材P2。2.元素和元素之間可能存在一對(duì)一、一對(duì)多等關(guān)系。

參考主教材P3。3.邏輯結(jié)構(gòu)反映數(shù)據(jù)元素之間的邏輯關(guān)系，線(xiàn)性結(jié)構(gòu)表示數(shù)據(jù)元素之間

一對(duì)一的關(guān)系，非線(xiàn)性結(jié)構(gòu)表示數(shù)據(jù)元素之間一對(duì)多或多對(duì)一的關(guān)系?？蓞⒖贾鹘滩腜4。4.算法最終必須由硬件動(dòng)作實(shí)現(xiàn)；

算法就是為解決某一類(lèi)問(wèn)題而編寫(xiě)的

程序；

算法的可行性是算法中執(zhí)行的任何計(jì)算步驟都是可以被分解為基本

的可執(zhí)行的操作步，

即每個(gè)計(jì)算步都可以在有限時(shí)間內(nèi)完成?？蓞⒖贾鹘滩腜9。5.

問(wèn)題的規(guī)模和待處理數(shù)據(jù)的初態(tài)都會(huì)影響算法的時(shí)間復(fù)雜度。

可參考主教材P10。1.3

習(xí)題解答20二、填空題1．

不可分割?！窘馕觥繀⒖贾鹘滩腜2數(shù)據(jù)項(xiàng)的概念。2．集合、線(xiàn)性結(jié)構(gòu)、樹(shù)形結(jié)構(gòu)、

圖狀（或網(wǎng)狀）結(jié)構(gòu)?！窘馕觥繀⒖贾鹘滩腜3數(shù)據(jù)的邏輯結(jié)構(gòu)分類(lèi)。3．順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)、索引存儲(chǔ)結(jié)構(gòu)、哈希（或散列）存儲(chǔ)結(jié)構(gòu)。~【解析】參考主教材P4

6數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。4．有窮性、確定性、可行性、輸入、輸出?！窘馕觥繀⒖贾鹘滩腜9。5．

臨時(shí)變量、形參?！窘馕觥繀⒖贾鹘滩腜13。1.3

習(xí)題解答2115

def

PrintOut(self)

:16

fn=int(input("請(qǐng)輸入需要求解階乘的數(shù)n：

"))17

jc=118

for

i

inrange(1,fn+1)

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

print("時(shí)間復(fù)雜度為O(n)")二、編程題1．

設(shè)計(jì)算法求解正整數(shù)n

的階乘，并分析其時(shí)間復(fù)雜度以及空間復(fù)雜度，

例如n=10

。（文件名：

ex010603_01.py）?！窘馕觥克惴▽?duì)應(yīng)的代碼僅含一個(gè)單重循環(huán)，

因此時(shí)間復(fù)雜度為O(n)，所占用的存儲(chǔ)空間為程序本身的空間和變量fn所占用的空間，

即空間復(fù)

雜度為O(1)。1.3

習(xí)題解答2215

def

PrintOut(self)

:16

a=117

b=218

for

i

in

range(1,18)

:19

c=a+b20

a=b21b=c22print("第20項(xiàng)的值為{0:}".format(c))23

print("時(shí)間復(fù)雜度為O(n)")二、編程題2．

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

…

，要求設(shè)計(jì)算法求第20項(xiàng)的值，并分析其時(shí)間和空間復(fù)雜度。（文件名：

ex010603_02.py）?！窘馕觥克惴▽?duì)應(yīng)的代碼僅含一個(gè)單重循環(huán)，

因此時(shí)間復(fù)雜度為O(n)，所占用的存儲(chǔ)空間為程序本身的空間及變量a、變量b和變量c所占用的

空間，

即空間復(fù)雜度為O(1)。1.3

習(xí)題解答2315

def

PrintOut(self)

:16

n=int(input("請(qǐng)輸入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("時(shí)間復(fù)雜度為O(n)")二、編程題3．

設(shè)計(jì)算法求解

1!+2!+3!+…+n!的和，并分析其時(shí)間復(fù)雜度，例如n=10

（文件名：

ex010603_03.py）?！窘馕觥克惴▽?duì)應(yīng)的代碼僅含一個(gè)單重循環(huán)，

因此時(shí)間復(fù)雜度為O(n)。1.3

習(xí)題解答241.3

習(xí)題解答二、編程題252616

def

PrintOut(self)

:17

n=int(input("請(qǐng)輸入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("時(shí)間復(fù)雜度為O(n)")二、編程題5．

設(shè)計(jì)算法求解

1!+2!+3!+…+n!的和，要求僅使用單重循環(huán)控制循環(huán)的

次數(shù)，

同時(shí)用于計(jì)算當(dāng)前數(shù)的階乘（記下此值用于計(jì)算下一個(gè)數(shù)的階乘），

輸出最終的結(jié)果并計(jì)算該算法的時(shí)間復(fù)雜度，例如n=10（文件名：ex010603_05.py）?！窘馕觥?/p>

由于題目要求僅使用單重循環(huán)，故算法對(duì)應(yīng)的代碼僅含一個(gè)單重

循環(huán)，

因此時(shí)間復(fù)雜度為O(n)。1.3

習(xí)題解答16

def

PrintOut(self)

:17

n=int(input("請(qǐng)輸入n

的值：

"))18num=input("請(qǐng)輸入{0:}個(gè)整數(shù)，每個(gè)數(shù)字以空格分隔：

".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．

設(shè)計(jì)算法獲取輸入的n個(gè)數(shù)據(jù)中的最大值，要求輸入一組數(shù)據(jù)使時(shí)間

復(fù)雜度為算法的最好時(shí)間復(fù)雜度，例如n=10（文件名:ex010603_06.py）。【解析】算法對(duì)應(yīng)的代碼包含兩個(gè)單重循環(huán)，第一個(gè)單重循環(huán)用于獲取輸

入的n個(gè)數(shù)據(jù)，若輸入的數(shù)據(jù)第一個(gè)為最大的，則在第二個(gè)單重循環(huán)中，就只會(huì)執(zhí)行第25行的if語(yǔ)句，而不會(huì)執(zhí)行第26行的代碼，這樣可以獲得

最好的時(shí)間復(fù)雜度。1.3

習(xí)題解答816

def

PrintOut(self)

:17n=int(input("請(qǐng)輸入n

的值：

"))18num=input("請(qǐng)輸入{0:}個(gè)整數(shù)，每個(gè)數(shù)字以空格分隔：

".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．

設(shè)計(jì)算法獲取輸入的n個(gè)數(shù)據(jù)中的最大值，要求輸入一組數(shù)據(jù)使時(shí)間復(fù)雜度為

算法的最壞時(shí)間復(fù)雜度，例如n=10（文件名:ex010603_07.py）?！窘馕觥克惴ú捎貌迦肱判虻乃悸?，此時(shí)如果輸入時(shí)將較小的值放在前面，較大的

值放在后面，則需要多次執(zhí)行第28和第29行代碼，從而導(dǎo)致最壞的時(shí)間復(fù)雜度。1.3

習(xí)題解答17

def

PrintOut(self)

:18

n=int(input("請(qǐng)輸入n

的值：

"))19

jc=120print("當(dāng)n=

{0:}時(shí)：

\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:}2=

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

{0:}3=

{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

習(xí)題解答二、編程題defPrintOut(self)

:n=int(input("請(qǐng)輸入n

的值：

"))temp=0num=input("請(qǐng)輸入{0:}個(gè)整數(shù)，每個(gè)數(shù)字以空格分隔：

".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．

設(shè)計(jì)算法對(duì)輸入的n個(gè)數(shù)據(jù)從小到大進(jìn)行排序，要求輸入一組數(shù)據(jù)使時(shí)間

復(fù)雜度為算法的最好時(shí)間復(fù)雜度，例如n=10（件名：

ex010603_09.py）

。

【解析】關(guān)鍵看輸入的數(shù)據(jù)是否需要執(zhí)行第27

29行代碼。1.3

習(xí)題解答16171819202122232425262728293031

def

PrintOut(self)

:32

n=int(input("請(qǐng)輸入n

的值：

"))33x=input("請(qǐng)輸入{0:}個(gè)待排序整數(shù)，每個(gè)數(shù)字以空格分隔".format(n))34

y=x.split()35arr=

[]36

for

i

in

y:37

arr.append(int(i))38

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

")40

for

i

in

arr:41

print(i,end='')二、編程題10．

設(shè)計(jì)算法對(duì)輸入的n個(gè)數(shù)據(jù)從小到大進(jìn)行排序，要求輸入一組數(shù)據(jù)使時(shí)間

復(fù)雜度為算法的最壞時(shí)間復(fù)雜度，例如n=10（文件名：

ex010603_10.py）?！窘馕觥咳糨斎氲臄?shù)據(jù)已經(jīng)是從小到大的順序，則時(shí)間復(fù)雜度最好，反之最壞1.3

習(xí)題解答31第二章

線(xiàn)性表32基礎(chǔ)實(shí)驗(yàn)綜合實(shí)驗(yàn)習(xí)題解答2.12.2

2.3錄目C

O

N

T

E

N

T

S332.1.12.1.22.1.32.1.5

基礎(chǔ)實(shí)驗(yàn)5

循環(huán)雙鏈表的基本操作基礎(chǔ)實(shí)驗(yàn)2單鏈表的基本操作基礎(chǔ)實(shí)驗(yàn)3基礎(chǔ)實(shí)驗(yàn)42.

1基礎(chǔ)實(shí)驗(yàn)基礎(chǔ)實(shí)驗(yàn)1循環(huán)單鏈表的基本操作雙鏈表的基本操作順序表的基本操作2.1.434創(chuàng)建一個(gè)名為

ex020501_

01

.py

的文件

，

在其中編寫(xiě)

一

個(gè)順序表的類(lèi)

，

該類(lèi)必須包含順序表的定義及基本操作，

并通過(guò)以下步驟測(cè)試基本操作的實(shí)現(xiàn)是否正確

。（1）

初始化一個(gè)順序表

SL

。（2）

判斷

SL

是否為空

。（3）

將元素

2

，

5

，

16

，

55

，

8

依次存入

SL

中

。（4）

輸出

SL

中元素的個(gè)數(shù)

。（5）獲取

SL

中元素

5

的位置

。（6）

在元素

5

之后插入元素

11

。（7）

刪除值為

16

的元素

。（8）

將

SL

中元素依次輸出

。（9）銷(xiāo)毀

SL

。理解線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)

，

并掌握順序表基本操作

。實(shí)驗(yàn)內(nèi)容基礎(chǔ)實(shí)驗(yàn)1順序表的基本操作實(shí)驗(yàn)

目

的351#############################################2#文件名：

ex020501_01.py3#版本號(hào)：0.14#創(chuàng)建時(shí)間：2019-1-45#############################################6#############################################7#類(lèi)名稱(chēng)：SequenceList8#類(lèi)說(shuō)明：

定義一個(gè)順序表SL9#類(lèi)釋義：創(chuàng)建一個(gè)順序表SL，并對(duì)其執(zhí)行相關(guān)操作。10############################################11classSequenceList(object)

:12#####################################13#初始化順序表函數(shù)14#####################################15

def__init__

(self)

:16

self.SeqList=[]17#####################################18#創(chuàng)建順序表函數(shù)19#####################################20

defCreateSequenceList(self)

:21print("---------------------------------------------------")22print("請(qǐng)輸入數(shù)據(jù)后按回車(chē)鍵確認(rèn)，若想結(jié)束輸入請(qǐng)按“#

”。")23print("---------------------------------------------------")24Element=input("請(qǐng)輸入元素：

")25

whileElement!='#'

:實(shí)驗(yàn)代碼3626self.SeqList.append(int(Element))27Element=input("請(qǐng)輸入元素：

")28print("順序表SL創(chuàng)建完成")29#####################################30#判斷順序表為空函數(shù)31#####################################32def

IsEmpty

(self)

:33

if

len(self.SeqList)==0

:34print("順序表SL為空！")35return

136else

:37

print("順序表SL不為空！",self.SeqList)

38#####################################39#獲取順序表長(zhǎng)度函數(shù)40#####################################41defGetLength(self)

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

中元素的個(gè)數(shù)為",length,"個(gè)")

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

:48key=int(input('請(qǐng)輸入想要查找的元素值：'))49if

key

in

self.SeqList

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

前順序表的第",ipos+1,"個(gè)位置。")52else

:53print("查找失?。‘?dāng)前順序表中不存在值為",key,"的元素")

54#####################################55#定位插入元素函數(shù)56#####################################57

defInsertElement(self)

:58iPos=int(input('請(qǐng)輸入待插入元素的位置：'))59Element=int(input('請(qǐng)輸入待插入的元素值：'))60

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

("成功插入元素",Element)62#####################################63#刪除列表元素函數(shù)64#####################################65defDeleteElement(self)

:66dElement=int(input('請(qǐng)輸入需要?jiǎng)h除元素的值：'))67

ifdElementin

self.SeqList

:68

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

:72print("順序表中不存在該元素")

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

74#遍歷順序表函數(shù)75#####################################

3876defTraverseElement(self)

:77

SeqListLen=len(self.SeqList)78

print("------------------遍歷順序表中元素------------------")79

for

i

inrange(0,SeqListLen)

:80print("第",i+1,"個(gè)元素的值為",self.SeqList[i])

81#####################################82#銷(xiāo)毀順序表函數(shù)83#####################################84defDestorySequenceList(self)

:85

del

self.SeqList[:]86print("順序表已成功銷(xiāo)毀！")87#####################################88#輸出函數(shù)89#####################################90

defPrintOut(self)

:91print("*****************************************************")92print("*******基礎(chǔ)實(shí)驗(yàn)1實(shí)現(xiàn)順序表的基本操作*******")93

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

”,end="")94

try

:95

self.__init__

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

except

:98print("順序表SL初始化失敗")99print("\n（2）判斷當(dāng)前順序表是否為空：

”,end="")100

self.IsEmpty

()39101

print("\n（3）創(chuàng)建順序表SL")102

try

:103

self.CreateSequenceList()104exceptValueError

:105print("輸入有誤，請(qǐng)重新輸入！")106

self.CreateSequenceList()107

print("\n（4）SL

中元素的個(gè)數(shù)為：

”,end="")108

try

:109

self.GetLength()110except

:111print("獲取SL

中元素個(gè)數(shù)出錯(cuò)！")112

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

try

:114

self.FindElement()115except

:116print("查找元素

5

出錯(cuò)！")117

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

11")118

try

:119self.InsertElement()120except

:121

print("插入元素

11

出錯(cuò)！")122

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

16")123

try

:124

self.DeleteElement()125except

:40126

print("刪除元素

16

出錯(cuò)！")127

print("\n（8）輸出順序表SL")128

try

:129

self.TraverseElement()130except

:131

print("輸出SL

出錯(cuò)！”)132

print("\n（9）銷(xiāo)毀線(xiàn)性表SL：

”,end="")133

try

:134

self.DestorySequenceList()135except

:136

print("銷(xiāo)毀SL

出錯(cuò)！”)137print("*****************************************************")138

if__name__=='__main__'

:139SL=SequenceList()140

SL.PrintOut()注意：在上述代碼中，我們?cè)赑rintOut()函數(shù)中調(diào)用初始化順序表函數(shù)（

init

(self)）、判斷順序表是否為空（IsEmpty

()）和創(chuàng)建順序表（CreateSequenceList()）時(shí)使用了Python提供的異常處理代碼（try......except），其目的是為了在發(fā)生錯(cuò)誤時(shí)，及時(shí)捕獲所產(chǎn)生的異常，

并對(duì)其做出調(diào)整，

以便程序更為穩(wěn)定流暢的運(yùn)行。在之后的例子中，

由于篇

幅的限制，調(diào)用其它函數(shù)時(shí)沒(méi)有增加異常處理代碼，請(qǐng)?jiān)趯?shí)際編寫(xiě)代碼時(shí)參

照此實(shí)例加上。41創(chuàng)建名為

ex020501_

02

.py

的文件

，

在其中編寫(xiě)一個(gè)結(jié)點(diǎn)類(lèi)，該類(lèi)中必須包含結(jié)點(diǎn)的定義及初始化操作

，

再編寫(xiě)一個(gè)單鏈表類(lèi)，

該類(lèi)中包含單鏈表的定義及基本操作

。請(qǐng)通過(guò)以下步驟測(cè)試基本

操作的實(shí)現(xiàn)是否正確（假定頭結(jié)點(diǎn)所處位置為第

0

個(gè)位置）

。（1）

初始化一個(gè)單鏈表

SLL

。（2）

判斷

SLL

是否為空

。（3）

將值為

33

，

24

，

231

，

3

，

11

的結(jié)點(diǎn)依次鏈入

SLL中

。（4）獲取

SLL

的長(zhǎng)度

。（5）

將值為

11

的結(jié)點(diǎn)插入至

SLL

中第

3

個(gè)位置

。（6）

在

SLL

首端插入值為

25

的結(jié)點(diǎn)

。（7）

刪除

SLL

中第

4

個(gè)位置的結(jié)點(diǎn)

。（8）

查找

SLL

中第

3

個(gè)位置結(jié)點(diǎn)的值

。（9）

遍歷

SLL

中所有結(jié)點(diǎn)

。理解單鏈表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

，

并掌握單鏈表的基本操作

。實(shí)驗(yàn)內(nèi)容基礎(chǔ)實(shí)驗(yàn)2單鏈表的基本操作實(shí)驗(yàn)

目

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

2#文件名：

ex020501_02.py3#版本號(hào)：0.14#創(chuàng)建時(shí)間：2019-4-105##################################################

6##################################################7#類(lèi)名稱(chēng)：Node8#類(lèi)說(shuō)明：

定義一個(gè)結(jié)點(diǎn)9#類(lèi)釋義：創(chuàng)建結(jié)點(diǎn)，并對(duì)結(jié)點(diǎn)進(jìn)行初始化操作。10#################################################11classNode(object)

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

13#初始化結(jié)點(diǎn)函數(shù)14#####################################15

def__init__

(self,data)

:16self.data=

data17

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

19#類(lèi)名稱(chēng)：SingleLinkedList20#類(lèi)說(shuō)明：

定義一個(gè)單鏈表SLL21#類(lèi)釋義：創(chuàng)建一個(gè)單鏈表SLL，并對(duì)其執(zhí)行相關(guān)操作。

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

23class

SingleLinkedList(object)

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

25#初始化頭結(jié)點(diǎn)函數(shù)實(shí)驗(yàn)代碼4326#####################################27def

__init__

(self)

:28self.head=Node(None)29#####################################30#創(chuàng)建單鏈表函數(shù)31#####################################32

defCreateSingleLinkedList(self)

:33print("---------------------------------------------------")34print("請(qǐng)輸入數(shù)據(jù)后按回車(chē)鍵確認(rèn)，若想結(jié)束輸入請(qǐng)按“#

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

cNode=self.head37Element=

input("請(qǐng)輸入當(dāng)前結(jié)點(diǎn)的值：

")38

whileElement!='#'

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

nNode41cNode

=

cNode.next42Element=

input("請(qǐng)輸入當(dāng)前結(jié)點(diǎn)的值：

")43

print("單鏈表SLL創(chuàng)建完成！")44#####################################45#判斷單鏈表是否為空46#####################################47defIsEmpty

(self)

:48ifself.GetLength()==0

:49returnTrue50else

:4451

returnFalse52#####################################53#獲取單鏈表長(zhǎng)度函數(shù)54#####################################55defGetLength(self)

:56

cNode=

self.head57

length=

058

while

cNode.next

!=None

:59

length=

length

+

160cNode

=

cNode.next61return

length62#####################################63#在表中指定位置插入結(jié)點(diǎn)64#####################################65

defInsertElement(self)

:66

Pos

=

067

cNode=

self.head68

iPos=int(input('請(qǐng)輸入待插入結(jié)點(diǎn)的位置：'))69

whilePos

<

iPos

:70cNode

=

cNode.next71

Pos

=Pos

+

172Element=

int(input('請(qǐng)輸入待插入結(jié)點(diǎn)的值：'))73

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

cNode.next75

cNode.next=

nNode4576print("結(jié)點(diǎn)",Element,"插入成功！")77#####################################78#在表中首端插入某一結(jié)點(diǎn)79#####################################80defInsertElementInHead(self)

:81Element=

int(input('請(qǐng)輸入待插入結(jié)點(diǎn)的值：'))82ifElement==

"#"

:83

return84

cNode=

self.head85

nNode=Node(int(Element))86

nNode.next=

cNode.next87

cNode.next=

nNode88print("結(jié)點(diǎn)",Element,

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

90#刪除指定位置結(jié)點(diǎn)值91#####################################92defDeleteElement(self)

:93

Pos

=

094

cNode=

self.head95

if

self.IsEmpty

()

:96print("當(dāng)前單鏈表為空！")97

return98

dPos=

int(input('請(qǐng)輸入待刪除結(jié)點(diǎn)的位置：'))99

whilePos

<

dPos

:100

cNode=

cNode.next46101

Pos

=Pos

+

1102

pNode

=

cNode103

cNode=

cNode.next104pNode.next=

cNode.next105

del

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

"個(gè)位置的結(jié)點(diǎn)！")

107#####################################108#在表中查找某一指定結(jié)點(diǎn)109#####################################110defFindElement(self)

:111

Pos

=

0112cNode=

self.head113

sPos=

int(input('請(qǐng)輸入想要查找的結(jié)點(diǎn)位置：'))114

whilePos

<

sPos

:115cNode

=

cNode.next116

Pos

=Pos

+

1117key=

cNode.data118print("查找成功！第",Pos,"個(gè)位置的結(jié)點(diǎn)值為",key)

119#####################################120#遍歷單鏈表函數(shù)121#####################################122defTraverseElement(self)

:123cNode=

self.head124

if

cNode.next==None

:125print("當(dāng)前單鏈表為空！")47126return127

print("您當(dāng)前的單鏈表為：

")128

while

cNode

!=None

:129cNode

=

cNode.next130

self.VisitElement(cNode)131#####################################132#輸出單鏈表某一元素函數(shù)133#####################################134

defVisitElement(self,tNode)

:135

if

tNode

!=None

:136

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

else

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

#輸出函數(shù)141#####################################142

defPrintOut(self)

:143print("*****************************************************")144print("*********基礎(chǔ)實(shí)驗(yàn)2實(shí)現(xiàn)單鏈表的基本操作*********")145

print("\n（1）初始化單鏈表SLL：

”,end="")146

try

:147

self.__init__

()148print("單鏈表SLL初始化成功！")149except

:150print("單鏈表SLL初始化失?。?)48151print("\n（2）判斷當(dāng)前單鏈表是否為空：

”,

end="")152

ifself.IsEmpty

()

:153print("當(dāng)前鏈表為空！")154

else

:155print("當(dāng)前鏈表不為空！")156

print("\n（3）創(chuàng)建單鏈表SLL")157

try

:158self.CreateSingleLinkedList()159exceptValueError

:160print("輸入有誤，請(qǐng)重新輸入！”)161self.CreateSingleLinkedList()162

print("\n（4）單鏈表SLL

中元素的個(gè)數(shù)為",end="")163

try

:164sum=

self.GetLength()165

print(sum)166except

:167print("獲取SLL

中結(jié)點(diǎn)個(gè)數(shù)出錯(cuò)！")168

print("\n（5）將值為

11

的結(jié)點(diǎn)插入至SLL

中的第3個(gè)位置")169

try

:170self.InsertElement()171except

:172

print("插入結(jié)點(diǎn)

18

出錯(cuò)！")173

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

的結(jié)點(diǎn)")174

try

:175

self.InsertElementInHead()49176except

:177

print("插入結(jié)點(diǎn)25

出錯(cuò)！")178

print("\n（7）刪除SLL

中第4個(gè)位置的結(jié)點(diǎn)")179

try

:180

self.DeleteElement()181except

:182print("刪除結(jié)點(diǎn)出錯(cuò)！")183

print("\n（8）查找SLL

中第3個(gè)位置結(jié)點(diǎn)的值")184

try

:185

self.FindElement()186except

:187print("查找出錯(cuò)！”)188