《数据结构与算法》第二章上机实习题目

第二章上机实习题目

1、试用C语言编写一个高效算法，将一循环单链表就地逆置2A Josephu问题Josephu问题为设编号为I,2,…n的n个人围坐一圈，约定编号为k1=k=n的人从1开始报数，数到m的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列提示用一个不带头结点的循环链表来处理Josephu问题先构成一个有n个结点的单循环链表，然后由k结点起从1开始计数，计到m时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从I开始计数，直到最后一个结点从链表中删除算法结束

3、一元多项式的相加提示1一元多项式的表示问题对于任意一元多项式P x=P+PiX+P X2+...+PiXM-...+P Xnno2n可以抽象为一个由“系数-指数”对构成的线性表，且线性表中各元素的指数项是递增的P=Po,O,P,2,...,P„,n22用一个单链表表示上述线性表，结点结构为:ypedefsiurct node—{float coef;产系数域号coef expnextintexp;/*指数域*/struct node*next;/*指针域*/}PloyNode;约瑟夫环问题约瑟夫环问题设编号为1,2,3,,n的nn0个人按顺时针方向围坐一圈，每个人持有一个正整数密码开始时任选一个正整数做为报数上限m,从第一个人开始顺时针方向自1起顺序报数，报到m是停止报数，报m的人出列，将他的密码作为新的m值，从他的下一个人开始重新从1报数如此下去，直到所有人全部出列为止令n最大值取30要求设计一个程序模拟此过程，求出出列编号序列源程序代码在Tubro C

2.0测试通过#include stdlib.h#includealloc.hstruct nodeintnumber;/*人的序号*/intcipher;/*密码*/struct node*next;/*指向下一个节点的指针*/;struct node*CreatListint num/*建立循环链表*/{inti;struct node*plrl,*head;ifptrl=strucl node*mallocsizeofstruct node==NULL perrormalloc;return ptrl;head=pir1;ptrl-next=head;fbri=l;inum;i++ifptr I-next=struct node*mallocsizeofstruct node=NULL pcrrormalloc;ptrl-nexl=head;return head;ptrl=ptrl-next;ptrl-ncxt=hcad;Ireturn head:1main{inti,n=30,m;/*人数n为3个*/struct node*head,*ptr;randomize;head=CrealListn;fori=l:i=30:i++head-number=i;hcad-ciphcr=rand;head=head-next;}m=rand;/*m取随机数*/i=0;/*因为我没办法删除head指向的节点，只会删除head的下一节点，所以只能从0数起*/whilehead-next!=head/*当剩下最后一个人时，退出循环*/ifi==m{plr=head-next;/*ptr记录数到m的那个人的位置*/printfnumbcr:%d\n,ptr-number;printfciphe二％d\n”,pir-cipher;ni=ptr-cipher;/*iE m等于数到m的人的密码*/head-next=ptr-nexl;/*让ptr从链表中脱节，将前后两个节点连接起来*/head=head-next;/*head移向后一个节点*/freeptr;/*释放ptr指向的内存*/i=0;/*将i重新置为0,从0再开始数*/elsehead=head-next;i++；printfnumbcr:%d\n,hcad-numbcr;printfcipher:%d\n,head-cipher;freehead;/*让最后■个人也出列*/。