数据结构课程设计题目

发布 2022-10-06 03:32:28 阅读 8535

[选题要求]

1) 选题采用1+x的方式,1指排序算法研究,是基本任务。x指代另外的题类不限,每组可任选题类,完成类别中的一小题要求即可。其中1<=x<=2,其中x=2有加分,并且要求所选的题目在不同的类型中。

2) 每组选完题后,请e-mail告之选题中要求的x是什么,并告诉同组成员有没有变动。如有变动,请告之变动情况。

3)最好在考试之前能对课程设计题目有所准备,在15-16周安排课程设计时间和答辩时间。如果能在15周前完成的小组,可以预先安排答辩时间,请e-mail或者**预约。

4)最后要求每组完成一个总的实验报告(可以粗略一点),每个同学均完成一个实验报告,报告的要求见下面的说明。每组同学上交的内容有:源**,答辩的ppt,实验报告,由班长收齐后统一复制给我(电子版本即可)。

报告规范] 实习报告的开头应该给出题目、班级、姓名、学号、和完成日期,并包括以下七个内容:

1. 需求分析:以无歧义的陈述说明程序设计的任务,强调的是程序要做什么?明确规定:

1) 输入的形式和输入值的范围;

2) 输出的形式;

3) 程序所能达到的功能;

4) 测试数据:包括正确的输入及其输出结果和含有错误的输入及其输出结果。

2.概要设计。

说明本程序序中用到的所有抽象数据类型的定义、主程序的流程及各程序模块之间的层次(调用)关系。

3.详细设计:实现概要设计中定义的所有数据类型,对每个操作只需要写出伪码算法;对主程序和其他模块都要写出伪码算法(伪码算法达到的详细程度建议为:按照伪码算法可以在计算机键盘直接输入高级程序设计语言程序);画出各类和各函数之间的调用关系。

4.调试分析。

内容包括:(1)调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论与分析;

2)算法的效率分析(基本操作和其他算法的时间复杂度)和改进想法。

3)经验和体会等。

5.用户使用说明:说明如何使用编写的程序,详细列出每一步的操作步骤。

6.测试结果:列出你的测试结果,包括输入和输出。这里的测试数据应该完整和严格,最好多于需求分析中所列。

7.附录:带注释的源程序。如果提交源**,可以在实验报告列出程序文件名的清单。

实验报告可以以电子档提交。

题目]一、 离散事件模拟。

银行业务模拟。

问题描述】客户业务分为两种,第一种是申请从银行得到一笔资金,即取款或者借款。第二种是向银行投入一笔资金,即存款或者还款。银行有两个服务窗口,相应的有两个队列。

客户到达银行后先排第一个队。处理每个客户业务时,如果属于第一种,且申请额超出银行现存资金总额而得不到满足,则立即排入第二个队等候,直至满足时才离开银行;否则业务处理完后立即离开银行。每接待完一个第二种业务的客户,则顺序检查和处理(如果可能)第二个队列中的客户,对能满足的申请者予以满足,不能满足的者重新排到第二个队列的队尾。

注意:在此检查过程中,一旦银行的资金总额少于或者等于刚才第一个队列中最后一个客户(第二种业务)被接待之前的数额,或者本次已将第二个队列检查或处理了一遍,就停止检查(因为此时已不可能还有能满足者)转而继续接待第一个队列客户。任何时刻都只开一个窗口。

假设检查不需要时间。营业时间结束时所有客户立即离开银行。

基本要求】利用动态存储结构实现模拟。

测试数据】一天营业开始时银行拥有的款额为10000(元),营业时间为600(分钟)。其他模拟参量自定,注意测定两种极端的情况:一是两个到达事件之间的间隔时间很短,而客户的交易时间很长,另一个恰好相反,设置两个到达事件的间隔时间很长,而客户的交易时间很短。

实现提示】事件有两类:到达银行的和离开银行。初始时银行现存资金总额为total。

