《数据结构线性表》PPT课件

《《数据结构线性表》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章栈和队列3.1栈3.1.1栈的概念一、什么是栈栈是限定仅能在表尾一端进行插入、删除操作的线性表（a1,a2,...,ai-1,ai,ai+1,…,an）插入删除能进行插入和删除的一端称为栈顶，另一端称为栈底。称插入操作为进栈，删除操作为出栈。进栈出栈操作只能在栈顶进行。3.1栈出栈进栈栈的特点后进先出第一个进栈的元素在栈底最后一个进栈的元素在栈顶第一个出栈的元素为栈顶元素最后一个出栈的元素为栈底元素栈的示意图栈顶栈底ana2a13.1栈二、栈的基本操作1）初始化操作InitStack(&S)功能：构造一个空栈S。2）销毁栈操作DestroyStack(&S

2、)功能：销毁一个已存在的栈。3）置空栈操作ClearStack(&S)功能：将栈S置为空栈。4）取栈顶元素操作GetTop(S,&e)功能：取栈顶元素，并用e返回。3.1栈二、栈的基本操作5）进栈操作Push(&S,e)功能：元素e进栈。6）退栈操作Pop(&S,&e)功能：栈顶元素退栈，并用e返回。7）判空操作StackEmpty(S)功能：若栈S为空，则返回True，否则，栈不空返回False。3.1栈3.1.2栈的顺序存储和实现一、栈的顺序存储结构#defineSTACK_INIT_SIZE100//栈存储空间的初始分配量#defineSTACKINCRE

3、MENT10//空间的分配增量typedefstruct{ElemType*base;//栈空间基址ElemType*top;//栈顶指针intstacksize;//当前分配的栈空间大小}SqStack;3.1栈3.1.2栈的顺序存储和实现顺序栈的图示S.stacksizeS.topS.base10099nn-1n-210anan-1a2a1约定栈顶指针指向栈顶元素的下一个位置当栈用顺序结构存储时，栈的基本操作如建空栈、进栈、出栈等如何实现？？3.1栈3.1.2栈的顺序存储和实现topbasebasetopABCDE空栈basetopAA进栈BCDE进栈bas

4、etopABEDC出栈称为：栈满空栈top=base栈满top-base=stacksize(无可分配空间)12340ABCDE3.1栈不可扩充栈的操作top=012340栈空栈顶指针top，指向实际栈顶后的空位置，初值为basetop进栈A栈满BCDE设数组大小为Mtop=M，栈满，此时入栈，则上溢(overflow)toptoptoptoptoptoptoptoptoptop栈空top==base，栈空，此时出栈，则下溢(underflow)top12340出栈12340ABCDE3.1栈可扩充栈的操作栈顶指针top，指向实际栈顶后的下一个位置，初值为top

5、=basetop进栈A出栈栈当前空间不足，需扩充BCDE设栈的初始分配量为Stacksize=STACK_INIT_SIZE。若top==Stacksize，栈满，此时入栈，则需扩充栈空间，每次扩充STACK_INCREMENT；若无可利用的存储空间，则上溢(overflow)。toptoptoptoptoptoptoptoptoptop栈空若top==base,栈空，此时出栈，则下溢(underflow)base栈空topbasebasetop12340123403.1栈二、顺序栈基本操作的算法1）初始化操作InitStack(SqStack&S)参数：S是存

6、放栈的结构变量功能：建一个空栈SS.stacksizeS.topS.base10099nn-1n-2103.1栈初始化操作算法StatusInitStack(SqStack&S){//构造一个空栈SS.base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType));//为顺序栈动态分配存储空间if(!S.base)exit(OVERFLOW);//分配失败S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;}//InitStack99nn-1n-210anan-1a

7、2a1S.stacksizeS.topS.base2）销毁栈操作DestroyStack(SqStack&S)功能：销毁一个已存在的栈100null0null3.1栈StatusDetroyStack(SqStack&S){if(!S.base)returnERROR;//若栈未建立（尚未分配栈空间）free(S.base);//回收栈空间S.base=S.top=NULL;S.stacksize=0;returnOK;}//DetroyStack销毁操作算法3.1栈3）置空栈操作ClearStack(SqStack&S)功能：将栈S置为空栈S.stack

8、sizeS.topS.b