数据结构课程设计说明书

行兽机科学马枝木数研宦

课程设计说明书

设计1:线性表

1、设计1目的

掌握线性表的存储结构，熟练使用线性表结构进行问题求解。

2、设计1正文

2.1实验内容

题目一：编写一个简单的学生成绩管理程序，每个学生记录包含学号、姓名、课程和分

数成员，采用顺序表存储，完成以下基本功能。并在此基础上自主增加其他功能，例如增加、

修改、查询功能等。

①屏幕显示所有学生记录。

②输入一个学生记录

③按学号和课程删除一个学生记录

④按学号排序并输出所有学生记录。

⑤按课程排序，对于一门课程，学生按分数递减排序。

题目二：编写一个实验程序实现以下功能：

①从文本文件xyz.txt中读取3行整数，每行的整数递增排列，两个整数之间用一个空

格分隔，全部整数的个数为n,这n个整数均不相同。

②求这n个整数中第k（lwkwn）小的整数。

题目三、由l~n（例如10000000）的n个整数建立顺序表a（采用列表表示）和带头结

点的单链表h,编写个实验程序输出分别将所有元素逆置的时间。

以上程序须采用异常处理机制，以确保程序能够正常运行。

2.2实验分析

题目一：学生信息管理

设计一个主菜单函数存放功能信息，编写函数实现添加学生信息、显示学生信息、删除

学生信息、修改学生信息、分别以年龄和成绩为关键词从低到高显示学生信息……编写类方

法在主函数调用实现相应为功能。

题目一：求n个整数的第n小整数

首先设计一个顺序表类，新建一个列表用来存储从文件中读取出来的三段数据，通过

topk()函数进而实现遍历每段从找到第K小的元素，在主函数中进行实现。

题目三：所有元素逆置的时间

引入time库实现时间的计算，对于元素的逆置顺序表a采用从两头交换的方式进行元

素逆置如：

i,j=0,len(a)-l

whilei<j:#两头交换

a[i],a[j]=aULa[i]

U=i+lJ-l

定义类方法记录开始时间和结束时间，单链表的实现也是如此。创建列表来存储顺序表

方式元素逆置的时间，单族表存储元素逆置的时间，两种都以保留两位小数的形式输出。

2.3实验结果与测试

题目一测试：

题目二结果：

月，[],，＞7)

m|e,j"•:“j

I91sMWFH，⑵10.12.7JJ

WN

.7小伪

题目三结果：成功运行

求稣结果

顺序表逆置时加卜1.28

4随&现置时何12.26

I

3、设计1总结

通过编写一个简单的学生成绩管理程序进行录入、查询、修改、删除学生信息等等，

进一步地熟悉函数的使用，能够进行一些基础的函数构造，编写一些方法进行函数功能的实

现。对文件操作的使用更加深刻，借助。pen()函数打开文件，没有则创建一个新的文件，

定义文件的访问方式只读、可编、追加等等，打开文件后获得一个对象，通过其属性获取文

件的各种信息，对文件操作完毕借助close()关闭文件。以本题为例包含异常处理：

•-13,1,9,8,5,6,2,7]

print，

printC

■、i7.L.•个壑

j:closest(a,x)1

print(-0接近％d的第lk：W\n位Ha【W】•%(xJra(jJ))

jsclosestta,x)

printsWCxJ.afj]))

此外还新学了如何使用顺序表和带头结点的单链表进行元素逆置并获取操作时间，加深

了如何引用并使用库。

元素逆置的函数构造，迷用单链表和顺序表两种形式完成，如图所示：

defreversel(a)：m太

tl=ti«e.tine()i»*”小时

i.j-9,len(a)*i

while1<j:«r、工2次

•Hh«Xj]■al：],ali)

i.i»i*l,j-1

,2•ti««U儿.KACS町叼

return_4,：

defreverse?(h):ir

tl=tiae.tiaeO

P=h.next

h.next■None

whilep!•None:

q■p.next

p.next■h.ntxt

h.next■p

P•Q

t2•tiae.ti»«()

rtturnt2-tl

针对木题目一首先进行主菜单编写，将具有的功能事先一一声明出来，学生信息的录入、

