线性表的应用举例

《线性表的应用举例》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、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。数据结构

2、的分析这个问题的主角是n个人，每个人需要描述的信息有：编号、密码和是否在桌旁的状态。假设有7个人，他们的信息可以表示成下面的形式。顺序存储结构算法描述让n个人围坐在一张圆桌旁；for(i=1;i<=n;i++){从1开始报数，报到m停止；报到m的人离开桌子；}最终的算法实现——#defineLIST_MAX_LENGTH7#definenLIST_MAX_LENGTHtypedefintEntryType;//将EntryType定义为int类型voidJoseph(intcode[],intn){//通过一维数组code带入n个人手

3、中的密码，n是开始就坐在桌旁的人数SQ_LISTpeople;inttemp,m;//m是报数的上限值scanf(“%d”,&m);//输入最初的mif(InitList(&people)==ERROR)exitERROR;for(i=1;i<=n;i++)if(ListInsert(&people,i,code[i-1])==ERROR)exitERROR;position=0;//记录当前报数人的编号count=0;//记录当前所报的数目for(i=1;i<=n;i++){do{//报数position=(position+1)%

4、n;GetElem(people,position,&temp);if(temp>0)count++;}while(count!=m);printf(“%d”,position);//输出当前离开桌旁人的编号GetElem(people,position,&m);people.item[position-1]=-people.item[position-1];//将密码变为负值}}链式存储结构使用一个不带头结点的循环单链表结构。结点结构为：Nocodenext图2-10用C语言定义typedefstruct{//循环链表中每个结点的数

5、据域部分的类型intNo;//编号intcode;//密码}INFO;typedefINFOEntryType;算法voidJoseph(intcode[],intn){LINK_LISTpeople;NODE*position,*pre;//position指向当前报数的结点if(InitList(&people)==ERROR)exitERROR;//初始化链表peoplefor(i=1;i<=n;i++)//以n个人的信息为数据域内容向链表插入n个结点if(ListInsert(&people,i,code[i-1])==ERR

6、OR)exitERROR;position=people.head;//让position指向最后一个结点，以便报数从第一个开始while(position->next!=people.head)position=NextElem(people,position);scanf(“%d”,&m);//输入最初的mfor(i=1;i

7、->item.No);//离开桌子处理m=position->item.code;pre=PriorElem(people,position);pre->next=position->next;free(position);position=pre;}printf(“%d”,position->item.No);//处理最后一个人free(position);}