2015年山西省数据统计基础

2、设指针变量p指向双向链表中结点A，指针变量q指向被插入结点B，要求给出在结点A的后面插入结点B的操作序列（设双向链表中结点的两个指针域分别为llink和rlink）。 3、约瑟夫环问题（Josephus问题）是指编号为1、2、…，n的n（n>0）个人按顺时针方向围坐成一圈，现从第s个人开始按顺时针方向报数，数到第m个人出列，然后从出列的下一个人重新开始报数，数到第m的人又出列，…，如此重复直到所有的人全部出列为止。现要求采用循环链表结构设计一个算法，模拟此过程。 #include 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\ free(p);

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

printf(\"%4d\输出最后一个结点*/ free(k1); }

main()

{linklist head,p,r; int n,s,m,i;

printf(\"n=\"); scanf(\"%d\ printf(\"s=\"); scanf(\"%d\ printf(\"m=\ scanf(\"%d\

if (n<1) printf(\"n<0\"); else {/*建表*/

head=(linklist)malloc(sizeof(listnode)); /*建第一个结点*/ head->data=n; r=head;

for (i=n-1;i>0;i--) /*建立剩余n-1个结点*/ { p=(linklist)malloc(sizeof(listnode)); p->data=i; p->next=head; head=p; }

r->next=head; /*生成循环链表*/ jose(head,s,m); /*调用函数*/ } }