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)；//构造一个空的单链表表LListEmpty(L); //判断单链表L是否是空表，若是，则返回1，否则返回0.ListLength(L); //求单链表L的长度GetElem（L，i）；//返回链表L中第i个数据元素的值；ListSort(LinkList<Type>&List) //单链表排序ListClear(&L); //将单链表L中的所有元素删除，使单链表变为空表ListDestroy(&L);//将单链表销毁}ADT List其他函数：主函数；结点类;约瑟夫函数2.1 存储结构[内容要求]1、存储结构：顺序表、单链表或其他存储结构，需要画示意图，可参考书上P59页图2-92.2 关键算法分析结点类：template<class Type> class CirList;//声明单链表类template<class Type> class ListNode{//结点类定义；friend class CirList<Type>;//声明链表类LinkList为友元类；Type data;//结点的数据域；ListNode<Type>*next;//结点的指针域；public:ListNode():next(NULL){}//默认构造函数；ListNode(const Type &e):data(e),next(NULL){}//构造函数Type & GetNodeData(){return data;}//返回结点的数据值；ListNode<Type>*GetNodePtr(){return next;}//返回结点的指针域的值；void SetNodeData(Type&e){data=e;}//设置结点的数据值；void SetNodePtr(ListNode<Type>*ptr){next=ptr;} //设置结点的指针值；};单循环链表类：template<class Type>class CirList{ListNode<Type>*head;//循环链表头指针public:CirList(){head=newListNode<Type>();head->next=head;}//构造函数，建立带头节点的空循环链表~CirList(){CirListClear();delete head;}//析构函数，删除循环链表void Clear();//将线性链表置为空表void AddElem(Type &e);//添加元素ListNode<Type> *GetElem(int i)const;//返回单链表第i个结点的地址void CirListClear();//将循环链表置为空表int Length()const;//求线性链表的长度ListNode<Type>*ListNextElem(ListNode<Type>*p=NULL);//返回循环链表p指针指向节点的直接后继，若不输入参数，则返回头指针ListNode<Type>*CirListRemove(ListNode<Type>*p);//在循环链表中删除p指针指向节点的直接后继，且将其地址通过函数值返回CirList<Type>&operator=(CirList<Type>&List);//重载赋值运算符};3. 程序运行结果源代码：#ifndef LISTNODE_H#define LISTNODE_Htemplate<class Type> class CirList;//声明单链表类template<class Type> class ListNode{//结点类定义；friend class CirList<Type>;//声明链表类LinkList为友元类；Type data;//结点的数据域；ListNode<Type>*next;//结点的指针域；public:ListNode():next(NULL){}//默认构造函数；ListNode(const Type &e):data(e),next(NULL){}//构造函数Type & GetNodeData(){return data;}//返回结点的数据值；ListNode<Type>*GetNodePtr(){return next;}//返回结点的指针域的值；void SetNodeData(Type&e){data=e;}//设置结点的数据值；void SetNodePtr(ListNode<Type>*ptr){next=ptr;} //设置结点的指针值；};#endif===================================================================== #ifndef CIRLIST_H#define CIRLIST_H#include<iostream>#include"ListNode.h"template<class Type>class CirList{ListNode<Type>*head;//循环链表头指针public:CirList(){head=new ListNode<Type>();head->next=head;}//构造函数，建立带头节点的空循环链表~CirList(){CirListClear();delete head;}//析构函数，删除循环链表void Clear();//将线性链表置为空表void AddElem(Type &e);//添加元素ListNode<Type> *GetElem(int i)const;//返回单链表第i个结点的地址void CirListClear();//将循环链表置为空表int Length()const;//求线性链表的长度ListNode<Type>*ListNextElem(ListNode<Type>*p=NULL);//返回循环链表p指针指向节点的直接后继，若不输入参数，则返回头指针ListNode<Type>*CirListRemove(ListNode<Type>*p);//在循环链表中删除p指针指向节点的直接后继，且将其地址通过函数值返回CirList<Type>&operator=(CirList<Type>&List);//重载赋值运算符};//=================================================================== //将循环链表置为空表template<class Type> void CirList<Type>::CirListClear(){ListNode<Type>*p;while(head->next!=head){p=head->next;head->next=p->next;delete p;}}//=================================================================== //返回循环链表p指针指向节点的直接后继，若不输入参数，则返回头指针template<classType>ListNode<Type>*CirList<Type>::ListNextElem(ListNode<Type>*p){if(p==NULL)return head;ListNode<Type>*q=p->next;if(q==head)q=q->next;return q;}//=================================================================== //将线性表置为空template<class Type>void CirList<Type>::Clear(){ListNode<Type>*p;while(head->next!=NULL){ p=head->next;head->next=p->next;delete p;}}//=================================================================== //在循环链表中删除p指针指向节点的直接后继，且将其地址通过函数值返回template<classType>ListNode<Type>*CirList<Type>::CirListRemove(ListNode<Type>*p){ListNode<Type>*q=p->next;if(q==head){q=q->next;head->next=q->next;}elsep->next=q->next;return q;}//=================================================================== //返回第i个结点的地址template<class Type>ListNode<Type>*CirList<Type>::GetElem(int i)const{ int j=0;ListNode<Type>*p=head;while(j<i&&p){j++;p=p->next;}if(!p||j>i) return NULL;return p;}//=================================================================== //添加元素template<class Type>void CirList<Type>::AddElem(Type&e){ListNode<Type>*p,*s=new ListNode<Type>(e);int i=Length();p=GetElem(i);p->next=s;s->next=head;}//=================================================================== //重载赋值运算符template<classType>CirList<Type>&CirList<Type>::operator=(CirList<Type>&List){if(this==&List)return *this;//赋值操作符重载，必须检查是否为自我赋值Clear();ListNode<Type>*p=List.head->next,*q=head,*s;while(p){s=new ListNode<Type>;s->data=p->data;q->next=s;q=s;p=p->next;}q->next=NULL;return *this;}//=================================================================== //求线性链表的长度template<class Type>int CirList<Type>::Length()const{int len=0;ListNode<Type>*p;for(p=head->next;p!=head;len++)p=p->next;return len;}#endif===================================================================== #include <iostream>#include "CirList.h"using namespace std;template<class Type>void Josephus(CirList<Type>&clist,int n,int m){ListNode<Type>*p,*current;for(int i=1;i<=n;i++)clist.AddElem(i);current=clist.ListNextElem();//得到循环链表的头指针for(int i=1;i<=n-1;i++)//删除过程循环n-1次{for(int j=1;j<=m-1;j++)//使current指针后移m-1次current=clist.ListNextElem(current);p=clist.CirListRemove(current);//删除满足要求的节点，且用 p 记录其地点cout<<"删除顺序："<<p->GetNodeData()<<endl;delete p;//释放已删除结点占用的内存}current=clist.ListNextElem();//得到循环链表的头指针p=clist.ListNextElem(current);//获得最后剩下结点的地址cout<<"最后剩下："<<p->GetNodeData()<<endl;}int main(int argc, char *argv[]){CirList<int> Jose;Josephus(Jose,14,17);system("PAUSE");return EXIT_SUCCESS;}4. 总结在课程设计中我更体会到：一个好的程序应该是一个所占空间小、运行时间短、其他性能也好的算法。