《数据结构》实验指导书.doc

1、实验指导书课程名称：数据结构计算机科学与工程系数据结构课程组 目 录前 言1一、实验的作用和目的2二、实验方式与考核方式2三、实验要求3四、实验报告要求4五、实验内容5实验一 线性表应用5实验二 栈与队列应用10实验三 二叉树的操作14实验四 图的遍历18实验五 查找算法应用21六、选做实验内容24实验六 排序24实验七 数组和广义表26实验八 串27前 言数据结构数据结构是计算机科学与技术及相关专业的一门重要专业基础课，它主要介绍线性结构、树型结构、图状结构三种逻辑结构元素的存储实现，在此基础上介绍一些典型算法，以及算法的时间、空间效率分析。这门课程的主要任务是培养学生的算法设计能力及良好的

2、程序设计习惯。通过本课程的学习，使学生熟练地掌握数据结构的内在逻辑关系及其在计算机中的表示方法（存储结构），以及相关基本操作的算法实现；掌握典型算法的设计思想及程序实现；熟悉各种数据结构在计算机科学中的基本应用；培养和训练学生结合实际应用，根据实际问题选取合适的数据结构、存储方案设计出简洁、高效、实用的算法；并为学习操作系统、编译原理、数据库原理等后续课程和研制开发各种系统和应用软件打下扎实的理论与实践基础。学习这门课程，习题和实验是两个关键环节。学生理解算法，上机实验是最佳的途径之一。因此，实验环节的好坏是学生能否学好数据结构的关键。为了更好地配合学生实验，特编写此实验指导书。实验指导书按照

3、实验教学大纲的要求，为每个主要的知识点精选了的典型的实验题目，对每个实验题目提出具体实现要求，并对算法的实现进行提示，希望对同学实验有所帮助。数据结构课程组2005年5月一、实验的作用和目的实验课是对学生的一种全面综合训练，是与课堂教学、课后练习相辅相成的必不可少的一个教学环节。数据结构是一门实践性很强的软件基础课程，为了学好这门课，每个学生必须完成一定数量的上机实验作业。通过课程的上机实验，可使学生深刻理解各种逻辑结构、存储结构的特性；学会如何把书上学到的知识用于解决实际问题，培养软件工作所需要的动手能力；另一方面，能使书上的知识变“活”，起到深化理解和灵活掌握教学内容的目的。 本课程的实验

4、着眼于原理与应用的结合点。通过课程的实验，培养学生分析问题，并能针对实际应用问题选择适用的逻辑结构、存储结构，设计和实现相应算法。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练，培养设计具有专业水准应用程序的能力。 二、实验方式与考核方式课程实验采用课内实验学时与课外实验学时相结合（课外实验学时是课内实验学时的2倍）的方式。本课程的课内实验学时为16学时，要完成的5个实验主要覆盖线性表、栈和队列、树、图、查找五部分内容。每个实验中的题目按类型可分为验证型、设计性、综合实验, 按难度可分为达到“实验设置基本要求”和“实验设置较高要求”的实验。每次实验，每位同学可

5、结合自己的情况，从任课教师布置的题目中选取具体实验题目，按要求完成实验任务。任课教师一般提前2周布置实验任务和具体实验题目。学生要在课下充分了解实验内容，并完成问题分析、算法设计，并利用课外实验学时基本完成程序设计。每个实验的课内实验学时安排同学集中在本系实验室进行，任课教师和实验指导教师针对同学的不同问题分别进行指导，并检查实验完成情况，要求学生回答相关的问题。每次实验完成后，学生需整理实验结果，并完成实验报告。实验成绩从两方面评定：实验完成情况和实验报告质量。实验完成情况：指导教师根据学生的实验准备情况、实验难度、实验完成情况、源程序质量、回答问题情况、实验纪律等方面给分。实验报告书写：学

