约瑟夫问题实验报告
- 格式：doc
- 大小：306.08 KB
- 文档页数：7
X X X X X X X X
实验报告
课程： 数据结构 班级： 姓名： 学号：
成绩： 指导教师： 实验日期： 2012.3
实验密级： 预习程度： 实验时间：
仪器组次： 必修/选修： 必修 实验序号： 01
实验名称： 线性结构的应用——约瑟夫问题
实验目的与要求：
编程实现约瑟夫问题。假设有n个人围圈而坐，现在从第k人开始数数，数到m的人出列，紧接着的后续人又从1开始数数，到m出列，如此重复下去，直到全体人员出列。编程实现新出列的数字序号输出。
实验仪器：
名称
型号 数量
微机 1
- 2 - 一、概要设计
本程序使用了循环链表这一数据结构。循环链表在普通链表的基础上，将最后一个节点的指针域指向头结点。具体定义为：
typedef struct CLNode{
int data;
struct CLNode *next;
}Node;//定义单向循环链表结构体，并令最后一个指针指向头结点
流程图如下：
注：在*处调用子函数 为head分配存储空间，如果内存不够，结束程序
head=head->next;
head->data=i;
i++; head==NULL? i<=n?
为p分配存储空间,如果内存不够，结束程序
pr->next=p;p->data=i;
p->next=head; pr=p; 开始
从主函数中接受头结点指针head，n
i=1，Node *p=NULL，
Node *pr=head;
返回head 是
是 否
否
图2——子函数：建立n阶循环链表，返回链表的头指针
图1——主函数 开始
输入总人数(n)、从第几个人开始数(k)、数到第几个人出列(m)
构造n项循环链表*
执行”head=head->next”k次，修改头指针指向 Node *head=NULL;int i=0;
按顺序输出？
否 是
是 否
结束 释放链表剩余存储空间 输出head->data 实现报数并出列* head!=head->next? 直接按顺序输出 - 3 -
二、详细设计
本程序核心算法主要有两部分：一是建立循环链表，二是实现目标人员的出列。
建立循环链表：
1.判断原链表是否为空，是的话，执行第2步，否则，执行第3步；
2.为头结点head分配存储空间，并令其指针域指向本身，head->data=1,用pr指向head，返回第1步；
3.判断计数器i（初始为2）是否不大于n，是的话，执行第4步，否则，执行第5步；
4.为节点p分配存储空间，并令其指针域指向head，给p->data赋值为i,令pr->next=p,用pr指向head，i增1，返回第3步；
5.返回head到主函数。
实现目标人员的出列：
1.输入从第k个人开始报数，在主函数中实现头指针的移动，修改后，执行第2步；
2.判断链表中的节点数是否大于1，是的话，执行第3步，否则，执行第5步；
3.调用子函数Search，定义指针 ：Node *p=head，执行第4步；
4.根据输入中第m个人出列，移动指针p m-1次,令其指向要出列的目标节点，输出其数据域p->data，并令此节点之后的第一个节点为head，删除目标节点，返回head到主函数，执行第2步；
5.输出head->data，并释放链表的剩余空间，结束程序。
代码清单： 此时，p->data便是出列编号，输出其值
删除p指向的节点，令p之后的节点为head
返回head 开始
从主函数中接受head和m
int i=1;
Node *p=head;
Node *pre=NULL;
执行：”pre=p;p=p->next;”m次，模拟报数并移动指针
图3——子函数：当链表中的结点个数大于1，调用此函数，实现目标出列，并删除该节点，另该节点下一结点为头结点，返回修改后的头结点 - 4 -
#include
#include
typedef struct CLNode{
int data;
struct CLNode *next;
}Node;//定义单向循环链表结构体
Node* Creat(Node* head,int n);
Node* Search(Node* head,int m);
int main()
{
int m,n,k,j;
Node *head=NULL;
printf("How many person?");
scanf("%d",&n);
if(n<=0){
printf("Can't be zero!\n");
exit(0);
}
head=Creat(head,n); //建立链表
printf("Which number do you want to start:");
scanf("%d",&k);
printf("Which number should be out:");
scanf("%d",&m);
for(j=1;j head=head->next; } printf("\n"); if(m==1){//如果是按顺序输出，不必调用Search函数 for(j=0;j printf("output number is:%d\n",head->data); head=head->next; } } else{ while(head!=head->next){ head=Search(head,m);//返回修改后的头结点 } if(head!=NULL){ printf("output number is:%d\n",head->data);//输出最后的节点 } } printf("****END****\n"); free(head); return 0; } /*Create函数：参数为Node型结点指针和数量n -建立单循环链表，如果成功，返回该链表的头指针*/ Node* Creat(Node *head,int n) { Node *p=NULL; Node *pr=head; int i; for (i=1; i<=n;i++){ if (head==NULL) { head=(Node*)malloc(sizeof(Node)); if(head==NULL){ printf("Allcate memory error!\n"); exit(1); } head->next=head; head->data=i; pr=head; } else { p=(Node*)malloc(sizeof(Node)); if(p==NULL){ printf("Allcate memory error!\n"); exit(1); } pr->next=p; p->data=i; p->next=head; pr=p; } } return head; } /*Search函数：输出从head开始数第m个结点的数据域，令该结点之后的结点为头结点, 并返回它，数据域从它开始再次循环*/ Node* Search(Node *head,int m) { int i=1; Node *cur_p=head,*pre=NULL;//head为开始数1的人 while(i pre=cur_p; cur_p=cur_p->next; i++; } printf("output number is:%d\n",cur_p->data); pre->next=cur_p->next; head=pre->next;//修改头指针 free(cur_p);//删除该节点 return head; }
