-数据结构-栈与队列

《-数据结构-栈与队列》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章栈与队列栈与队列：限定操作的线性表。第一节栈一、逻辑结构1、栈的定义限定只能在表的一端进行插入、删除的线性表。　　栈顶top，栈底bottom。　　后进先出LIFO表(LastInFirstOut)实例：“进制数转换”、“表达式求值”、“函数调用关系”、“括号匹配问题”、“汉诺塔问题”、“迷宫问题”……2、基本操作进栈Push/出栈Pop取栈顶元素GetTop判别栈空StackEmpty/栈满StackFull3、栈的应用背景许多问题的求解分为若干步骤，而当前步骤的解答，是建立在后继步骤的解答基础上的。=》问题分解的步骤和求解的步骤次序恰好相反。二、

2、顺序存储结构动态顺序存储结构：存储空间随栈的大小而变化。#defineSTACK_INIT_SIZE100//初始化时分配的空间typedefstruct//定义栈类型{ElemType*base,*top;//栈底、栈顶指针intstacksize;//栈的存储空间大小}SqStack;SqStackS;//定义一个栈结构1、初始化栈StatusSqStack_Init(SqStack&S){S.base=malloc(STACK_INIT_SIZE*sizeof(ElemType));if(!S.base)return(OVERFLOW);S.top=

3、S.base;S.stacksize=STACK_INIT_SIZE;return(OK);}栈空：S.top==S.base栈满：S.top==S.base+S.stacksize2、进栈StatusSqStack_Push(SqStack&S,ElemTypee){if(S.top==S.base+S.stacksize)return(OVERFLOW);S.top=e;S.top++;return(OK);}3、出栈算法StatusSqStack_Pop(SqStack&S,ElemType&e){if(S.top==S.base)return(UN

4、DERFLOW);S.top--;e=S.top;return(OK);}缺点：空间浪费思考：二栈合用同一顺序空间？#definemaxsize=100intstack[maxsize],top0=0,top1=maxsize-1;intpush0(inte){if(top0>top1)return(0);stack[top0]=e;top0++;return(1);}intpush1(inte){if(top0>top1)return(0);stack[top1]=e;top1--;return(1);}intpop0(int*e){if(top0==0

5、)return(0);top0--;*e=stack[top0];return(1);}intpop1(int*e){if(top0==0)return(0);top0++;*e=stack[top1];return(1);}三、链栈typedefstructlinknode//栈中结点类型{ElemTypedata;structlinknode*link;}LinkNode;typedefstruct//定义栈类型{LinkNode*top;//栈顶指针intstacksize;//栈的大小(可选)}LinkStack;LinkStackS;初始化:S.

6、top==NULL;S.stacksize==0栈空：S.top==NULL栈满：系统内存不够1、进栈StatusLinkStack_Push(LinkStack&S，ElemTypee){LinkNode*p;p=(LinkNode*)malloc(sizeof(LinkNode));if(p==NULL)return(OVERFLOW);//上溢p->data=e;p->link=S.top;S.top=p;return(OK);}2、出栈StatusLinkStack_Pop(LinkStack&S,ElemType&e){LinkNode*p;if

7、(S.top==NULL)return(UNDERFLOW);p=S.top;e=S.top->data;S.top=S.top->link;free(p);return(OK);}3、特殊头结点的讨论进栈、出栈是最常用的操作=》链栈的头指针频繁变更=》参数传递的负担=》应约定链栈具有特殊头结点。第二节栈的应用1、函数调用栈f(n)=f(n-1)+f(n-2)intf(intn){intx,y;if(n==1

8、

9、n==2)return(1);x=f(n-1);y=f(n-2);return(x+y);}main(){printf("%d",f(5));

10、}2、将十进制数转换为八进制数。例如(1348)10=(2504)