开始营业后的第一个事件是客户到达,营业时间从0到closetime。到达事件发生时随机地设置此客户的交易时间和距下一到达事件之间的时间间隔。每一个客户要办理的款额也是随机确定的,用负值和正值分别表示第一类和第二类业务。

变量total,closetime以及上述两个随机量的上下界均交互地从终端读入,作为模拟参数。

两个队列和一个事件表均要用动态存储结构实现。注意弄清应该在什么条件下设置离开事件,以及第二个队列用怎么样的存储结构实现时可以获得较高的效率。注意:事件表是按时间顺序有序的。

航空客运订票系统。

问题描述】航空客运订票的业务活动包括:查询航线、客票预订和办理退票等。试设计一个航空客运订票系统,以使上述业务可以借助计算机来完成。

基本要求】(1)每条航线所涉及的信息有:终点站名、航班号、飞机号、飞行周日(星期几)、乘员定额、余票量、已订票的客户名单(包括姓名、订票量、舱位等级1,2或3)以及等候替补的客户名单(包括姓名、所需的票量);

2)作为示意系统,全部数据可以只放在内存中;

3)系统能实现的操作和功能如下:a-查询航线:根据旅客提出的终点站名输出下列信息:

航班号、飞机号、星期几飞行、最近一天航班的日期和余票;b-承办订票业务:根据客户提出的要求(航班号、订票数额)查询该航班票额情况,若尚有余票,则为客户办理订票手续,输出座位号;若已满员或余票额少于订票额,则需重新询问客户要求。若需要,可登记排队候补;c-承办退票业务:

根据客户提供的情况(日期、航班),为客户办理退票手续,后人内查询该航班时候有人排队候补,首先询问排在第一的客户,若所退票额能满足他的要求,则为他办理订票手续,否则依次询问其他排队候补的客户。

测试数据】自行拟定。

实现提示】两个客户名单可分别由线性表和队列实现。为查找方便,已订票客户的线性表应按客户姓名有序,并且,为插入和删除方便,应以链表作存储结构。由于预约人数无法预计,队列也应以链表作存储结构。

整个系统需汇总各条航线的情况登录在一张线性表上,由于航线基本不变,可采用顺序存储结构,并按航班有序或按终点站名有序。每条航线是这张表上的一个记录,包含上述8个域,其中乘员名单域为指向乘员名单链表的头指针,等候替补的客户名单域为分别指向队头和队尾的指针。

选作内容】当客户订票要求不能满足时,系统可向客户提供到达同一目的地的其他航线的情况。读者还可以充分发挥自己的想象力,增加你的系统的功能和其他服务项目。

电梯模拟。问题描述】设计一个电梯模拟系统。这是一个离散的模拟程序,因为电梯系统是乘客和电梯等“活动体”构成的集合。

虽然他们彼此交互作用,但是他们的行为是基本独立的。在离散的模拟中,以模拟时钟决定每个活动体的动作发生的时刻和顺序,系统在某个模拟瞬间处理有待完成的各种事情,然后把模拟时钟推进到某个动作预定要发生的下一个时刻。

基本要求】(1)模拟某校5层教学楼电梯系统。该楼有个自动电梯,能在每一层停留。5个楼曾由下至上依次称为地下层,第一层,第二层,第三层和第四层,其中第一层是大楼的进出层,即是电梯的“本垒层”,电梯“空闲”时,将来到该层待命。

2)乘客可随机地进出于任何层。对每个人来说,他有一个能容忍的最长等待时间,一旦等候电梯时间过长,他将放弃。

3)模拟时钟从0开始,时间单位为0.1秒。人和电梯各种动作均要耗费一定时间单位(记为t),如:

有人进出时,电梯每隔40t测试一次,若无人进出,则关门;

关门和开门各需20t;

每个人进出电梯均需要25t;

如果电梯在某层静止时间超过300t,则驶回1层待命。

