下载文档原格式
2013级软件工程专业《数据结构课程设计》方案V1.0一、课程任务要求独立完成一个或多个较为完整的应用需求分析，在完成设计和编程大型作业的过程中，深化对数据结构课程中概念、理论和方法的理解；训练综合运用所学知识处理实际问题的能力，强化面向对象的程序设计理念；使同学的程序设计与调试水平有一个明显的提高；经过查找参考资料、技术手册和撰写文档的实践，进一步培养软件工程师的综合素质。
二、具体要求1.每人应至少独立完成一道题目并撰写课程报告，具体题目由任课老师组织分配，题目一旦选定，未经老师同意，不得私自更换，否则总评成绩为缺成绩。
2.按时出勤，旷课2次直接取消答辩资格，旷课1次总评成绩降低1个等级。
3. 听从值班老师安排，按所选题目分区坐在指定位置。
4. 按时提交课程设计资料，未按格式或未在规定时间提交资料的，总评成绩为缺成绩。
三、具体安排1. 时间：18周周一至周五上午、下午2. 地点：4-312（1、2、3题）、4-313（4、5、6题）3. 答辩时间：19周周1上午、下午4. 课程设计具体考核标准和流程由题目指导老师负责。
四、课程设计题目与内容1. 数据压缩与解压缩利用哈夫曼编码完成数据的压缩与解压缩，具体要求如下：（1）哈夫曼编码的动画显示，程序运行界面如下：（40分）在上面文本框中输入待编码的字符串，点击“Show Huffman Tree”按钮输入，生成哈夫曼树并显示该字符串的哈夫曼编码。
如下图所示：在下面文本框中输入二进制哈夫曼串，点击“Decode Text”，能够还原为原来的字符。
比如输入"001" 显示"w"，输入"01001" 显示"ow"，如下图所示：（2）在上面程序的基础上，编写程序，在控制台或GUI中输入文件名（如filename.dat)，通过哈夫曼数据压缩算法生成filename.new, 同时，使用数组存储每个字符哈夫曼编码，通过对象输出流将该数组写入文件filename.huf中。
《软件工程》实验指导书任课教师：周喜平授课班级：2012级软件工程(软件开发方向)1班、2014计算机科学与技术专升本1班《软件工程（考试）》实验指导书实验目录实验一软件过程模型.......................................................................... 错误！未定义书签。
实验二可行性分析 ............................................................................. 错误！未定义书签。
实验三需求分析 ................................................................................. 错误！未定义书签。
实验四总体设计 ................................................................................. 错误！未定义书签。
实验五详细设计 ................................................................................. 错误！未定义书签。
实验六实现之编码 ............................................................................. 错误！未定义书签。
实验七实现之测试 ............................................................................. 错误！未定义书签。
实验八维护 ........................................................................................ 错误！未定义书签。
辽宁工程技术大学应用与技术学院实验指导书实验科目：软件工程及测试系别：计算机系专业：计算机应用编写人：包剑时间： 2013年2月前言《软件工程及测试实验》是为应用技术学院计算机应用专业《软件工程及测试》课程配套设置的，是《软件工程及测试》课程讲授中一个重要的、不可或缺的环节。
其目的是使学生能够针对具体软件工程项目，全面掌握软件工程管理、需求分析、概要设计、详细设计、软件测试等阶段的方法和技术，通过实验使学生进一步理解和掌握软件开发模型、软件生命周期、软件过程等理论在软件项目开发过程中的意义和作用，培养学生按照软件工程的原理、方法、技术、标准和规范，进行软件开发的能力，培养学生的合作意识和团队精神，培养学生对技术文档的编写能力，使学生提高软件工程的综合能力，提高软件项目的管理能力。
按该课程的特点，实验内容包括软件开发的两大方法学的专题训练，即结构化（生命周期学）的方法学和面向对象的方法学，通过分析一个简单项目，要求学生利用结构化软件开发技术或面向对象的软件开发技术完成对该项目的开发。
因此设置的实验项目，从项目开发的准备工作，系统分析过程，系统设计过程，软件测试到系统实施，覆盖软件开发的整个过程，此外又引入我国国家《计算机开发规范》，以规范技术文档的书写标准，提高实验教学质量。
通过实验训练，达到如下目的：使学生进一步了解和掌握软件工程原理，提高对实际项目的分析和设计能力，通过实验课程，熟悉和基本掌握软件工程方法学、软件开发的过程，文档资料的编写格式及规范，全面领会和贯通所学习的理论知识，从而培养学生综合运用所学课程知识，分析解决问题的能力，培养学生理论联系实际作风，实事求是，严肃认真的科学态度和良好的工作作风，为今后工作打下基础。
概述一、实验目的《软件工程及测试》是一门实践性很强的课程，上机实验是其重要的环节，实验配合《软件工程及测试》课程的学习而制订的，其实验目的和任务是：通过实验，熟悉和基本掌握软件的工程设计方法、软件工程设计的表达形式、以及实现工程设计的辅助软件工程工具的使用。
数据结构实验指导书一、实验目的数据结构是计算机科学中的重要基础课程，通过实验，旨在帮助学生更好地理解和掌握数据结构的基本概念、原理和算法，提高学生的编程能力和问题解决能力。
具体而言，实验的目的包括：1、加深对常见数据结构（如数组、链表、栈、队列、树、图等）的理解，掌握其特点和操作方法。
2、培养学生运用数据结构解决实际问题的能力，提高算法设计和程序实现的能力。
3、增强学生的逻辑思维能力和调试程序的能力，培养学生的创新意识和团队合作精神。
二、实验环境1、操作系统：Windows 或 Linux 操作系统。
2、编程语言：C、C+＋、Java 等编程语言中的一种。
3、开发工具：如 Visual Studio、Eclipse、Code:：Blocks 等集成开发环境（IDE）。
三、实验要求1、实验前，学生应认真预习实验内容，熟悉相关的数据结构和算法，编写好实验程序的代码框架。
2、实验过程中，学生应独立思考，认真调试程序，及时记录实验过程中出现的问题及解决方法。
3、实验完成后，学生应撰写实验报告，包括实验目的、实验内容、实验步骤、实验结果、问题分析与解决等。
四、实验内容（一）线性表1、顺序表的实现与操作实现顺序表的创建、插入、删除、查找等基本操作。
分析顺序表在不同操作下的时间复杂度。
2、链表的实现与操作实现单链表、双向链表的创建、插入、删除、查找等基本操作。
比较单链表和双向链表在操作上的优缺点。
（二）栈和队列1、栈的实现与应用实现顺序栈和链式栈。
利用栈解决表达式求值、括号匹配等问题。
2、队列的实现与应用实现顺序队列和链式队列。
利用队列解决排队问题、广度优先搜索等问题。
（三）树1、二叉树的实现与遍历实现二叉树的创建、插入、删除操作。
实现二叉树的前序、中序、后序遍历算法，并分析其时间复杂度。
2、二叉搜索树的实现与操作实现二叉搜索树的创建、插入、删除、查找操作。
分析二叉搜索树的性能。
（四）图1、图的存储结构实现邻接矩阵和邻接表两种图的存储结构。
《软件工程》课程实验指导书华北水利水电大学信息工程学院计算机科学与技术专业2016年5月《软件工程》课程实验指导书一、实验选题与要求自由选择题目，但每个班级的选题按照学号尾数为0、5选第1题，尾数为1、6选第2题，尾数为2、7选第3题，尾数为3、8选第4题，尾数为4、9选第5题。
1、单科学生成绩管理系统任务：对在校某班学生一门课程的平时成绩与考试成绩进行统一管理。
每个学生记录包括学号、姓名、每次习题（按16次计）、测验（按3次计）、考试成绩和总评成绩等信息，以学号为序存放。
要求：（1）一个文件按以班为单位存储学生记录。
（2）将允许的操作分为四种，以A、B、C、D为标志（若设置菜单操作更佳）：A：插入一个新的学生记录；B：登记某次成绩（可以是每次习题、测验、考试成绩）；C：修改某次成绩（可以是每次习题、测验、考试成绩）；D：删除一个学生记录。
（3）计算学生的最终成绩，各项成绩权重为：习题10%、测验20%、考试70%。
（4）按学号排序打印全班成绩表，表格内容包括习题、测验、考试、总评成绩，前三项为百分制，总评成绩为加权计算结果值。
设置教师和学生两种登录系统身份，每个用户应有自己的口令；教师身份可以完成上述基本要求的功能，学生可以通过输入学号查询个人成绩。
2、飞机航班订票系统任务：通过此系统可以实现如下功能：（1）录入：录入航班信息（数据可以存储在一个数据文件中）（2）查询：可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）；可以输入起飞抵达城市，查询飞机航班情况；（3）订票：（订票情况可以存在一个数据文件中）可以订票，如果该航班已经无票，可以提供相关可选择航班；（4）退票：可退票，退票后修改相关数据文件；订票的客户信息有姓名，证件号，订票数量及航班，订单要有编号。
（5）修改航班信息：当航班信息改变可以修改航班数据文件。
3、宾馆管理信息系统任务：入住或预订客房时，用户要对客户管理模块或预订管理模块进行核对审查，并进行登记；客户换房时，要对换房信息进行查询和更新；客户退房时，要进行结算，并对更新客房信息。
数据结构实验指导书适用所有开设数据结构实验的专业雷文赵攀编写概述一、课程目的《数据结构》是一门实践性很强的软件基础课程，为了学好这门课，每个学生必须完成一定数量的上机作业。
通过本课程的上机作业，要求在数据结构的选择和应用、算法的设计及实现等方面加深对课程基础内容的理解，同时，实验题中的问题比平时的练习题要复杂，也更接近实际，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。
本课程实验的目的是旨在使学生进一步巩固课堂上所学的理论知识；深化理解和灵活掌握教学内容；培养学生算法设计的能力和解决实际问题的程序设计的能力。
二、实验名称与学时分配三、实验要求⒈问题分析充分地分析和理解问题本身，弄清要求做什么，包括功能要求、性能要求、设计要求和约束以及基本数据特性，数据间的联系等。
⒉数据结构设计针对要求解决的问题，考虑各种可能的数据结构，并且力求从中出最佳方案(必须连同算法一起考虑)，确定主要的数据结构及全程变量。
对引入的每种数据结构和全程变量要详细说明其功能、初值和操作特点。
⒊算法设计算法设计分概要设计和详细设计，概要设计着重解决程序的模块设计问题，这包括考虑如何把被开发的问题程序自顶向下分解成若干顺序模块，并决定模块的接口，即模块间的相互关系以及模块之间的信息交换问题.详细设计则要决定每个模块内部的具体算法，包括输入、处理和输出，采用类C语言描述。
⒋测试用例设计准备典型测试数据和测试方案，测试数据要有代表性、敏感性，测试方案包括模块测试和模块集成测试。
⒌上机调试对程序进行编译，纠正程序中可能出现的语法错误，测试前，先运行一遍程序看看究竟将会发生什么，如果错误较多，则根据事先设计的测试方案并结合现场情况进行错误跟踪，包括打印执行路径或输出中间变量值等手段。
三、实验考核每次实验结束后，均应上交实验报告。
数据结构课程实验成绩单独考核，占1个学分。
实验报告应包括如下内容：1、问题描述：简述题目要解决的问题是什么。
《数据结构》实验指导书第一部分前言一、实验的目的《数据结构》是计算机学科一门重要的专业基础课程,也是计算机学科的一门核心课程。
本课程的另一重要教学目的是训练学生进行复杂程序设计的技能和培养良好程序设计的习惯，要做到这一点，上机实习是必须的。
数据结构实验是对学生的一种全面综合训练，是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。
通常，实验课题中的问题比平时的习题复杂得多，也更接近实际。
实验着眼于原理与应用的结合点，使学生学会如何把书上学到的知识用于解决实际问题，训练学生实际动手进行程序设计和调试程序的能力，加深对数据结构相关概念和算法的理解。
通过完成本实验课程的实验，学生应学会并掌握本课程的基本和重点知识，深刻理解逻辑结构、物理结构和算法设计之间的关系，初步学会算法分析的方法，并能在一定范围内运用所掌握的分析方法进行算法分析，培养软件工作所需要的动手能力和作为一个软件工作者所应具备的科学工作方法和作风。
二、实验前的准备工作1．每个学生需配备一台计算机，操作系统需Windows2000/XP以上版本，软件需Visual C++6.0以上版本。
2．实验前要求学生按实验要求编写好相关实验程序，准备上机调试运行。
三、实验的步骤（一）建立一个文件夹，如“数据结构”，用来存放自己的所有实验程序，在该文件夹中建立子目录用来存放每个项目（一个子目录一个项目），如“顺序表”，项目中需要的所有文件都存在该文件夹中。
（二）新建一个项目文件1．双击Visual C++ 6.0快捷图标，进入Visual C++ 6.0集成开发环境；或者点击“开始”→“程序”→“Microsoft Visual Studio 6.0”→“Microsoft Visual C++ 6.0”进入Visual C++ 6.0集成开发环境。
2．单击“File”菜单，选择“New”命令3．创建一个项目文件并保存在项目所在文件夹中；3. 创建源程序文件并保存在项目所在文件夹中；4．输入源程序；5．单击“保存”按钮保存源程序。
《数据结构》实验指导书实验一线性表【实验目的】1、掌握用Turbo c上机调试线性表的基本方法；2、掌握线性表的基本操作，插入、删除、查找以及线性表合并等运算在顺序存储结构和链式存储结构上的运算；3、运用线性表解决线性结构问题。
【实验学时】4 学时【实验类型】设计型【实验内容】1、顺序表的插入、删除操作的实现；2、单链表的插入、删除操作的实现；3、两个线性表合并算法的实现。
(选做)【实验原理】1、当我们在线性表的顺序存储结构上的第i个位置上插入一个元素时，必须先将线性表中第i个元素之后的所有元素依次后移一个位置，以便腾出一个位置，再把新元素插入到该位置。
若是欲删除第i个元素时，也必须把第i个元素之后的所有元素前移一个位置；2、当我们在线性表的链式存储结构上的第i个位置上插入一个元素时，只需先确定第i个元素前一个元素位置，然后修改相应指针将新元素插入即可。
若是欲删除第i个元素时，也必须先确定第i个元素前一个元素位置，然后修改相应指针将该元素删除即可；3、详细原理请参考教材。
【实验步骤】一、用C语言编程实现建立一个顺序表，并在此表中插入一个元素和删除一个元素1、通过键盘读取元素建立线性表；2、指定一个元素，在此元素之前插入一个新元素；3、指定一个元素，删除此元素。
二、用C语言编程实现建立一个单链表，并在此表中插入一个元素和删除一个元素1、通过键盘读取元素建立单链表；2、指定一个元素，在此元素之前插入一个新元素；3、指定一个元素，删除此元素。
三、用C语言编程实现两个按递增顺序排列线性表的合并1、编程实现合并按递增顺序排列的两个顺序表算法；2、编程实现合并按递增顺序排列的两个单链表算法。
【思考问题】结合实验过程，回答下列问题：1、何时采用顺序表处理线性结构的问题为最佳选择；2、何时采用链表处理线性结构的问题为最佳选择。
【实验报告要求】1、根据对线性表的理解，如何创建顺序表和单链表；2、实现顺序表插入和删除操作的程序设计思路；3、实现链表插入和删除操作的程序设计思路；4、实现两表合并操作的程序设计思路；5、调试程序过程中遇到的问题及解决方案；6、本次实验的结论与体会。
******************* 《软件工程》实验指导书（自编）******************* 计算机科学与信息工程学院目录一．课程实验目的和任务 (1)二．综合实验题目 (1)三．实验安排 (2)实验一系统需求分析....................................................................................错误!未定义书签。
一．实验目的............................................................................................错误!未定义书签。
二．准备知识............................................................................................错误!未定义书签。
三．实验内容............................................................................................错误!未定义书签。
四．实验指导............................................................................................错误!未定义书签。
实验二系统概要设计. (12)一．实验目的 (12)二．准备知识 (12)三．实验内容 (12)四．实验指导 (19)实验三系统详细设计 (24)一．实验目的 (24)二．准备知识 (24)三．实验内容 (24)四．实验指导 (25)实验四系统编码实现 (28)一．实验目的 (28)二．准备知识 (28)三．实验内容 (28)四．实验指导 (29)实验五系统测试 (30)一．实验目的 (30)二．准备知识 (30)三．实验内容 (30)四．实验指导 (30)一．课程实验目的和任务软件工程课程实验目的是通过具体的应用软件系统的开发实现，使学生能够结合课程有关软件生命期的介绍，规范软件设计与实现过程的文档要求，掌握软件设计的规范，理解软件工程课程的基本理论与方法。
数据结构实验指导书前言《数据结构》是软件工程等专业的一门核心基础课程，也是很多高校考研专业课之一。
它主要介绍线性结构、树结构、图结构三种逻辑结构元素的存储实现，在此基础上介绍一些典型算法及时、空效率分析。
这门课程的主要任务是培养学生的算法设计能力及良好的程序设计习惯。
通过学习，要求学生能够掌握典型算法的设计思想及程序实现，能够根据实际问题选取合适的存储方案，设计出简洁、高效、实用的算法，为后续课程的学习及软件开发打下良好的基础。
学习这门课程，习题和实验是两个关键环节。
学生理解算法，上机实验是最佳的途径之一。
因此，实验环节的好坏是学生能否学好《数据结构》的关键。
为了更好地配合学生实验，特编写实验指导书。
一、实验目的更好的理解算法的思想、培养算法设计、分析及程序调试能力。
二、实验要求1、每次实验前学生必须根据试验内容认真准备实验程序及调试时所需的输入数据及预期输出数据。
2、独立完成或在指导教师的帮助下，完成实验项目，得出正确的实验结果。
3、遵守实验室规章制度、不缺席、按时上、下机。
4、实验学时内必须做数据结构的有关内容，不允许上网聊天或玩游戏，如发现上述现象，取消本次上机资格，平时成绩扣10分。
5、实验项目有一次未完成，扣5分，两次以上未完成者，平时成绩以零分记，不允许参加期末考试。
三、实验环境 VC++6.0或其它C++集成环境四、说明1、本实验的所有算法中元素类型可以根据实际需要选择。
2、实验题目中带＊者为较高要求，学生可自选；其余部分为基本内容，必须完成，否则实验不合格。
3、数据结构是很多高校的硕士研究生入学考试的专业课之一，希望有志于考研的学生能够在学习过程中注意各种算法的理解，以便为考研做一定的准备。
4、所有实验项目布置在在线评测系统平台（Online Judge System）上，校内访问IP：59.73.73.133，每位学生需实名注册账号，并将完成的实验项目在平台上提交，平台能够实现自动评测。
给大家的实验文档中分为一下几部分1.实验准备：其中是c＋＋的一些内容，希望大家能借此好好复习c＋＋。
因为大家现在使用的教材是c＋＋版本的，所以，对于c＋＋的一些基本语法，程序的编写都需要有些了解2.c语言实验教案中是一些c语言的基础知识，包括VC环境的使用和程序的调试，希望对c 语言已经忘记的同学好好看看复习一下。
（程序的编写调试是长年累月的过程，需要不断的积累，写得多了，程序调试的多了，自然就熟练了）3.对应的flash课件：其中是一些实验的flash课件演示，给大家做一下参考4.实验指导书和实验教案大家在做每个实验前都需要看看。
阅读的时候，可以使用【视图】|【文档结构图】，可以比较自由跳到相应位置5. 总体实验难度比较大，时间紧，单靠实验课上的几个学时，作为初学者是无法完成的，需要大家在课前课后尽自己最大的努力。
实验一栈和队列（2学时）实验二多项式加减法（2学时）实验三迷宫（4学时）实验四二叉树（4学时）实验五图（2学时）实验六归并排序（2学时）Programming Project one ：Application of Stack & Queue 一、实验目的通过几段代码的编写，熟悉栈和队列二、实验内容1、Reversing a list （必做，分3个小题目task1,task2,task3）2、Small airport simulation（选作）具体如下：Task 1:Compile and run the following sample application of stack from the text. You may need to make changes to the code if necessary. Write down your input and output.// Section 2.1:Reversing a List#include <stack>int main( )/* Pre: The user supplies an integer n and n decimal numbers.Post: The numbers are printed in reverse order.Uses: The STL class stack and its methods */{int n;double item;stack<double> numbers; // declares and initializes a stack of numberscout << " Type in an integer n followed by n decimal numbers."<< endl<< " The numbers will be printed in reverse order."<< endl;cin >> n;for (int i = 0; i < n; iCC) {cin >> item;numbers.push(item);}cout << endl << endl;while (!numbers.empty( )) {cout << numbers.top( ) << " ";numbers.pop( );}cout << endl;}Task 2:Assemble the appropriate declarations from the text into the files stack.h and stack.cpp. Make any necessary changes as re-compiling the above application Reversing a List by replacing the use of STL class stack with the use of user defined class Stack.// Section 2.2:const int maxstack = 10; // small value for testingclass Stack {public:Stack();bool empty() const;Error_code pop();Error_code top(Stack_entry &item) const;Error_code push(const Stack_entry &item);private:int count;Stack_entry entry[maxstack];};Error_code Stack::push(const Stack_entry &item)/*Pre: None.Post: If the Stack is not full, item is added to the topof the Stack. If the Stack is full,an Error_code of overflow is returned and the Stack is left unchanged.*/{Error_code outcome = success;if (count >= maxstack)outcome = overflow;elseentry[count++] = item;return outcome;}Error_code Stack::pop()/*Pre: None.Post: If the Stack is not empty, the top ofthe Stack is removed. If the Stackis empty, an Error_code of underflow is returned. */{Error_code outcome = success;if (count == 0)outcome = underflow;else --count;return outcome;}Error_code Stack::top(Stack_entry &item) const/*Pre: None.Post: If the Stack is not empty, the top ofthe Stack is returned in item. If the Stackis empty an Error_code of underflow is returned. */{Error_code outcome = success;if (count == 0)outcome = underflow;elseitem = entry[count - 1];return outcome;}bool Stack::empty() const/*Pre: None.Post: If the Stack is empty, true is returned.Otherwise false is returned.*/{bool outcome = true;if (count > 0) outcome = false;return outcome;}Stack::Stack()/*Pre: None.Post: The stack is initialized to be empty.*/{count = 0;}Task 3:Assume the following definition file for an extended stack data structure.class Extended_stack {public:Extended_stack();Error_code pop();Error_code push(Stack_entry item);Error_code top(Stack_entry &item) const;bool empty() const;void clear(); // Reset the stack to be empty.bool full() const ; // If the stack is full, return true; else return false.int size() const; // Return the number of entries in the stack.private:int count;Stack_entry entry[maxstack];};Implement the following methods: (a) clear (b) full (c) sizeUse method size of the class Extended_stack in your application Reversing a List to display the number of decimal numbers you imputed.Task 4:Combine all the functions and methods for the airport simulation into a complete program. Experiment with several sample rums of the airport simulation, adjusting the values for the expected numbers of planes ready to land and take off. Find approximate values for these expected numbers that are as large as possible subject to the condition that it is very unlikely that a plane must be refused service. What happens to these values if the maximum size of the queues is increased or decreased?/* Program extracts from Chapter 3 of"Data Structures and Program Design in C++"by Robert L. Kruse and Alexander J. RybaCopyright (C) 1999 by Prentice-Hall, Inc. All rights reserved.Extracts from this file may be used in the construction of other programs,but this code will not compile or execute as given here. */// Section 3.3:const int maxqueue = 10; // small value for testingclass Queue {public:Queue();bool empty() const;Error_code serve();Error_code append(const Queue_entry &item);Error_code retrieve(Queue_entry &item) const;protected:int count;int front, rear;Queue_entry entry[maxqueue];};Queue::Queue()/*Post: The Queue is initialized to be empty.*/{count = 0;rear = maxqueue - 1;front = 0;}bool Queue::empty() const/*Post: Return true if the Queue is empty, otherwise return false.*/{return count == 0;}Error_code Queue::append(const Queue_entry &item)/*Post: item is added to the rear of the Queue. If the Queue is full return an Error_code of overflow and leave the Queue unchanged. */{if (count >= maxqueue) return overflow;count++;rear = ((rear + 1) == maxqueue) ? 0 : (rear + 1);entry[rear] = item;return success;}Error_code Queue::serve()/*Post: The front of the Queue is removed. If the Queueis empty return an Error_code of underflow.*/{if (count <= 0) return underflow;count--;front = ((front + 1) == maxqueue) ? 0 : (front + 1);return success;}Error_code Queue::retrieve(Queue_entry &item) const/*Post: The front of the Queue retrieved to the outputparameter item. If the Queue is empty return an Error_code of underflow.*/{if (count <= 0) return underflow;item = entry[front];return success;}int Extended_queue::size() const/*Post: Return the number of entries in the Extended_queue.*/{return count;}// Section 3.5:int main() // Airport simulation program/*Pre: The user must supply the number of time intervals the simulation is torun, the expected number of planes arriving, the expected numberof planes departing per time interval, and themaximum allowed size for runway queues.Post: The program performs a random simulation of the airport, showingthe status of the runway at each time interval, and prints out asummary of airport operation at the conclusion.Uses: Classes Runway, Plane, Random and functions run_idle, initialize.*/{int end_time; // time to run simulationint queue_limit; // size of Runway queuesint flight_number = 0;double arrival_rate, departure_rate;initialize(end_time, queue_limit, arrival_rate, departure_rate);Random variable;Runway small_airport(queue_limit);for (int current_time = 0; current_time < end_time; current_time++) { // loop over time intervalsint number_arrivals = variable.poisson(arrival_rate); // current arrival requestsfor (int i = 0; i < number_arrivals; i++) {Plane current_plane(flight_number++, current_time, arriving);if (small_airport.can_land(current_plane) != success)current_plane.refuse();}int number_departures= variable.poisson(departure_rate); // current departure requests for (int j = 0; j < number_departures; j++) {Plane current_plane(flight_number++, current_time, departing);if (small_airport.can_depart(current_plane) != success)current_plane.refuse();}Plane moving_plane;switch (small_airport.activity(current_time, moving_plane)) {// Let at most one Plane onto the Runway at current_time.case land:moving_nd(current_time);break;case takeoff:moving_plane.fly(current_time);break;case idle:run_idle(current_time);}}small_airport.shut_down(end_time);}enum Runway_activity {idle, land, takeoff};class Runway {public:Runway(int limit);Error_code can_land(const Plane ¤t);Error_code can_depart(const Plane ¤t);Runway_activity activity(int time, Plane &moving);void shut_down(int time) const;private:Extended_queue landing;Extended_queue takeoff;int queue_limit;int num_land_requests; // number of planes asking to landint num_takeoff_requests; // number of planes asking to take off int num_landings; // number of planes that have landed int num_takeoffs; // number of planes that have taken off int num_land_accepted; // number of planes queued to landint num_takeoff_accepted; // number of planes queued to take off int num_land_refused; // number of landing planes refused int num_takeoff_refused; // number of departing planes refused int land_wait; // total time of planes waiting to land int takeoff_wait; // total time of planes waiting to take off int idle_time; // total time runway is idle};enum Plane_status {null, arriving, departing};class Plane {public:Plane();Plane(int flt, int time, Plane_status status);void refuse() const;void land(int time) const;void fly(int time) const;int started() const;private:int flt_num;int clock_start;Plane_status state;};void initialize(int &end_time, int &queue_limit,double &arrival_rate, double &departure_rate)/*Pre: The user specifies the number of time units in the simulation, the maximal queue sizes permitted,and the expected arrival and departure rates for the airport.Post: The program prints instructions and initializes the parameters end_time, queue_limit, arrival_rate, and departure_rate tothe specified values.Uses: utility function user_says_yes*/{cout << "This program simulates an airport with only one runway." << endl << "One plane can land or depart in each unit of time." << endl;cout << "Up to what number of planes can be waiting to land "<< "or take off at any time? " << flush;cin >> queue_limit;cout << "How many units of time will the simulation run?" << flush;cin >> end_time;bool acceptable;do {cout << "Expected number of arrivals per unit time?" << flush;cin >> arrival_rate;cout << "Expected number of departures per unit time?" << flush;cin >> departure_rate;if (arrival_rate < 0.0 || departure_rate < 0.0)cerr << "These rates must be nonnegative." << endl;elseacceptable = true;if (acceptable && arrival_rate + departure_rate > 1.0)cerr << "Safety Warning: This airport will become saturated. " << endl;} while (!acceptable);}Runway::Runway(int limit)/*Post: The Runway data members are initialized to record noprior Runway use and to record the limit on queue sizes.*/{queue_limit = limit;num_land_requests = num_takeoff_requests = 0;num_landings = num_takeoffs = 0;num_land_refused = num_takeoff_refused = 0;num_land_accepted = num_takeoff_accepted = 0;land_wait = takeoff_wait = idle_time = 0;}Error_code Runway::can_land(const Plane ¤t)/*Post: If possible, the Plane current is added to thelanding Queue; otherwise, an Error_code of overflow isreturned. The Runway statistics are updated.Uses: class Extended_queue.*/{Error_code result;if (landing.size() < queue_limit)result = landing.append(current);elseresult = fail;num_land_requests++;if (result != success)num_land_refused++;elsenum_land_accepted++;return result;}Error_code Runway::can_depart(const Plane ¤t)/*Post: If possible, the Plane current is added to thetakeoff Queue; otherwise, an Error_code of overflow isreturned. The Runway statistics are updated.Uses: class Extended_queue.*/{Error_code result;if (takeoff.size() < queue_limit)result = takeoff.append(current);elseresult = fail;num_takeoff_requests++;if (result != success)num_takeoff_refused++;elsenum_takeoff_accepted++;return result;}Runway_activity Runway::activity(int time, Plane &moving) /*Post: If the landing Queue has entries, its frontPlane is copied to the parameter movingand a result land is returned. Otherwise,if the takeoff Queue has entries, its frontPlane is copied to the parameter movingand a result takeoff is returned. Otherwise,idle is returned. Runway statistics are updated. Uses: class Extended_queue.*/{Runway_activity in_progress;if (!landing.empty()) {landing.retrieve(moving);land_wait += time - moving.started();num_landings++;in_progress = land;landing.serve();}else if (!takeoff.empty()) {takeoff.retrieve(moving);takeoff_wait += time - moving.started();num_takeoffs++;in_progress = takeoff;takeoff.serve();}else {idle_time++;in_progress = idle;}return in_progress;}Plane::Plane(int flt, int time, Plane_status status)/*Post: The Plane data members flt_num, clock_start, and state are set to the values of the parameters flt,time and status, respectively.*/{flt_num = flt;clock_start = time;state = status;cout << "Plane number " << flt << " ready to ";if (status == arriving)cout << "land." << endl;elsecout << "take off." << endl;}Plane::Plane()/*Post: The Plane data members flt_num, clock_start, state are set to illegal default values.*/{flt_num = -1;clock_start = -1;state = null;}void Plane::refuse() const/*Post: Processes a Plane wanting to use Runway, when the Queue is full.*/{cout << "Plane number " << flt_num;if (state == arriving)cout << " directed to another airport" << endl;elsecout << " told to try to takeoff again later" << endl; }void Plane::land(int time) const/*Post: Processes a Plane that is landing at the specified time.*/{int wait = time - clock_start;cout << time << ": Plane number " << flt_num << " landed after "<< wait << " time unit" << ((wait == 1) ? "" : "s")<< " in the takeoff queue." << endl;}void Plane::fly(int time) const/*Post: Process a Plane that is taking off at the specified time.*/{int wait = time - clock_start;cout << time << ": Plane number " << flt_num << " took off after "<< wait << " time unit" << ((wait == 1) ? "" : "s")<< " in the takeoff queue." << endl;}int Plane::started() const/*Post: Return the time that the Plane entered the airport system.*/{return clock_start;}void run_idle(int time)/*Post: The specified time is printed with a message that the runway is idle. */{cout << time << ": Runway is idle." << endl;}void Runway::shut_down(int time) const/*Post: Runway usage statistics are summarized and printed.*/{cout << "Simulation has concluded after " << time << " time units." << endl << "Total number of planes processed "<< (num_land_requests + num_takeoff_requests) << endl<< "Total number of planes asking to land "<< num_land_requests << endl<< "Total number of planes asking to take off "<< num_takeoff_requests << endl<< "Total number of planes accepted for landing "<< num_land_accepted << endl<< "Total number of planes accepted for takeoff "<< num_takeoff_accepted << endl<< "Total number of planes refused for landing "<< num_land_refused << endl<< "Total number of planes refused for takeoff "<< num_takeoff_refused << endl<< "Total number of planes that landed "<< num_landings << endl<< "Total number of planes that took off "<< num_takeoffs << endl<< "Total number of planes left in landing queue "<< landing.size() << endl<< "Total number of planes left in takeoff queue "<< takeoff.size() << endl;cout << "Percentage of time runway idle "<< 100.0 * (( float ) idle_time) / (( float ) time) << "%" << endl;cout << "Average wait in landing queue "<< (( float ) land_wait) / (( float ) num_landings) << " time units";cout << endl << "Average wait in takeoff queue "<< (( float ) takeoff_wait) / (( float ) num_takeoffs)<< " time units" << endl;cout << "Average observed rate of planes wanting to land "<< (( float ) num_land_requests) / (( float ) time)<< " per time unit" << endl;cout << "Average observed rate of planes wanting to take off "<< (( float ) num_takeoff_requests) / (( float ) time)<< " per time unit" << endl;}/*************************************************************************/Programming Project two –PolynomialArithmetic一、实验目的1.进一步熟悉数据结构中的栈和队列2.进一步练习使用栈和队列实现简单的算法二、实验内容编写程序实现多项式的加减法，具体如下：Assemble the functions developed in section 4.5 and the functions get_command( ), introduction() and instructions() illustrated below, make the necessary changes in the code, write the Polynomial method equals_difference as to produce a working skeleton for the calculator program, one that will read, write, add, and subtract polynomials.void introduction()/*PRE: None.POST: An introduction to the program Polynomial Calculator is printed.*/{cout << "Polynomial Calculator Program." << endl<< "This program simulates a polynomial calculator that works on a\n"<< "stack and a list of operations. It models a reverse Polish\n"<< "calculator where operands are entered before the operators. An\n"<< "example to add two polynomials and print the answer is ?P?Q+= .\n"<< "P and Q are the operands to be entered, + is add, and = is\n"<< "print result. The result is put onto the calculator's stack.\n\n";}void instructions()/*PRE: None.POST: Prints out the instructions and the operations allowed on thecalculator.*/{cout << "\nEnter a string of instructions in reverse Polish form.\n"<< "The allowable instructions are:\n\n"<< "?:Read +:Add =:Print -:Subtract\n"<< "*:Multiply q:Quit /:Divide h:Help\n\n";}char get_command()/*PRE: None.POST: A legal command is read from the user and returned. */{char command, d;cout << "Select command and press <Enter>:";while (1) {do {cin.get(command);} while (command == '\n');do {cin.get(d);} while (d != '\n');command = tolower(command);if (command == '?' || command == '=' || command == '+' || command == '-' || command == 'h' || command == '*' || command == '/' || command == 'q' || command == 'p' || command == 'h') {return (command);}cout << "Please enter a valid command:" << endl; instructions();}}Programming Project three - Maze Path Searching一、实验目的通过设计走迷宫的算法，了解递归程序设计，使用非递归和递归方法分别完成走迷宫的算法二、PROBLEM DESCRIPTIONA maze is a rectangular space with an entrance at the upper left-hand corner, an exit at the lower right-hand corner, and some internal walls. Your algorithm will find a path through a given maze starting from the entrance and finishing at the exit that does not go through any walls (a path must go around walls).You will represent the maze by a two dimensional array, MAZE[m][n], where a value of 1 implies a blocked path, while a 0 means one can walk right on through. The search algorithm will start at maze[0][0] and find a path to maze[n][m].You are to implement the algorithm for finding a path through a rectangular maze by using a stack. If a path is found, the positions in the path are printed to stdout with a success message, otherwise, an error message is printed to the screen. Your program will print the paths.A path is represented by a sequence of maze[i][j] coordinates starting with maze[0][0] and ending with maze[n][m]. A path can move from one position to another at any directions horizontally, vertically or diagonally. From a position (i,j) in a path, the next position in the path can be any one of 8 contiguous positions to the right, lower right, down, lower left, left, upper left, up, or upper right from positions (i,j).You are to use the following data of the array of a 10x10 for the maze:Enter-> 0 1 1 1 0 0 0 0 0 00 0 0 1 0 0 0 1 0 00 1 0 1 1 0 0 1 0 00 1 0 0 1 0 1 1 0 00 1 0 0 1 0 1 1 0 01 1 1 0 1 0 1 0 0 00 0 1 0 0 0 1 0 1 10 0 1 0 0 0 1 0 1 10 1 1 0 1 0 1 0 0 00 0 0 0 1 0 1 1 0 0 --> EXITThe following is a one possible path through this maze:Path: ( maze[0][0], maze[1][0], maze[1][1], maze[1][2], maze[2][2],maze[3][2], maze[3][3], maze[4][3], maze[5][3], maze[6][3],maze[6][4], maze[6][5], maze[5][5], maze[4][5], maze[3][5],maze[2][5], maze[2][6], maze[1][6], maze[0][6], maze[0][7],maze[0][8], maze[1][8], maze[2][8], maze[3][8], maze[4][8],maze[5][8], maze[5][7], maze[6][7], maze[7][7], maze[8][7],maze[8][8], maze[8][9], maze[9][9])Enter-> X 1 1 1 0 0 X---X---X 0X---X---X 1 0 0 X 1 X 00 1 X 1 1 X---X 1 X 00 1 X---X 1 X 1 1 X 00 1 0 X 1 X 1 1 X 01 1 1 X 1 X 1 X---X 00 0 1 X---X---X 1 X 1 10 0 1 0 0 0 1 X 1 10 1 1 0 1 0 1 X-- X-- X0 0 0 0 1 0 1 1 0 X --> EXITGETTING STARTEDYour program will perform the following actions:You will print the maze, using '0' to indicated non-wall positions and '1' to indicate wall positions in the maze.Your program will search for a path from the maze entrance point to the exit point in the maze. The path searching algorithm will terminate either when it finds a path through the maze or when it determines that there is no path through the maze. Your program will either print an error message (if there is no path through the maze) or will print:The path as a list of (i,j) positions starting at the entrance point and ending at the maze exit pointThe length of the pathThe maze with the path coordinates indicated by 'X' characters.Your program will search for a path from the maze entrance point to the exit point in the maze, and print the path or an error message indicating the results of the search as in step (3) above.The Path Finding AlgorithmYou should implement the following algorithm for finding a path (the details are left for you to fill in):Set list to the maze entrance coordinates and direction up;While list is not empty do{ (i, j, mov) <- coordinates and direction from front of list;while there are more moves do{ if (g, h)=(m, n) then success;if MAZE(g,h)=0 and MARK(g,h)=0// the move is legal and we haven’t been here beforethen {[MARK(g,h)<-1;add (i, j, mov) to front of list;(i, j, mov) <- (g, h, null)}}}print no path has been foundData StructuresArray MAZE[m][n] holds the maze. Array MARK[m][n] is zero in spot (i, j) if MAZE(i, j) has not yet been reached. MOVE[7][1] is a table used to change coordinates (i, j) to one of the possible directions. Use stack to hold the current path.HAND INFiles in your project should include:All project files necessary for compiling your code (include any of the classes that that you use in your solution).A Makefile for building your codeA README file with:The names of the two search methods in your implementation.The big-O complexity of each search showing how you computed it.Path(MAZE, MARK, m, n, MOVE, STACK)//A binary matrix MAZE(0:m+1,0:n+1) holds the maze.STACK(mn,2) records the path //{MARK(1,1)=1;STACK.push((1,1,1));While not STACK.empty(){(i,j,mov) = STACK.top();STACK.pop();While mov!=8{g=i+MOVE(mov,1);h=j+MOVE(mov,2);if g=m and h=n{reverseprint STACK;print i,j;print m,n;return;}if MAZE(g,h)=0 and MARK(g,h)=0{MARK(g,h)=1;STACK.push((i,j,mov));i=g;j=h;mov=0;}else mov=mov+1;}}print “No path has been found”}Programming Project four -Build a binary tre e一、实验目的设计数据结构和算法，实现树的构建掌握树的前根序、中根序和后根序遍历算法了解c++中类模板的定义和使用二、实验内容Task 1:You are to build a binary tree using C++ template classes presented in Section 10.1. You are to structure your main program to read and interpret the input with the following format of a sequence of entries in the level by level order, each of which indicates either a existing node with normal value or empty by a special value such 0 or ‘.’. For example, the following binary tree has the input sequence represented in such a list A( e, b, f, a, d, ., g, ., ., c ).Output the tree in the sequence format. When you have built the binary tree for the input nodes, you need to print the nodes of the tree in preorder, in-order and post-order.Task 2:Modify the above insert function so that the new entry will inserted into the root if the root of the tree is empty, otherwise it will be inserted into the short of the two subtrees of the root (or into the left subtree if both subtrees have the same height).Programming Project five-Build a minimal spanning tree or shortest paths in a graph一、实验目的1.学习掌握图的存储结构2.学会编写求最小生成树的Prim算法和最短路径的Dijkstra算法二、实验内容You are to write Digraph methods called read that will read from the terminal the number of vertices in an undirected graph and lists of adjacent vertices. Be sure to include error checking. The graph is to be implemented with an adjacency table. Implement and test the methods of Dijkstra for finding the shortest paths or Prim for determining minimal spanning trees of a connected network..。
