资源描述：
《数据结构与算法——链表与栈资料教学文案.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数据结构与算法——链表与栈资料3.1栈3.2栈的应用举例3.3队列3.1栈3.1.1抽象数据类型栈的定义3.1.2栈的表示和实现3.1.1抽象数据类型栈的定义栈的定义栈(Stack)是一种特殊的线性表，其插入和删除操作均在表的一端进行，是一种运算受限的线性表。栈顶(top)是栈中允许插入和删除的一端。栈底(bottom)是栈顶的另一端。栈的术语栈的特点栈的示意图后进先出(LastInFirstOut，简称LIFO)。又称栈为后进先出表(简称LIFO结构)。an……a2a1栈底栈顶入栈出栈3.1.1抽象数据类型栈的定义ADTStack
2、{数据对象：数据关系：抽象数据类型栈基本操作：}ADTStackR1＝{
3、ai-1,ai∈D,i=2,...,n}约定an端为栈顶，a1端为栈底。D＝{ai
4、ai∈ElemSet,i=1,2,...,n,n≥0}见下页3.1.1抽象数据类型栈的定义InitStack(&S)//初始化栈DestroyStack(&S)//销毁栈ClearStack(&S)//清空栈StackEmpty(S)//判栈空StackLength(S)//求栈长度GetTop(S,&e)//取栈顶元素Push(&S,e)//入栈Pop(&S
5、,&e)//出栈StackTravers(S,visit())//遍历栈栈的基本操作3.1.1抽象数据类型栈的定义3.1栈3.1.1抽象数据类型栈的定义3.1.2栈的表示和实现3.1.2栈的表示和实现//-----栈的顺序存储表示-----#defineSTACK_INIT_SIZE100;//存储空间初始分配量#defineSTACKINCREMENT10;//存储空间分配增量typedefstruct{SElemType*base;//栈底指针SElemType*top;//栈顶指针intstacksize;//当前可使用最大容
6、量}SqStack;SqStackS;顺序栈的C语言实现3.1.2栈的表示和实现栈初始化过程演示(1)给栈S申请栈空间(2)设置基地址S.base和栈顶地址S.topS.topS.base(3)设置栈容量S.stacksize=STACK_INIT_SIZEStatusInitStack(SqStack&S){//构造一个空栈SS.base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType));if(!S.base)exit(OVERFLOW);//存储分配失败S.top=S.bas
7、e;S.stacksize=STACK_INIT_SIZE;returnOK;}3.1.2栈的表示和实现栈初始化算法3.1.2栈的表示和实现入栈操作演示(1)如果栈满，给栈增加容量abcdef(2)将数据存入栈顶位置，栈顶后移一位S.topS.baseeS.topStatusPush(SqStack&S,SElemTypee){if(S.top-S.base>=S.stacksize){S.base=(ElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemT
8、ype));if(!S.base)exit(OVERFLOW);//存储分配失败S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top++=e;returnOK;}3.1.2栈的表示和实现入栈操作演示3.1.2栈的表示和实现DestroyStack(&S)//销毁栈ClearStack(&S)//清空栈StackEmpty(S)//判栈空StackLength(S)//求栈长度GetTop(S,&e)//取栈顶元素Pop(&S,&e)//出栈StackTravers(
9、S,visit())//遍历栈其它栈操作讨论TypedefstructSNode{ElemTypedata;//数据域structSnode*next;//链域}SNode,*LinkStack;3.1.2栈的表示和实现链栈的C语言类型定义链栈的实现与链表的实现基本相同，头结点作为栈顶位置。LinkStack*top;//栈顶指针InitStack(&S)//初始化栈DestroyStack(&S)//销毁栈ClearStack(&S)//清空栈StackEmpty(S)//判栈空StackLength(S)//求栈长度GetTop
10、(S,&e)//取栈顶元素Push(&S,e)//入栈Pop(&S,&e)//出栈StackTravers(S,visit())//遍历栈讨论链栈基本操作的实现3.1.2栈的表示和实现3.2栈的应用举例3.2.1数制转换3.2.2括号
