数据结构链表-约瑟夫环

《数据结构链表-约瑟夫环》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、浙江万里学院实验报告成绩：教师：刘晓利课程名称：数据结构实验名称：线性表专业班级：计算机111实验小组：第十组实验日期：2012-9-21成员姓名李俊胡一凡魏净达程俊鹏成绩9888成员姓名（以下写实验内容、分析与程序清单、调试报告等）一、实验目的：（1）了解线性表的逻辑结构特性，以及这种特性在计算机内的两种存储结构。（2）重点是线性表的基本操作在两种存储结构上的实现；其中以链表的操作为侧重点；并进一步学习结构化的程序设计方法。二、实验内容1、约瑟夫环问题：用链式存储表示实现约瑟夫环问题2、算法思想

2、：（1）用循环链表模拟约瑟夫环。即该链表的尾指针指向头结点的地址。（2）创建一个循环链表存入初始数据，包括编号，密码。（3）用模拟约瑟夫环的办法将其输出，每输出一个数据循环链表中就少一个结点。3具体程序：#include#includetypedefstructnode{intnum;//编号存放地址intsm;//密码存放地址structnode*next;//指针域}JOS;JOS*creat();//创建一个JOS函数函数的返回值是指向该类结构体的地址v

3、oidouts(JOS*h,intm);//打印结果成绩voidmain(){intm;JOS*h;h=creat();printf("输入起始密码m(m>1):");scanf("%d",&m);outs(h,m);}/*生成约瑟夫环*/JOS*creat(){inti=0,mi;JOS*New,*ptr,*h;h=(JOS*)malloc(sizeof(JOS));h->next=h;//将头结点的next指向自己，构成一个循环链表ptr=h;//令操作指针指向头结点printf("第

4、%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("第%d个人密码=",i+1);sc

5、anf("%d",&mi);}ptr->next=h->next;free(h);//由于对于最后一个人的操作其结点指向头结点，但头结点是为空的，所以要删除head结点。h=ptr->next;return(h);//最后令head指针指向第一个元素的结点就可以了}voidouts(JOS*h,intm){inti;JOS*q=h,*p;printf("");while(q->next!=q)//判定条件是该环中至少还要有两个元素才能继续{for(i=1;in

6、ext;}//q是一个移动指针当模拟报数报到第m个人得时候q也指向了第m个人printf("第%d人密码:%d",q->num,q->sm);/*输出第m个人的编号和密码*/m=q->sm;//让出列的人得密码为新密码p->next=q->next;free(q);//释放q指针模拟第m人出列q=p->next;}printf("第%d人密码:%d",q->num,q->sm);//最后环中只剩一人将其输出free(q);}4、程序调试：课本中该程序有三处错误，第一结构体的指针名称为nex

7、t而具体操作时指针名又为link；第二new是关键字这里我讲new改为了New；第三在outs函数中p应该为结构指针。将该错误改完后，为了实现以出列的人的密码为新的报数值加了m=q->sm;这一句话。最后将程序汉化。调试测试：三、心得体会对于链式结构虽然抽象但是掌握其本质后无非是指针的操作。只要对指针有个很好的掌握就可以了。这个程序中我觉得对于头结点的操作过于麻烦，其实可以有调整的空间。只要对头结点也做数据存放那么最后就不用再去删除头结点了。当然头结点的数据该不该为空应该因地制宜。