2013年山西省数据整理加强

1、冒泡排序算法是把大的元素向上移（气泡的上浮），也可以把小的元素向下移（气泡的下沉）请给出上浮和下沉过程交替的冒泡排序算法。

48.有n个记录存储在带头结点的双向链表中，现用双向起泡排序法对其按上升序进行排序，请写出这种排序的算法。（注：双向起泡排序即相邻两趟排序向相反方向起泡）

2、约瑟夫环问题（Josephus问题）是指编号为1、2、…，n的n（n>0）个人按顺时针方向围坐成一圈，现从第s个人开始按顺时针方向报数，数到第m个人出列，然后从出列的下一个人重新开始报数，数到第m的人又出列，…，如此重复直到所有的人全部出列为止。现要求采用循环链表结构设计一个算法，模拟此过程。

#include<stdlib.h>

typedef int datatype;

typedef struct node

{datatype data;

struct node *next;

}listnode;

typedef listnode *linklist;

void jose(linklist head,int s,int m)

{linklist k1,pre,p;

int count=1;

pre=NULL;

k1=head; /*k1为报数的起点*/

while (count!=s) /*找初始报数起点*/

{pre=k1;

k1=k1->next;

count++;

}

while(k1->next!=k1) /*当循环链表中的结点个数大于1时*/

{ p=k1; /*从k1开始报数*/

count=1;

while (count!=m) /*连续数m个结点*/

{ pre=p;

p=p->next;

count++;

}

pre->next=p->next; /*输出该结点，并删除该结点*/

printf("%4d",p->data);

free(p);

k1=pre->next; /*新的报数起点*/

}

printf("%4d",k1->data); /*输出最后一个结点*/

free(k1);

}

main()

{linklist head,p,r;