PDF《课程实验报告》

数据结构课程实验报告 -

1 - 数据结构 课程实验报告 题目:学生排队 学生姓名路玉欢 学生学号201608010306 专业班级计科1603 班 完成日 期2017年10月15日 数据结构课程实验报告 -

2 -

一、 需求分析 1.

问题描述 (1) 体育老师小明要将自己班上的学生按顺序排队.

1 他首先让学生按学号从小到大的顺序排成一排,学号小的排在前面.

2 然后进行多次调整.一次调整小明可能让一位同学出队,向前或者向后移动 一段距离后再插入队列. (2) 例如,下面给出了一组移动的例子,例子中学生的人数为

8 人. 1)初始队列中学生的学号依次为 1, 2, 3, 4, 5, 6, 7, 8;

2)第一次调整,命令为"3 号同学向后移动 2" ,表示

3 号同学出队,向后移动

2 名同学的距离, 再插入到队列中, 新队列中学生的学号依次为 1, 2, 4, 5, 3, 6, 7, 8;

3)第二次调整,命令为"8 号同学向前移动 3" ,表示

8 号同学出队,向前移动

3 名同学的距离, 再插入到队列中, 新队列中学生的学号依次为 1, 2, 4, 5, 8, 3, 6, 7;

4)第三次调整,命令为"3 号同学向前移动 2" ,表示

3 号同学出队,向前移动

2 名同学的距离, 再插入到队列中, 新队列中学生的学号依次为 1, 2, 4, 3, 5, 8, 6, 7. (3) 请特别注意,上述移动过程中所涉及的号码指的是学号,而不是在队伍中的位 置.在向后移动时,移动的距离不超过对应同学后面的人数,如果向后移动的 距离正好等于对应同学后面的人数则该同学会移动到队列的最后面.在向前移 动时,移动的距离不超过对应同学前面的人数,如果向前移动的距离正好等于 对应同学前面的人数则该同学会移动到队列的最前面. (4) 小明记录了所有调整的过程, 请问, 最终从前向后所有学生的学号依次是多少? 2.输入数据 (1)输入的第一行包含一个整数 n,表示学生的数量,学生的学号由

1 到n编号. (2)第二行包含一个整数 m,表示调整的次数. (3)接下来 m 行,每行两个整数 p, q,如果 q 为正,表示学号为 p 的同学向后移动 q, 如果 q 为负,表示学号为 p 的同学向前移动-q. 3.输出数据 输出一行,包含 n 个整数,相邻两个整数之间由一个空格分隔,表示最终从前向后所有 学生的学号. 4.测试样例设计 (1)常规输入,调整既有向前又有向后. 样例输入:

8 3

3 2

8 -3

3 -2 样例输出:

1 2

4 3

5 8

6 7 (2)反例输入,如经过几次排序某同学已经到了最后一位,但输入的指令仍让他后退. 样例输入:

3 数据结构课程实验报告 -

3 -

8 1

2 2 -1

1 1

3 -2

1 1

2 -1

3 -1

1 2 样例输出:

2 0

1 [3 号同学因指令错误而已经不在规定位置了] (3)仅有向前调整. 样例输入:

8 3

3 -2

8 -3

5 -2 样例输出:

3 1

2 5

4 8

6 7 (4)仅有向后调整 样例输入:

8 3

3 2

5 3

4 2 样例输出:

1 2

3 6

4 7

5 8 (5)调整

0 次 样例输入:

8 0 样例输出:

1 2

3 4

5 6

7 8

二、概要设计 1.抽象数据类型 数据对象:两个整数和另外两组整数 数据关系:从键盘输入一个整数 n 表示这组学生个数,学号从

1 到n排列,按照大小顺 序,符合线性特征.输入整数 m 表示调整位置的次数,声明两个,数组用来储存 调整指令,指令通过键盘输入,按照输入的先后顺序,满足线性特征. 基本操作: (1) 根据输入的整数 n 准备一个数组的储存空间, 再将