6、生在实验后的一周内提交打印好的实验报告。教师根据实验报告质量评定成绩。 5 实验总成绩=（ 第i次实验成绩） i=1 三、实验要求 问题分析：充分地分析和理解问题本身，弄清要求做什么，包括功能要求、性能要求、设计要求和约束以及基本数据特性，数据间的联系等。 数据结构设计：针对要求解决的问题，考虑各种可能的数据结构，并且力求从中出最佳方案（必须连同算法一起考虑），确定主要的数据结构及全程变量。对引入的每种数据结构和全程变量要详细说明其功能、初值和操作特点。 算法设计：算法设计分概要设计和详细设计，概要设计着重解决程序的模块设计问题，包括考虑如何把程序自顶向下分解成若干顺序模块，并决定模块的接口，

7、即模块间的相互关系以及模块之间的信息交换问题。详细设计则要决定每个模块内部的具体算法，包括输入、处理和输出，相当于C语言中具体的函数设计。 测试用例设计：准备典型测试数据和测试方案，测试数据要有代表性、敏感性，测试方案包括模块测试和模块集成测试。 上机调试并分析结果：对程序进行编译，纠正程序中可能出现的语法错误。测试前，先运行一遍程序看看究竟将会发生什么，如果错误较多，则根据事先设计的测试方案并结合现场情况进行错误跟踪。最后，详细记录实验过程，并对实验结果进行分析，并于一周内提交实验报告。 四、实验报告要求1实验报告格式：实验报告首页按学校统一印刷的实验报告模版书写。2实验报告内容：实验基本信

8、息按照实验报告模版要求内容填写，不得有空项。其中： 实验内容按任课教师下达的实验任务填写：包括实验目的、任务、具体实验题目和要求； 实验过程与实验结果应包括如下主要内容： 算法设计思路简介 核心算法设计描述：可以用自然语言、伪代码或流程图等方式 算法的实现和测试结果：包括算法时的输入、输出，测试结果的分析与讨论，测试过程中遇到的主要问题及所采用的解决措施。 附录可包括源程序清单或其它说明（如功能模块之间的调用与被调用关系等） 实验报告雷同者，本次实验成绩为0分或雷同实验报告平分得分五、实验内容实验一 线性表应用一. 实验目的1、 掌握用Turbo C或VC+上机调试线性表的基本方法；2、 掌握

9、线性表的基本操作，如插入、删除、查找，以及线性表合并等运算在顺序存储结构和链式存储结构上的运算；并能够运用线性表基本操作解决问题，实现相应算法。二. 实验学时：课内实验学时：2学时课外实验学时：4学时三备选实验题目1 单链表基本操作练习（实验类型：验证型）1）问题描述：在主程序中设计一个简单的菜单，分别调用相应的函数功能： 1建立链表 2连接链表 3输出链表 0结束2）实验要求：在程序中定义下述函数，并实现所要求的函数功能： CreateLinklist( ): 从键盘输入数据，创建一个单链表 ContLinklist( )：将前面建立的两个单链表首尾相连 OutputLinklist( )：

10、输出显示单链表3）实验提示: 单链表数据类型定义（C语言） # include typedef int ElemType； /元素类型 typedef struct LNode ElemType data; struct LNode *next; LNode,*LinkList; 为了算法实现简单，最好采用带头结点的单向链表。4）注意问题: 重点理解链式存储的特点及指针的含义。 注意比较顺序存储与链式存储的各自特点。 注意比较带头结点、无头结点链表实现插入、删除算法时的区别。 单链表的操作是数据结构的基础，一定要注意对这部分的常见算法的理解。2 顺序表基本操作练习（实验类型：验证型）1）问题描

11、述： 从键盘输入一组整型元素序列，建立顺序表。 实现该顺序表的遍历。 在该顺序表中进行顺序查找某一元素,查找成功返回1,否则返回0。 判断该顺序表中元素是否对称,对称返回1,否则返回0。2）实验要求： 对应问题描述，在程序中定义4个相应的函数，实现上面要求的函数功能： 在主程序中设计一个简单的菜单，调用上述4个函数3）实验提示: 顺序表存储数据类型定义（C语言） # define MAXSIZE 100 /表中元素的最大个数 typedef int ElemType； /元素类型 typedef struct list ElemType elemMAXSIZE; /静态线性表 int leng

