数据结构栈总结

数据结构第3章栈与队列总结栈顺序栈单链栈循环链栈双向链栈双向循环链栈数组结构体结构模型#defineMAXSIZE10typedefstruct{SEIemTypeStack[MAXSIZE];inttop;}SeqStack;typedefstruct{SElemType*base;〃在栈构造之前和销毁之后，base的值为NULLSElemType*top;〃栈顶指针intstacksize;//当前分配的存储空间，以元素为单位}SqStack;typedefstruct{SElemType*base;〃在栈构造之前和销毁之后，base的值为NULLSElemType*top;〃栈顶指针intstacksize;//当前分配的存储空间，以元素为单位}SqStack;structCirNode{intdata; 〃数据域structCirNode*next;〃指针域};typedefCirNode*CirLinkList;structDulNode{intdata;structDulNode*prior;structDulNode*next;};typedefDulNode*DulLinkList;冋双向链表

初始化voidInitStack(SeqStack&S)//构voidInitStack(SqStack&S)〃构StatusInitList_Cir(CirLinkListStatusStatus(Init)造一个空栈S造一个空栈S&L)〃构造一个空的头结点InitList_Dul(DulLinkList&L)InitList_Dul(DulLinkList&L){{{〃构造一个空的头结点//构造一个空的头结点S.top=-1;//top为下标if(!(S.base=(SElemType{{}*)malloc(STACK_INIT_SIZE*sizeoL=(CirLinkList)malloc(sizeof(CirL=(DulLinkList)malloc(sif(SElemType))))Node));L=(DulLinkList)malloc(sizeof(zeof(DulNode));exit(OVERFLOW);〃存储分if(!L)DulNode));if(!L)配失败returnERROR;if(!L)returnERROR;S.top=S.base;L->next=L;returnERROR;L->next=L;S.stacksize=STACK_INIreturnOK;L->next=L;L-〉prior=L-〉next;T_SIZE;}L->prior=NULL;returnOK;}returnOK;}}插入元StatusListInsert_Sq(SqListvoidPush(SqStackStatusStatus冋双向链表素&L,inti,ElemTypee)〃在顺序线&S,SElemTypee)//插入元素eListInser_Cir(CirLinkListListInser_Dul(DulLinkList性表L中第i个位置之前插入新为新的栈顶元素L,inti,inte)//在i处插入元L,inti,inte)//在i处插入的元素e{素e,算法-8兀素e,算法-8{//算法2.4if(S.top-S.base>=S.stacksize{{int*p,*q,*newbase;)〃栈满，追加存储空间intj=1;intj=1;if(i<1||i>L.length+1){CirLinkListp,q;DulLinkListp,q;returnERROR;〃值不合法S.base=(SElemTypeq=L;q=L;*)realloc(S.base,(S.stacksize+STif(i〈l||i〉(ListLength_Ciif(i〈l||i〉(ListLength_if(L.length>=L.listsize)ACK_INCREMENT*sizeof(SElemTr(L)+l))Dul(L)+1)){//当前存储空间已满，增ype)));returnERROR;returnERROR;加分配if(!S.base)while(j<i&&q)while(j<i&&q)newbase=(ElemType{{

