约瑟夫问题及习题实验-2014.ppt

无头链表及应用无头链表及应用2.5.2约瑟夫问题“约瑟夫问题”是指n个人围坐在一张圆桌周围，从某人开始由1报数，数到m的人就出列（离开座位，不再参加以后的报数），然后从下一个人开始重新从1报数，数到m的人又出列。如此下去，直到所有的人都出列。试求他们出局的次序。2.5.2约瑟夫问题例如，当n=8、m=4时，若从第1个人开始报数，那么得到的出列次序是：4，8，5，2，1，3，7，6如图所示（方框内数字为人的编号，圆圈内数字为出列顺序）12345687①②③④⑤⑥⑦⑧人员编号出列顺序可用不带头结点的循环链表来解决该问题：它共有n个存储结点，每个结点由data（里面是人的编号）和next（指向下一个结点的指针）组成。假定第1次从编号为s的人那里开始数数m。算法取名为Josephus()，参数为n、m、s。HZHAOQIANSUNLIZHOUWUZHENGWANG用不带头结点的循环链表求解约瑟夫问题的算法算法2-18Josephus(n,m,s){ Ck_t=NULL; for(i=n;i=1;i--){ ptr=malloc(size); ptr-data=i; if(Ck_t==NULL) { ptr-next=ptr; Ck_t=ptr;} else {ptr-next=Ck_t-next; Ck_t-next=ptr;}}算法描述//是从后往前形成有n个结点的Josephus循环链表，//如果插入的为第一个元素p=Ck_t;q=Ck_t-next;for(i=1;is;i++){p=q;q=q-next;}for(i=1;in;i++){for(j=1;jm;j++){p=q;q=q-next;}printf(“%d”,q-data);p-next=q-next;free(q);q=p-next;}printf(“%d”,q-data);free(q);}//用来从表头开始顺序查找第s个结点C语言实现约瑟夫问题#includestdio.h//文件包函#includestdlib.htypedefstructnode{ intdata; structnode*next;}node,*linklist;//数据类型生成#defineN10//定义符号常量#defineM4#defineS6datanext结点voidmain(){ node*h=NULL,*q,*p; inti,j; for(i=N;i=1;i--) {p=(linklist)malloc(sizeof(node)); p-data=i; if(h==NULL) { p-next=p; h=p; } else { p-next=h-next; h-next=p; } }datanext∧hqp10xtdatanext9xt没有头结点的链表，插入操作不一致。voidmain(){ node*h=NULL,*q,*p; inti,j; for(i=N;i=1;i--) {p=(linklist)malloc(sizeof(node)); p-data=i; if(h==NULL) { p-next=p; h=p; } else { p-next=h-next; h-next=p; } }datanext∧hqp10xtdatanext9xt相当于头插法datanext8xtdatanext∧hqp10xt9nextxt8nextxtdatanext…xtdatanext3xtdatanext2xtdatanext1xtq=h-next; for(i=1;iS;i++) { p=q; q=q-next; } q从第s=3个开始，报数为m=4，pdatanext∧h10xt9nextxt8nextxt