12、th; /表的实际长度 SqList; /顺序表的类型名4）注意问题: 插入、删除时元素的移动原因、方向及先后顺序。 理解不同的函数形参与实参的传递关系。3 约瑟夫环问题（实验类型：综合型）1）问题描述：有编号为1, 2n 的 n 个人按顺时针方向围坐一圈，每人持有一个正整数密码。开始给定一个正整数 m，从第一个人按顺时针方向自1开始报数，报到m者出列，不再参加报数，这时将出列者的密码作为m，从出列者顺时针方向的下一人开始重新自1开始报数。如此下去，直到所有人都出列。试设计算法，输出出列者的序列。2）实验要求: 采用顺序和链式两种存储结构实现3) 实现提示： 用顺序表来存储围座者的序号和密码(

13、顺序存储结构).n 用number 和code分别表示围座者的序号和密码.假设围座者人数为 j,当前使用密码为m,开始报数者位置为s, 那么下一出列者位置为s=(s+m-1) mod j.n 当我们要在线性表的顺序存储结构上的第i个位置上插入一个元素时，必须先将线性表的第i个元素之后的所有元素依次后移一个位置，以便腾空一个位置，再把新元素插入到该位置。若要删除第i个元素时，也必须把第i个元素之后的所有元素前移一个位置。 用链式存储解决此问题时可以采用循环链表.4）注意问题: 顺序存储和链式存储实现此算法时计算出列位置的不同方法，人员出列后所做操作的区别。4 一元稀疏多项式简单的计算器（实验类型

14、：综合型）1）问题描述：用线性表表示一元稀疏多项式，设计一个一元多项式运算器2）实验要求: 采用单链表存储结构一元稀疏多项式 输入并建立多项式 输出多项式 实现多项式加、减运算3) 实现提示：以两个多项式相加为例 结果多项式另存 扫描两个相加多项式，若都未检测完：n 若当前被检测项指数相等，系数相加，若结果未变成0，则将结果插入到结果多项式。n 若当前被检测项指数不等，则将指数较小者插入到结果多项式。 若有一个多项式已检测完，则将另一个多项式剩余部分直接连接到结果多项式。5 长整数（任意长度）四则运算演示程序（实验类型：综合型）1）问题描述：设计一个实现任意长的整数进行加法运算的演示程序2）实

15、验要求: 利用双向循环链表实现长整数的存储，给各结点含一个整型变量。任何整型变量的的范围是 -（215-1）（215-1）。 输入和输出形式：按照中国对长整数的表示习惯，每四位一组，组间用逗号隔开。3) 实现提示： 每个结点中可以存放的最大整数为215-1=32767，才能保证两数相加不会溢出。但若这样存，即相当于按32768进制数存，在十进制数与32768进制数之间的转换十分不方便。故可以在每个结点中仅存十进制数的4位，即不超过9999的非负整数，整个链表视为万进制数。 可以利用头结点数据域的符号代表长整数的符号。用其绝对值表示元素结点的树木。相加过程中不要破坏两个操作数链表。两操作数的头指

16、针存于指针数组中是简化程序结构的一种方法。4）注意问题: 不能给常整数位数规定上限。实验二 栈与队列应用一. 实验目的1. 实验设置基本要求：通过实验掌握栈或队列的基本操作的实现，并能灵活运用栈或队列特性，综合运用程序设计、算法分析等知识解决实际问题。2. 实验设置较高要求：理解组成递归算法的基本条件，理解递归算法与相应的非递归算法的区别，理解栈和队列的应用与作用。二. 实验学时：课内实验学时：4学时课外实验学时：8学时三. 备选实验题目1 十进制数N进制数据的转换 （实验类型：综合型）1）问题描述：将从键盘输入的十进制数转换为N（如二进制、八进制、十六进制）进制数据。2）实验要求: 利用顺序

