24 线性的应用举例.pptVIP

2.4 线性表的应用举例 约瑟夫（Joseph）问题：编号为1，2，···，n的n个人按顺时针方向围坐在一张圆桌旁，每个人手中持有一个密码（正整数）。首先输入一个正整数作为报数上限值m，然后，从第一个人开始按顺时针方向自1开始顺序报数，报到m的人离开桌旁，并将他手中的密码作为新的m值，从顺时针方向的下一个就坐在桌旁的人人开始重新从1报数，如此下去，直至所有人全部离开桌旁为止。 假设有7个人，编号从1到7，他们手中的密码分别是3，1，7，2，4，8，4，最初的m=2，通过报数，这7个人离开桌旁的顺序应该是：2，3，5，4，7，6，1。 数据结构的分析 这个问题的主角是n个人，每个人需要描述的信息有：编号、密码和是否在桌旁的状态。假设有7个人，他们的信息可以表示成下面的形式。 顺序存储结构 算法描述 让n个人围坐在一张圆桌旁； for (i=1;i=n;i++){ 从1开始报数，报到m停止； 报到m的人离开桌子； } 最终的算法实现—— #define LIST_MAX_LENGTH 7 #define n LIST_MAX_LENGTH typedef int EntryType; //将EntryType定义为int类型 void Joseph(int code[ ],int n) {//通过一维数组code带入n个人手中的密码，n是开始就坐在桌旁的人数 SQ_LIST people; int temp,m; //m是报数的上限值 scanf(“%d”,m); //输入最初的m if (InitList(people)==ERROR) exit ERROR; for (i=1;i=n;i++) if (ListInsert(people,i,code[i-1])==ERROR) exit ERROR; position=0; //记录当前报数人的编号 count=0; //记录当前所报的数目 for (i=1;i=n;i++) { do{ //报数 position=(position+1)%n; GetElem(people,position,temp); if (temp0) count++; }while (count!=m); printf(“%d”,position); //输出当前离开桌旁人的编号 GetElem(people,position,m); people.item[position-1]=-people.item[position-1]; //将密码变为负值 } } 链式存储结构 使用一个不带头结点的循环单链表结构。结点结构为： 用C语言定义 typedef struct{ //循环链表中每个结点的数据域部分的类型 int No; //编号 int code; //密码 }INFO; typedef INFO EntryType; 算法 void Joseph(int code[],int n) { LINK_LIST people; NODE *position,*pre; //position指向当前报数的结点 if (InitList(people)==ERROR) exit ERROR; //初始化链表people for (i=1;i=n;i++) //以n个人的信息为数据域内容向链表插入n个结点 if (ListInsert(people,i,code[i-1])==ERROR) exit ERROR; position=people.head; //让position指向最后一个结点，以便报数从第一个开始 while (position-next!=people.head) position= NextElem(people,position); scanf(“%d”,m); //输入最初的m for (i=1;in;i++){ count=0; //报数处理 do{