从第s(sn)个人开始报数-数到m的人出圈;再由下一个人

1．约瑟夫问题：n个人围成一圈，从第s（sn）个人开始报数，数到m的人出圈；再由下一个人开始报数，数到m的人出圈；……。输出依次出圈的人的编号。m的值预先选定，n由键盘输入。分析：我们将这n个人组成一个链表，表中每一个元素为一记录类型，第一个域变量lvalue为人的编号，第二个域变量next指向下一个人，这样链接下去构成一个环形链。然后由lvalue值为s的记录开始，对链中的元素逐一记数，数到第m个记录时，将它删去，即把第（m-1）个记录的指针改成指向第（m+1）个记录，然后从第（m+1）个向下记数，这样重复进行下去，直到剩下一个记录。出列的人也组成一条链，r是其首指针，只要打印这条链就得到结果。源程序如下：#includeiostream.h#includestdio.h#includestdlib.h//使用malloc()函数的库函数#includemalloc.htypedefstructlinknode{intlvalue;structlinknode*next;}point;intmain(){intn,m,s,node,i;point*p,*q,*r;coutInputtotalnumber,initialnumberanddistance:;cinnsm;p=(point*)malloc(sizeof(point));q=p;for(i=1;i=n-1;i++){//生成链表q-lvalue=s;s=s%n+1;q-next=(point*)malloc(sizeof(point));q=q-next;}q-lvalue=s;q-next=p;//生成循环链表node=n;r=(point*)malloc(sizeof(point));q=r;while(node1){if(m==1){r-next=p;node=1;}else{for(i=1;i=m-2;i++)p=p-next;q-next=p-next;//将数到m的人出圈，链到出列人的链表中q=q-next;p-next=p-next-next;p=p-next;node--;}}for(i=1;i=n-1;i++){//依次打印出列人的序号r=r-next;coutTheithpersonisnumber:r-lvalueendl;}if(m==1)coutThelastoneisnumber:r-next-lvalueendl;elsecoutThelastoneisnumber:p-lvalueendl;return1;}2．设单链表中存放着n个字符，试设计算法判断字符串是否中心对称。例如xyzzyx和xyzyx都是中心对称的字符串。分析：先将链表的前半部分倒置与后半部分比较，再倒置（设无头节点）。源程序如下：#includeiostream.h#includestdio.h#includestdlib.h#includemalloc.htypedefstructlinknode{chardata;structlinknode*next;}point;intmain(){inti,n;point*f,*p,*q,*h,*s;coutInputthenumberofcharacterstring:;cinn;coutendlInputthecharacterstring:;p=(point*)malloc(sizeof(point));q=p;for(i=1;i=n-1;i++){cinq-data;q-next=(point*)malloc(sizeof(point));q=q-next;}cinq-data;q-next=NULL;f=p;//f为指向字符串单链表的头指针p=NULL;i=0;s=f;while(i(n/2)){//前半部分倒置q=s;s=s-next;q-next=p;p=q;i++;}if(n%2==1)q=s-next;//跳过中间点elseq=s;h=p;while((p!=NULL)&&(q!=NULL)&&(p-data==q-data)){//逐个比较元素值p=p-next;q=q-next;}if((p==NULL)&&(q==NULL))//得到判断结果coutYes!;elsecoutNo!;while(h!=NULL){//倒置回来，恢复原来的单链表q=h;h=h-next;q-next=s;s=q;}return1;}3．试设计一个民航公司的自动订票和退票系统的算法。设某个时刻的乘客之间的关系如下：序号datallinkrlink1Li652Chang493Wang57h→4Bai025Ma136Du817Xiu308Ding969Chen28分析：由题中乘客之间的关系可以看出，这是一个按乘客姓氏的字典顺序链接的静态双向链表，有表头节点。（1）自动订票实际上是在链表中插入节点，使其链表仍保持字典顺序；（2）自动退票系统实际上是在链表中删除一个节点。