17、栈实现数制转换问题3) 实现提示： 转换方法利用辗转相除法; 所转换的N进制数按低位到高位的顺序产生，而通常的输出是从高位到低位的，恰好与计算过程相反，因此转换过程中每得到一位N进制数则进栈保存，转换完毕后依次出栈则正好是转换结果。4）注意问题: 何时入栈、出栈 算法结束条件2 算术表达式求值演示（实验类型：综合型）1）问题描述：从键盘输入一个算术表达式并输出它的结果2）实验要求：算术表达式可包含加、减、乘、除、十进制整数和小括号，利用栈实现。3) 实现提示： 表达式作为一个串存储，如表达式“3*2-(4+2*1)”,其求值过程为：自左向右扫描表达式，当扫描到3*2时不能马上计算，因后面可能还

18、有更高的运算，正确的处理过程是：n 需要两个栈：对象栈OPND和算符栈OPTR;n 自左至右扫描表达式, 若当前字符是运算对象，入OPND栈;n 对运算符，若这个运算符比栈顶运算符高则入栈，继续向后处理，若这个运算符比栈顶运算符低则从OPND栈出栈两个数，从OPTR栈出栈一运算符进行运算，并将其运算结果入OPND栈，继续处理当前字符，直到遇到结束符。 4）注意问题 重点理解栈的算法思想，能够根据实际情况选择合适的存储结构。 注意算法的各个函数之间值的传递情况。3 停车场管理问题（实验类型：综合型）1）问题描述：设有一个可以停放n辆汽车的狭长停车场，它只有一个大门可以供车辆进出。车辆按到达停车场

19、的早晚依次从停车场最里面向大门口处停放(最先到达的第一辆车放在停车场的最里面)。如果停车场已放满n辆车，则后来的车辆只能在停车场大门外的便道上等待，一旦停车场内有车走开，则排在便道上的第一辆车就进入停车场。停车场内如有某辆车要开走，在它之后进入停车场的车都必须先退出停车场为它让路，待其开出停车场后，这些车辆再依原来的次序进场。每辆车在离开停车场时，都应根据它在停车场内停留的时间长短交费。如果停留在便道上的车未进停车场就要离去，允许其离去，不收停车费，并且仍然保持在便道上等待的车辆的次序。编写程序模拟该停车场的管理。2）实验要求: 要求程序输出每辆车到达后的停车位置（停车场或便道上），以及某辆车

20、离开停车场时应缴纳的费用和他在停车场内停留的时间3）实现提示：以栈模拟停车场，以队列模拟便道，按照从终端读入的车辆“到达”“离开”信息模拟停车场管理4）注意问题 重点理解栈、队列的算法思想，能够根据实际情况选择合适的存储结构。 栈、队列的算法是后续实验的基础（广义表、树、图、查找、排序等）。4 判断“回文”问题（实验类型：综合型）1）问题描述：所谓回文，是指从前向后顺读和从后向前倒读都一样的字符串。例如，did; pop; I was able 与 elba saw I 等等。2）实验要求：编写程序，利用栈结构判断一个字符串是否是“回文”。3）实现提示： 从左向右遇到的字符，若和栈顶元素比较，

21、若不相等，字符入栈，若相等，出栈。如此继续，若栈空，字符串是“回文”，否则不是。5 用递归和非递归两种方法实现自然数的拆分（实验类型：综合型）1）问题描述：任何大于 1 的自然数 n，总可以拆分成若干大于等于1 的自然数之和。 例: n=4 4=1+3 4=1+1+2 4=1+1+1+1 4=2+2 2）实验要求: 采用递归和非递归两种方法实现 利用交换率得出的拆分看作相同的拆分。3）实现提示： 递归算法:n 用数组a，ak中存储已完成的一种拆分n ak能否再拆分取决于ak/2是否大于等于ak-1；n 递归过程有两个参数：n表示要拆分数值的大小；k表示n存储在数组元素ak中。 非递归算法：（1