4)按时序显示系统状态的变化过程:发生的全部人和电梯的动作序列。

测试数据】模拟时钟time的初始值为0,终值可在500~10000范围内逐步增加。

实现提示】(1)楼层由上自下依次编号为0,1,2,3,4。每层有要求up(上)和down(下)的两个按钮,对应10个变量callup[0,4]和calldown[0..4]。

电梯内5个目标层按钮对应变量callcar[0..4]。有人按下某个按钮时,相应的变量就置为1,一旦要求满足后,电梯就把该变量清为0。

2)电梯处于三种状态之一:going(上行)、goingdown(下行)和idle(停候)。如果电梯处于idle状态且不在1层,则关门并驶回1层。

在1层停留时,电梯是闭门候命。一旦收到往另一层的命令,就转入goingup或goingdown状态,执行相应的操作。

(3)用变量time表示模拟时钟,初值为0,时间单位(t)为0.1秒。其他重要的变量有:

floor---电梯的当前位置(楼层);

d1---值为0,除非人们正在进入和离开电梯;

d2---值为0,如果电梯已经在某层停候300t以上;

d3---值为0,除非电梯门正开着又无人进出电梯;

state---电梯的当前状态(goingup,goingdown,idle)。

系统初始时,floor=1,d1=d2=d3=0,state=idle。

4)每个人从进入系统到离开称为该人在系统中的存在周期。在此周期内,他有6种可能发生的动作:

m1.[进入系统,为下一人的出现作准备]产生以下数值:

infloor---该人进入哪层楼;

outfloor---他要去哪层楼;

giveuptime---他能容忍的等候时间;

intertime---下一人出现的时间间隔,据此系统预置下一人进入系统的时刻。

m2.[按电钮并等候]此时应对以下不同情况作不同的处理:

1 floor==infloor且电梯的下一个活动是e6(电梯在本层,但正在关门)

2 floor==infloor且d3≠0(电梯在本层,正有人进出)

3 其他情况,可能d2=0或电梯处于活动e1(在1层停候)。

m3.[进入排队]在等候队列queue[infloor]末尾插入该人,并预置在giveuptime

个t之后,他若仍在队列中将实施动作m4。

m4.[放弃]如果floor≠infloor或d1=0,则从queue[infloor]和系统删除该人。

如果floor=infloor且d1≠0,他就继续等候(他知道马上就可以进入电梯)

m5.[进入电梯]从queue[infloor]删除该人,并把他插入到elevator(电梯)栈中。置callcar[outfloor]为1。

5)电梯的活动有9种:

e1.[在1层停候]若有人按下一个按钮,则调用controler将电梯转入活动e3或e6。

数据结构课程设计题目

题目1实现两个链表的合并。要求 编一程序将a表和b表归并成一个新的递增有序的单链表c 值相同的元素均保留在c表中 并要求利用原表的空间存放c。测试数据 1 a表 30,41,15,12,56,80 b表 23,56,78,23,12,33,79,90,55 2 a表 30,41,15,12,56,8...

数据结构课程设计题目

题目1 图的遍历。功能 实现图的深度优先,广度优先遍历算法,并输出原图结构及遍历结果。分步实施 1 初步完成总体设计,搭好框架 2 完成最低要求 两种必须都要实现,写出画图的思路 3 进一步要求 画出图的结构,有兴趣的同学可以进一步改进图的效果。要求 1 界面友好,函数功能要划分好。2 总体设计应画...

数据结构课程设计题目

数据结构课程设计 题目与要求。一 实验学时 两周。二 要求 1 题目从以下题目中选择,完成程序设计及设计文档。2 程序的要求 实现的功能要求尽量完善。完善基本功能的基础上,再扩充其它功能。3 课程设计说明书的格式要求 a4纸打印,格式设置统。一 规范 美观。三 题目。1.运动会分数统计 限1 人完成...