*)realloc(L.elem,(L.listsize+LISTIexit(OVERFLOW);〃存储分q=q—>next;q=q—>next;NCREMENT)*sizeof(ElemType));配失j++;j++;if(!newbase)〃存储分配失S.top=S.base+S.stacksize;}}败S.stacksize+=STACK_INCREp=(CirLinkList)malloc(sip=(DulLinkList)malloc(exit(OVERFLOW);MENT;zeof(CirNode));sizeof(DulNode));L.elem=newbase;〃新基址}p—>data=e;p—>data=e;L.listsize+=LIST_INCREMEN*(S.top)++=e;p—>next=q—>next;p—>next=q—>next;T;//增加存储容量}q—>next=p;p—>prior=q;}returnOK;q—>next—>prior=p;q=L.elem+i-1;//q为插入位}q—>next=p;置returnOK;for(p=L.elem+L.length-1;p>}=q;--p) //插入位置及以后兀素右移*(p+1)=*p;*q=e;〃插入e++L.length;〃表长增1returnOK;}头插入无StatusInsFirst_Link(LinkListStatusStatus同法&L,LinkList&p) //头插入，算法InsFirst_Cir(CirLinkListInsFirst_Dul(DulLinkList-10&L,CirLinkList&p) //头插入，&L,DulLinkList&p){算法TO{p—>next二L—>next;{p—>next=L—>next;L-〉next=p;p—>next=L—>next;p—>prior=L;returnOK;L—>next=p;L—>next—>prior=p;

}returnOK;}L->next=p;returnOK;}尾插入无StatusInsLast_Link(LinkListStatusStatusStatus法&q,LinkList&p) //尾插入法InsLast_Cir(CirLinkListInsLast_Dul(DulLinkListInsLast_Dul(DulLinkList{&q,CirLinkList&p) //尾插入&q,DulLinkList&p) //尾插入&q,DulLinkList&p) //尾插入q->next=p;法法法q=p;{{{p-〉next=NULL;q->next=p;q->next=p;q->next=p;returnOK;q=p;p->prior=q;p->prior=q;}p->next=L;q=p;q=p;returnOK;p-〉next=NULL;p->next=L;}returnOK;}returnOK;}删除相Status ListDelete_Sq(SqListStatusListDelete_Link(LinkListStatusStatus同双向链表应序号&L,inti,ElemType&e)//在顺序L,inti,int&e)//删除第i个元素，ListDelete_Cir(CirLinkListListDelete_Dul(DulLinkList的结点线性表L中删除第i个兀素，并用e返回，算法-9L,inti,int&e)//删除第i个元L,inti,int&e)//删除第i个元并用e返回其值{素，并用e返回，算法-9素，并用e返回，算法-9{//算法2.5intj=1;{{int*p,*q;if(i〈l||i〉ListLength_Link(intj=1;intj=1;if(i<1||i>L.length)L))if(i〈l||i〉ListLength_Cirif(i〈l||i〉ListLength_LreturnERROR;//i值returnERROR;(L))ink(L))不合法while(j<i)returnERROR;returnERROR;

p=&(L.elem[i-1]);//p为被删除元素的位置{L=L->next;while(j<i){while(j<=i){e=*p;J++；L=L->next;L=L->next;q=L.elem+L.length-1;〃表}j++;j++;尾的位置LinkListp;}}for(++p;p<=q;++p)〃被删p=L->next;CirLinkListp;DulLinkListp,q;除元素之后的元素左移e=p->data;p=L->next;p=L->next;*(p-1)=*p;L->next=p->next;e=p->data;q=L->prior;--L.length;free(p);L->next=p->next;e=L->data;returnOK;returnOK;free(p);q->next=p;}}returnOK;p->prior=q;}free(L);returnOK;}求表的长度intListLength_Sq(SqListL)//返intListLength_Link(LinkListintintint回L中数据元素个数L)//得到表的长度ListLength_Cir(CirLinkListListLength_Dul(DulLinkListListLength_Dul(DulLinkList{{L)//得到表的长度L)//得到表的长度L)//得到表的长度returnL.length;inti=0;{{{}LinkListp;inti=0;inti=0;inti=0;p=L->next;CirLinkListp;DulLinkListp;DulLinkListp;while(p)p=L->next;p=L->next;p=L->next;{while(p!=L)while(p)while(p!=L)i++;{{{p=p->next;i++;i++;i++;}p=p->next;p=p->next;p=p->next;returni;}}}

}returni;}returni;}}returni;判断是StatusListEmpty_Sq(SqListL)//StatusListEmpty_Link(LinkListStatusStatusStatus否为空判断L表是否为空表L)//判断L表是否为空表ListEmpty_Cir(CirLinkListL)ListEmpty_Dul(DulLinkListL)ListEmpty_Dul(DulLinkListL)表{{//判断L表是否为空表//判断L表是否为空表//判断L表是否为空表if(L.length==O)if(L-〉next==NULL){{{returnTRUE;returnOK;if(L->next==L)if(L->next==L&&L-〉prioif(L->next==L&&L->prior=elsereturnERROR;returnOK;r=NULL)=L)returnFALSE;}returnERROR;returnOK;returnOK;}}returnERROR;}}returnERROR;得到序StatusGetElem_Sq(SqListL,intStatusGetElem_Link(LinkListStatusStatus同双向链表位的元i,ElemType&e)〃用e返回L中第L,inti,int&e)//得到表中第i个GetElem_Cir(CirLinkListL,intGetElem_Dul(DulLinkList素i个数据元素的值元素，算法-7i,int&e)//得到表中第i个元素，L,inti,int&e)//得到表中第{{算法-7i个元素，算法-7if(i<1||i>L.length)intj=1;{{returnERROR;if(i〈l||i〉ListLength_Link(intj=1;intj=1;e=*(L.elem+i-1);L))if(i〈l||i〉ListLength_Cirif(i〈l||i〉ListLength_DreturnOK;returnERROR;(L))ul(L))}LinkListp;returnERROR;returnERROR;p=L->next;CirLinkListp;DulLinkListp;while(j<i)p=L->next;p=L->next;