22、） 栈为两个数组a,b，ax,bx表示两个栈的栈顶元素；初始化：a1=1,b1=n，i=1, ax=ai,bx=bi（2） 若i1 or axbx,重复u 若axbx/2，进栈并取栈顶元素，返回（2） i=i+1;ai=ax,bi=bx-ax,bx=biu 若ax=bx，则数出拆分，退栈兵修改栈顶元素，返回（2） i=i-1;ai=ai+1,ax=ai,bx=biu 其余情况，bx/2axbx，修改栈顶元素，返回（2） ai=ai+1,ax=ai实验三 二叉树的操作一实验目的1、 基本要求：深刻理解二叉树性质和及各种存储结构的特点及适用范围；掌握用指针类型描述、访问和处理二叉树的运算；熟练掌握

23、二叉树的遍历算法； 2、 较高要求: 在遍历算法的基础上设计二叉树更复杂操作算法；认识哈夫曼树、哈夫曼编码的作用和意义;掌握树与森林的存储与便利。二. 实验学时：课内实验学时：3学时课外实验学时：6学时三备选实验题目1 以二叉链表为存储结构，实现二叉树的创建、遍历（实验类型：验证型）1）问题描述：在主程序中设计一个简单的菜单，分别调用相应的函数功能： 1建立树2前序遍历树3中序(非递归)遍历树 4后序遍历树0结束2）实验要求：在程序中定义下述函数，并实现要求的函数功能： CreateTree(): 按从键盘输入的前序序列，创建树 PreOrderTree()：前序遍历树（递归） InOrder

24、Tree()：中序(非递归)遍历树 LaOrderTree(): 后序遍历树（递归）3）实验提示: 二叉链表存储数据类型定义 # define ElemType char /元素类型 typedef struct BiTNode ElemType data; struct BiTNode *lchild,*rchild; BiTNode,*BiTree; 元素类型可以根据实际情况选取。4）注意问题: 注意理解递归算法的执行步骤。 注意字符类型数据在输入时的处理。 重点理解如何利用栈结构实现非递归算法2 编写算法交换二叉树中所有结点的左、右子树（实验类型：综合型）1）问题描述：编写一算法，交换二

25、叉树中所有结点的左、右子树2）实验要求：以二叉链表作为存储结构3) 实现提示：设二叉树的根指针未t，且以二叉链表表示，可利用一个类型为seqstack的指针来实现，且栈单元包含两个域，一个为data，另一个为top，整个栈容量为maxsize，当树非空时，将当前的树根结点入栈，同时将当前栈顶元素出栈当作根结点，然后依据当前的根结点是否具有孩子结点来判定是否将其左、右指针进行交换；再将交换后的左指针或右指针入栈，这样反复进行，直到栈空为止。4）注意问题: 注意理解算法中栈结构的利用3 试编写按层次顺序遍历二叉树的算法（实验类型：综合型）1）问题描述：编写按层次顺序遍历二叉树的算法2）实验要求：以

26、二叉链表作为存储结构3) 实现提示：本算法要采用一个队列q，先将二叉树根结点入队列，然后出队列，输出该结点；若它有左子树，便将左子树根结点入队列；若它有右子树，便将右子树根结点入队列，直到队列空为止。因为队列的特点是先进先出，从而达到按层次顺序遍历二叉树目的。4）注意问题: 理解算法中队列结构的利用4 实现一个哈夫曼编/译码系统（实验类型：综合型）1）问题描述：利用哈夫曼编码进行信息通信可以大大编写按层次顺序遍历二叉树的算法提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传输数据预先编码，在接收端将传来的数据进行译码。对于双工信道，每端都需要一个完整的编

27、码/译码系统。试为这样的信息收发站写一个哈夫曼的编/译码系统。2）实验要求：一个完整的系统应具有以下功能：(1) I：初始化(Initialization)。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。(2) E：编码(Encoding)。利用已建好的哈夫曼树对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。(3) D：译码(Decoding)。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。(4) P：打印代码文件(Print)。将文件CodeFile以紧凑格式显示在终端

