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

实验指导书实验指导书 课课程名称：数据程名称：数据结结构构 计算机科学与工程系计算机科学与工程系 数据结构数据结构课程组课程组 目 录 前 言 1 一、实验的作用和目的 .2 二、实验方式与考核方式 2 三、实验要求 3 四、实验报告要求 4 五、实验内容 5 实验一 线性表应用 5 实验二 栈与队列应用 10 实验三 二叉树的操作 14 实验四 图的遍历 18 实验五 查找算法应用 21 六、选做实验内容 .24 实验六 排序 24 实验七 数组和广义表 .26 实验八 串 .27 1 前前 言言 数据结构数据结构是计算机科学与技术及相关专业的一门 重要专业基础课，它主要介绍线性结构、树型结构、图状结构三种 逻辑结构元素的存储实现，在此基础上介绍一些典型算法，以及 算法的时间、空间效率分析。 这门课程的主要任务是培养学生的算法设计能力及良好的程 序设计习惯。通过本课程的学习，使学生熟练地掌握数据结构的 内在逻辑关系及其在计算机中的表示方法（存储结构），以及相关 基本操作的算法实现；掌握典型算法的设计思想及程序实现；熟悉 各种数据结构在计算机科学中的基本应用；培养和训练学生结合 实际应用，根据实际问题选取合适的数据结构、存储方案设计出 简洁、高效、实用的算法；并为学习操作系统、 编译原理、 数据 库原理等后续课程和研制开发各种系统和应用软件打下扎实的 理论与实践基础。 学习这门课程，习题和实验是两个关键环节。学生理解算法， 上机实验是最佳的途径之一。因此，实验环节的好坏是学生能否 学好数据结构的关键。为了更好地配合学生实验，特编写此实 2 验指导书。实验指导书按照实验教学大纲的要求，为每个主要的 知识点精选了的典型的实验题目，对每个实验题目提出具体实现 要求，并对算法的实现进行提示，希望对同学实验有所帮助。 数据结构课程组 2005 年 5 月 3 一、一、实验实验的作用和目的的作用和目的 实验课是对学生的一种全面综合训练，是与课堂教学、课后 练习相辅相成的必不可少的一个教学环节。 数据结构是一门实践性很强的软件基础课程，为了学好这 门课，每个学生必须完成一定数量的上机实验作业。通过课程的 上机实验，可使学生深刻理解各种逻辑结构、存储结构的特性；学 会如何把书上学到的知识用于解决实际问题，培养软件工作所需 要的动手能力；另一方面，能使书上的知识变“活”，起到深化理解 和灵活掌握教学内容的目的。 本课程的实验着眼于原理与应用的结合点。通过课程的实验， 培养学生分析问题，并能针对实际应用问题选择适用的逻辑结构、 存储结构，设计和实现相应算法。同时，在程序设计方法以及上 机操作等基本技能和科学作风方面受到比较系统和严格的训练， 培养设计具有专业水准应用程序的能力。 二、二、实验实验方式与考核方式方式与考核方式 课程实验采用课内实验学时与课外实验学时相结合（课外实 验学时是课内实验学时的 2 倍）的方式。本课程的课内实验学时 为 16 学时，要完成的 5 个实验主要覆盖线性表、栈和队列、树、 图、查找五部分内容。每个实验中的题目按类型可分为验证型、 设计性、综合实验, 按难度可分为达到“实验设置基本要求”和“实 验设置较高要求”的实验。每次实验，每位同学可结合自己的情况， 从任课教师布置的题目中选取具体实验题目，按要求完成实验任 务。 4 任课教师一般提前 2 周布置实验任务和具体实验题目。学生 要在课下充分了解实验内容，并完成问题分析、算法设计，并利 用课外实验学时基本完成程序设计。每个实验的课内实验学时安 排同学集中在本系实验室进行，任课教师和实验指导教师针对同 学的不同问题分别进行指导，并检查实验完成情况，要求学生回 答相关的问题。每次实验完成后，学生需整理实验结果，并完成 实验报告。 实验成绩从两方面评定：实验完成情况和实验报告质量。 实验完成情况：指导教师根据学生的实验准备情况、实验难 度、实验完成情况、源程序质量、回答问题情况、实验纪律等方面 给分。 实验报告书写：学生在实验后的一周内提交打印好的实验报 告。教师根据实验报告质量评定成绩。 5 实验总成绩=（ 第 i 次实验成绩） i=1 三、三、实验实验要求要求 问题问题分析：分析：充分地分析和理解问题本身，弄清要求做什么， 包括功能要求、性能要求、设计要求和约束以及基本数据特性， 数据间的联系等。 数据数据结结构构设计设计： ：针对要求解决的问题，考虑各种可能的数 据结构，并且力求从中出最佳方案（必须连同算法一起考虑），确 5 定主要的数据结构及全程变量。对引入的每种数据结构和全程变 量要详细说明其功能、初值和操作特点。 算法算法设计设计： ：算法设计分概要设计和详细设计，概要设计着 重解决程序的模块设计问题，包括考虑如何把程序自顶向下分解 成若干顺序模块，并决定模块的接口，即模块间的相互关系以及 模块之间的信息交换问题。详细设计则要决定每个模块内部的具 体算法，包括输入、处理和输出，相当于 C 语言中具体的函数设 计。 测试测试用例用例设计设计： ：准备典型测试数据和测试方案，测试数据 要有代表性、敏感性，测试方案包括模块测试和模块集成测试。 上机上机调试调试并分析并分析结结果：果：对程序进行编译，纠正程序中可能 出现的语法错误。测试前，先运行一遍程序看看究竟将会发生什 么，如果错误较多，则根据事先设计的测试方案并结合现场情况 进行错误跟踪。最后，详细记录实验过程，并对实验结果进行分 析，并于一周内提交实验报告。 四、四、实验报实验报告要求告要求 1实验报告格式：实验报告首页按学校统一印刷的实验报告 6 模版书写。 2实验报告内容：实验基本信息按照实验报告模版要求内容 填写，不得有空项。其中： 实验内容按任课教师下达的实验任务填写：包括实验 目的、任务、具体实验题目和要求； 实验过程与实验结果应包括如下主要内容： 算法设计思路简介 核心算法设计描述：可以用自然语言、伪代码或 流程图等方式 算法的实现和测试结果：包括算法时的输入、输 出，测试结果的分析与讨论，测试过程中遇到的 主要问题及所采用的解决措施。 附录可包括源程序清单或其它说明（如功能模块之间 的调用与被调用关系等） 实验报告雷同者，本次实验成绩为 0 分或雷同实验 报告平分得分 7 五、五、实验实验内容内容 实验实验一一 线线性表性表应应用用 一一. 实验实验目的目的 1、 掌握用 Turbo C 或 VC+上机调试线性表的基本方法； 2、 掌握线性表的基本操作，如插入、删除、查找，以及线性表 合并等运算在顺序存储结构和链式存储结构上的运算；并 能够运用线性表基本操作解决问题，实现相应算法。 二二. 实验实验学学时时： ： 课内实验学时：2 学时 课外实验学时：4 学时 三三备选实验题备选实验题目目 1、 单链单链表基本操作表基本操作练习练习（ （实验类实验类型：型：验证验证型）型） 1）问题描述：在主程序中设计一个简单的菜单，分别调用相 应的函数功能： 1建立链表 8 2连接链表 3输出链表 0结束 2）实验要求：在程序中定义下述函数，并实现所要求的函数 功能： CreateLinklist( ): 从键盘输入数据，创建一个单链表 ContLinklist( )：将前面建立的两个单链表首尾相连 OutputLinklist( )：输出显示单链表 3）实验提示: 单链表数据类型定义（C 语言） # include typedef int ElemType； /元素类型 typedef struct LNode ElemType data; struct LNode *next; LNode,*LinkList; 为了算法实现简单，最好采用带头结点的单向链表。 4）注意问题: 重点理解链式存储的特点及指针的含义。 注意比较顺序存储与链式存储的各自特点。 9 注意比较带头结点、无头结点链表实现插入、删除算 法时的区别。 单链表的操作是数据结构的基础，一定要注意对这 部分的常见算法的理解。 2、 顺顺序表基本操作序表基本操作练习练习（ （实验类实验类型：型：验证验证型）型） 1）问题描述： 从键盘输入一组整型元素序列，建立顺序表。 实现该顺序表的遍历。 在该顺序表中进行顺序查找某一元素,查找成功返回 1,否则返回 0。 判断该顺序表中元素是否对称,对称返回 1,否则返回 0。 2）实验要求： 对应问题描述，在程序中定义 4 个相应的函数，实现 上面要求的函数功能： 在主程序中设计一个简单的菜单，调用上述 4 个函 数 3）实验提示: 10 顺序表存储数据类型定义（C 语言） # define MAXSIZE 100 /表中元素的最大个数 typedef int ElemType； /元素类型 typedef struct list ElemType elemMAXSIZE; /静态线性表 int length; /表的实际长度 SqList; /顺序表的类型名 4）注意问题: 插入、删除时元素的移动原因、方向及先后顺序。 理解不同的函数形参与实参的传递关系。 3、 约约瑟夫瑟夫环问题环问题（ （实验类实验类型：型：综综合型）合型） 1）问题描述：有编号为 1, 2n 的 n 个人按顺时针方向围坐 一圈，每人持有一个正整数密码。开始给定一个正整数 m，从第 一个人按顺时针方向自 1 开始报数，报到 m 者出列，不再参加报 数，这时将出列者的密码作为 m，从出列者顺时针方向的下一人 开始重新自 1 开始报数。如此下去，直到所有人都出列。试设计 算法，输出出列者的序列。 2）实验要求: 采用顺序和链式两种存储结构实现 11 3) 实现提示： 用顺序表来存储围座者的序号和密码(顺序存储结构). 用 number 和 code 分别表示围座者的序号和密 码.假设围座者人数为 j,当前使用密码为 m,开始 报数者位置为 s, 那么下一出列者位置为 s=(s+m- 1) mod j. 当我们要在线性表的顺序存储结构上的第 i 个位 置上插入一个元素时，必须先将线性表的第 i 个 元素之后的所有元素依次后移一个位置，以便腾 空一个位置，再把新元素插入到该位置。若要删 除第 i 个元素时，也必须把第 i 个元素之后的所 有元素前移一个位置。 用链式存储解决此问题时可以采用循环链表. 4）注意问题: 顺序存储和链式存储实现此算法时计算出列位置的 不同方法，人员出列后所做操作的区别。 4、 一元稀疏多一元稀疏多项项式式简单简单的的计计算器（算器（实验类实验类型：型：综综合型）合型） 12 1）问题描述：用线性表表示一元稀疏多项式，设计一个一元 多项式运算器 2）实验要求: 采用单链表存储结构一元稀疏多项式 输入并建立多项式 输出多项式 实现多项式加、减运算 3) 实现提示：以两个多项式相加为例 结果多项式另存 扫描两个相加多项式，若都未检测完： 若当前被检测项指数相等，系数相加，若结果未 变成 0，则将结果插入到结果多项式。 若当前被检测项指数不等，则将指数较小者插入 到结果多项式。 若有一个多项式已检测完，则将另一个多项式剩余 部分直接连接到结果多项式。 5、 长长整数（任意整数（任意长长度）四度）四则则运算演示程序（运算演示程序（实验类实验类型：型：综综合型）合型） 13 1）问题描述：设计一个实现任意长的整数进行加法运算的演 示程序 2）实验要求: 利用双向循环链表实现长整数的存储，给各结点含 一个整型变量。任何整型变量的的范围是 -（215-1） （215-1）。 输入和输出形式：按照中国对长整数的表示习惯，每 四位一组，组间用逗号隔开。 3) 实现提示： 每个结点中可以存放的最大整数为 215-1=32767，才 能保证两数相加不会溢出。但若这样存，即相当于按 32768 进制数存，在十进制数与 32768 进制数之间的 转换十分不方便。故可以在每个结点中仅存十进制数 的 4 位，即不超过 9999 的非负整数，整个链表视为万 进制数。 可以利用头结点数据域的符号代表长整数的符号。 用其绝对值表示元素结点的树木。相加过程中不要破 14 坏两个操作数链表。两操作数的头指针存于指针数组 中是简化程序结构的一种方法。 4）注意问题: 不能给常整数位数规定上限。 实验实验二二 栈栈与与队队列列应应用用 、.实验实验目的目的 1. 实验设置基本要求：通过实验掌握栈或队列的基本操作的 实现，并能灵活运用栈或队列特性，综合运用程序设计、 算法分析等知识解决实际问题。 2. 实验设置较高要求：理解组成递归算法的基本条件，理解 递归算法与相应的非递归算法的区别，理解栈和队列的应 用与作用。 二二. 实验实验学学时时： ： 课内实验学时：4 学时 课外实验学时：8 学时 三三. 备选实验题备选实验题目目 1、 十十进进制数制数 N 进进制数据的制数据的转换转换 （ （实验类实验类型：型：综综合型）合型） 15 1）问题描述：将从键盘输入的十进制数转换为 N（如二进制、 八进制、十六进制）进制数据。 2）实验要求: 利用顺序栈实现数制转换问题 3) 实现提示： 转换方法利用辗转相除法; 所转换的 N 进制数按低位到高位的顺序产生，而通 常的输出是从高位到低位的，恰好与计算过程相反，因 此转换过程中每得到一位 N 进制数则进栈保存，转换 完毕后依次出栈则正好是转换结果。 4）注意问题: 何时入栈、出栈 算法结束条件 2、 算算术术表达式求表达式求值值演示（演示（实验类实验类型：型：综综合型）合型） 1）问题描述：从键盘输入一个算术表达式并输出它的结果 2）实验要求：算术表达式可包含加、减、乘、除、十进制整数 和小括号，利用栈实现。 3) 实现提示： 16 表达式作为一个串存储，如表达式“3*2-(4+2*1)”,其 求值过程为：自左向右扫描表达式，当扫描到 3*2 时不 能马上计算，因后面可能还有更高的运算，正确的处理 过程是： 需要两个栈：对象栈 OPND 和算符栈 OPTR; 自左至右扫描表达式, 若当前字符是运算对象， 入 OPND 栈; 对运算符，若这个运算符比栈顶运算符高则入栈， 继续向后处理，若这个运算符比栈顶运算符低则 从 OPND 栈出栈两个数，从 OPTR 栈出栈一运算 符进行运算，并将其运算结果入 OPND 栈，继续 处理当前字符，直到遇到结束符。 4）注意问题 重点理解栈的算法思想，能够根据实际情况选择合 适的存储结构。 注意算法的各个函数之间值的传递情况。 3、 停停车场车场管理管理问题问题（ （实验类实验类型：型：综综合型）合型） 17 1）问题描述：设有一个可以停放 n 辆汽车的狭长停车场，它 只有一个大门可以供车辆进出。车辆按到达停车场的早晚依次从 停车场最里面向大门口处停放(最先到达的第一辆车放在停车场 的最里面)。如果停车场已放满 n 辆车，则后来的车辆只能在停车 场大门外的便道上等待，一旦停车场内有车走开，则排在便道上 的第一辆车就进入停车场。停车场内如有某辆车要开走，在它之 后进入停车场的车都必须先退出停车场为它让路，待其开出停车 场后，这些车辆再依原来的次序进场。每辆车在离开停车场时， 都应根据它在停车场内停留的时间长短交费。如果停留在便道上 的车未进停车场就要离去，允许其离去，不收停车费，并且仍然 保持在便道上等待的车辆的次序。编写程序模拟该停车场的管理。 2）实验要求: 要求程序输出每辆车到达后的停车位置（停车 场或便道上），以及某辆车离开停车场时应缴纳的费用和他在停 车场内停留的时间 3）实现提示：以栈模拟停车场，以队列模拟便道，按照从终端 读入的车辆“到达”“离开”信息模拟停车场管理 4）注意问题 18 重点理解栈、队列的算法思想，能够根据实际情况选 择合适的存储结构。 栈、队列的算法是后续实验的基础（广义表、树、图、 查找、排序等）。 4、 判断判断“回文回文”问题问题（ （实验类实验类型：型：综综合型）合型） 1）问题描述：所谓回文，是指从前向后顺读和从后向前倒读 都一样的字符串。 例如，did; pop; I was able 与 elba saw I 等等。 2）实验要求：编写程序，利用栈结构判断一个字符串是否是 “回文”。 3）实现提示： 从左向右遇到的字符，若和栈顶元素比较，若不相等， 字符入栈，若相等，出栈。如此继续，若栈空，字符串是 “回文”，否则不是。 5、 用用递归递归和非和非递归递归两种方法两种方法实现实现自然数的拆分自然数的拆分（ （实验类实验类型：型： 综综合型）合型） 1）问题描述：任何大于 1 的自然数 n，总可以拆分成若干大 于等于 1 的自然数之和。 例: n=4 4=1+3 4=1+1+2 4=1+1+1+1 4=2+2 19 2）实验要求: 采用递归和非递归两种方法实现 利用交换率得出的拆分看作相同的拆分。 3）实现提示： 递归算法: 用数组 a，ak中存储已完成的一种拆分 ak能否再拆分取决于 ak/2 是否大于等于 ak- 1； 递归过程有两个参数：n 表示要拆分数值的大小； k 表示 n 存储在数组元素 ak中。 非递归算法： 、1、栈为两个数组 a,b，ax,bx 表示两个栈的栈 顶元素；初始化：a1=1,b1=n，i=1, ax=ai, bx=bi 、2、若 ibx,重复 若 ax， 将插入活区中第行之后。 行删除。格式：d 删除活区中第行（到第行）。 例如：“d10Enter”和“d10 14Enter