{p=p->next;j++；}e=p—>data;returnOK;}while(j〈i){p=p_>next;j++;}e=p_>data;returnOK;}while(j<i){p=p_>next;j++;}e=p_>data;returnOK;}得到相StatusElemType_Sq(SqListp,intStatusElemType_Link(LinkListStatusStatusStatus应指针&e)p,int&e)ElemType_Cir(CirLinkListElemType_Dul(DulLinkListElemType_Dul(DulLinkList指向位{{p,int&e)p,int&e)p,int&e)置的元e=*p;if(!p){{{素returnOK;returnERROR;if(!p)if(!p)if(!p)｝；e=p->data;returnERROR;returnERROR;returnERROR;returnOK;}e=p_>data;e=p_>data;e=p_>data;returnOK;}returnOK;}returnOK;}得到满intLocateElem_Sq(SqListintLocateElem_Link(LinkListintintint足条件L,ElemTypee,StatusL,intLocateElem_Cir(CirLinkListLocateElem_Dul(DulLinkListLocateElem_Dul(DulLinkList的元素(*compare)(int,int))〃返回L中e,Status(*compare)(int,int))//L,intL,intL,int的位置第一个与e满足compare()关系得到满足条件的e在表的第一次出e,Status(*compare)(int,int))/e,Status(*compare)(int,int)e,Status(*compare)(int,int))/的元素的位序，若无返回0现的位置/得到满足条件的e在表的第一次)//得到满足条件的e在表的第/得到满足条件的e在表的第一次{{出现的位置一次出现的位置出现的位置int*p;inti=1;{{{p=L.elem;//p的初值为第1LinkListp=L->next;inti=1;inti=1;inti=1;个元素的存储位置while(p&&!compare(p->data,CirLinkListp=L_>next;DulLinkListp=L_>next;DulLinkListp=L_>next;inti=1;//i的初值为第1个e))while(p&&!compare(p_>datwhile(p&&!compare(p_>dwhile(p!=L&&!compare(p_>元素的位序{a,e))ata,e))data,e))

while(i<=L.length&&!(*p=p->next;{{{compare)(*p++,e))i++；p=p->next;p=p->next;p=p->next;++I；}i++;i++;i++;if(i<=L.length)if(i>ListLength_Link(L))}}}returni;returnERROR;if(i>ListLength_Cir(L))if(i>ListLength_Dul(L)if(i>ListLength_Dul(L))elseelsereturnERROR;)returnERROR;return0;returni;elsereturnERROR;else}}returni;elsereturni;}returni;}}遍历表voidListTraverse_Sq(SqListvoidListTraverse_Link(LinkListvoidvoidvoidL,void(*vi)(int&))//依次对L的L,void(*vist)(LinkList))//遍历ListTraverse_Cir(CirLinkListListTraverse_Dul(DulLinkLisListTraverse_Dul(DulLinkList每个数据兀素调用函数vi(),链表L,void(*vist)(CirLinkList))tL,void(*vist)(DulLinkList))vi()的形参加&,表明可通过调{//遍历链表L,void(*vist)(DulLinkList))//遍历链表用vi()改变兀素的值LinkListp=L->next;{//遍历链表{{while(p)CirLinkListp=L->next;{DulLinkListp=L->next;int*p;{while(p!=L)DulLinkListp=L->next;while(p!=L)inti;vist(p);{while(p){p=L.elem;p=p->next;vist(p);{vist(p);for(i=1;i<=L」ength;i++)}p=p->next;vist(p);p=p->next;vi(*p++);}}p=p->next;}}printf("\n");}}}}

得到相StatusPriorElem_Sq(SqListL,intStatusPriorElem_Link(LinkListStatusStatusStatus应兀素的前驱cur_e,ElemType&per_e)〃若L,intcure_e,int&pre_e)//得到PriorElem_Cir(CirLinkListPriorElem_Dul(DulLinkListPriorElem_Dul(DulLinkListL中存在cur_e且不是第一个，cure_e的前驱L,intcure_e,int&pre_e)//得到L,intcure_e,int&pre_e)//得L,intcure_e,int&pre_e)//得到则直接用per_e返回它的前驱{cure_e的前驱到cure_e的前驱cure_e的前驱{LinkListp;{{{int*p=L.elem;P=L;CirLinkListp;DulLinkListp;DulLinkListp;inti=1;while(p->next->data!二cure_P=L;p=L;p=L;while(*p!=cur_e&&i<=L.lee&&p->next)while(p->next->data!=curwhile(p->next->data!=cwhile(p->next->data!=curngth){e_e&&p->next!=L)ure_e&&p->next!=L&&p->next!e_e&&p->next!=L){p=p->next;{=NULL){p++;}p=p->next;{p=p->next;i++;if(p==L||!p->next)}p=p->next;}}returnERROR;if(p==L||p->next==L)}if(p==L||p->next==L)if(i==1)pre_e=p->data;returnERROR;if(p==L||p->next==L||preturnERROR;returnERROR;returnOK;pre_e=p->data;->next=NULL)pre_e=p->data;per_e=*(--p);}returnOK;returnERROR;returnOK;returnOK;}pre_e=p->data;}}returnOK;}得到相StatusNextElem_Sq(SqListL,intStatusNextElem_Link(LinkList应兀素cur_e,int&next_e)〃若L中存L,intcur_e,int&next_e)//得到的后继在cur_e且不是最后一个，则直cure_e的后继接用next_e返回它的后继{{LinkListp;int*p=L.elem;p=L->next;inti=1;while(p->data!=cure&&p)

while(*p!=cur_e&&i<=L」ength)p++；i++；if(i==L.length)returnERROR;next_e=*(++p);returnOK;{p=p_>next;if(!p||!p-〉next)returnERROR;next_e=p_〉next_〉data;returnOK;归并算法调用函数实现StatusMergeList_Sq(SqListLa,SqListLb,SqList&Lc)〃La,Lb为非递减排列，合并得到Lc也为非递减排列，算法2.2InitList(Lc);inti,j,k;i=j=1;k=0;intai,bi;while((i<=La.length)&&(j<=Lb.length))GetElem(La,i,ai);GetElem(Lb,j,bi);

if(ai<=bi)Listlnsert(Lc,++k,ai);i++；else_;j++;while(i<=La.length)GetElem(La,i,ai);ListInsert(Lc,++k,ai);i++；while(j<=Lb.length)GetElem(Lb,j,bi);ListInsert(Lc,++k,bi);j++;

returnOK;}归并算法指针实现StatusListMarge_Point_Sq(SqListLa,SqListLb,SqList&Lc)〃归并函数，指针模式，算法2-6{int*pa,*pb,*pc;pa=La.elem;pb=Lb.elem;Lc.listsize=Lc.length=La.length+Lb.length;pc=Lc.elem=(int*)malloc(Lc.listsize*sizeof(int));while(pa<=(La.elem+La.length-1)&&pb<=(Lb.elem+Lb.length-1)){if(*pa<*pb){*pc=*pa;pc++;StatusMergeList_Link(LinkList&La,LinkList&Lb,LinkList&Lc)//归并算法，算法2-11；{LinkListpa,pb,pc;pa二La—>next;pb=Lb->next;pc=Lc=La;while(pa&&pb){if(pa->data〈pb->data){pc—>next=pa;pc二pa;pa=pa—>next;}else{pc—>next=pb;pc二pb;StatusMergeList_Cir(CirLinkList&La,CirLinkList&Lb,CirLinkList&Lc){CirLinkListpa,pb,pc;pa=La—>next;pb=Lb—>next;pc=Lc=La;while(pa&&pb){if(pa—>data<pb—>data){pc—>next=pa;pc二pa;pa=pa—>next;}else{

pa++;else*pc=*pb;pc++;pb++;while(pa<=(La.elem+La.length-1))*pc=*pa;pc++;pa++;while(pb<=(Lb.elem+Lb.length-1))*pc=*pb;pc++;pb++;returnOK;pb=pb->next;二)pc->next=pa;elsepc->next=pb;free(Lb);returnOK;pc->next=pb;pc=pb;pb=pb->next;i.)pc->next二pa;elsepc->next=pb;while(pb->next!Lb)pb=pb->next;pb->next=Lc;}free(Lb);returnOK;

清空表voidClearList_Sq(SqList&L)//StatusCrearList_Link(LinkListStatusSta