} Lnode,*LinkList;
LinkList Creat_LinkList1(int n ) { LinkList L=NULL;/*空表*/ Lnode *s,*r;
int x,y,i; /*设数据元素的类型为int*/ y=n%4+1;
s=malloc(sizeof(Lnode)); /*建立头结点*/ s->next=L; L=s;r=s;
for(i=1;i<=n;i++) {x=y*i-1;
s=malloc(sizeof(Lnode)); /*在尾部插入结点*/ s->data=x; s->next=NULL; r->next=s; s->prior=r; s->freq=0; r=s; }
return L; }
void printf_LinkList( LinkList L) /*输出链表L中各结点及频度*/ { Lnode * p=L->next; printf(\ while ( p!=NULL)
{ printf(\ p=p->next; }
return ; }
LinkList *Locata(LinkList A,int x) { LinkList p,q; int f,y;
p=A->next; /*指向链表头结点后的数据结点*/ while (p!=NULL && p->data!=x)
p=p->next; /*查找X结点*/
21
if(p->data==x)
{p->freq++; /*找到修改频度*/ f=p->freq; q=p->prior;
while(q!=A&&q->freq
return p; }
void main() { int n,m,i,x; LinkList A,p; n=14;m=11;
A=Creat_LinkList1(n ); printf_LinkList(A); printf(\ for(i=0;i<5;i++) {
scanf(\ p=Locata(A,x);
printf(\ printf_LinkList(A); } }
五 上机实习题目
22
1． Josephu 问题
Josephu 问题为：设编号为1，2，? n的n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m 的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。 提示：用一个不带头结点的循环链表来处理Josephu 问题：先构成一个有n个结点的单循环链表，然后由k结点起从1开始计数，计到m时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从1开始计数，直到最后一个结点从链表中删除算法结束。 2． 一元多项式的相加 提示：
（1） 一元多项式的表示问题：对于任意一元多项式：
12in
Pn(x)= P0+ P1X+ P2X+ ? + PiX+ ? + PnX
可以抽象为一个由“系数-指数”对构成的线性表，且线性表中各元素的指数项是递增的：
P=( ( P0,0), ( P1,1), ( P2,2), ? , ( Pn,n) ) (2 ) 用一个单链表表示上述线性表，结点结构为： typedef sturct node
coef exp next { float coef; /*系数域*/
int exp; /*指数域*/
struct node *next; /*指针域*/ } Ploy Node;
约瑟夫环问题
约瑟夫环问题：设编号为1，2，3，??，n的n(n>0)个人按顺时针方向围坐一圈，每个人持有一个正整数密码。开始时任选一个正整数做为报数上限m，从第一个人开始顺时针方向自1起顺序报数，报到m是停止报数，报m的人出列，将他的密码作为新的m值，从他的下一个人开始重新从1报数。如此下去，直到所有人全部出列为止。令n最大值取30。要求设计一个程序模拟此过程，求出出列编号序列。
源程序代码：（在Tubro C 2.0测试通过） #include
struct node {
int number; /* 人的序号 */ int cipher; /* 密码 */
23
struct node *next; /* 指向下一个节点的指针 */ };
struct node *CreatList(int num) /* 建立循环链表 */ {
int i;
struct node *ptr1,*head;
if((ptr1=(struct node *)malloc(sizeof(struct node)))==NULL) {
perror(\ return ptr1; }
head=ptr1;
ptr1->next=head; for(i=1;i if((ptr1->next=(struct node *)malloc(sizeof(struct node)))==NULL) { perror(\ ptr1->next=head; return head; } ptr1=ptr1->next; ptr1->next=head; } return head; } main() { int i,n=30,m; /* 人数n为30个 */ struct node *head,*ptr; randomize(); head=CreatList(n); for(i=1;i<=30;i++) { head->number=i; head->cipher=rand(); 24 head=head->next; } m=rand(); /* m取随机数 */ i=0; /* 因为我没办法删除head指向的节点，只会删除head的下一节点，所以只能从0数起。*/ while(head->next!=head) /* 当剩下最后一个人时，退出循环 */ { if(i==m) { ptr=head->next; /* ptr记录数到m的那个人的位置 */ printf(\ printf(\ m=ptr->cipher; /* 让m等于数到m的人的密码 */ head->next=ptr->next; /* 让ptr从链表中脱节，将前后两个节点连接起来 */ head=hea/d->next; /* head移向后一个节点 */ free(ptr); /* 释放ptr指向的内存 */ i=0; /* 将i重新置为0，从0再开始数 */ } else { head=head->next; i++; } } printf(\ printf(\ free(head); /* 让最后一个人也出列 */ } 25