杭电数据结构joseph环
- 格式：doc
- 大小：87.00 KB
- 文档页数：6
《数据结构》
课程设计报告
课程名称：《数据结构》课程设计课程设计题目：joseph环
姓名：
院系：计算机学院
专业：计算机科学与技术
年级：大二
学号：
指导教师：王立波
2012年5月17日
目录
1 课程设计的目的 (x)
2 需求分析 (x)
3 课程设计报告内容 (x)
1、概要设计 (x)
2、详细设计 (x)
3、测试结果 (x)
4、程序清单 (x)
4 小结 (x)
5 参考文献 (x)
1、课程设计的目的
（1）熟练使用C++语言编写程序，解决实际问题；
（2）了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；
（3）初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；（4）提高综合运用所学的理论知识和方法独立分析和解决问题的能力；
2、需求分析
1、任务：
（一）：设置一个含有{data，num，*next}变量的结构体。
（二）：输入链表的长度n，以及初始密码m。
（三）：建立只有tail指针且不带头结点，长度是n的循环链表。
将第一个数赋给tail->data，用p指针标记，然后再不断的在链表尾部插入数据节点，并且最后个节点的next指针指向p，形成环状。
（四）：进行数据处理，初始密码为m，从第一个仍开始顺时针方向自1开始顺序报数，报到m时停止报数。
报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。
2、测试数据
n=5,m=1 数据为1 2 3 4 5。
出队顺序为1 2 4 3 5
n=5,m=1 数据为5 4 3 2 1 出队顺序为1 2 3 4 5
n=7,m=20 数据为3 1 4 2 4 7 4 出队顺序为6 7 4 1 5 3 2
3、课程设计报告内容
概要设计
（1）在分析题目要求的基础上，我首先设计了一个结构体，定义如下struct Node //设置一个含有{data，num，*next}变量的结构体
{
Node *next;
int data;
int num;
};存储信息。
测试结果：
4、小结
一、这次课程设计的心得体会通过实践我的收获如下：
1、巩固和加深了对数据结构的理解，提高综合运用本课程所学知识的能力。
2、培养了我选用参考书，查阅手册及文献资料的能力。
培养独立思考，深入研究，分析问题、解决问题的能力。
3、通过实际编译系统的分析设计、编程调试，掌握应用软件的分析方法和工程设计方法。
二、根据我在实习中遇到得问题，我将在以后的学习过程中注意以下几点：
1、认真上好专业实验课，多在实践中锻炼自己。
2、写程序的过程中要考虑周到，严密。
3、在做设计的时候要有信心，有耐心，切勿浮躁。
4、认真的学习课本知识，掌握课本中的知识点，并在此基础上学会灵活运用。
5、在课余时间里多写程序，熟练掌握在调试程序的过程中所遇到的常见错误，以便能节省调试程序的时间。
5、程序清单：
#include<iostream>
using namespace std;
struct Node //设置一个含有{data，num，*next}变量的结构体
{
Node *next;
int data;
int num;
};
class Joseph
{
public:
Joseph();//构造函数,创建空链表
void Create(const int n);//创建单循环链表
bool Deal(int m);//处理约瑟夫环
private:
Node *tail;
int len;
};
Joseph::Joseph()
{
tail = new Node; //分配一个新单元，tail指向新单元
tail->next=NULL;
len=0;
}
void Joseph:: Create(const int n)//创建n个元素的链表
{
int m;
Node *p,*q;
cout<<"请分别输入"<<n<<"个人的密码: "<<endl;
cin>>m;//第一次，在尾指针所在单元输入值
tail->data=m;
tail->num=1;
q=tail;
for(int i=2;i<=n;i++)
{
cin>>m;
p=new Node;
p->data=m;
p->num=i;
tail->next=p;//尾部添加元素
tail=p;//tail指针下移，指向p
}
tail->next=q;
}
bool Joseph:: Deal(int m)//处理约瑟夫环
{
int number;
while(len)
{
Node *q,*p=tail;//p指向链表的第一个元素
while(--m)
p = p->next;//p指向要删除的前一个元素
q=p->next;//q指向要删除的元素
m = q->data;
number=q->num;
tail=p;//tail所指向删除单元的前一个
p->next=q->next;
delete q;
len--;
cout<<number<<" ";
}
return true;
}
int main()
{
int m,n;
Joseph joseph;
cout<<"请输入m的初值："<<endl;
cin>>m;
cout<<"请输入人数n的值："<<endl;
joseph.Create(n);
joseph.Deal(m);
system("PAUSE");
return 0;
}
6、参考文献
[1] 万健、王立波、赵葆华、吴志芳编著. 数据结构实用教程（C++版）.。
