线性表的应用举例.ppt

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”, /记录当前所报的数目,for (i=1;i0) count+; while (count!=m); printf(“%d”,position); /输出当前离开桌旁人的编号 GetElem(people,position, /将密码变为负值 ,链式存储结构 使用一个不带头结点的循环单链表结构。结点结构为：,图 2-10,用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(,position=people.head; /让position指向最后一个结点，以便报数从第一个开始 while (position-next!=people.head) position= NextElem(people,position); scanf(“%d”,printf(“%d”,position-item.No); /离开桌子处理 m=position-item.code; pre=PriorElem(people,position); pre-next=position-next; free(position); positi