修改、删除、显示、保存等等。借助函数来实现这些功能，主函数内进行实际的程序操作，

通过输入的选项数字选择实现对学生信息的加工处理，例如：输入1,将会进行对学生信息

的录入操作，程序自动查找文件进行编写，当学生信息全部编写完成时对下一输入姓名enter

即可。注意除了输入9会攻变打开文件的数据外，其他的选项操作都不能更改文件数据。

defnain()：

student.info«()

)whileTrue:

•print($tu(Jent_info)

Mun()

nu・b”"・人也“：-)

ifnumber>•>.7if；,

•()

•litnueber”2:

sho»_(stud«nt_info)tfi!(>71f•<•

elifnuaber。3・：力上「州@「

try:

student.lnfore«ove(())

•xceptExceptionas•:

print(e)

•lifnoaber

ttud«nt)1.ttuden(itud«)

•MC«ptExceptionat•：

题目二结果：

(1)8-14遇队

'(2)人头=8

■(3)出队3次，

>出队无火=8

|出队近点=9

出从无，=1。

(5)出队所仆几木

出队元家二11

出从元京=12

出队元素=13

出队同*=14

题目三:

sl:Vi«kai

s2:pinji«

*2:的长l«：6

sl=>«3

s3:liekai

slfus2aft=>s4

s4:liekaipinjie

»4[2..5]=>s5

s5:«kaip

s4'l*FrV2RIMXs2=>s6

s6：lipln]ieekaipinjie

S6'I'K»[2<3]=>«7

s7:lijietkaipinjle

s6l'(2.3)HM^cl=>s8

>8:lili«kaijieekaipin}ie

3、设计2总结

通过设计并完成对栈、队、串的基本操作运算我明白自己还有很多地方是不懂的，虽然

在算法数据结构课程上学习了基本的数据结构的知识，但是并没有进行过手动的实质性操作,

未能及时掌握并巩固知识，通过这次课程设计让自己算是好好的进行了一番自我查找错误，

自我进行一次深度的学习这方面的知识，能够进行一些基本的串插入、串连接、求子串、特

殊位置插入其他串及取找顶元素和队列、找输出。

针对这三个题目•依旧是采用定义类方法形式进行操作完成队栈、队列、字符串的基本

操作运算，当用到某一项基本运算时直接调用类对象的方式得到想要实现的功能。对于栈来

说，有判断栈是否为空、进栈、出栈、取得栈顶元素这些基本操作，学习数据结构明白栈的

进栈出栈那是在栈顶进行，所以出栈顺序会依据情况而定。以1234顺序进栈，先让12进栈

再出栈，3进栈再出栈，4进栈在出栈，得到出栈结果为2134。这显然体现栈的特点是先进

后出，而队列则与之相反是先进先出。队列的基本运算与栈相似，有进队、出队、判断队列

是否为空、取队首元素，不同的是借助队尾指针rear进行实现。题目二中建立一个单链表

采用队列完成队列的基本操作，初始化链队尾结点rear为None,元素进队判断是否为空，

s.next=self.rear.next完成添加队列元素。字符串的学习使用让我更明白串连接和串插

入和串复制，能够进行一些小代码编写。除此之外，能够设置串的编号、求某一编号位置的

字符，求子串等等，队栈、队、列有了进一步的认识。

栈的基本操作功能函数：

八“sSqStack:

