软件开发技术指导书.doc

软件开发技术实验指导书软件开发技术指导书目 录软件开发技术基础实验报告4实验一 线性表的操作（2学时）5实验二 栈、队列的操作（3学时）6实验三 停车场管理(3学时)7实验四 树和二叉树的操作（3学时）8实验五 查找算法实现（2学时）9实验六 排序综合实验（3学时）10 软件技术开发主要介绍线性结构、树结构、图结构三种逻辑结构元素的存储实现，在此基础上介绍一些典型算法及时、空效率分析。这门课程的主要任务是培养学生的算法设计能力及良好的程序设计习惯。通过学习，要求学生能够掌握典型算法的设计思想及程序实现，能够根据实际问题选取合适的存储方案，设计出简洁、高效、实用的算法，为后续课程的学习及软件开发打下良好的基础。学习这门课程，习题和实验是两个关键环节。学生理解算法，上机实验是最佳的途径之一。因此，实验环节的好坏是学生能否学好软件技术开发的关键。为了更好地配合学生实验，特编写实验指导书。一、实验目的 更好的理解算法的思想、培养编程能力。二、实验要求1、 每次实验前学生必须根据试验内容认真准备实验程序及调试时所需的输入数据。 2、在指导教师的帮助下能够完成实验内容，得出正确的实验结果。 3、实验结束后总结实验内容、书写实验报告。 4、遵守实验室规章制度、不缺席、按时上、下机。 5、实验学时内必须做有关内容，不允许上网聊天或玩游戏，如发现上述现象，取消本次上机资格，平时成绩扣10分。 三、实验环境 VC+6.0；本实验的所有算法中元素类型可以根据实际需要选择。四、实验报告的书写要求 1明确实验的目的及要求； 2记录实验的输入数据和输出结果； 3说明实验中出现的问题和解决过程； 4写出实验的体会和实验过程中没能解决的问题；五、参考书目 软件技术开发（C+语言描述） 王红梅等 清华大学出版社DATA STRUCTURE WITH C+ William Ford,William Topp清华大学出版社（影印版）软件开发技术基础实验报告（后面的都参照这样写） 实验名称：实验一 线性表的操作 班 级 学 号 姓 名 第 周 星 期 、 节 成 绩 实验目的：参照给定的线性表顺序表类和链表类的程序样例，验证给出的线性表的常见算法实验内容：参照给定的线性表顺序表类和链表类的程序样例，验证给出的线性表的常见算法实验要求：（1）将程序输入计算机，编译运行。（2）程序的实际功能与上述所列功能不完全相符，调试程序，找出问题所在，并纠正。实验原理具体写出线性表的生成、插入、删除和查找运算的算法描述（形式语言或程序流程图表示出来）。实验步骤：写出调试、查找程序中问题的思路和步骤。实验结果：写出修改前后的运行结果。附：源程序和输入对应数据以及对应输出结果。实验一 线性表的操作（2学时）实验类型：验证性 实验要求：必修实验学时： 2学时一、实验目的：参照给定的线性表顺序表类和链表类的程序样例，验证给出的线性表的常见算法。二、实验要求：1、掌握线性表顺序表类和链表类的特点。掌握线性表的常见算法。2、提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。三、实验内容：设计一个静态数组存储结构的顺序表类，要求编程实现如下任务：1）建立一个线性表，首先依次输人整数数据元素（个数根据自己的需要键盘给定）2）删除指定位置的数据元素（指定元素位置通过键盘输入）再依次显示删除后的线性表中的数据元素。3）查找指定数据的数据元素（指定数据的大小通过键盘输入），若找到则显示位置，若没有找到就显示0。四、要求1）采用顺序表实现，假设该顺序表的数据元素个数在最坏情况下不会超过50个。2）写出完整的程序并能调试通过即可实验二 栈、队列的操作（3学时）实验类型：验证性 实验要求：必修实验学时： 3学时一、实验目的：参照给定的栈类和队列类的程序样例，验证给出的栈和队列的常见算法，并结合线性表类实现有关串的操作。二、实验要求：1、掌握栈、队列、串的特点。掌握特殊线性表的常见算法。2、提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。三、实验内容： 1. 堆栈类测试和应用问题。要求： (1)设计一个主函数实现对顺序堆栈类和链式堆栈类代码进行测试。测试方法为：依次把数据元素1,2,3,4,5入栈，然后出栈堆栈中的数据元素并在屏幕上显示。 (2)定义数据元素的数据类型为如下形式的结构体：typedef struct char taskname10;/任务名 int taskno;/任务号 DataType； 设计一个包含5个数据元素的测试数据，并设计一个主函数实现依次把5个数据元素入栈，然后出栈堆栈中的数据元素并在屏幕上显示。2. 队列类测试和应用问题。要求： 设计一个主函数对循环队列类和链式队列类代码进行测试.测试方法为：依次把数据元素1,2,3,4,5入队，然后出队中的数据元素并在屏幕上显示。四、要求1）栈和队列的长度都由自己定；2）写出完整的程序并能调试通过即可。3)重点理解栈、队列和串的算法思想，能够根据实际情况选择合适的存储结构。 4)栈、队列的算法是后续实验的基础（树、图、查找、排序等）。实验三 停车场管理(3学时) 实验类型：设计性【实验内容与要求】设停车场内只有一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后开入的车辆必须先退出车场为它让路，待该辆车开出大门外，其它车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。【知识要点】综合利用栈和队列模拟停车场管理，学习利用栈和队列解决实际问题。【实现提示】以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，对每一组输入数据进行操作后的输出数据为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车离去；则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表实现。需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照号码和进入停车场的时刻。设n=2,输入数据为：（A，1，5），（A，2，10），（D，1，15），（A，3， 20）， （A，4，25），（A，5，30），（D，2，35），（D，4，40），（E，0，0）。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，其中，A表示到达；D表示离去，E表示输入结束。实验四 树和二叉树的操作（3学时）实验类型：验证性 实验要求：必修实验学时： 2学时一、实验目的：参照给定的二叉树类的程序样例，验证给出的有关二叉树的常见算法，并实现有关的操作。二、实验要求：1、掌握二叉树、哈夫曼树和树的特点。掌握它们的常见算法。2、提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。三、实验内容： 1设计实现二叉树类，要求：（1）编写一个程序，首先建立不带头结点的二叉链式存储结构的二叉树，然后分别输出按照前序遍历二叉树、中序遍历二叉树和后序遍历二叉树访问各结点的序列信息，最后再测试查找函数和撤销函数的正确性。（2）实现二叉树层次遍历的非递归算法。 （3）编写一主函数来验证算法实现。 2. 假设二叉树采用链式存储结构进行存储，编写一个算法，输出一个二叉树的所有叶子结点，并统计叶子结点个数。实验五 查找算法实现（2学时）实验类型：验证性 实验要求：必修实验学时： 2学时一、实验目的：参照各种查找算法程序样例，验证给出的查找常见算法。 二、实验要求：1、掌握各种查找算法的特点，测试并验证查找的常见算法。2、提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。三、实验内容：1. 建立有序表，采用折半查找实现某一已知的关键字的查找。2利用折半查找算法在一个有序表中插入一个元素，并保持表的有序性。实验六 排序综合实验（3学时）实验类型：综合性 实验要求：必修实验学时： 2学时一、实验目的：参照各种排序算法程序样例，验证给出的排序常见算法。 二、实验要求：1、掌握各种排序算法的特点，测试并验证排序的常见算法。2、提交实验报告，报告内容包括：目