北京理工大學數(shù)據(jù)結(jié)構(gòu)實驗1

1、北京理工大學數(shù)據(jù)結(jié)構(gòu)實驗11、采用單向環(huán)表實現(xiàn)約瑟夫環(huán)。請按以下要求編程實現(xiàn)： 從鍵盤輸入整數(shù) m,通過create函數(shù)生成一個具有 m個結(jié)點的單向環(huán)表。 環(huán)表中的結(jié)點編號依次為1, 2, ,m。從鍵盤輸入整數(shù)s (1<=s<=m)和n,從環(huán)表的第s個結(jié)點開始計數(shù)為1,當計數(shù)到第 n 個結(jié)點時， 輸出該第 n 結(jié)點對應的編號， 將該結(jié)點從環(huán)表中消除，從輸出結(jié)點的下一個結(jié)點開始重新計數(shù)到n,這樣，不斷進行計數(shù)，不斷進行輸出，直到輸出了這個環(huán)表的全部結(jié)點為止。例如，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、歸并順序表請按以下要求編程實現(xiàn)： 從鍵盤輸入兩個升序排列的整數(shù)序列l(wèi)inka和linkb ,每個序列以輸入0為結(jié) 束標記。 將鏈表linka和linkb歸并為linkc, linkc仍然為升序排列。歸并完成后，linka 和

5、linkb為空表。輸出linkc。 對linkc進行處理，保持升序不變，刪除其中重復的整數(shù)，對重復的整數(shù)只 保留一個，輸出刪除重復整數(shù)后的鏈表。例如：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