数据结构实验指导书(版本2)

1目录前言 (1)实验一一元稀疏多项式的计算 (2)实验二长整数四则运算 (18)实验三停车场管理 (40)实验四算术表达式求值 (59)实验五文学研究助手实验指导书 (71)实验六多维数组 (94)实验七哈夫曼编/译码器实验指导书 (119)实验八最短路径实验指导书 (138)实验九 B-树及图书管理实验指导书 (150)实验十内部排序算法比较实验指导书 (184)前言数据结构是软件开发的基础。

数据结构课程是软件工程、计算机科学与技术、网络工程、信息安全等专业的必修技术基础课程。

该课程是在学生学习高级语言程序设计课程基础上，使学生掌握各种常用数据结构的逻辑表示、存储表示、处理方法及应用算法设计，学会常用数据分类和数据查找的技术，对所设计的算法会做定量或定性的分析比较，培养学生的算法设计与分析的能力。

通过该课程的学习，使学生学会分析数据对象特性，选择合适的数据结构、存贮结构及相应的基本处理算法；初步掌握算法的时间空间复杂度分析技巧。

既为学生学习后继课程打好基础，也为将来软件开发提供理论指导。

数据结构具有很强的实践性，只有通过编程上机实验，才能真正领会数据结构的真正内涵，并灵活运用数据结构的基本知识提高自己的软件开发能力。

本数据结构实验选择了具有一定难度的实验项目10个，涉及到线性表、栈、队列、字符串、数据、二叉树、图、数据查找、数据排序等全部教学内容。

学生不一定完成全部实验内容，根据课程的学分不同，可以选择不同数目的实验。

一般而言，《数据结根A》可以选择其中3个实验，《数据结根B》可以选择其中两个实验。

鼓励学生多做实验，如果学生所做实验数目超过规定数据，可以加分。

本实验是以标准C语言为背景，以微型计算机为主要机型，实验用编程语言采用Turbo C 2.0，Borland C 3.0等以上版本。

为了使学生不仅掌握数据结构的一般原理，而且掌握具有一定实用性的程序的一般结构，实验指导书中给出了程序的总体框架和部分源程序代码，以及程序运行控制和交互式操作的基本方式。

通过程序总体框架，让学生学会如何组织程序。

通过对程序要解决的问题按功能进行分解，使学生逐步适应和学会运用抽象思维方式和模块化程序设计技术编写有一定规模、具有一定实用性的程序的能力。

编写数据结构实验指导书是对软件类课程的一个尝试。

我们将通过学生在实验过程中的反馈意见不断完善。

实验一 一元稀疏多项式的计算一、实验目的通过一元稀疏多项式的表示和计算，帮助学生熟练掌握线性表的基本操作，以及用线性链表表示线性表的存储结构和操作的实现。

二、实验内容实现一元稀疏多项式的如下运算：(1)两个一元稀疏多项式相加运算(2)两个一元稀疏多项式相减运算(3)两个一元稀疏多项式相乘运算三、实验原理1、一元多项式的逻辑表示一元多项式p n (x)可表示成:p n (x)=p 0+p 1x+p 2x 2+…+p n x nn+1个系数可用线性表来表示：p 0，p 1，p 2，…，p n ）其中每一项的指数i 隐含在其系数p i 的序号中。

一个一元多项式，如果其系数不为0的项相对于其多项式的次数（最大指数）而言要少得多，则称该一元多项式为一元稀疏多项式。

对一元稀疏多项式，若采用顺序存储结构，需n+1个元素单元存放系数。

当n 很大且为零的系数较多时，既浪费存储空间，又浪费运算时间。

如：s(x)=1+3x 10000+2x 20000采用顺序存储分配需20001个元素空间，但只有3个元素有意义。

若参与同数量级的加法运算，要运行2000次以上。

因此，对一元多项式采用链式存储结构是必然的选择。

上例的链表表示形式如图1-1所示。

p2、一元稀疏多项式的链式存储表示结点结构定义如下：typedef struct Item{double coef;图1-1：一元稀疏多项式的链表表示示意图3int expn;struct Item *next;}Item,*Polyn;3、一元稀疏多项式运算原理设有两个稀疏多项式A和B，其运算原理如下：（1）两个多项式相加(C=A＋B)的运算原则：指数相同，系数相加，若不为0，则在结果多项式中构成一新项。

指数不同，则两项分别抄入结果多项式中。

（2）两个多项式相减(C=A－B)的运算原则：指数相同，系数相减，若不为0，则构成一新项。

指数不同，对A多项式的项，直接抄入结果多项式中。

对B多项式的项，系数符号变换后，再将放入结果多项式中（3）两个多项式相乘(C=A×B)的运算原则用B多项式的每一项分别去乘A多项式的每一项，并将乘得得结果放入结果多项式中。

若结果多项式中有指数相同的项，则应把它们合并为一项。

四、实现1、约定使用带头结点的链表表示一元稀疏多项式。

（2）用线性链表表示的一元稀疏多项式中，各结点按指数的升序排列。

（3）每个多项式都独立存在，即参与运算的两个多项式的数据不能因运算而受到破坏，加、减、乘运算的结果应相互不受影响。

因此，对于每种情况都必须单独建立一个链表进行表示。

（4）每一种重复性的操作都要进行确认，以免破坏原有操作的结果。

