约瑟夫环数据结构设计.docxVIP

.需求分析 约瑟夫环问题是典型的线性表的应用实例，其开辟主要包括后台数据库的建 立和维护以及前端应用程序的开辟两个方面。对于前者要求建立起数据一致性和 完整性强、数据安全性好的库。而对于后者则要求应用程序功能完备，易使用等 特点。 关键词：单循环链表；c语言；约瑟夫环； .概要设计 本次课程设计的内容是用单循环链表摹拟约瑟夫环问题，循环链表是一种首尾相 接链表，其特点是无须增加存储容量，仅对表的链接方式稍作改变，使表处理更加灵 活，约瑟夫环问题就是用单循环链表处理的一个实际应用。 .问题描述 约瑟夫环问题描述的是：设编号为1, 2,…，n的n(n>0)个人按顺时针方向围 坐一圈，每一个人持有一正整数密码。开始时选择一个正整数作为报数上限m, 从第一个人开始顺时针方向自1起顺序报数，报到m时住手报数，报m的人出圈， 将他的密码作为新的m值，从他在顺时针方向上的下一个人起重新从1报数。如 此下去，直到所有人都出圈为止。令n最大值为100。要求设计一个程序摹拟此过 程，求出出圈的编号序列。 .采用类c语言定义相关的数据类型 结点的定义 typedef struct Node { int data; int password; struct Node *next; (Node, *LinkList; 单向循环链表的抽象数据类型定义为： ADT List 参考文献 1严蔚敏，吴伟民.《数据结构（C语言版）》.清华大学出版社. 2严蔚敏，吴伟民.《数据结构题集（C语言版）》.清华大学出版社. 3谭浩强.《c语言程序设计》.清华大学出版社. 4宁正元，易金聪等.《数据结构习题解析与上机试验指导》.中国水利水出电版社, 上海交通大学出版社，东南大学出版社 课程设计完成之际，除了感到一种轻松以外，即将想到的就是对老师以及在 课程设计过程中匡助我的同学们，因为他们的指导和鞭策，才使我下定决心，集 中精力投入到课程设计的建设。 首先感谢我的指导老师王旭阳王老师，他在我的课程设计过程中提出了指导性 的方案和架构，比如让我把密码设计成自动和手动两种方式，使我在不熟悉的领 域中仍能迅速掌握新的技术。 感谢我的数据结构老师张永张老师和C语言老师王连相王老师在以往的基础 课学习中为我打下良好的基础，这是我这次课程设计能够顺利完成的前提。 我的同学在这次课设中也赋予了我一些好的建议！在此，也谢谢他们！ 附件I基本算法实现、 /*Hash链表的删除*/ struct node /*定义线性单链表结点类型*/ {intd;/*定义线性单链表结点数据类型*/ struct node *nex 结哽*指针*/ )； whasht(h,k,f)/*Hash 表的填入*/ int(*f)()； /*Hash码函数*/ ini k; struct node 外链Hash表的Hash表顺序存储空间*/ {int i; struct node *p; i=(*f)(k); p=(struct node *)malloc(sizeof(slruct n 取od?fe)结); h>d=k;/*填入关键字*/ p~>next=h[i-l];h[i?l]咻;新/结*点连接到以H(i)为头指针的链表链头*/ return; ) whashs(h,k,f)/*Ha 表 sh 的删除*/ ini (*0(); /*码as函h数*/ int k; /*关键字*/ struct node *h[]; /*外链Hash表的顺序存储空间*/ {int i,flag; struct node *p,*q,*s; i=(*f)(k); /*计算 Hash 码*/ p=h[i-l];q=NULL;flag=O; whilc(p!=NULL)/*在以H(i)为头指针的链表中查找所有关键字k*Z {if(p_>d=k)/* 找到 */ {iRp=h[i-1 ])h[i-l ]=p~>ne 修 xt 改；* 表结点的指针*/ else q->next=p->next; flag=l ;s=p;p=p->next;free(s); 1 else {q=p;p=p->next;} ) if(flag=O) return; ) main() {struct node *p,*h[I2]; static int k[l 2]={9,31,26,19,1,13,2,11,27,16,5,21); int m,n=12,i(); *h=(slrucl node *)malloc(n*sizeoflstruct n 分 od 配 e)Ha;s H* 表顺序存储空间*/ 执行结果 ⑴找到输入值的情况 亘 D:\Temp\MYDOCU~l\XIAOCH~l.exe k=ll 111112223 input 2