数据结构与算法与形考作业一（占比15%）

江苏开放大学实验报告

学号：_______________________________

姓名：_______________________________

课程代码：060220____________________

课程名称：数据结构与算法

评阅教师：许小媛______________________

实验名称：线性表的应用

一、实验目的及要求

1.熟练掌握线性表的基本操作在顺序存储和链式存储上的实现；

2.以线性表的各种操作（建立、插入、删除、遍历等）的实现为重点；

3.掌握线性表的动态分配顺序存储结构的定义和基本操作的实现；

4.通过本章实验帮助学生加深对C语言的使用（特别是函数的参数调用、指针类型的

应用和链表的建立等各种基本操作）。

二、实验内容

约瑟夫问题的实现：n只猴子要选猴王，所有猴子按1,2，…，n编号围坐一圈，从第1

只开始按1,2，…，m报数，凡报到m号的猴子退出圈外，如此循环报数，直到圈内剩下一

只猴子时，这个猴子就是猴王。编写一个程序实现上述过程，n和m由键盘输入。

三、实验设备及环境

安装C语言编译环境。

四、实验步骤（功能实现的核心代码及说明，包括数据库表）

#include<stdio.h>

#include<stdlib.h>

#defineOK1;

#defineERROR0;

typedefintStatus;

typedefintElemtype;

typedefstructCnode{

Elemtypedata;

structCnode*next;

}CNode;

CNode*joseph;

intking_value=0;

StatusCreate_clist(CNode*clist,intn){

CNode*p,*q;

inti;

clist=NULL;//NULL=O?

for(i=n;i>=1;i-)

(

p=(CNode*)malloc(sizeof(CNode));

if(p==NULL)

(

return・1;〃存储空间分配失败

)

p->data=i;

p->next=clist;

clist=p;

if(i==n)

(

q=p;

)

)

q->next=clist;

joseph=clist;

returnOK;

)

StatusJoseph(CNodeMist,inttotal_num,intout_index){

inti;

CNode*p,*q;

2

if(out_index<=0)

returnERROR;

)

if(!Create_clist(clist,total_num))

(

returnERROR;

)

p=joseph;

while(p)

(

for(i=1;i<out_index-l;i++)

(

p=p->next;

}

q=p->next;

king_value=q->data;

if(p->next==p)

(

p=NULL;

Jelse

(

p->next=q->next;

p=p->next;

free(q);

)

)

clist=NULL;

intmain(){

3

inttotal_num,out_index;

CNode*clist;

clist=NULL;

printf("\n请输入猴子的数量：")；

scanf("%d",&total_num);

printf(,f\n请输入报数到第几个数的猴子出列：”);

scanf("%dn,&out_index);

Create_clist(clist,total_num);

Joseph(clist,total_num,out_index);

printf("猴王是：%d\nn,king_value);

五、实验结果（程序运行结果等，可附截图）

UshuchenQlishuchendeftacBook-ProXflQSSk9^clisjwork.c

.ist_Mork.c:67:l:warning：controlmyr«»ch«ndofnon-voidfunction("Wretum-typ«]

:warninggenerated._________

Ushuchen§li$huchendeHac8ook-Pro./a.out

满注入接子的数・17

法输入报数箕第几个效的娘子出列5

螺王！1：11..

Ushuchen®l.i5huchendeKacBook-ProFl