数据结构 期末机考 参考资料

returnOK;ElemTypecur_e,ElemType*pre_e){ElemTypee){

9inti=2;ElemType*newbase,*q,*p;

《数据结构》的全)

部代码实现(C语言StatusListEmpty(SqListL){ElemType*p=L.elem+1;if(i<1||i>(*L).length+

第二章线性表、链表if(L.length==0)while(i<=L.length&&*p!=1)

线性表的动态分配顺序存储结构returnTRUE;cur_e){returnERROR;

#defineLIST_INIT__SIZE10elseP++；if((*L).length>=

#defineLISTINCREMENT2returnFALSE;i++；(*L).listsize){

typedefstruct{})newbase=(ElemType

ElemType*elem;intListLength(SqListL){if(i>L.length)*)realloc((*L).elem,

intlength;returnL.length;returnINFEASIBLE;((*L).listsize+LISTINCREMENT)*

intlistsize;)else{sizeof(ElemType));

}SqList;StatusGetElem(SqListL,inti,*pre_e=*--p;if(!newbase)

顺序表示的线性表的基本操作(12个)ElemType*e){returnOK;exit(OVERFLOW);

StatusInitList(SqList*L){if(i<1||i>L.length))(*L).elem=newbase;

(*L).elem=(ElemTypeexit(ERROR);}(*L).listsize+=

*)malloc(LIST_INIT_SIZE**e=*(L.elem+i-1);StatusNextElem(SqListL,LISTINCREMENT；

sizeof(ElemType));returnOK;ElemTypecur_e,ElemType*next_e))

if(!(*L).elem)){q=(*L).elem+i-1;

exit(OVERFLOW);intLocateElem(SqListL,ElemTypeinti=1;for(p=(*L).elem+

(*L).length=0;e,Status(*compare)(ElemTypeJElemType*p=L.elem;(*L).length-1;p>=q;--p)

(*L).listsize=ElemType)){while(i<L.length&&*p!=*(p+1)=*p;

LIST_INIT_SIZE;ElemType*p;cur_e){*q=e;

returnOK;inti=1;i++；++(*L).length;

)p=L.elem;P++；returnOK;

StatusDestroyList(SqList*L){while(i<=L.length)}

free((*L).elem);&&!compare(*p++Je))if(i==L.length)StatusListDelete(SqList*L,inti,

(*L).elem=NULL;++i；returnINFEASIBLE;ElemType*e){

(*L).length=0;if(i<=L.length)else{ElemType*p,*q;

(*L).listsize=0;returni;*next_e=*++p;if(i<1||i>(*L).length)

returnOK;elsereturnOK;returnERROR;

)return0;}p=(*L).elem+i-1;

StatusClearList(SqList*L){}}*e=*pj

(*L).length=0;StatusPriorElem(SqListL,StatusListlnsert(SqList*L,inti,q=(*L).elem+(*L).length-

1;LinkListq;}if(q->data==cur_e){

for(++p;p<=q;++p)while(*L){StatusGetElem(LinkListL,inti,*pre_e=p->data;

*(p-1)=*p;q=(*L)->next;ElemType*e){returnOK;

(*L).length--;free(*L);intj=1;)

returnOK;*L=q;LinkListp=L->next;p=q;

})while(p&&j<i){)

StatusListTraverse(SqListL,returnOK;p=p->next;returnINFEASIBLE;

void(*vi)(ElemType*)){}j++；)

ElemType*p;StatusClearList(LinkListL){}StatusNextElem(LinkListL,

inti;LinkListp,q;if(!p||j>i)ElemTypecur_e,ElemType*next__e)

p=L.elem;p=L->next;returnERROR;{

for(i=1;i<=L.length;i++)while(p){*e=p->data;LinkListp=L->next;

vi(p++)；q=p->next;returnOK;while(p->next){

printf("\n");free(p);)if(p->data==cur__e){

returnOK;p=q;intLocateElem(LinkListL,*next_e=

)}ElemTypee,p->next->data;

线性表的单链表存储结构L->next=NULL;Status(*compare)(ElemType.,returnOK;

structLNode{returnOK;ElemType)){}

ElemTypedata;}inti=0;p=p->next;

structLNode*next;StatusListEmpty(LinkListL){LinkListp=L->next;)

}；if(L->next)while(p){returnINFEASIBLE;

typedefstructLNode*LinkList;returnFALSE;i++；}

