欢迎来到天天文库
浏览记录
ID:38569667
大小:281.31 KB
页数:11页
时间:2019-06-15
《线性表的应用举例》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
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;i7、->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);}
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);}
此文档下载收益归作者所有