秋数据结构与算法课程设计题目要求徐红梅.doc

《秋数据结构与算法课程设计题目要求徐红梅.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、一、学生成绩管理1.问题描述要求以学生成绩管理业务为背景，设计一个“学生成绩管理系统”程序。对于学校来讲，学生成绩管理系统是不可缺少的组成部分，主要是对学生成绩资料的录入、浏览、插入和删除等基本功能的实现。2.设计要求编制一个学生成绩管理程序。设学生成绩以一个学生一条记录的形式存储，每个学生记录包含的信息有学号和各门功课的成绩。设每位学生学习数学、英语、语文、物理和化学5门课程。3.数据结构本课程设计使用单链表作为实现该问题的数据结构。4.问题分析程序设计一般由算法和数据结构两部分组成。管理学生的成绩适合用单链表，方便随

2、时插入和删除学生记录，实现动态管理。一个学生作为一个结点，该结点类型为结构体，结构体中的域表示学生的属性。每个结点除了存放属性外，还存放指向后继结点的指针。二、马踏棋盘1.问题描述设计一个国际象棋的马踏遍棋盘的演示程序。2.设计要求（1）程序的输入：设计程序按要求输入马的初始位置（相应的坐标）。（2）程序的输出：程序的设计完成后应给出马从初始位置走遍棋盘的过程，并按照求出的行走路线的顺序，将数字1，2，…，64依次填入一个8*8的方阵并输出。3.数据结构本课程设计使用的数据结构是栈，利用顺序栈来实现。4.问题分析所谓马踏

3、棋盘问题，是指将马随机放在国际象棋的8*8棋盘的某个方格中，马按走棋规则（马走日子）进行移动。要求每个方格只进入一次，走遍棋盘上全部64个方格。由用户自行指定一个马的初始位置，求出马的行走路线，并按照求出的行走路线的顺序，将数字1，2，…，64依次填入一个8*8的方阵并输出。从用户给出的初始位置开始判断，按照顺时针顺序，每次产生一个新的路点，并验证此路点的可用性，需要考虑的是当前路点是否超出棋盘范围和此路点是否已经走过，如果新路点可用，则入栈，并执行下一步，重复进行如上步骤，每次按照已走路点的位置生成新路点。如果一个新路

4、点的可扩展路点数为0，进行回溯，直到找到一个马能踏遍棋盘的行走路线并输出。三、停车场管理1.问题描述设停车场内是一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若停车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在其之后开入的车辆必须先退出车场让路，待该辆车开出大门外，其他车辆再按原次序进入停车场，每辆停放在停车场的车在

5、其离开停车场时必须按其停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。2.设计要求以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据的方式进行模拟管理。输入1，表示车辆到达；输入2，表示车辆离开；输入3，表示显示出停车场内及便道上的停车情况；输入4，表示退出系统。车辆到达操作，需输入汽车汽车牌照号码及到达的时刻；车辆离开操作，需输入汽车在停车场的位置及离开的时刻，且应输出汽车在停车场内停留的时间和应缴纳的费用（在便道上停留的时间不收费）。3.数据结构本课程设计使用的数据结构是顺序栈和链式

6、队列。4.问题分析模拟停车场车辆进出时需要输入车辆的信息，包括车牌号码及进入与离开的时刻，因此可以定义一个时间结点类型和一个车辆信息结点类型，在顺序栈及链式队列中定义结点类型为车辆信息结点类型。四、大整数计数器1.问题描述实现大整数（200位以内的整数）的加、减、乘、除运算。2.设计要求设计程序实现两个大整数的四则运算，输出这两个大整数的和、差、积、商及余数。3.数据结构本课程设计采用顺序串来实现。4.问题分析由于整数数据存储位数有限，因此引入串的概念，将整型数据用字符串进行存储，利用字符串的一个字符存储大整数的一位数值

7、，然后根据四则运算规则，对相应位依次进行相应运算，同时保存进位，从而实现大整数精确的运算。具体设计思路如下：（1）计算大整数加法时，采用数学中列竖式的方法，从个位（即字符串的最后一个字符）开始逐位相加，超过或达到10则进位，同时将该位计算结果存到另一个字符串中，直至加完大整数的所有位为止。（2）计算大整数减法时，首先调用库函数strcmp判断这两个大整数是否相等，如果相等则结果为0，否则用compare函数判断被减数和减数的大小关系，进而确定结果为正数还是负数，然后对齐位依次进行减法，不够减则向前借位，直至求出每一位减法

8、之后的结果。（3）计算大整数乘法时，首先让乘数的每一位都和被乘数进行乘法运算，两个乘数之积与进位相加作为当前位乘积，求得当前位的同时获取进位值，进而实现大整数的乘法运算。（4）计算大整数除法时，类似做减法，基本思想是反复做减法，从被除数里最多能减去多少次除数，所求得的次数就是商，剩余不够减的部分则是余数，这样便可计算