28、上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrin中。(5) T：打印哈夫曼树(Tree printing)。将已在内存中的哈夫曼树以直观的方式显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。3) 实现提示：(1) 文件CodeFile的基类型可以设为字节型。(2) 用户界面可以设计为“菜单”方式：显示上述功能符号，再加上“Q”，表示退出运行Quit。请用户键入一个选择功能符。此功能执行完毕后再显示此菜单，直至某次用户选择了“E”为止。(3) 在程序的一次执行过程中，第一次执行I、D或C命令之后，哈夫曼树已经在内存了，不必再读入。每次执行中不一定执行I

29、命令，因为文件hfmTree可能早已建好。5 森林（孩子兄弟链表）的建立与遍历（实验类型：验证型）1）问题描述：以“孩子兄弟二叉链表”为存储结构，建立和遍历一个森林2）实验要求：以“孩子兄弟二叉链表”作为存储结构3) 实现提示： 可参考二叉树的前序遍历和中序遍历算法4）注意问题: 理解二叉树与树的对应关系 理解树和森林遍历的实质实验四 图的遍历一、 实验目的1、 基本要求：通过实验掌握理解图的两种主要存储结构，掌握图的构造算法，掌握图的深度优先遍历、广度优先遍历算法。2、 较高要求：理解拓扑排序、AOV网、AOE网等图型结构的操作方法应用价值。二. 实验学时：课内实验学时：3学时课外实验学时：

30、6学时三. 备选实验题目1 键盘输入的数据建立图，并进行深度优先搜索和广度优先搜索（实验类型：验证型）1）问题描述：在主程序中设计一个简单的菜单，分别调用相应的函数功能： 1图的建立 2深度优先遍历图 3广度优先遍历图 0结束2）实验要求：在程序中定义下述函数，并实现要求的函数功能： CreateGraph(): 按从键盘的数据建立图 DFSGrahp()：深度优先遍历图 BFSGrahp()：广度优先遍历图3）实验提示: 图的存储可采用邻接表或邻接矩阵； 图存储数据类型定义 （邻接表存储） # define MAX_VERTEX_NUM 8 /顶点最大个数 typedef struct Ar

31、cNode int adjvex; struct ArcNode *nextarc; int weight; /边的权 ArcNode; /表结点 # define VertexType int /顶点元素类型 typedef struct VNode int degree,indegree;/顶点的度，入度 VertexType data; ArcNode *firstarc;Vnode /*头结点*/,AdjListMAX_VERTEX_NUM; typedef struct AdjList vertices; int vexnum,arcnum;/顶点的实际数，边的实际数 ALGraph

32、; 4）注意问题: 注意理解各算法实现时所采用的存储结构。 注意区别正、逆邻接。2 利用最小生成树算法解决通信网的总造价最低问题（实验类型：综合型）1）问题描述：若在n个城市之间建通信网络，秩序架设n-1条线路即可。如何以最低的经济代价建设这个通信网，是一个网络的最小生成树问题。2）实验要求：利用克鲁斯卡尔算法求网的最小生成树3) 实现提示：通信线路一旦建立，必然是双向的。因此，构造最小生成树的网一定是无向网。为简单起见，图的顶点数不超过10个，网中边的权值设置成小于100。3 教学计划编制问题（实验类型：综合型）1）问题描述：软件专业的学生要学习一系列课程，其中有些课程必须在其先修课完成后才

33、能学习。2）实验要求：假设每门课程的学习时间为一个学期，试为该专业的学生设计教学计划，使他们能在最短时间内修完专业要求的全部课程。3) 实现提示： 以顶点代表课程，弧代表课程的先后修关系，按课程先后关系建立有向无环图。 利用拓扑排序实现。4 给定实际背景，解决最短路径问题（实验类型：综合型）1）问题描述：假设以一个带权有向图表示某一区域的公交线路网，图中顶点代表一些区域中的重要场所，弧代表已有的公交线路，弧上的权表示该线路上的票价（或搭乘所需时间），试设计一个交通指南系统，指导前来咨询者以最低的票价或最少的时间从区域中的某一场所到达另一场所。2）实验要求：利用Dijkstra算法或Floyd算

