北邮算法与数据结构3

《北邮算法与数据结构3》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构---第三章栈和队列1第三章栈和队列栈和队列是两种特殊的线性表，它们的逻辑结构和线性表相同，只是其插入、删除元素时的运算规则受到更多的限制。3.1栈3.2栈与递归的实现3.3队列本章学习要点习题与上机作业数据结构---第三章栈和队列2线性表插入删除Insert(L,i,x)Delete(L,i)(1≤i≤n+1)(1≤i≤n)Insert(L,n+1,x)Delete(L,n)Insert(L,n+1,x)Delete(L,1)栈队列数据结构---第三章栈和队列33.1栈3.1.1栈的定义栈是一种特殊的线性表，限定插入和删除操作只能在表尾进行。具有后进先出(LIF

2、O—LastInFirstOut)的特点。a1a2an栈顶（表尾）栈底bottomtop入栈push出栈pop进栈出栈栈顶栈底an…a2a1数据结构---第三章栈和队列4定义在栈结构上的基本运算(1)生成空栈InitStack(&S)(2)销毁已存在的栈DestroyStack(&S)(3)清空已存在的栈ClearStack(&S)(4)判栈空与否StackEmpty(S)(5)求当前栈元素个数(栈长)StackLength(S)(6)取栈顶元素GetTop(S，&e)(7)数据元素入栈Push(&S,e)(8)数据元素出栈Pop(&S,&e)(9)遍历栈元素StackT

3、raverse(S,visit())数据结构---第三章栈和队列5抽象数据类型栈的定义ADTStack{数据对象：D={ai

4、aiElemSet,i=1,2,…,n,n0}数据关系：R1={,aiD,i=2,…,n}约定an端为栈顶，a1端为栈底基本操作：InitStack(&S)操作结果：构造一个空栈S。DestroyStack(&S)初始条件：栈S已存在。操作结果：销毁栈S。……}ADTList数据结构---第三章栈和队列63.1.2栈的顺序存储结构以及操作的实现一个栈独占一组地址连续的存储单元[类型定义]空间基址+栈顶指示+栈容量Typede

5、fstruct{SElemType*base;SElemType*top;intstacksize;}SqStack;Si-1ai...1a20a1stacksize-1S.topSqStackS；S.baseS.baseS.top空栈栈不存在：base==NULL栈空：top==base可不用最后一个结点以保证指针正确数据结构---第三章栈和队列7[基本运算实现示例]#defineSTACK_INIT_SIZE100;StatusInitStack(SqStack&S){S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(S

6、ElemType));if(!S.base)exit(OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;}//InitStackP47StatusStackEmpty(SqStackS){if(S.top==S.base)returnTRUE;elsereturnFALSE;}//StackEmpty(1)(4)数据结构---第三章栈和队列8(5)intStackLength(SqStackS){returnS.top-S.base;}//StackLength(6)StatusGetTop(SqStackS,SElem

7、Type&e){if(S.top==S.base)returnERROR;e=*(S.top-1);returnOK;}//GetTopP47(S.top-S.base)/sizeof(SElemType)topbase数据结构---第三章栈和队列9(7)#defineSTACK_INCREMENT50;StatusPush(SqStack&S,SElemTypee){if(S.top-S.base==S.stacksize-1){S.base=(SElemType*)realloc(S.base,(S.stacksize+STACK_INCREMENT)*sizeof(

8、SElemType))if(!S.base)exit(OVERFLOW);S.top=S.base+S.stacksize-1;S.stacksize+=STACK_INCREMENT;}*S.top=e;S.top++;}//PushS.topS.base栈满状态数据结构---第三章栈和队列10StatusPop(SqStack&S,SElemType&e){if(S.top==S.base)returnERROR;S.top--;e=*S.top;}//PopP47(8)S.topS.baseS.topS.base数据结构