杭电数据结构joseph环

杭电数据结构joseph环

《数据结构》

课程设计报告

课程名称：

课程设计题目：

姓 名： 院系：

专 业：

年 级：

学 号：

指导教师： 《数据结构》课程设计 joseph环 计算机学院 计算机科学与技术 大二 王立波

2012年5月17日

杭电数据结构joseph环

目 录

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

杭电数据结构joseph环

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、小结

杭电数据结构joseph环

一、这次课程设计的心得体会通过实践我的收获如下：

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;

杭电数据结构joseph环

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环

joseph.Create(n);

joseph.Deal(m);

system("PAUSE");

return 0;

}

6、参考文献

[1] 万健、王立波、赵葆华、吴志芳 编著. 数据结构实用教程（C++版）.

本文来源：https://www.bwwdw.com/article/n604.html