2009级数据结构实验报告
实验名称：约瑟夫问题
学生姓名：李凯
班级：21班
班内序号：06
学号：09210609
日期：2010年11月5日
1．实验要求
1）功能描述：有n个人围城一个圆圈，给任意一个正整数m，从第一个人开始依次报数，数到m时则第m个人出列，重复进行，直到所有人均出列为止。请输出n个人的出列顺序。
2）输入描述：从源文件中读取。
输出描述：依次从显示屏上输出出列顺序。
2. 程序分析
1）存储结构的选择
单循环链表
2）链表的ADT定义
ADT List{
数据对象：D={a i|a i∈ElemSet,i=1,2,3,…n,n≧0}
数据关系：R={< a i-1, a i>| a i-1 ,a i∈D,i=1,2,3,4….,n}
基本操作：
ListInit(&L)；//构造一个空的单链表表L
ListEmpty(L); //判断单链表L是否是空表，若是，则返回1，否则返回0.
ListLength(L); //求单链表L的长度
GetElem（L，i）；//返回链表L中第i个数据元素的值；
ListSort(LinkList&List) //单链表排序
ListClear(&L); //将单链表L中的所有元素删除，使单链表变为空表
ListDestroy(&L);//将单链表销毁
}ADT List
其他函数：
主函数；
结点类;
约瑟夫函数
2.1 存储结构
[内容要求]
1、存储结构：顺序表、单链表或其他存储结构，需要画示意图，可参考书上P59
页图2-9
2.2 关键算法分析
结点类：
template class CirList;//声明单链表类
template class ListNode{//结点类定义；
friend class CirList;//声明链表类LinkList为友元类；
Type data;//结点的数据域；
ListNode*next;//结点的指针域；
public:
ListNode():next(NULL){}//默认构造函数；
ListNode(const Type &e):data(e),next(NULL){}//构造函数
Type & GetNodeData(){return data;}//返回结点的数据值；
ListNode*GetNodePtr(){return next;}//返回结点的指针域的值；
void SetNodeData(Type&e){data=e;}//设置结点的数据值；
void SetNodePtr(ListNode*ptr){next=ptr;} //设置结点的指针值；
};
单循环链表类：
templateclass CirList
{
ListNode*head;//循环链表头指针
public:
CirList(){head=new
ListNode();head->next=head;}//构造函数，建立带头节点的空循环链表
~CirList(){CirListClear();delete head;}//析构函数，删除循环链表
void Clear();//将线性链表置为空表
void AddElem(Type &e);//添加元素
ListNode *GetElem(int i)const;//返回单链表第i个结点的地址
void CirListClear();//将循环链表置为空表
int Length()const;//求线性链表的长度
ListNode*ListNextElem(ListNode*p=NULL);//返回循环链表p指针指向节点的直接后继，若不输入参数，则返回头指针
ListNode*CirListRemove(ListNode*p);//在循环链表中删除p指针指向节点的直接后继，且将其地址通过函数值返回
CirList&operator=(CirList&List);//重载赋
值运算符
};
3. 程序运行结果
源代码：#ifndef LISTNODE_H
#define LISTNODE_H
template class CirList;//声明单链表类
template class ListNode{//结点类定义；
friend class CirList;//声明链表类LinkList为友元类；
Type data;//结点的数据域；
ListNode*next;//结点的指针域；
public:
ListNode():next(NULL){}//默认构造函数；
ListNode(const Type &e):data(e),next(NULL){}//构造函数
Type & GetNodeData(){return data;}//返回结点的数据值；
ListNode*GetNodePtr(){return next;}//返回结点的指针域的值；
void SetNodeData(Type&e){data=e;}//设置结点的数据值；
void SetNodePtr(ListNode*ptr){next=ptr;} //设置结点的指针值；
};
#endif
===================================================================== #ifndef CIRLIST_H
#define CIRLIST_H
#include