如需要输入A多项式，而A多项式已经存在，这时通过“确认”后再确定是否真正需要输入。

2、基本功能(1)多项式的输入(2)两个一元稀疏多项式相加运算：P(x)+Q(x(3)两个一元稀疏多项式相减运算：P(x)－Q(x)(4)两个一元稀疏多项式相乘运算：P(x)×Q(x)(5)多项式打印3、辅助功能(1)菜单选择：将上述功能通过“菜单”形式罗列出来，通过菜单选择进行交互式控制程序运行。

4(2)插入结点位置查找：确定将一个新结点插入到多项式链表结构中的位置，以保证链表中结点按指数升序排列。

(3)交互选择：当出现重复性操作时，提供交互式选择方式，以确定其重复操作是否进行。

(4)撤消多项式：释放表示多项式链表中所有结点的存储空间。

(5)多项式项插入：将表示多项式中一项的结点插入到链表中给定的位置。

(6)判多项式非空：判断某个多项式是否存在。

(7)判断两个多项式的当前运算项的关系（指数大于，等于，小于）4、程序结构本程序可以由13个函数组成，其中主函数1个，基本功能函数5个，辅助功能函数7个。

函数间的调用关系图1-2所示。

图1-2：程序结构示意图5、程序函数（1）主函数：main功能：通过菜单选择控制对系统功能的操作（2）菜单选择函数：menu函数格式：int menu(void)函数功能：构造功能菜单，并选择下一步要操作的功能。

函数参数：无参数。

函数返回值：1～11中的一个序号。

5可供选择的功能如下：1--create P(x) 表示生成P多项式2--create Q(x) 表示生成Q多项式3--p(x)+Q(x) 表示两多项式相加4--P(x)-Q(x) 表示两多项式相减5--p(x)*Q(x) 表示两多项式相乘6--print P(x) 表示打印P多项式7--print Q(x) 表示打印Q多项式8--print P(x)+Q(x) 表示打印两多项式相加的结果9--print P(x)-Q(x) 表示打印两多项式相减的结果10--print P(x)*Q(x) 表示打印两多项式相乘的结果11—Quit 表示退出系统，结束程序的运行在运行过程中，输入其中一个序号，即表示下一步执行后面的功能。

如输入3，表示执行P(x)+(x)额运算。

(3)输入多项式函数：input函数格式：Polyn Input(void)函数参数：无参数函数功能：输入多项式各项的系数和指数，生成一个多项式链表。

函数返回值：指向一个多项式链表的头指针(4)两多项式相加函数：AddPolyn函数格式Polyn AddPolyn(Polyn h1,Polyn h2)函数功能：实现两个多项式h1和h2相加。

函数参数：Polyn h1—指向第一个多项式链表的头指针Polyn h2—指向第二个多项式链表的头指针函数返回值：指向相加后的结果链表的头指针(5)两多项式相减函数：SubtractPolyn函数格式Polyn SubtractPolyn(Polyn h1,Polyn h2)函数功能：实现两个多项式h1和h2相减。

函数参数：Polyn h1—指向第一个多项式链表的头指针Polyn h2—指向第二个多项式链表的头指针函数返回值：指向相减后的结果链表的头指针(6)两多项式相乘函数：MultPolyn函数格式Polyn MultPolyn(Polyn h1,Polyn h2)函数功能：实现两个多项式h1和h2相乘。

函数参数：Polyn h1—指向第一个多项式链表的头指针Polyn h2—指向第二个多项式链表的头指针6函数返回值：指向相乘后的结果链表的头指针(7)显示多项式函数：Output函数格式：void Output(Polyn h,char *title)函数功能：输出多项式的完整表示。

如：P(x)=1.00+2.50x^3-3.5x^9函数参数：Polyn h－要输出的多项式链表的头指针char *title－字符串，提示要输出一个什么样的多项式，如“P(x)”。

函数返回值：无返回值。

(8)判断选择函数：Select函数格式：int Select(char *str)函数功能：根据str提示的内容判断是执行指定的操作，还是不执行。

输入“Y”则表示执行，若输入“N”表示不执行。

如当P(x)多项式已经产生后，若再选择产生P(x)，这是提示：P(x) is not Empty,Create P(x) again?Input Y or N:若输入“Y”则表示重新产生多项式P(x)，若输入“N”表示维持原多项式不变。

函数参数：char *str－将要确定的内容。

函数返回值：1－表示执行指定的操作0－表示不执行指定的操作(9)插入位置定位函数：InsertLocate函数格式：int InsertLocate(Polyn h,int expn,Item **p)函数功能：确定新结点的插入位置。

其插入位置的确定是保证多项式链表按指数递增排列的关键。

函数参数：Polyn h－要查找的多项式链表的头指针int expn－新插入项的指数值。

Item **p－插入位置的前驱结点指针，由该函数的调用而被确定的内容。

新结点一定插入到该结点的后面。

函数返回值：-1－若指数expn值在某两个结点之间，则返回－1，参数p带回的值为指数值小于expn的结点指针。

0－若指数expn值等于某结点的指数值，则返回0，参数p带回的值为指数值等于expn的结点指针。

1－若指数expn值大于最后一个结点的指数值，则返回1，参数p带回最后一个结点的指针（10）结点插入函数：insert函数格式：void insert(Item *pre,Item *p)7函数功能：在指定结点pre后插入一个新结点p。