课程设计软工班

《据构程计级软工3班说明：（1）根个人情，在下面的目中选至少道完成才记为通。（2）程要定期成原则上后一讲完之，一章的机程序不再查。比，第三章讲后，第章的程序应部检查毕，之后不检查。需延长的会统通知。（3）所题目均在机房检查随机提。程序完成量按正性、程序风格和界来评价。（4）所程序的子版都要上，请自保存好。期时用“号姓名”格式建立个文件夹，序用题命名，发到的QQ邮箱（5）每至少选一个带*题目完1.3除外，并完一个实验报，与电子版序一并上交报告模附后。第章实（选一1.3加）1.1设一个程序，统计一个（最多有50人的学生成绩，要求能实现如下四个功能：由盘或文件输入每个学生的学号和四门课程的成绩；计每个学生的平均成绩和总成绩；按成绩从高到低排名，并按名次输出每个学生的情况，包括：学号，各科成绩，平均成绩，总成绩，排名由盘输入课程号，输出该课程成绩在90分（90分以上且总分在前3名学生情况，要求能多次查询用结构体数据类型，并采用模块化结构实现）1.2每城信息由城市名（字符串）和位置坐标组(x,y)。设计实现一程序，完成如下功能：（1从键盘或文件输入各城市信息（2按城市名字非递减排序后输出（3输入某个位置信息，查询该位置的城市名称，要求能多次查询。1.3*挖坑是一种比较流行的游戏，编写程序模拟挖坑的发牌程序。游戏介绍：挖坑是三人游戏，一副牌去掉大小王不用，共张，发牌时每人发张牌，剩余为底牌。最后由三人叫分，谁的分多4底牌全部归谁。提示：回想下我们现实生活如何进行挖坑的？首先需要有一副扑克牌，然后经过洗牌（洗的越均匀越好顺发给个人。因此需要一个创建扑克牌模块、洗牌模块和发/

1n……n1n……n2n-131牌模块。第章实2.1顺表选其一）（1编写一个程序，其功能是：顺表的i个位置开始，删除k个素。（2编写一个程序，其功能是：在一个非递减的顺序表中，删除所有值相等的多余元素，要求时间复杂度为，间复杂度为。2.2链选其一）（）瑟夫环。编号为1，2，，人按顺时针方向围坐一圈，每人持有一个密码（正整数开始任选一整数作为报数上限值m,第一个人开始顺时针自1开顺序报数，报到时停报数。报m人出列将的密码作为新的m值从他在顺时针方向上的下一个人开始重新从1报数此下去至所有的人全部出列为止设计一个程序，求出出列顺序。利用单向循环链表作为存储结构模拟此过程，按照出列顺序打印出各人的编号。例如m的值为20n=7，7个的密码依次是3，248，4，出列的顺序为6，，，，，，。（）已有如下单链表（,…,a为偶数。Laa1

a2

…

a^n要求写出一个时间复杂度为O助间为（1）的算法，将上述链表转换成：Laan

an-2

…

a2

a1

a3

…

an

^即（,a…,a,a…,a2.3*链应用：大整数加法。设计一个程序实现两个任意的整数加法算。不同的计算机系统所能表示的整数范围不同，一个类的整数的范围-。但是在一些应用中，我们需要处理的数远远大于这个范围，利用双向链表实现。提示：根据大整数本身的特征以及计算过程中对于存取时间复杂度的要求，我们选择双向链表作为其存储结构我将个大整数从右到左分组三位为一个节点若余一个组不满三位也将其作为一个节点处理。大整数本身的符号用头节点来表示1表正数，-1表示负数通过这样的方式我们构造了一个存储大整数的双向链表后可以进行大整数的基本运算了。基本思想：构造三个双向链表，分别存放加数，被加数和运算结果。其运算顺序是从最右边节点开始，以3个也就是1个节点作为一个单位进行，本次运算结果要进行分组，后三位作为一个节点存入结果链表中余位作为进位参加左边节点的运算此进行例如（这里用括弧（）来表示节点123445+9754=）+（009/

