内容发布更新时间 : 2024/5/4 19:07:46星期一 下面是文章的全部内容请认真阅读。

Heilongjiang University of Science and Technology

专业基础训练1（数据结构）

课程设计指导书

计算机与信息工程学院

一、课程性质及教学目标

1、本课程是软件工程专业本科生培养方案所规定的一门专业实践必修课。而本实践课程做为一门综合实践课程，要求学生利用现阶段所学的程序设计语言、数据结构等有关理论知识，结合实际问题设计相关算法及程序，以达到理论与实践相结合的目的。

2、本课程的教学目标是通过本综合实践课程的实践训练，使学生能够掌握综合运用现阶段所学的程序设计、数据结构等有关理知识来解决实际问题的方法；巩固和掌握程序设计、数据结构设计、算法设计的基本方法与技能；进一步加强学生的程序设计、编码、运行与调试能力和算法设计与分析的能力；培养学生分析问题、解决问题的能力。 二、设计题目

1.带命令的顺序表 顺序表的类型定义如下。 typedef struct SqList{ int *base; int length; int listsize; }SqList;

给定一个长度为n的顺序表L，顺序表L中存放了n个整数。 下面对顺序表L实施两种命令，命令的代号为A和B。 命令A的格式为：A X Y

它的含义是将顺序表L中值为X的元素移到值为Y的元素的左边 命令B的格式为：B X Y

它的含义是将顺序表L中值为X的元素移到值为Y的元素的右边 例如，假设当前顺序表L的长度为8，所含的8个元素如下所示。

length=8

base listsize=8 L 0 1 2 3 4 5 6 7 8 10 95 23 41 6 7 9

则执行命令A 10 41后，顺序表L如下图所示。

length=8 base listsize=8 L0 1 2 3 4 5 6 7 8 95 23 10 41 6 7 9

再执行命令B 95 6后，顺序表L如下图所示。

length=8 base listsize=8 L0 1 2 3 4 5 6 7 8 23 10 41 6 95 7 9

要求：

输入顺序表中的元素个数n和命令的条数m，然后向顺序表中输入n个整数，再输入m条命令，最后输出经过m条命令操作后得到的顺序表。

例如，若输入： 8 2

8 10 95 23 41 6 7 9 A 10 41 B 95 6 则输出：

8 23 10 41 6 95 7 9

2. Josephus环问题和反Josephus环问题 （1）带人名的Josephus环问题

Josephus环问题为：设编号为1，2，? n的n个人围坐一圈，约定从编号为k（1<=k<=n）的人开始从1报数，数到m 的那个人出列，它的下一位又重新从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止。