数据结构-约瑟夫环

江西农业大学

软件学院

数据结构课程设计

设计题目：约瑟夫环问题

专 业 软件工程 班 级 软件1014 学 号 20102073 姓 名 周洋 指导教师 史劲亭

2011年12月20日

约瑟夫环

一、需求分析

设计题目：约瑟夫环 问题描述：

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

1.利用单向循环链表存储结构模拟此过程。 2.按照出列的顺序输出各个人的编号。 3.测试数据。

二、概要设计

实验设计思路：

1．以无头结点的单循环链表为存储结构模拟此过程。 2．键盘录入各各同学所持密码，存储在一维数组a[]中。 3．单循环链表初始化时，将密码和编号存入结构体中。

4．进行单链表删除操作，直到链表为空，输出的编号存入数组b[]中 5．依次输出b[]中的元素。 程序结构：

本程序是单文件程序，构成的函数有

LinkedList LinkedListInit(int n,int a[]) 初始化循环单链表 void LinkedListTraverse(LinkedList L) 遍历单链表

void Play(LinkedList L,int m,int b[],int n) 单循环链表的删除 void main() 主函数，输出出队序列

其中，void Play()是最主要的函数，初始化单链表后，开始执行该函数，指针按给定的密码值m依次后移m次删除定位后的结点，输出编号，同时获得新的m值，继续循环，直到该链表为空。

三、详细设计

1.头文件 （保存在主程序文件夹内）

typedef struct node {

DataType data; struct node *next; }SCLNode;

void SCLLInitiate(SCLNode **head) {

if((*head=(SCLNode *)malloc(sizeof(SCLNode)))== NULL) exit(1); (*head)->next= *head; }

int SCLLInsert(SCLNode *head, int i, DataType x) {

SCLNode *p, *q; int j;

p=head->next; j=1; while(p!=head&&jp=p->next; j++; }

if(j!=i-1&&i!=1) {

printf(\"插入位置参数错！\"); return 0; }

if((q=(SCLNode *)malloc(sizeof(SCLNode)))==NULL) exit(1); q->data=x;

q->next=p->next; p->next=q; return 1; }

int SCLLDelete(SCLNode *head, int i,DataType *x) {

SCLNode *p,*q; int j;

p=head; j=0;

while(p->next!=head&&jp=p->next;j++; }

if(j!=i-1) {

printf(\"删除位置参数错！\");

return 0; }

q=p->next;

p->next=p->next->next; *x=q->data; free(q); return 1; }

int SCLLGet(SCLNode *head, int i,DataType *x) {

SCLNode *p; int j;

p=head; j=0;

while(p->next!=head&&jp=p->next; j++; }

if(j!=i) {

printf(\"取元素位置参数错！\"); return 0; }

*x=p->data; return 1; }

int SCLLNotEmpty(SCLNode *head) {

if(head->next==head) return 0; else return 1;

}

2.主函数

#include #include

typedef struct {

int number; int cipher;

}DataType;

#include\"SCLinList.h\"

void SCLLDeleteAfter(SCLNode *p) {

SCLNode * q=p->next; p->next=p->next->next; free(q); }

void JesephRing(SCLNode *head,int m) {

SCLNode *pre,*curr; int i;

pre =head;

curr = head->next;

while(SCLLNotEmpty(head)==1) { for(i=1;inext; if(curr==head) { pre=curr; curr=curr->next; } } printf(\"%d \ m=curr->data.cipher; curr=curr->next; if(curr==head)curr=curr->next; SCLLDeleteAfter(pre); } }

void main(void) { DataType test[7]={{1,3},{2,1},{3,7},{4,2},{5,4},{6,4},{7,4}}; int n =7,m=6,i; SCLNode *head;

}

SCLLInitiate(&head) ; for(i=1;i<=n;i++) SCLLInsert(head,i,test[i-1]); JesephRing(head,m);

四、调试分析

1.数据测试：

按照实验指导书要求，

m的初始值为20，n=7,7个人的密码依次为 3，1，7，2，4，7，4，首先m=6。则依次出列的个人编号为1，2，3，4，5，6，7。