数据结构第3章栈和队列.ppt

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

1、特殊线性表栈队列串逻辑结构逻辑结构逻辑结构物理结构物理结构物理结构顺序栈链式栈顺序队列顺序存储链式队列链式存储⑴栈的定义⑵操作特性⑶ADT定义⑴队列定义⑵操作特性⑶ADT定义⑴串的定义⑵操作特性⑶ADT定义⑴基本操作的实现⑵时间性能⑴基本操作的实现⑵时间性能模式匹配第三章栈和队列栈和队列是两种特殊的线性表，是操作受限的线性表，称限定性DS“取”操作必须在这端进行“放”操作必须在同一端进行3.1栈（stack）定义：限定仅在表尾进行插入或删除操作的线性表。表尾—栈顶表头—栈底不含元素的空表称空栈特点：先进后出（FIL

2、O）3.1.1抽象数据类型栈的定义ADTStack{数据对象：D＝{ai

3、ai∈ElemSet,i=0,1,...,n-1,n≥0}数据关系：R1＝{

4、ai-1,ai∈D,i=1,...,n-1}约定an-1端为栈顶，a0端为栈底。基本操作：InitStack(&S);DestroyStack(&S);StackLength(S);StackEmpty(s);GetTop(S,&e);……}ADTStack3.1.2栈的表示与实现顺序栈：是利用一块地址连续的存储单元来存放栈中的元素，同时要利用一个

5、指针top来指示栈顶元素的位置。//-----栈的顺序存储表示-----#defineSTACK_INIT_SIZE100;#defineSTACKINCREMENT10;typedefstruct{SElemType*base;SElemType*top;intstacksize;}SqStack;顺序栈示意图*base*topstacksize......a1...aian*base*topstacksize初始空栈*top=*base;stacksize=STACK_INIT_SIZE顺序栈栈的几种状态示意图

6、top=0123450栈空栈顶指针top,指向实际栈顶后的空位置，初值为0top123450进栈Atop出栈栈满BCDEF设数组维数为Mtop=0,栈空，此时出栈，则下溢（underflow)top=M,栈满，此时入栈，则上溢（overflow)toptoptoptoptop123450ABCDEFtoptoptoptoptoptop栈空StatusInitStack(SqStack&S){//构造一个空栈SS.base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemTy

7、pe));if(!S.base)exit(OVERFLOW);//存储分配失败S.top=S.base;//栈顶指针指向待插入的位置S.stacksize=STACK_INIT_SIZE;returnOK;}在此存储结构下的基本操作实现:StatusPush(SqStack&S,SElemTypee){//插入元素e为新的栈顶元素if(S.top-S.base>=S.stacksize){//栈满，追加存储空间S.base=(ElemType*)realloc(S.base,(S.stacksize+STACKIN

8、CREMENT)*sizeof(ElemType));if(!S.base)exit(OVERFLOW);//存储分配失败S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top++=e;//先传数据再移指针returnOK;}StatusPop(SqStack&S,SElemType&e){//若栈不空，则删除S的栈顶元素，//用e返回其值，并返回OK；//否则返回ERRORif(S.top==S.base)returnERROR;e=*--S.to

9、p；//先移指针再传数据returnOK;}2.链栈（1）链栈的存储结构链栈是指采用链式存储结构存储的栈。链栈是一种特殊的单链表，即限定仅在表头进行插入和删除操作的单链表，因此链栈的结点结构与单链表的结点结构相同。a1a2an∧topdatanext栈顶栈底…3.2栈的应用举例3.2.1数制转换十进制N和其它进制数的转换是计算机实现计算的基本问题,其中一个简单算法基于下列原理:N=(Ndivd)10d+Nmodd例如:(1348)10=283+582+08+4=(2504)8NNdiv8Nmod81348

10、16841682102125202结果：2504计算时从低位到高位顺序产生八进制数的各个数位显示时按从高位到低位的顺序输出voidconversion(){InitStack(s);//建空栈scanf(“%d”,&n);//输入一个非负十进制整数while(n){//x不等于零循环push(s,n%8);//x/8第一个余数进栈n=n/8;//整除运