} 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->freqprior; /*查找频度不小于Y的结点*/ if(q->freq>=f||q==A) {q=q->next; /*交换两结点*/ y=p->data; p->data=q->data; p->freq=q->freq; q->data=y; q->freq=f; } }

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 #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