数据结构实验指导书(2008)

《数据结构与算法》实验指导书

秦俊平 赵志燕 编

内蒙古工业大学信息工程学院计算机系

2008年2月23日

《数据结构与算法》实验教学大纲

课程编号：020213040 课程学时／学分：64/3 实验总学时：12 课程英文名称： Data Structure and Algorithm 课程类别：技术基础课 开出学期：第四学期 开出单位（实验室）：信息学院教学机房

制定人：秦俊平、赵志燕讲师 一、制定依据

根据内蒙古工业大学06版计算机科学与技术专业培养方案、数据结构课程教学大纲制订本课程实验教学大纲。 二、实验安排

课程实验内容安排 实验学时 4 4 4 每组人数 1 1 1 实验类型 开出对象 开出要求 序号 实 验 项 目 1 Josephus环算法的设计 设本必计 科 做 设本必计 科 做 设本必计 科 做 ２ 二叉树遍历算法的设计 ３ BFS和DFS算法的设计 三、实验内容与要求

实验前充分预习实验指导书内容及相关理论知识内容；实验中严格遵守实验室规范和制度，认真完成实验内容并做好实验纪录；实验后必须按照要求独立完成实验报告。

四、考核方式及成绩评定

实验的考核方式:根据实验课考勤、实验预习报告、课上实验能力、原型系统效果验收与实验报告的完成情况确定最终的实验成绩，成绩采用百分制，实验成绩占课程总成绩的10%。

五、教材及主要参考资料

1．教材

[1] 数据结构（C语言版）.严蔚敏,吴伟民主编. 北京：清华大学出版社，1997.4。 [2] 数据结构实验指导书.秦俊平,赵志燕 编.自编，2008.2。 2．教学参考书

[1] 数据结构.刘振鹏主编. 北京：中国铁道出版社，2003。

2

六、其它说明

实验报告格式参照信息学院实验报告规范要求。

实验一 Josephus环算法的设计

一、实验目的

本实验的目的是进一步理解线性表的逻辑结构和两种存储结构，进一步提高使用理论知识指导解决实际问题的能力，并对算法性能进行分析。

二、实验题目

Josephus环算法的设计

约瑟夫（Josephus）问题的一种描述是：编号为1,2,…,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。

3

三、实验类型

设计性。

方案一采用顺序存储结构实现线性表。 方案二采用循环链表结构实现线性表。

四、要求及提示

要求：

（1）两种数据结构的各种基本操作（创建、删除）定义为独立函数（注意函数接口的规定）。 （2）采用菜单驱动方式调用各种功能。

（3）用测试数据测试程序的正确性，如m的初值为20；密码：3，1，7，2，4，8，4。

（4）分析算法完成所定义基本操作的时间复杂度。 提示：

（1）由于当某个人退出圆圈后，报数的工作要从下一个人开始继续，剩下的人仍然是围成一个圆圈的，可以使用循环表，由于退出圆圈的工作对应着表中结点的删除操作，对于这种删除操作频繁的情况，选用效率较高的链表结构，为了程序指针每一次都指向一个具体的代表一个人的结点而不需要判断，链表不带头结点。所以，对于所有人围成的圆圈所对应的数据结构采用一个不带头结点的循环链表来描述。设头指针为p，并根据具体情况移动。

可以采用数据类型定义： typedef struct node {

int number; //每个人的编号

int code; //每个人的密码

struct node *next; //指向表示下一个人的结点的指针 }lnode

同样，顺序存储结构的每个元素数据类型定义如下: typedef struct node {

int number; //每个人的编号

int code; //每个人的密码

}

4