33从右向左第一个节点（其结果链表最右边的一个节点1）将参加节点从右至左第二个节点的运算，此时又三个数行相加，其结果再作相同处理。这里需要对参加加法运算的两个数的符号作特别的分类。假设两个数分别为add1和分下三种情况考虑：Aadd1与add2号，此时运算结果的符号与它们相同。运算过程如上。Badd1与add2号且长度不等，此时又分为两种情况：为负的整数位数较多，此时运算结果的符号为负，该负数的每个节点需以负值参加运算。为整地整数位较多，此时运算结果的符号为正，其中负数作同上处理。C．

add1与异且长度相等，此时分种情况：负数绝对值大于正数，此时运算结果为负，负数作同上处理。正数绝对值大于负数，此时运算结果为正，负数作同上处理。两数绝对值相等，此时结果为。加数与被加数以字符串的形式输入。2.4链表应用：一元多项式运算器。基本要求：（1）入并建立多项式，并用友好的界面显示多项式，如，8x^3-6x^2+8（2能计算两个多项式的加法和减法；（3给定x，计算多项式在x处的值。第章实3.1栈的应用选其一）

8x-6x+8显示为（1四则运算器。实现多整的括的则运算。参考书上算法3.13。（2设一个栈的输入序列为1,2…n编算法判一个给定的序列p1,p2,…,pn是否是一个合理的输出序列。3.2递算选一）（）皇后问题。（）马走棋盘。在8*8的方格棋盘上从意方格出发为马找一条走遍每一格且只走一次的路径。（）素数环从到这20个摆成一个环求邻的两个数的和是一个素。（）数字游戏：在3×方格的方阵中要填入数字到（≥10）内的某9个字每方格填一个整数使得有相邻两个方格内的两个整数之和为质数求所有满足这个要求的各种数字填法。3.2*栈与队列的应用：停车场管理。设停车场是一个可停放n辆的狭长通道有一个大门可供汽车进出场内，/

汽车按到达的先后次序由向依次排（设大门在最南端场已停满车，则后来的汽车需在门外的便道上等候有车开走时便上的第一辆车即可开入当停车场内某辆车要离开时之进入的车辆必须先退出车场为它让路辆车开出大门后，其他车辆再按原次序返回车场辆车离开停车场时应其停留时间的长短交（在便道上停留的时间不收费试编写程序，模拟上述管理过程。要求以顺序栈模拟停车场队模拟便道从端读入汽车到达或离去的数据，每组数据包括三项：①是“到达”还是“离去车牌照号码；③“到达”或“离去”的时刻（获取系统时间，以秒为单位每组输入信息相应的输出信息为如果是到达的辆则出其在停车场中或便道上的位置果离去的车辆，则输出其在停车场中停留的时间和应交的费用：需另设一个栈，临时停放为让路而从车场退出的车3.3*设计一个电梯模拟系统。这是一个模拟程序，因为电梯系统是乘客和电梯等“活动体”构成的集合，虽然它们彼此交互作用，但它们的行为是基本独立的。在离散的模拟中拟时钟决定每个活动体的动作发生的时刻和顺序某个模拟瞬间处理有待完成的各种事情，然后把模拟时钟推进到某个动作预定要发生的下一个时刻。(1)模拟某校五层教学楼的电梯系。该楼有一个自动电梯，能在每层停留。五个楼层由下至上依次称为地下层一二层三层和第四层中第一层是大楼的进出层，即是电梯的“本垒层梯“闲”时，将来到该层候命。(2)乘客可随机地进出于任何层。每个人来说，他有一个能容忍的最长等待时间，一旦等候电梯时间过长，他将放弃。(3)模拟时钟从始．时间单位为0.1秒。人和电梯的各种动作均要耗费定的时间单位简记为，比如：有人进出时，电梯每隔40t测一次，若无人进出，则关门；关门和开门各需要；每个人进出电梯均需要，如果电梯在某层静止时间超过，则驶回层候命。(4)按时序显示系统状态的变化过：发生的全部人和电梯的动作序列第章实（任选其一）5.1P154实习题1。5.2自动生成一个大特殊矩阵（对称或者三角或者带状压在一个维数组中，输入行号列号，在一维数组中查找其所在位置与值。5.3对一n阶阵，编写算法，通过行变换使其每行元素的均值递增排列。第章实6.1二树历应用：二叉树采用二叉链表存储，要求建立一棵二叉树，并输要求的树状形式与结点编号。结点结构为：lchilddatanumrchild其中二叉树的编号域为整数类，data数据域为字符类型，要求生成二叉树中编号，/