34、法求最低的票价或最少的时间3) 实现提示： 该问题可以归结为一个求带权有向图中顶点间最短路径的问题。 分别建立以票价（或搭乘所需时间）为权的有向图，再利用Dijkstra算法或Floyd算法求最短路径及其路径长度。实验五 查找算法应用一、实验目的1、 实验设置基本要求：理解二叉排序树、AVL树的查找、插入、删除、建立算法的思想及程序实现；掌握散列存储结构的思想，能选择合适散列函数，实现不同冲突处理方法的散列表的查找、建立。运用折半查找、分块查找、二叉排序树、散列表等查找算法解决实际问题。2、 实验设置较高要求：利用B+树设计大数据集索引结构。 二. 实验学时：课内实验学时：4学时课外实验学时：

35、8学时三、备选实验题目1. 哈希表查找（实验类型：综合型）1）问题描述：针对某个集体的“人名”构造哈希表，解决按“人名”进行查找的索引结构。2）实验要求：要求表的平均查找长度不超过R，完成相应的建表和查表程序。3) 实现提示：假设人名为汉语拼音形式。代填入哈希表人名共30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用再散列法处理冲突。2. 构造二叉排序树，并进行中序遍历（实验类型：综合型）1）问题描述：从键盘读入一串整数构造一棵二叉排序树，并对得到的二叉排序述进行中序遍历，得到有序序列。2）实验要求：该二叉排序树以二叉链表存储3）实现提示：二叉排序树的构成，可从空的二叉树开始，每输

36、入一个结点数据，就建立一个新结点插入到当前已生成的二叉排序树中，所以它的主要操作是二叉排序树插入运算。在二叉排序树中插入新结点，只要保证插入后仍符合二叉排序树的定义即可。3. 折半查找算法（实验类型：验证型）1）问题描述：从键盘读入一串整数和一个待查关键字，查找在该整数串中是否有这个待查关键字。如果有，输出它在整数串中的位置；如果没有，输出-12）实验要求： 利用折半查找算法查找 用递归和非递归两种方式实现折半查找算法3) 实现提示： 递归实现参考书上折半查找算法的实现 非递归算法利用栈实现4. 借助B树实现图书索引管理（实验类型：综合型）1）问题描述：图书管理基本业务活动包括：对一本书的采编

37、入库、清除库存、借阅和归还等。设计一个图书管理系统，将上述业务活动借助计算机系统完成。2）实验要求：作为演示系统，不必使用文件，全部数据可以在内存中存放。3) 实现提示：建立B树结构，利用B树插入、删除算法做入库、出库操作。六、选做实验内容（可利用课外实验学时完成）实验六 排序一、实验目的1、 掌握常见的排序算法(插入排序、交换排序、选择排序、归并排序、基数排序等)的思想、特点及其适用条件。2、 能够分析各种算法的效率3、 熟练掌握常见的排序算法的程序实现。二. 实验学时：课内实验学时：2学时课外实验学时：4学时三、备选实验题目1常见排序算法实现（实验类型：验证型）1）问题描述：输入一组关键字

38、序列分别实现下列排序: （1）实现简单选择排序、直接插入排序和冒泡排序。 （2）实现希尔排序算法。 （3）实现快速排序算法。 （4）实现堆排序算法。 *（5）快速排序的非递归算法。 （6）实现折半插入排序。（7）在主函数中设计一个简单菜单，分别测试上述算法。2) 实现提示： 数据类型定义（C语言） # define MAXSIZE 100 /*参加排序元素的最大个数*/ typedef struct list int key; RedType; typedef struct RedType rMAXSIZE+1; int length; /*参加排序元素的实际个数*/ SqList; 算法5可

