华农数据结构上机实验答案

数据结构上机答案1.1顺序线性表的基本操作#includestdio.h#includemalloc.h#defineOK1#defineERROR0#defineLIST_INIT_SIZE100#defineLISTINCREMENT10#defineElemTypeinttypedefstruct{int*elem,length,listsize;}SqList;intInitList_Sq(SqList&L){L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));L.length=0;L.listsize=LIST_INIT_SIZE;returnOK;}intLoad_Sq(SqList&L){inti;if(L.length==0)printf(TheListisempty!);else{printf(TheListis:);for(i=0;iL.length;i++)printf(%d,L.elem[i]);}printf(\n);returnOK;}intListInsert_Sq(SqList&L,inti,inte){if(i1||iL.length+1)returnERROR;ElemType*newbase,*q,*p;if(L.length=L.listsize){newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));L.elem=newbase;L.listsize+=LISTINCREMENT;}q=&(L.elem[i-1]);for(p=&(L.elem[L.length-1]);p=q;--p)*(p+1)=*p;*q=e;++L.length;returnOK;}intListDelete_Sq(SqList&L,inti,int&e){ElemType*q,*p;if(i1||iL.length)returnERROR;p=&(L.elem[i-1]);e=*p;q=L.elem+L.length-1;for(++p;p=q;p++)*(p-1)=*p;L.length--;returnOK;}intmain(){SqListT;inta,i;ElemTypee,x;if(InitList_Sq(T)){printf(ASequenceListHasCreated.\n);}while(1){printf(1:Insertelement\n2:Deleteelement\n3:Loadallelements\n0:Exit\nPleasechoose:\n);scanf(%d,&a);switch(a){case1:scanf(%d%d,&i,&x);if(!ListInsert_Sq(T,i,x))printf(InsertError!\n);elseprintf(TheElement%disSuccessfullyInserted!\n,x);break;case2:scanf(%d,&i);if(!ListDelete_Sq(T,i,e))printf(DeleteError!\n);elseprintf(TheElement%disSuccessfullyDeleted!\n,e);break;case3:Load_Sq(T);break;case0:return1;}}}1.2合并顺序表#includestdio.h#includemalloc.h#defineOK1#defineERROR0#defineLIST_INIT_SIZE100#defineLISTINCREMENT10#defineElemTypeinttypedefstruct{int*elem,length,listsize;}SqList;intInitList_Sq(SqList&L){L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));L.length=0;L.listsize=LIST_INIT_SIZE;returnOK;}intLoad_Sq(SqList&L){inti;for(i=0;iL.length;i++)printf(%d,L.elem[i]);printf(\n);returnOK;}intListLength(SqListL){returnL.length;}intGetElem(SqListL,inti,ElemType&e){e=L.elem[i-1];returnOK;}intListInsert_Sq(SqList&L,inti,inte){if(i1||iL.length+1)returnERROR;ElemType*p,*q,*newbase;if(L.listsize=L.length){newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));L.elem=newbase;L.listsize+=LISTINCREMENT;}q=&(L.elem[i-1]);for(p=&(L.elem[L.length-1]);p=q;p--)*(p+1)=*p;*q=e;L.length++;returnOK;}voidMergeList(SqListLa,SqListLb,SqList&Lc){inti,j,k,La_len,Lb_len,ai,bj;i=j=1;k=0;InitList_Sq(Lc);La_len=ListLength(La);Lb_len=ListLength(Lb);while((i=La_len)&&(j=Lb_len)){GetElem(La,i,ai);GetElem(Lb,j,bj);if(ai=bj){ListInsert_Sq(Lc,++k,ai);i++;}else{ListInsert_Sq(Lc,++k,bj);j++;}}while(i=La_len){GetElem(La,i++,ai);ListInsert_Sq(Lc,++k,ai);}while(j=Lb_len){GetElem(Lb,j++,bj);ListInsert_Sq(Lc,++k,bj);}Load_Sq(Lc);}intmain(){intan,bn,i,e;SqListLa,Lb,Lc;InitList_Sq(La);scanf(%d,&an);for(i=1;i=an;i++){scanf(%d,&e);ListInsert_Sq(La,i,e);}printf(ListA:);Load_Sq(La);InitList_Sq(Lb);scanf(%d,&bn);for(i=1;i=an;i++){scanf(%d,&e);ListInsert_Sq(Lb,i,e);}printf(ListB:);Load_Sq(Lb);printf(ListC:);MergeList(La,Lb,Lc);return0;}1.3顺序表逆置#includestdio.h#includemalloc.h#defineOK1#defineERROR0#defineLIST_INIT_SIZE100#defineLISTINCREMENT10#defineElemTypeinttypedefstruct{int*elem,length,listsize;}SqList;intInitList_Sq(SqList&L){L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L.elem){printf(NO1);returnERROR;}L.length=0;L.listsize=LIST_INIT_SIZE;returnOK;}intLoad_Sq(SqList&L){inti;if(!L.length){printf(ThisListisempty!\n);returnERROR;}else{for(i=0;iL.length;i++)printf(%d,L.elem[i]);}printf(\n);returnOK;}intListInsert_Sq(SqList&L,inti,inte){ElemType*newbase,*p,*q;if(L.length=L.listsize){newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));if(!newbase){printf(NO2);returnERROR;}L.elem=newbase;L.listsize+=LISTINCREMENT;}q=&(L.elem[i-1]);for(p=&(L.elem[L.length-1]);p=q;p--)*(p+1)=*p;*q=e;L.length++;returnOK;}intswap(SqList&L,intn){inti,j,temp;for(i=0,j=n-1;ji;i++,j--){temp=L.elem[i];L.elem[i]=L.elem[j];L.elem[j]=temp;}returnOK;}intmain(){SqListT;intn,i;ElemTypex;scanf(%d,&n);InitList_Sq(T);for(i=1;in+1;i++){scanf(%d,&x);ListInsert_Sq(T,i,x);}printf(TheListis:);Load_Sq(T);swap(T,n);printf(TheturnedListis:);Load_Sq(T);return0;}1.4链式线性表的基本操作#includestdio.h#includemalloc.h#defineERROR0#defineOK1#defineElemTypeinttypedefstructLNode{intdata;structLNode*next;}LNode,*LinkList;intCreateLink_L(LinkList&L,intn){LinkListp,q;inti;ElemTypee;L=(LinkList)malloc(sizeof(LNode));L-next=NULL;q=(LinkList)malloc(sizeof(LNode));q=L;for(i=0;in;i++){scanf(%d,&e);p=(LinkList)malloc(sizeof(LNode));p-data=e;p-next=q-next;q-next=p;q=q-next;}returnOK;}intLoadLink_L(LinkList&L){LinkListp=L-next;if(!p)printf(TheListisempty!);else{printf(TheLinkListis:);while(p){printf(%d,p-data);p=p-next;}}printf(\n);returnOK;}intLinkInsert_L(LinkList&L,inti,ElemTypee){LNode*p=L,*s;intj=0;while(p&&ji-1){p=p-next;j++;}if(!p||ji-1)returnERROR;s=(LinkList)malloc(sizeof(LNode));s-data=e;s-next=p-next;p-next=s;returnOK;}intLinkDelete_L(LinkList&L,inti,El