一、实验要求⒈问题分析:充分地分析和理解问题本身,弄清要求做什么,包括功能要求、性能要求、设计要求和约束以及基本数据特性,数据间的联系等。
⒉数据结构设计:针对要求解决的问题,考虑各种可能的数据结构,并且力求从中出最佳方案(必须连同算法一起考虑),确定主要的数据结构及全程变量。
对引入的每种数据结构和全程变量要详细说明其功能、初值和操作特点。
⒊算法设计:算法设计分概要设计和详细设计,概要设计着重解决程序的模块设计问题,包括考虑如何把程序自顶向下分解成若干顺序模块,并决定模块的接口,即模块间的相互关系以及模块之间的信息交换问题。
详细设计则要决定每个模块内部的具体算法,包括输入、处理和输出,相当于C语言中具体的函数设计。
⒋测试用例设计:准备典型测试数据和测试方案,测试数据要有代表性、敏感性,测试方案包括模块测试和模块集成测试。
⒌上机调试并分析结果:对程序进行编译,纠正程序中可能出现的语法错误。
测试前,先运行一遍程序看看究竟将会发生什么,如果错误较多,则根据事先设计的测试方案并结合现场情况进行错误跟踪。
最后,详细记录实验过程,并对实验结果进行分析,并于一周内提交实验报告。
二、实验报告要求1.实验报告格式:实验报告首页按学校统一印刷的实验报告模版书写。
2.实验报告内容:实验基本信息按照实验报告模版要求内容填写,不得有空项。
其中:☐实验预习报告内容包括:实验目的、任务、具体实验题目和要求;☐实验操作原始记录与实验报告内容应包括如下主要内容:算法设计思路简介核心算法设计描述:可以用自然语言、伪代码或流程图等方式算法的实现和测试结果:包括算法时的输入、输出,测试结果的分析与讨论,测试过程中遇到的主要问题及所采用的解决措施。
☐附录可包括源程序清单或其它说明(如功能模块之间的调用与被调用关系等)☐实验报告雷同者,本次实验成绩为0分或雷同实验报告平分得分三、实验内容实验一线性表应用一. 实验目的1、掌握用Turbo C或VC++上机调试线性表的基本方法;2、掌握线性表的基本操作,如插入、删除、查找,以及线性表合并等运算在顺序存储结构和链式存储结构上的运算;并能够运用线性表基本操作解决问题,实现相应算法。
二.实验题目1.单链表基本操作练习1)问题描述:在主程序中设计一个简单的菜单,分别调用相应的函数功能:1…建立链表2…连接链表3…输出链表0…结束2)实验要求:在程序中定义下述函数,并实现所要求的函数功能:CreateLinklist( ): 从键盘输入数据,创建一个单链表 ContLinklist( ):将前面建立的两个单链表首尾相连OutputLinklist( ):输出显示单链表3)实验提示:✧单链表数据类型定义(C语言)# include <stdio.h>typedef int ElemType; //元素类型typedef struct LNode{ ElemType data;struct LNode *next;}LNode,*LinkList;✧为了算法实现简单,最好采用带头结点的单向链表。
4)注意问题:✧重点理解链式存储的特点及指针的含义。
✧注意比较顺序存储与链式存储的各自特点。
✧注意比较带头结点、无头结点链表实现插入、删除算法时的区别。
✧单链表的操作是数据结构的基础,一定要注意对这部分的常见算法的理解。
2.约瑟夫环问题1)问题描述:有编号为1, 2…n 的 n 个人按顺时针方向围坐一圈,每人持有一个正整数密码。
开始给定一个正整数 m,从第一个人按顺时针方向自1开始报数,报到m者出列,不再参加报数,这时将出列者的密码作为m,从出列者顺时针方向的下一人开始重新自1开始报数。
如此下去,直到所有人都出列。
试设计算法,输出出列者的序列。
2)实验要求: 采用顺序和链式两种存储结构实现3) 实现提示:✧用顺序表来存储围座者的序号和密码(顺序存储结构).⏹用number 和code分别表示围座者的序号和密码.假设围座者人数为 j,当前使用密码为m,开始报数者位置为s, 那么下一出列者位置为s=(s+m-1)mod j.⏹当我们要在线性表的顺序存储结构上的第i个位置上插入一个元素时,必须先将线性表的第i个元素之后的所有元素依次后移一个位置,以便腾空一个位置,再把新元素插入到该位置。
若要删除第i个元素时,也必须把第i个元素之后的所有元素前移一个位置。
✧用链式存储解决此问题时可以采用循环链表.4)注意问题:✧顺序存储和链式存储实现此算法时计算出列位置的不同方法,人员出列后所做操作的区别。
实验二栈与队列应用一.实验目的1.实验设置基本要求:通过实验掌握栈或队列的基本操作的实现,并能灵活运用栈或队列特性,综合运用程序设计、算法分析等知识解决实际问题。
2.实验设置较高要求:理解组成递归算法的基本条件,理解递归算法与相应的非递归算法的区别,理解栈和队列的应用与作用。
二.实验题目1.算术表达式求值演示1)问题描述:从键盘输入一个算术表达式并输出它的结果2)实验要求:算术表达式可包含加、减、乘、除、十进制整数和小括号,利用栈实现。
3) 实现提示:✧表达式作为一个串存储,如表达式“3*2-(4+2*1)”,其求值过程为:自左向右扫描表达式,当扫描到3*2时不能马上计算,因后面可能还有更高的运算,正确的处理过程是:⏹需要两个栈:对象栈OPND和算符栈OPTR;⏹自左至右扫描表达式, 若当前字符是运算对象,入OPND栈;⏹对运算符,若这个运算符比栈顶运算符高则入栈,继续向后处理,若这个运算符比栈顶运算符低则从OPND栈出栈两个数,从OPTR栈出栈一运算符进行运算,并将其运算结果入OPND栈,继续处理当前字符,直到遇到结束符。
4)注意问题✧重点理解栈的算法思想,能够根据实际情况选择合适的存储结构。
✧注意算法的各个函数之间值的传递情况。
2.停车场管理问题1)问题描述:设有一个可以停放n辆汽车的狭长停车场,它只有一个大门可以供车辆进出。
车辆按到达停车场的早晚依次从停车场最里面向大门口处停放(最先到达的第一辆车放在停车场的最里面)。
如果停车场已放满n辆车,则后来的车辆只能在停车场大门外的便道上等待,一旦停车场内有车走开,则排在便道上的第一辆车就进入停车场。
停车场内如有某辆车要开走,在它之后进入停车场的车都必须先退出停车场为它让路,待其开出停车场后,这些车辆再依原来的次序进场。
每辆车在离开停车场时,都应根据它在停车场内停留的时间长短交费。
如果停留在便道上的车未进停车场就要离去,允许其离去,不收停车费,并且仍然保持在便道上等待的车辆的次序。
编写程序模拟该停车场的管理。
2)实验要求: 要求程序输出每辆车到达后的停车位置(停车场或便道上),以及某辆车离开停车场时应缴纳的费用和他在停车场内停留的时间3)实现提示:以栈模拟停车场,以队列模拟便道,按照从终端读入的车辆“到达”“离开”信息模拟停车场管理4)注意问题✧重点理解栈、队列的算法思想,能够根据实际情况选择合适的存储结构。
✧栈、队列的算法是后续实验的基础(广义表、树、图、查找、排序等)。
实验三二叉树的操作一.实验目的1、基本要求:深刻理解二叉树性质和及各种存储结构的特点及适用范围;掌握用指针类型描述、访问和处理二叉树的运算;熟练掌握二叉树的遍历算法;2、较高要求: 在遍历算法的基础上设计二叉树更复杂操作算法;认识哈夫曼树、哈夫曼编码的作用和意义;掌握树与森林的存储与便利。
二.实验题目1.以二叉链表为存储结构,实现二叉树的创建、遍历1)问题描述:在主程序中设计一个简单的菜单,分别调用相应的函数功能:1…建立树2…前序遍历树3…中序(非递归)遍历树4…后序遍历树0…结束2)实验要求:在程序中定义下述函数,并实现要求的函数功能:CreateTree(): 按从键盘输入的前序序列,创建树PreOrderTree():前序遍历树(递归)InOrderTree():中序(非递归)遍历树LaOrderTree(): 后序遍历树(递归)3)实验提示:✧二叉链表存储数据类型定义# define ElemType char //元素类型typedef struct BiTNode{ ElemType data;struct BiTNode *lchild,*rchild;}BiTNode,*BiTree;✧元素类型可以根据实际情况选取。
4)注意问题:✧注意理解递归算法的执行步骤。
✧注意字符类型数据在输入时的处理。
✧重点理解如何利用栈结构实现非递归算法2.编写算法交换二叉树中所有结点的左、右子树1)问题描述:编写一算法,交换二叉树中所有结点的左、右子树2)实验要求:以二叉链表作为存储结构3) 实现提示:设二叉树的根指针未t,且以二叉链表表示,可利用一个类型为seqstack的指针来实现,且栈单元包含两个域,一个为data,另一个为top,整个栈容量为maxsize,当树非空时,将当前的树根结点入栈,同时将当前栈顶元素出栈当作根结点,然后依据当前的根结点是否具有孩子结点来判定是否将其左、右指针进行交换;再将交换后的左指针或右指针入栈,这样反复进行,直到栈空为止。
4)注意问题:✧注意理解算法中栈结构的利用3.试编写按层次顺序遍历二叉树的算法1)问题描述:编写按层次顺序遍历二叉树的算法2)实验要求:以二叉链表作为存储结构3) 实现提示:本算法要采用一个队列q,先将二叉树根结点入队列,然后出队列,输出该结点;若它有左子树,便将左子树根结点入队列;若它有右子树,便将右子树根结点入队列,直到队列空为止。
因为队列的特点是先进先出,从而达到按层次顺序遍历二叉树目的。
4)注意问题:✧理解算法中队列结构的利用实验四图的遍历一、实验目的1、基本要求:通过实验掌握理解图的两种主要存储结构,掌握图的构造算法,掌握图的深度优先遍历、广度优先遍历算法。
2、较高要求:理解拓扑排序、AOV网、AOE网等图型结构的操作方法应用价值。
二.实验题目1.键盘输入的数据建立图,并进行深度优先搜索和广度优先搜索1)问题描述:在主程序中设计一个简单的菜单,分别调用相应的函数功能:1…图的建立2…深度优先遍历图3…广度优先遍历图0…结束2)实验要求:在程序中定义下述函数,并实现要求的函数功能:CreateGraph(): 按从键盘的数据建立图DFSGrahp():深度优先遍历图BFSGrahp():广度优先遍历图3)实验提示:✧图的存储可采用邻接表或邻接矩阵;✧图存储数据类型定义(邻接表存储)# define MAX_VERTEX_NUM 8 //顶点最大个数typedef struct ArcNode{ int adjvex;struct ArcNode *nextarc;int weight; //边的权}ArcNode; //表结点# define VertexType int //顶点元素类型typedef struct VNode{int degree,indegree;//顶点的度,入度VertexType data;ArcNode *firstarc;}Vnode /*头结点*/,AdjList[MAX_VERTEX_NUM]; typedef struct{AdjList vertices;int vexnum,arcnum;//顶点的实际数,边的实际数}ALGraph;4)注意问题:✧注意理解各算法实现时所采用的存储结构。