self.data■(J»Clkt«C

GH•3”(3。1千)：丁—“

iflen(»tlf,o«ta)••e：

returnTrut

rtturnFalse

defpush(s«lfr<):•<••,

self.data.append(•)

d«fpop(M\f):■H、

・s“rtnotself.e«pty()«*A.,；>■

returnself.data.pop()<--hA

defg«ttop(tt\f)：f..：h4

•sstrtnotselfU

returnself.data(\en(self.d«tai-1J*

队列的基本操作功能函数:

cUnSqStack:

self.d«t«•C・〃-M

6"eapty(teVf)：s?林人【,力

s«lf,f«ir.Noneif“e：

MptyCteXf)：•rtturnTrue

returnself.r««r>■nonertturnFalse

defpu$h(telfre)：4

,•linii*od«(«)•Mg”.。,self.Oeta.append(•)

if“tf.rt"••Nona:"、I,dttpop(Mif)：0lAftn

notself.euptyOtth

«tlf.rear•srtturnself.data.pop()r人匕/入

•lie:；def4

rt«r•isertnoti«Xf.»«ptY()«*v.*j,

wtfrearrwtvmw\f.o«x«(\vn(%«\rO4t«)-1)*,

字符串的功能函数:

s=Sqstring()»k*tr•个♦：：

asserti>=eandi<self.sizeandj>6andi*j<=self,size«fZwVft

forkinrange(i)：s\.Td«ta(fl..i-lj->s

s.data[k]=self.datajk]

forkinrange(i*j,self.size):«»rniilOata(i*j..size-lJ->s

s.data[k-j]=self.data[k]

s.size=self.size-j

returns«ii；''

defRepStr(self,i,j,t):«r?'f；；

s=Sqstrin9()si；J：个彳尸

asserti>=6and"self.sizeandj>8andi«j<=self.sizes-

07

forkinrange(i):«：；；.Idata(O..i-lj->s

，”().»世卜工，中

.”・rtl>«0andJs.data[k)=sel.f.data[k]

for)"ranged):*：forkinranged.getsizeO)：B^$.data[8..t.size-1J->s

s.st.mwt•⑴

s.data[i*k]>t.data[k]

forjinr«nQ«(t.9tt»Ue())：»»ft.d«t*(l,.iize-lj->s

forkinrange(i»j,self.size):»b.size-lj->s

«or1inr>n9«(i,self.size)：«.data(t.getsize()*k-jj=self.data(kj

.»ize»j)aself.d«ta(j)

s.»iz»s$elf.size-j»t.9etsize()

设计3：树与二叉树

1、设计3目的

掌握树的存储结构，熟练使用树遍历算法进行问题求解。

2、设计3正文

2.1实验内容

题目一：假设一颗非空二叉树中的结点值为整数，所有结点值均不同。编写一个实验，给

出该二义树的先序序列pres和中序序列ins,构造该二叉树的二叉链存储结构，再给出其

中两个不同的结点值x和y,输出这两个结点的所有公共祖先结点，采用相关数据进行测试。

（对于二叉链bt中两个不同的结点值x和y,用alor列表存放它们的所有公共祖先结点，

先求出它们的最近公共祖先结点，求出后置find为True,当退回到t结点时若find为true,

说明结点t时公共祖先结点,将t.data添加到atorzhong.zuihou返回atoro）

题目二：假设二.义树采用二叉链存储结构，所有结点值为单个字符口不相同。编写一个实

验，用三种方法按层次顺序输出一棵二叉树中的所有结点，并且用相关数据进行测试。

（采用层次遍历，难点是如何确定每一层结点访问完。）

题目三：编写一个实验程序，构造哈夫曼树和哈夫曼编码，要求输出建立的哈夫曼树和相

关哈夫曼编码。

2.2实验分析

题目一：由先序序列和中序序列找到二叉树，再设计一个方法将x,y的公共祖先求出放

到列表al"中，分别从左右了树中去查看是否左右了树含有x,y的结点值，同时考虑做右

子树是否相等以免有遗漏，找到离他们最近的公共祖先，将find=Truc,将数据插入到ator

的末尾。

题目二：第一种用ent变量计算每一层的所有结点个数。设计队列中的2个元素属性

lev（结点层次）和node（结点引用），crul（层数）遍历将所求得的数据放在str中并输出结果。

第二种采取迭代思路遍历每一层的最右节点last判断是否将每一层的节点访问完全。

第三种从第一层开始，在访问一层的全部结点后到下一层，循环往复。

题目三：哈大曼树和哈大曼编码引用堆heapq,借助其中的heappop。和heappush。从而

进行弹出元素和添加元素，将二叉树的左子树置0右子树置1,从底层将最小的数加和比他

俩次小的数加和，如此循环往复得到一颗哈夫曼树并形成哈夫曼编码。

2.3实验结果与测试

题目一:

bt；2(13(9,12(8)),5(3(1(18),4(7]),11(,6)))

(1)7W1。的场“公”机先：(3,5,2)

(2)6川7的所，|公式川丸：[5,21

(3)9付4的所“公式"先：(21

(4)1。和7的，“公小机先5,21

Process.通"-ith,xit'皿

题目二：

结果：

bt:A(B(D(,G)),C(E,F))

求解结果

「解法「

P第1层站点：1

=笫2了结点.2

第3层站点:3

第4次结点，1

解法2：

第1乂结点।1

第2层结点।2

第3层拈点，3

第4展站点,1

解法3,

第1层站点,1

第2乂结点,2

第3瓜结点,3

第4层站点,1

题目三测试：

输入：D=['a','b','c','d','e','f','g','h']

W=[1,2,3,4:5,6,7,8]

结果:

：\Us«r»\OtLL\AppD«t«\loc«l\Pro9re«s\Fvtbon\PythonM-32\pytbon

(2)■附哈人V

0(1)

«(i)

910ie111212911J315M

parent

r2356

Ichild-1-

rchild-1'

(3)比)电人*9%

(Q9出哈夫*

•:11110

b：111H

c：mo

d:100

•：iei

f:lie

3、设计3总结

对于树这三个问题的学习掌握了怎样去用代码实现已知先序和中序来求二叉树,

Crot«8Treei(prcs,ins)：

Z■BTrwO

■,Cre«teBTre«l(pr»».o.ins

IEurobt

g，.CreateBTret1(prts,i,ins.j,n)

d•pz4⑴

t•BTMod«(4)

p•ins.lnd«R(d)

・0•，

t.Uhll4■.CrMteSTr«*l(pr«s,I•1.1M.j,*)・

t.rcMlf■.CrwtttTrttKprtt.I•k•1,Ins.p•1,nk-1)

retvrnt

根据求得的二叉树再进一步去求任意两个的公共祖先，熟悉了使用层次遍历实现对每一

层的结点数的求解，具体了解哈夫曼树和哈夫曼编码，设计一个优先队列heap按照权值越

小越优先出队nO个叶子结点和nOT个分支结点，每次heap出队两个结点，建立一个新的

结点ht[i]表示他俩的双亲，求这两个的双亲结点的权值并将权值进队heap,最后在输出。

对于二叉链bt中两个不同的结点值x和y,用ator列表存放它们的所有公共祖先结点，先

求出它们的最近公共祖先结点，求出后置find为True,当退I可到t结点时若find为true,

说明结点t时公共祖先结点,将t.data添加到atorzhong.zuihou返回ator。

CA(M,1(7*y7r_■

‘find

•tor«世则巾分从..

.CA(bt.b,x,y.ator)

『•tornator

:d"x,y,ator):

gl血Ifind

“tisHone:returnNone

Kat*xort.data•・y：

rtturnt

•.CA(t.lcMXd,x.y,ator)

MgM•.CA(t.rctiild,x,y.ator)

§ifleftand7的t:

find«True

ator.append(t.0«ta)

returnt

7ifleftisnotNone:

”find：ator.app«n0(t.data)

returnleft

.ifrightisnotMe♦:

iffind：ator.append(t.data)

returnright

层次遍历对一层的结点访问完后，在按照它们的访问次序对各个结点的左右孩子顺序访

问，这样一层层进行，即先访问结点的左、右孩子，又因为和队列相似所以采用双端队列

deque实现普通队列。先将根结点b进队，在队不空时循环：从队列中出队一个结点p,访

问它：若它有左孩子结点，将做孩子进队；若它有右孩子，将右孩子结点进队，直到队空为

止。

构造哈夫曼树的合并裸作是将两个根结点权值最小的二叉树进行合并，为此设计一个优

先队列heap,heap中的每个元素为列表[w,i],其中i为ht中对应结点的索引，w为该结点

的权值，he”默认为最小根堆,出队时自动按w越小越优先出队。

defCr«at«HT(seVf)：二：卜世村

globalht.nO,0,・®•*Q,.<、，：人气•二'i.«

ht•(None)*(2*n01)比2r»e・l1J：,，'的《f

h“p■()”，入物(人为[■,11・一*—枇的

for1inrange(ne)：0AMs公•U

ht(i).MTNode(0(iLW(i))•.'itAA

heapq.heappush(he«p,(W(iLi))»^(W(iLi]i认

for1inrange(nO,2*n01):«iM.nOr2n02(nO-1.1>•「

pl■heapq.heappop(beap)•U■(&“.pl•p2

p2•heapq.heappop(heap)

ht(i)»MTNodeO«.ht(x)

ht(i].weight•.weight*ht[p2(l]).««lflht。长—।

ht(pl(l)1.parent■Iant[£]

ht(i]Achi\d■Pld)®1P1'・(1Jif：i

ht(pl(l)1.flag■True

ht(p2(l)).parent-1，，2HP2♦ht('】

ht(i).rchlld•p2(l)—g-ht(*J

ht(p2(l)).«V«9•False

heapq.h«»ppush(he«p,(ht(1).wight.1))

构造好哈夫曼树ht后i从nO到2n0-2循环，从ht：i]结点向根结点查找路径并产生逆

向的哈夫曼树编码hcd[i],将hcd[i]逆置得到正向的哈夫曼树编码。哈夫曼编码创建及输出

的功能函数:

八31IK4

he4a(|

•Ml・M(J].2!•-1

1♦nt[9].・3：“”

c-

j•MlJJxrtnt*

co«».erw«ri«()»

641I

—•:,•hellIB

树这一章的学习让我明白如何构造二叉树，怎样去求每层结点数和给定k值层数的结点数,

还学会了哈夫曼树的构造和有哈夫曼树怎样得到某结点的哈夫曼编码。

设计4：图

1、设计4目的

(1)掌握图的存储结构，学会使用Python实现邻接表和邻接矩阵。、

(2)掌握图的深度优先、广度优先搜索算法，使用Python进行实现，并能使用它们解

决实际问题。

(3)学会使用普里姆算法或克鲁斯卡尔算法解决实际问题，并使用Python进行实现；

(4)学会使用迪杰斯特拉算法解决单源最短路径问题，学会使用弗洛伊德算法解决多源

最短路径问题，并使用Python进行实现。

2、设计4正文

2.1实验内容

题目一、迷宫求解。

一个迷宫由n行m列格子组成。有的格子是空地，可以走；有的格子处是障碍物，不

能走。小明准备从迷宫的某一格子(起点)走到另一个格子(终点)，假定他只可以朝.1二、

下、左、右四个方向移动，不能斜着走。每移动一个位置(格子)需要1分钟。给定迷宫和

小明的起点和终点，请编写程序计算小明从起点到终点最短需要花费多少时间。

题目二、征服游戏。

Conquer是一款桌面游戏，在这个游戏里，几个相互对立的玩家要灭掉对方的国家。游

戏板上分成很多假设的国家。当轮到一个玩家时，一个国家的军队只能攻击边界相连的敌对

国家。在征服一个国家之后，军队就可以移动到刚被征服的国家。在游戏期间，玩家通常要

征服一连串的国家，以便把大量军队从起始国家转移到目标国家。通常，玩家在选择要征服

路径上的国家时，尽量使要征服的国家数量最少。假定游戏板上有n个国家，编号为。至

n-l。

请编写程序，对于给定的起始国家和目标国家，计算到达目标国家至少需要征服多少个

国家，不必输出征服的国家序列，只输出征服的国家数量即可。例如下图所示的国家地图，

从起始国家。到目标国家4,最少需征服2个国家。

题目三、最短路径。

城市的道路四通八达，我们经常需要查找从某地出发到其他地方的路径，当然我仅希望

能最快到达。现得到去每个地方需要花费的时间，现请你编写程序，计算从特定地点出发到

所有城市之间的最短时间，

题目四、MST（最小生成树）。

PrimorKruskal'salgorithmisanalgorithmingraphtheorythatfindsaminimumspanning

treeforaconnectedundirectedweightedgraph.

普里姆算法或克鲁斯戈尔算法是图论中的重要算法。可以用来在无向有权图中寻找最小

生成树。

2.2实验分析

题目一：dfs+回溯求解

将矩阵外围以及路障统一设置为

设置currcnt_stcp和ncxt_stcp两个值。如果面临的点大于ncxt_stcp,或者从未走过，就

可以对它递归

存储矩阵：直接在原迷宫上修改，每个点标记的是从起点过来经过的步数，遇到。或者

是比当前大至少2的，就考察

题目四：用Prim算法算最小生成树的主要有两个重复过程：寻找一个满足条件的未插

入到生成树集合的结点；利用该结点更新其余顶点到生成树集合的最小权值信息。

2.3实验结果与测试

题目四:

A—BHft.ie

AT权侑，11

B—12

I—Cfeffl.8

B—GUffti16

G—7

G-19

H—16

su«=99

,0]

插入站点帔序，,'B','F\'

3、设计4总结

通过使用dfs和I可溯算法对迷宫进行求解，每次设置current_step和nexl_siep两个值。

如果面临的点大于ncxt_stcp,或者从未走过，就可以对它递归。用存储矩阵：直接在原迷

宫上修改，每个点标记的是从起点过来经过的步数，遇到0或者是比当前大至少2的，就考

察。使用prim算法每步按照最小权重的边添加到最小生成树中，当街点差入完全后这棵最

小生成树就完成创建。这次手动操作学习到了以后针对这种情况可是采取同样的策略去实现,

比以往更加对prim算法、回溯算法和深度优先遍历有进一步的认识针对什么问题可以去使

用，怎样去实现等等。

先设置迷宫整体，在进行回溯算法将要解决的问题化成图来表示借助深度优先遍历。

Graph表示迷宫，deepFirstSearch()函数完成初始位置的设定及以后对于下一步进行的操

作往左右前后哪个方向走，下图处理怎样走：

每次currcnjstcp会更新，对迷宫数组的数据进行修改用来存放所需的步数，最后输出

到指定位置所需的最小步数。

Prim算法找到最小生成树，先设计好prinigraph存放对应点位置的权值，chararray存

放将要插入的结点值，chWist口存放插进去后的结点，mid。］存放生成树中离i近的编号，

lowcost［i］表示生成树集合中与点i最近的点构成的边最小权值，-1表示i已经在生成树集中，

9forxinranged,n):xn-1?

ninid=e

min=MAX

forjinranged,n):»•,<

if(lowcost[j]!:-Landlowcost(:

minid=r?

min=lowcost!j)»小

charlistappend(chararray[minid))»<rj".

print(chararray[mid[ninidJJ^^—^chararraylBinidJ^^ftia*str(lowcost(ninid

su»*=minn,^ninid,，♦「；上；.

lowcost(minid]=-laI：；

forjinranged,n):lowcostfifll

if(lowcost(j]!：<andlowcost[j1>priwgraph[minidj(j))：

lowcost(j)=primgraph[ninid][j)

mid[j)=minid

上图实现对于完成最小生成树的添加结点的核心操作操作。

图的学习更加理解dfs深度优先搜索具体怎样去实现，当问题是要求满足某种性质（约束

条件）的所有解或最优解时，往往使用回溯法。对回溯算法应用有了更进一步的理解，学到

了可以使用回溯算法画成图或树的方式解决实际问题。

设计5：查找与排序

1、设计目的

掌握典型的查找和排序的方法，并用python语言实现。

2、设计正文

2.1实验内容

题目一：对于给定的一个无序整数数组a,求其中与x最接近的整数的位置，若有多个这样

的整数，返回最后一个整数的位置和数值。

题目二：给定一个序列，在给序列中运用折半查找的方法查找给定的数值，如果找到，请给

出杳找的路径（比较过的元素），如果没有找到，请输出明确信息。

题目三：给定•个序列，运用快速排序的思想对其进行升序排序，要求输出排序过程。

2.2实验分析

此部分写每个实验的实现过程，（也是编程思路），体现出具体方法的思路。可以附带关键

性语句。（按照三个题目一个一个的写）

题目一：最接近给出x值得数通过更新与所给出值得误差，逐渐变小接近得到

题目二：折半查找非递归算法，取区间中间位置，更新区间m