单链表线性表的基本操作(12个)elseif(compare(p->datae))StatusListlnsert(LinkListL,int

StatusInitList(LinkList*L){returnTRUE;returni;ElemTypee){

*L=}p=p->next;intj=0;

(LinkList)malloc(sizeof(structintListLength(LinkListL){)LinkListp=L,s;

LNode));inti=0;return0;while(p&&j<i-1){

if(!*L)LinkListp=L->next;}p=p->next;

exit(OVERFLOW);while(p){StatusPriorElem(LinkListL,j++;

(*L)->next=NULL;i++；ElemTypecur_e,ElemType*pre_e){)

returnOK;p=p->next;LinkListq,p=L->next;if(!p||j>i-1)

}}while(p->next){returnERROR;

StatusDestroyList(LinkList*L){returni;q=p->next;s=

(LinkList)malloc(sizeof(struct)if(!*L)else

LNode));线性表的静态单链表存储结构exit(OVERFLOW);returnFALSE;

s->data=e;#defineMAXSIZE100(*L)->next=*L;}

s->next=p->next;typedefstruct{returnOK;intListLength_CL(LinkListL){

p->next=s;ElemTypedata;}inti=0;

returnOK;intcur;StatusDestroyList_CL(LinkList*L)LinkListp=L->next;

)}component,SLinkList[MAXSIZE];{while(p!=L){

StatusListDelete(LinkListL,int实现算法2.15、2.16的程序(3个)LinkListq,p=(*L)->next;i++；

i,ElemType*e){intMalloc(SLinkListspace){while(p!=*L){p=p->next;

intj=0;inti=space[0].cur;q=p->next;}

LinkListp=L,q;讦⑴free(p);returni;

while(p->next&&j<i-1){space[0].cur=P=q;)

p=p->next;space[i].cur;}StatusGetElem_CL(LinkListL,int

j++；returni;free(*L);i,ElemType*e){

}}*L=NULL;intj=1;

if(!p->next||j>i-1)voidFree(SLinkListspace,intk)returnOK;LinkListp=L->next->next;

returnERROR;{}if(i<=0||i>

q=p->next;space[k].cur=space[0].cur;StatusClearList_CL(LinkList*L)ListLength_CL(L))

p->next=q->next;space[0].cur=k;{returnERROR;

*e=q->data;}LinkListp,q;while(j<i){

free(q);voidDestroyList(){*L=(*L)->next;p=p->next;

returnOK;)p=(*L)->next;j++；

)线性表的双向链表存储结构while(p!=*L){}

StatusListTraverse(LinkListL,typedefstructDuLNode{q=p->next;*e=p->data;

void(*vi)(ElemType))ElemTypedata;free(p);returnOK;

(structDuLNode*prior^*next;p=q;}

LinkListp=L->next;}DuLNode,*DuLinkList;)intLocateElem_CL(LinkListL,

while(p){设立尾指针的单循环链表的12个基本操(*L)->next=*L;ElemTypee,

vi(p->data);作returnOK;Status(*compare)(ElemType,

p=p->next;StatusInitList_CL(LinkList*L){}ElemType)){

}*L=StatusListEmpty_CL(LinkListL){inti=0;

printf("\n");(LinkList)malloc(sizeof(structif(L->next==L)LinkListp=L->next->next;

returnOK;LNode));returnTRUE;while(p!=L->next){

i++；returnFALSE;DuLinkListq,p=(*L)->next;

if(compare(p->dataje)))q=p->next;while(p!=*L){

returni;StatusListInsert_CL(LinkList*Lp->next=q->next;q=p->next;

p=p->next;inti,ElemTypee){*e=q->data;free(p);

}LinkListp=(*L)->next,s;if(*L==q)p=q;

return0;intj=0;*L=p；)

}if(i<=0||i>free(q);free(*L);

StatusPriorElem__CL(LinkListL,ListLength_CL(*L)+1)returnOK;*L=NULL;

ElemTypecur_e,ElemType*pre_e){returnERROR;}returnOK;

LinkListq,p二L->next->next;while(j<i-1){StatusListTraverse_CL(LinkListL,)

q=p->next;p=p->next;void(*vi)(ElemType)){StatusClearList(DuLinkListL){

while(q!=L->next){j++；LinkListp=L->next->next;DuLinkListq,p=L->next;

if(q->data==cur_e){}while(p!=L->next){while(p!=L){

*pre__e=p->data;s=vi(p->data);q=p->next;

returnTRUE;(LinkList)malloc(sizeof(structp=p->next;free(p);

}LNode));)p=q;

p=q;s->data=e;printf("\n");)

q=q->next;s->next=p->next;returnOK;L->next=L->prior=L;

)p->next=s;)returnOK;

returnFALSE;if(p==*L)双链循环线性表的基本操作(14个))

)*L=s；StatusInitList(DuLinkList*L){StatusListEmpty(DuLinkListL){

StatusNextElem_CL(LinkListL,returnOK;*L=if(L->next==L&&L->prior==

ElemTypecur_e,ElemType*next_e)}(DuLinkList)malloc(sizeof(DuLNodL)

(StatusListDelete_CL(LinkList*Le))；returnTRUE;

LinkListp=L->next->next;inti,ElemType*e){if(*L){else

while(p!=L){LinkListp=(*L)->next,q;(*L)->next=(*L)->prior=returnFALSE;

if(p->data==cur_e){intj=0;*L;}

*next_e=if(i<=0||i>returnOK;intListLength(DuLinkListL){

p->next->data;ListLength_CL(*L))}elseinti=0;

returnTRUE;returnERROR;returnOVERFLOW;DuLinkListp=L->next;

}while(j<i-1){}while(p!=L){

p=p->next;p=p->next;StatusDestroyList(DuLinkList*L)i++；

}j++；p=p->next;

}while(p!=L){inti,ElemTypee){}

returni;if(p->data==cur_e){DuLinkListp,s;voidListTraverse(DuLinkListL,

)*pre_e=if(i<1||i>ListLength(L)void(*visit)(ElemType)){

StatusGetElem(DuLinkListL,inti,p->prior->data;+1)DuLinkListp=L->next;

ElemType*e){returnTRUE;returnERROR;while(p!=L){

intj=1;)p=GetElemP(L,i-1);visit(p->data);

DuLinkListp=L->next;p=p->next;if(!p)p=p->next;

while(p!=L&&j<i){)returnERROR;)

p=p->next;returnFALSE;s=printf("\n");

j++;)(DuLinkList)malloc(sizeof(DuLNod}

)StatusNextElem(DuLinkListL,e))；voidListTraverseBack(DuLinkList

if(p==L||j>i)ElemTypecur_e,ElemType*next_e)if(!s)L,void(*visit)(ElemType)){

returnERROR;(returnOVERFLOW;DuLinkListp=L->prior;

*e=p->data;DuLinkListp=L->next->next;s->data=e;while(p!=L){

returnOK;while(p!=L){s->prior=p;visit(p->data);

}if(p->prior->data==s->next=p->next;p=p->prior;

intLocateElem(DuLinkListL,cur_e){p->next->prior=s;}

ElemTypee,*next__e=p->data;p->next=s;printf("\n");

Status(*compare)(ElemType,returnTRUE;returnOK;}

ElemType)){)}带头结点的线性链表类型

inti=0;p=p->next;StatusListDelete(DuLinkListL,typedefstructLNode{

DuLinkListp=L->next;}inti,ElemType*e){ElemTypedata;

while(p!=L){returnFALSE;DuLinkListp;structLNode*next;

i++；)if(i<1||i>ListLength(L))}LNode,*Link,"Position;

if(compare(p->dataje))DuLinkListGetElemP(DuLinkListL,returnERROR;typedefstructLinkList{

returni;inti){p=GetElemP(L,i);Linkhead,tail;

p=p->next;intj;if(1p)intlen;

}DuLinkListp=L;returnERROR;}LinkList;

return0;for(j=1;j<=i;j++)*e=p->data;具有实用意义的线性链表的24个基本操

}p=p->next;p->prior->next=p->next;作

StatusPriorElem(DuLinkListL,returnp;p->next->prior=p->prior;StatusMakeNode(Link*p,ElemType

ElemTypecur_e,ElemType*pre_e){)free(p);e){

DuLinkListp=L->next->next;StatusListinsent(DuLinkListL,returnOK;*p=

(Link)malloc(sizeof(LNode));(*L).tail=(*L).head;StatusAppend(LinkList*L,Links)*q=(*L).tail;

if(!*p)(*L).len=0;{p->next=NULL;

returnERROR;}inti=1;(*L).tail=p;

(*p)->data=e;returnOK;(*L)•tail->next=s;(*L).len--;

returnOK;}while(s->next){returnOK;

}StatusDestroyList(LinkList*L){s=s->next;}

voidFreeNode(Link*p){ClearList(L);i++；StatusInsBefore(LinkList*L,

free(*p);FreeNode(&(*L).head);)Link*p,Links){

*p=NULL;(*L).tail=NULL;(*L).tail=s;Linkq;

)(*L).len=0;(*L).len+=i;q=RriorPos(*Lj*p);

StatusInitList(LinkList*L){returnOK;returnOK;if(!q)

Linkp;))q=(*L).head;

P=StatusInsFirst(LinkList*L,LinkPositionPriorPos(LinkListL,s->next=*p;

(Link)malloc(sizeof(LNode));h.Links){Linkp){q->next=s;

if(P){s->next=h->next;Linkq;*p=s;