数据结构链表-约瑟夫环.doc

浙江万里学院实验报告成绩： 教师： 刘晓利 课程名称： 数据结构 实验名称： 线性表 专业班级： 计算机111 实验小组： 第十组 实验日期： 2012-9-21 成员姓名李俊胡一凡魏净达程俊鹏成 绩9888成员姓名（以下写实验内容、分析与程序清单、调试报告等）一、实验目的：（1） 了解线性表的逻辑结构特性，以及这种特性在计算机内的两种存储结构。（2） 重点是线性表的基本操作在两种存储结构上的实现；其中以链表的操作为侧重点；并进一步学习结构化的程序设计方法。二、实验内容1、约瑟夫环问题：用链式存储表示实现约瑟夫环问题2、算法思想：（1）用循环链表模拟约瑟夫环。即该链表的尾指针指向头结点的地址。（2）创建一个循环链表存入初始数据，包括编号，密码。（3）用模拟约瑟夫环的办法将其输出，每输出一个数据循环链表中就少一个结点。3具体程序：#include #include typedef struct node int num;/编号存放地址 int sm;/密码存放地址 struct node *next; /指针域 JOS;JOS *creat(); /创建一个JOS函数函数的返回值是指向该类结构体的地址void outs(JOS *h, int m); /打印结果成 绩void main() int m; JOS *h; h=creat(); printf(n输入起始密码m(m1):);scanf(%d,&m); outs(h,m); /* 生成约瑟夫环 */JOS *creat() int i=0, mi; JOS *New, *ptr, *h; h=(JOS *)malloc(sizeof(JOS); h-next=h; /将头结点的next指向自己，构成一个循环链表 ptr=h; /令操作指针指向头结点 printf(n第%d个人密码=,i+1);scanf(%d,&mi); while( mi != -111) /指定当密码为-111时停止输入 New=(JOS *)malloc(sizeof(JOS); /定义New为新的插入结点对其分配内存空间 i+; New-num=i;New-sm=mi; /为New中的数据赋值 New-next=h; ptr-next=New; /将New插入循环链表中，新元素的next始终指向头结点 ptr=New; /操作指针移动 printf(n第%d个人密码=,i+1); scanf(%d,&mi); ptr-next= h-next; free(h); /由于对于最后一个人的操作其结点指向头结点，但头结点是为空的，所以要删除head结点。 h=ptr-next; return(h); /最后令head指针指向第一个元素的结点就可以了 void outs(JOS *h, int m) int i; JOS *q=h,*p; printf(n); while (q-next!=q) /判定条件是该环中至少还要有两个元素才能继续 for(i=1;inext; /q是一个移动指针当模拟报数报到第m个人得时候q也指向了第m个人printf(第%d人密码:%dn,q-num,q-sm); /* 输出第m个人的编号和密码 */m=q-sm; /让出列的人得密码为新密码p-next=q-next; free(q); /释放q指针模拟第m人出列q=p-next; printf(第%d人密码:%dn,q-num,q-sm); /最后环中只剩一人将其输出free(q);4、程序调试：课本中该程序有三处错误，第一结构体的指针名称为next而具体操作时指针名又为link；第二new是关键字这里我讲new改为了New；第三在outs函数中p应该为结构指针。将该错误改完后，为了实现以出列的人的密码为新的报数值加了m=q-sm;这一句话。最后将程序汉化。调试测试：三、心得体会对于链式结构虽然抽象但是掌握其本质后无非是指针的操作。只要对指针有个很好的