实验指导书吕.doc

数 据 结 构 实 验 实验目的意义 数据结构实验是《数据结构》课程必不可少的一个教学环节。通过实验，学生不仅能够深化理解教学内容，进一步提高灵活运用数据结构和算法的能力，而且可以在问题分析、总体结构设计、算法设计、程序设计、上机操作及程序调试等基本技能方面受到综合训练。实验着眼于原理与应用的结合点，使学生学会如何把书本上和课堂上学到的知识用于解决实际问题，从而培养软件工作所需要的动手能力。 实验基本步骤及要求 阅读实验指导书 每一次实验从阅读实验指导书开始。对于本次实验的实验目的、实验题目、实现提示以及思考题目、选做题目等应认真了解。 算法设计 分析实验题目，参考实现提示，进行算法设计。 程序设计 根据已完成的算法，用C语言进行程序设计。 调试和测试 将所编程序在计算机上调试通过，并选取若干组测试数据对程序进行尽可能全面的测试。 整理完成实验报告 实验报告一般包括下列内容： 实验者姓名、学号、专业和班级，课程名称（数据结构实验），实验日期等； 本次实验的实验编号及实验名称（例如：实验一 线性表的应用）； 本次实验的实验目的（可参考《数据结构实验指导》相关内容）； 本次实验的实验地点、设备编号、硬件及软件环境； 程序结构的描述及各模块的规格说明； 主要算法及其基本思想； 调试过程简述（调试过程是否顺利，遇到些什么问题，如何解决的，以及上机操作所花费的时间等）； 测试数据和相应输出的客观记录，对运行结果的分析讨论。 注意：为了有效地利用上机时间，上述实验步骤1，2，3应在上机之前完成。 实验一 线性表的应用 一．实验目的 熟悉线性表的链式存储结构，熟练掌握线性表各种基本操作的实现，培养灵活运用线性表解决实际问题的能力。 二．实验题目 1.键盘输入一组元素，建立一个带头结点的单向链表（有无序均可）。 2.遍历单向链表，在单向链表中删除元素E。 3.判断一个单向链表是否有序，是输出“yes”；否则输出“no”。 设计一个MAIN（）函数，分别调试上述算法。 4.假设有两个按元素值递增有序排列的线性表A和B，均以单链表做存储结构，请编写算法将A表和B表归并成一个按元素值递减有序（即非递增有序，允许表中含有值相同的元素）排列的线性表C，并要求利用原表的结点空间构造C表。 说明：对于单向链表的建立可以有两种方式选择，一种是从头结点后面依次插入，一种是从尾结点后面依次插入，可以根据实际需要选择这两种方法之一实现。 三．实现提示 数据的存储结构选择链表，链表的每个结点的定义如下。 typedef int ElemType; typedef struct LNode{ ElemType data; struct LNode *next; }LNode, *LinkList; 四．思考及选做 1．如何使用顺序表实现本实验提出的要求，比较顺序表和单向链表的优缺点。 2．将单向链表逆置。 3．如何用递归算法实现不带头结点的线性链表的逆置。 说明：单向链表的逆置要求不增加新的存储空间，只是在原来已有链表的基础上进行逆置，而不是构造一个新的链表，将元素逆向插入到新的链表实现逆置功能。 实验二 栈和队的应用 一．实验目的 熟悉掌握数据结构中栈的基本操作，能够使用栈的结构解决一些实际中常见的问题。 二．实验题目 1．解决问题时，对数值的操作可以是二、十、八以及十六，四种数制，利用栈的特性设计程序自动实现数制之间的转化。 2. 在许多语言现象中，常见到一种形如abcba的文字，这种文字从左到右读和从右到左读结果是一样的，这种文字就是常说的回文。设计一个程序可以判断给定的一个文字是否是回文。 说明： （1）需要注意的是，在程序中要能实现带小数部分的数值的转化。尤其需要注意的是对十六进制的转化，在实际中分别用A、B、C、D、E、F来表示10、11、12、13、14、15。在实际输出的时候要注意这一现象。具体实现中，将待转化的数按照数制取模，将余数放入栈中，而将商作为下一次取模的操作数，重复上述过程，直到最后的商为0。而对于有小数部分的数进行转化时一定要注意，将整数部分和小数部分分开处理，小数部分的转化与前述过程类似，不同之处在于，每次都是乘以待转数制，然后取整数部分放入栈中，重复这一过程。 （2）考虑到栈的先进后出以及队列的后进先出，可以结合这两种结构来实现需要的功能，即将文字分别入队和入栈，然后依次输出判断是否有不相同的字符，一旦发现就证明文字不是一个回文。 三．实现提示 栈的主要数据结构定义如下： typedef struct{ ElemType *base; ElemType *top; int stacksize; }sqstack; 四．思考及选做 1．对于有小数部分进行转化后，输出怎么能将整数和小数部分