北京理工大学数据结构实验1

1、北京理工大学数据结构实验11、采用单向环表实现约瑟夫环。请按以下要求编程实现： 从键盘输入整数 m,通过create函数生成一个具有 m个结点的单向环表。 环表中的结点编号依次为1, 2, ,m。从键盘输入整数s (1<=s<=m)和n,从环表的第s个结点开始计数为1,当计数到第 n 个结点时， 输出该第 n 结点对应的编号， 将该结点从环表中消除，从输出结点的下一个结点开始重新计数到n,这样，不断进行计数，不断进行输出，直到输出了这个环表的全部结点为止。例如，m=10, s=3, n=4。则输出序列为：6, 10, 4, 9, 5, 2, 1, 3, 8, 7。#include&

2、lt;stdio.h>#include<malloc.h>#define ERROR 0typedef struct LNodeint num;struct LNode *next;LNode,*Linklist;void main()int m,s,n,i,j;Linklist head,p,q;printf("input m:n");scanf("%d",&m);printf("input s and n:n");scanf("%d %d",&s,&n);if(!(he

3、ad=(Linklist)malloc(sizeof(LNode) return ERROR;head->next=head;head->num=m;for(i=m-1;i>0;i-)p=(Linklist)malloc(sizeof(LNode);if(!p) return ERROR;p->next=head->next;p->num=i;head->next=p;p=head->next;while(p->next->num!=s) p=p->next;for(i=m;i>1;i-)for(j=1;j<n;j+

4、) p=p->next;q=p->next;p->next=q->next;printf("%d,",q->num);free(q);printf("%d 。 n",p->num);C;U$ersAdministratorDeskrop'www e»e | n '回起|2、归并顺序表请按以下要求编程实现： 从键盘输入两个升序排列的整数序列linka和linkb ,每个序列以输入0为结 束标记。 将链表linka和linkb归并为linkc, linkc仍然为升序排列。归并完成后，linka 和

5、linkb为空表。输出linkc。 对linkc进行处理，保持升序不变，删除其中重复的整数，对重复的整数只 保留一个，输出删除重复整数后的链表。例如：linka 输入为：10203040 500linkb 输入为：15202530 354045 50 0归并后的 linkc 为：10 15 20 20 25 30 30 35 40 40 4550 50删除重复后的 linkc 为： 10 15 20 25 30 35 40 45 50#include<stdio.h>#include<malloc.h>#define ERROR 0typedef struct LNod

6、eint data;struct LNode *next;LNode,*Linklist;Linklist MergeList(Linklist La,Linklist Lb)Linklist pa,pb,pc,Lc,q;pa=La->next;pb=Lb->next;Lc=(Linklist)malloc(sizeof(LNode);if(!Lc) return ERROR;Lc->next=NULL;pc=Lc;while(pa&&pb)q=(Linklist)malloc(sizeof(LNode); if(!q)return ERROR;if(pa-&

7、gt;data<=pb->data)q->data=pa->data; q->next=pc->next; pc->next=q; pc=q;pa=pa->next;elseq->data=pb->data; q->next=pc->next; pc->next=q; pc=q;pb=pb->next;while(pa)q=(Linklist)malloc(sizeof(LNode);if(!q)return ERROR; q->data=pa->data; q->next=pc->ne

8、xt; pc->next=q; pc=q;pa=pa->next;while(pb)q=(Linklist)malloc(sizeof(LNode);if(!q)return ERROR; q->data=pb->data; q->next=pc->next; pc->next=q; pc=q;pb=pb->next;free(La);free(Lb);return Lc;Linklist Creatlist(Linklist L)Linklist p,q;int i;L=(Linklist)malloc(sizeof(LNode);if(!L)

9、 return ERROR;L->next=NULL;p=L;scanf("%d",&i);while(i)q=(Linklist)malloc(sizeof(LNode);if(!q)return ERROR;q->data=i;q->next=p->next;p->next=q;p=q;scanf("%d",&i);return L;void Output(Linklist L)Linklist p=L->next;while(p->next)printf("%d ",p-

10、>data);p=p->next;printf("%dn",p->data);void Delete(Linklist L)Linklist p,q,r;p=L->next;q=L->next->next;while(q!=NULL) if(q->data=p->data)r=q;q=q->next;p->next=r->next;free(r);elsep=p->next;q=q->next;void main()Linklist La,Lb,Lc;printf("input linka:n");La=Creatlist(La);printf("input linkb:n");Lb=Creatlist(Lb);Lc=MergeList(La,Lb);printf("linkc:n");Output(Lc);Delete(Lc);printf("linkc':n");Output(Lc); C:UsersAdrrii ni5tratorDe5ktopv/ww.exeI input linka： 10 20 30 43 50 e input linkb：15 20 2