从1开进行连续编号每个结点的编号大于其左右子树中孩子的编号一结点的左右孩子中左子的编号小于其孩子的编号给出对二叉树中结点的实现如上要求编号并按如下树状形式打印出相应点编号的程序。测试数据：输入AB∪∪CEF∪∪∪（中符号∪表空格）字符）6.2二树遍历与栈、队列选其一）二树的层次遍历。求叉树根结点到某指定结点之间的路径。6.3P214第。6.4*程实现：要传输一些数据（比如英文单词计个利用哈夫曼算法的编码系统，为这些单词编码。并在接收端进行译码。基本要:（）将需要传输的数据存放在数据文件data.txt。（2读入数据文件并为其编码，将编码后的内容存入文件中（3读入code.txt，译码。并将译码后的容输出在屏幕上。第章实7.1分用邻接矩阵实现图的度优先遍历邻表实现图广度优先遍历的型不限。7.2*秀村是一个美丽的山村，可长期以来，村民们的房子都零散的分布在各个地方，没有道路直接相连大走动不便为方便大家串门村长决定带领大家修建道路连接各家各户。但由于修路要花很多钱（修的路越长，花费越多经费不足，因此村长召集大家一起商量看么样修路花钱最还能把各家各户都连起来你现在就帮助村民们设计一下修路方案吧。输入：输入文件road.in中每一行为三个数a,b,c分别表示房子和子之的距离为c（该文件请自己编写程序生输出输文件road.out中一行为三个数a,b,c分表示房子和子间是否会修路，c为示修路，为0示不修路。7.3*出不同目的的旅客对交通工具有不同的要求。例如，因公出差的旅客希望在旅途中的时间尽可能短自旅游的游客期望旅费尽可能省老年旅客则要求中转次数最少编制一个全国城市的交通咨询程序，为旅客提供两种或三种最优决策的交通咨询。7.4*四图。任何一张地图只用四种颜色就能使具有共同边界的国家着上不同的颜色。设有图所示地图，每个区域代表一个省，区域中的数字代表省的编号，今将每个省涂上红/

兰（Y（）种颜色之一，使相邻的省份有不同的颜色。7.5*现一些公交查询网站上，输入起点和终点，系统会给出所有方案的详细信息，如换乘站，总票价，总站数等。你能否设计这么一个模拟系统？第章实8.1【考察点：二叉排序树的实现】某图书管理系统采用二叉排序树做存储结构。完成以下功能：（）从键盘输入若干图书信息，至少包括：书名，作者，价格免每次从键盘输入的麻烦，可将图书信息存入一文件中，从文件中读取）（）按书名构建一棵二叉排序树。（）输入要查找的书的信息，可以输入一个或多个条件，查找是否存在该书（若存在多本则应全部输出）8.2针对某一集体中的人名30人）计一哈希表（假设姓名用汉语拼音得查找成功的平均查找长度不超过2，完成应的建表和查表程序。基本要求:（）每个学生信息至少包括：姓名，性别，年龄。（）要求用除留余数法构造哈希函数，用线性探测法处理冲突。（）计算等概率情况下的ASLsucc和ASLunsucc8.3*图管理基本业务活动包括：对一本书的采编入库、清除库存、借阅和归还等等。试设计一个图书管理系统，将上述业务活动借助于计算机系统完成。图书信息总不能一直停留在内存吧，所以要用文件存储。尽可能的运用数据结构学到的知识)第章实9.1*利随机函数产生N个随整数20000以上这些数进行多种方法进行排序。基本要求:（1分别采用直接插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序以及归并