数据结构（C语言版）程海英-上机2.docVIP

上机2 的操作实验 1.问题描述 2.数据结构设计 typedef struct node{ //单链表结点结构 ElemType data; //ElemType可以是任何数据类型 struct node *next; }LinkList; #define MAXSIZE 100 //MAXSI2E为线性表可能的级大长度 #define ERROR -1 typedef struct{ ElemType data[MAXSIZE]; int length; //length为线性表的长度 }SqList; /线性表定义3.问题求解 [约瑟夫环问题描述] 约瑟夫（Joseph）问题的一种描述是：编号为1 2， …… n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序打印出列顺序。 [基本要求] 利用循环单链表存储结构模拟此过程，按照出列的顺序打印出各人的编号。 [测试数据] n=7，即7个人按顺时针方向围坐一圈； 每个人持有的密码分别为：3，1，7，2，4，8，4； m的初值为20； 则正确的结果应为：6，1，4，7，2，3，5。 [实现提示] 循环单链表的结点中应该存放对应人员的编号和密码； 程序运行后，首先创建、打印循环单链表，然后要求用户指定初始报数m值。 创建、打印循环单链表，以及游戏过程分别用子函数实现。4.编码实现 typedef struct Lnode{ int data; struct Lnode *next; }joseph; （2）建立循环链表 void Create_List(joseph *L,int n){ int i; Joseph *p,*s; s=new joseph; s-data=1; p=s=L; for(i=2;i=n;i++){ s= new joseph; s-data=i; p- next=s; p=s; } p- next=L; } （3）实现Josephus并输出 void josephus ( joseph* L, int s, int m){ joseph *p,*q; int i; p=L; for (i=1; i=s-1; i++) //定位报数的起始位置，将p指针指向该结点 p=p-next; q=p-next; while (q-next! =p) q=q-next; //删除p所指的结点 while (p-next!=p) { //控制整个循环链表 for(int j=l;jm;j++){ q=p; p=p-next; } printf (“% d,”, p-data); //输出m Delete_List(L,p,q); p=q-next; } printf (“% d,”, p-data); //输出最后一个结点 printf(\n); } （4）删除指定结点 void Delete_List(joseph*L,joseph *p,joseph *q){ q- next= p- next; delete p; } （5）主函数 void main(){ joseph * L=NULL; int m,n,s; printf (“请输入人数、约定编号数，出列值：\n”); scanf (“%d% d%d”, n, s, m); if((m 1000) || (n 1000)) printf (“输入的人数m，n不合法\n”); else if (sn) printf (“输入数据不合法！\n”); else { Create_List(L, n); prititf (“\n”); josephus(L,s,m); } } 5.运行测试 建立循环链表，按提示输入相关数据，调试相关功能函数，测试各函数。并用顺序结构求解上述约瑟夫（Joseph）