39、以借助栈实现。3）注意问题： 在RedType中增加一个数据项验证各种排序算法的稳定性。 注意理解各种算法的思想、了解算法的适用情况及时间复杂度，能够根据实际情况选择合适的排序方法。2统计成绩：（实验类型：综合型）1）问题描述：给出n个学生的考试成绩表，每条信息由姓名和分数组成，试设计一个算法： 按分数高低次序，打印出每个学生在考试中获得的名次，分数相同的为同一名次； 按名次列出每个学生的姓名与分数。2）基本要求：学生的考试成绩表必须通过键盘输入数据而建立，同时要对输出进行格式控制。实验七 数组和广义表一、实验目的1、 掌握稀疏矩阵的表示方法及其运算的实现2、 实现稀疏矩阵在三元组、十字链表等

40、表示下的各运算并分析其效率二. 实验学时：课外实验学时：4学时三、备选实验题目：1稀疏矩阵运算器（实验类型：综合型）1）问题描述：稀疏矩阵是指那些多数元素为零的矩阵。利用“稀疏”特点进行存储和计算可以大大节省存储空间，提高计算效率。本实验的主要任务是实现一个能进行稀疏矩阵基本运算的运算器。 2）实验要求： 以“带行逻辑链接信息” 的三元组顺序表表示稀疏矩阵，实现两个矩阵相加、相减和相乘的运算。稀疏矩阵的输入形式采用三元组表示，而运算结果的矩阵则以通常的阵列形式列出。 测试数据：10 0 0 0 0 0 10 0 00 0 9 + 0 0 -1 = 0 0 8-1 0 0 1 0 -3 0 0

41、-3 10 0 0 0 10 00 9 + 0 -1 = 0 10-1 0 1 -3 -2 34 -3 0 0 1 0 0 0 8 0 0 0 1 0 0 0 0 0 0 70 3 0 04 2 00 1 01 0 00 0 00 -6 0 = 8 0 0 0 1 0 0 0 0 3）实现提示 首先应输入矩阵的行数和列数，并判别给出的两个矩阵的行、列数对于所要求作的运算是否相匹配。可设矩阵的行数和列数均不超过20。 程序可以对三元组的输入顺序加以限制，例如，按行优先。注意研究教科书5.3.2节中的算法，以便提高计算效率。 在用三元组表示稀疏矩阵时，相加或相减所得结果矩阵应该另生成，乘积矩阵也可

42、用二维数组存放。实验八 串一、实验目的1、 理解串的模式匹配算法（包括KMP算法）。2、 明确串也是特殊的线性表，掌握其特殊性所在。3、 熟悉一般文字处理软件的设计方法、较复杂问题的分解方法。二. 实验学时：课外实验学时：6学时三、备选实验题目：1实现一个简单行编辑程序（实验类型：综合型）1）问题描述：文本编辑程序利用计算机进行文字加工的基本软件工具，实现对文本文件的插入、删除等修改操作。限制这些操作以行为单位进行的编辑程序为行编辑程序。被编辑的文本文件可能很大，全部读入编辑程序的数据空间（内存）的作法既不经济，也不总能实现。一种解决逐段编辑。任何时刻只把待编辑文件的一段放在内存，称为活区。试

43、按照这种方法实现一个简单的行编辑程序。设文件每行不超过320个字符，很少超过80个字符。2）实验要求：实现以下4条基本编辑命令： 行插入。格式：i， 将插入活区中第行之后。 行删除。格式：d删除活区中第行（到第行）。例如：“d10Enter”和“d10 14Enter”。 活区切换。格式：n将活区写入输出文件，并从输入文件中读入下一段，作为新的活区。 活区显示。格式：p逐页地（每页20行）显示活区内容，每显示一页之后请用户决定是否继续显示以后各页（如果存在）。印出的每一行要前置行号和一个空格符，行号固定占4位，增量为1。 各条命令中行号均须在活区中各行行号范围之内，只有插入命令的行号要以等于活区第一行行号减1，表示插入当前屏幕中第一行之前，否则