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

1、采用單向環(huán)表實(shí)現(xiàn)約瑟夫環(huán)請按以下要求編程實(shí)現(xiàn)：①從鍵盤輸入整數(shù)m，通過create函數(shù)生成一個具有m個結(jié)點(diǎn)的單向環(huán)表。環(huán)表中的結(jié)點(diǎn)編號依次為1,2,,m。②從鍵盤輸入整數(shù)s(1<=s<=m)和n,從環(huán)表的第s個結(jié)點(diǎn)開始計(jì)數(shù)為1,當(dāng)計(jì)數(shù)到第n個結(jié)點(diǎn)時(shí),輸出該第n結(jié)點(diǎn)對應(yīng)的編號,將該結(jié)點(diǎn)從環(huán)表中消除,從輸出結(jié)點(diǎn)的下一個結(jié)點(diǎn)開始重新計(jì)數(shù)到n，這樣，不斷進(jìn)行計(jì)數(shù)，不斷進(jìn)行輸出,直到輸出了這個環(huán)表的全部結(jié)點(diǎn)為止。例如，m=10,s=3,n=4。則輸出序列為：6，10，4,9,5,2,1,3,8,7。#include<stdio.h>#include<malloc.h>#defineERROR0typedefstructLNode{intnum;structLNode*next;}LNode,*Linklist;voidmain(){intm,s,n,i,j;Linklisthead,p,q;printf("inputm:\n");scanf("%d",&m);printf("inputsandn:\n");scanf("%d%d",&s,&n);if(!(head=(Linklist)malloc(sizeof(LNode))))returnERROR;head->next=head;head->num=m;for(i=m-1;i>0;i--){p=(Linklist)malloc(sizeof(LNode));if(!p)returnERROR;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++)p=p->next;q=p->next;p->next=q->next;printf("%d,",q->num);free(q);}printf("%d。\n",p->num);}2、歸并順序表請按以下要求編程實(shí)現(xiàn)：①從鍵盤輸入兩個升序排列的整數(shù)序列l(wèi)inka和linkb,每個序列以輸入0為結(jié)束標(biāo)記。②將鏈表linka和linkb歸并為linkc，linkc仍然為升序排列。歸并完成后，linka和linkb為空表。輸出linkc。③對linkc進(jìn)行處理，保持升序不變，刪除其中重復(fù)的整數(shù)，對重復(fù)的整數(shù)只保留一個，輸出刪除重復(fù)整數(shù)后的鏈表。例如：linka輸入為：10203040500linkb輸入為：15202530354045500歸并后的linkc為：10152020253030354040455050刪除重復(fù)后的linkc為：101520253035404550#include<stdio.h>#include<malloc.h>#defineERROR0typedefstructLNode{intdata;structLNode*next;}LNode,*Linklist;LinklistMergeList(LinklistLa,LinklistLb){Linklistpa,pb,pc,Lc,q;pa=La->next;pb=Lb->next;Lc=(Linklist)malloc(sizeof(LNode));if(!Lc)returnERROR;Lc->next=NULL;pc=Lc;while(pa&&pb){q=(Linklist)malloc(sizeof(LNode));if(!q)returnERROR;if(pa->data<=pb->data){q->data=pa->data;q->next=pc->next;pc->next=q;pc=q;pa=pa->next;}else{q->data=pb->data;q->next=pc->next;pc->next=q;pc=q;pb=pb->next;}}while(pa){q=(Linklist)malloc(sizeof(LNode));if(!q)returnERROR;q->data=pa->data;q->next=pc->next;pc->next=q;pc=q;pa=pa->next;}while(pb){q=(Linklist)malloc(sizeof(LNode));if(!q)returnq->next=pc->next;pc->next=q;pc=q;pb=pb->next;}ERROR;q->data=pb->data;free(La);free(Lb);returnLc;}LinklistCreatlist(LinklistL){Linklistp,q;inti;L=(Linklist)malloc(sizeof(LNode));if(!L)returnERROR;L->next=NULL;p=L;scanf("%d",&i);while(i){q=(Linklist)malloc(sizeof(LNode));if(!q)returnERROR;q->data=i;q->next=p->next;p->next=q;p=q;scanf("%d",&i);}returnL;}voidOutput(LinklistL){Linklistp=L->next;while(p->next){printf("%d",p->data);p=p->next;}printf("%d\n",p->data);}voidDelete(LinklistL){Linklistp,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);}else{p=p->next;q=q->next;}}}voidmain(){LinklistLa,Lb,Lc;printf("inputlinka:\n");La=Creatlist(La);p