数据结构-利用线性表解决约瑟夫问题

北京服装学院商学院

上机实验报告

实验名称： 利用线性表解决约瑟夫问题

学生姓名： XXXXXX

班级学号： 11111111

指导教师： 111111111

实验日期： 2010年11月26日

一、实验名称

利用线性表解决约瑟夫问题

二、实验目的

（1）掌握线性表的基本操作中的算法

（2）灵活运用线性表的基本算法设计算法解决具体问题 三、实验内容

（1）设计解决约瑟夫问题的算法

（2）根据算法编写程序实现算法，调试程序 （3）编写实验报告 四、实验环境

硬件：学生机房 软件：TC2.0 五、实验过程和结果

1．算法：

for(i=0; i

s=(struct Node *)malloc(sizeof(struct Node)); s->data=i+1; s->next=NULL; if(i==0) {

head=s; q=head; } else {

q->next=s; q=q->next; } }

q->next=head; printf(\ q=head;

2

while(q->next!=head) {

printf(\ q=q->next; }

printf(\ q=head; printf(\ do {

count++; if(count==n-1) {

t=q->next; q->next=t->next; count=0;

printf(\ free(t); } q=q->next; }

while(q->next!=q); 2．程序： 单链表实现 #include #include struct Node { int data;

struct Node *next; };

int main()

{ struct Node *head, *s, *q, *t;

3

int n, m, count=0, i;

printf(\ scanf(\

printf(\ scanf(\ for(i=0; i

s=(struct Node *)malloc(sizeof(struct Node)); s->data=i+1; s->next=NULL; if(i==0) {

head=s; q=head; } else {

q->next=s; q=q->next; } }

q->next=head; printf(\ q=head;

while(q->next!=head) {

printf(\ q=q->next; }

printf(\ q=head; printf(\

4

do {

count++; if(count==n-1) {

t=q->next; q->next=t->next; count=0;

printf(\ free(t); } q=q->next; }

while(q->next!=q);

printf(\}

3．运行结果：

input the monkey number m:5 input the number n:3

before:1 2 3 4 5 3 1 5 2 the king is:4 六、总结

猴子选大王的问题对我来说特别难，看到这个题目，我一点头绪也没有。

之后在网上参看了很多程序，才完成这次作业。以前C语言学的就不怎么好，现在学数据结构更是吃力，许多语句都看不懂是什么意思。通过这次作业，我发现了越来越多不懂的问题，获益匪浅。

5