数据结构（c语言版中）清华大学出版社ppt

《数据结构（c语言版中）清华大学出版社ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构——C语言版清华大学出版社2009年9月栈（Stack）栈的应用队列（Queue）队列的应用第三章栈和队列定义：3.1栈限定只能在表的一端进行插入和删除运算的线性表。在栈中通常将表中允许进行插入、删除操作的一端称为栈顶(Top)，同时表的另一端被称为栈底(Bottom)。栈顶的当前位置是动态变化的，它由一个称为栈顶指针的位置指示器指示。当栈中没有元素时称为空栈。栈的插入操作被形象地称为进栈或入栈，删除操作称为出栈或退栈。栈的示意图与线性表相同，仍为一对一(1:1)关系。用顺序栈或链栈存储均可，但以顺序栈更常见

2、只能在栈顶运算，且访问结点时依照后进先出（LIFO）或先进后出（FILO）的原则。关键是编写入栈和出栈函数，具体实现依顺序栈或链栈的存储结构有别而不同。存储结构运算规则实现方式逻辑结构基本操作建栈、判断栈满或栈空、入栈、出栈、读栈顶元素值，等等。栈的逻辑表示法表尾(即an端)称为栈顶/top;表头(即a1端)称为栈底/base例如：栈S=(a1,a2,a3,……….,an-1,an)插入元素到栈顶的操作，称为入栈。从栈顶删除最后一个元素的操作，称为出栈。an称为栈顶元素a1称为栈底元素强调：插入和删除都只能在表的一端

3、（栈顶）进行！栈的物理表示法一、顺序栈的存储结构和操作的实现顺序栈:是利用一组地址连续的存储单元依次存放从栈底到栈顶的数据元素。在C语言中，预设一个数组的最大空间,栈底设置在0下标端，栈顶随着插入和删除元素而变化，用一个整型变量top来指示栈顶的位置。a1a2……an顺序栈Sai……0n栈底栈顶top压入(PUSH):S[top++]=a弹出(POP):e=S[--top]栈的基本操作ClearStack(S)：栈S已经存在，清除栈S中的所有元素将S置成空栈。InitStack()：初始化，构造一个空栈SStackE

4、mpty(S)：判断栈S是否为空，若为空，则返回true；否则返回falseGetTop(S)：返回S的栈顶元素，但不移动栈顶指针也不改变栈顶元素的值Push(S,x)：在S的顶部插入(亦称压入)元素x；若S栈未满，将x插入栈顶位置，若栈已满，则返回FALSE，表示操作失败，否则返回TRUE。（入栈操作)Pop(S)：删除S的栈顶元素并返回其值（出栈操作）顺序栈存储结构的描述：#defineMaxsize100/*设顺序栈的最大长度为100，可依实现情况而修改*/typedefintdatatype;typedefs

5、truct{datatypestack[Maxsize];inttop；/*栈顶指针*/}SeqStack；/*顺序栈类型定义*/SeqStack*s；/*s为顺序栈类型变量的指针*/顺序栈的几种状态以及在这些状态下栈顶指针top和栈中结点的关系栈为空的条件：top==0;栈满的条件：top==Maxsize若入栈动作使地址向高端增长，称为“向上生成”的栈；若入栈动作使地址向低端增长，称为“向下生成”的栈；对于向上生成的堆栈:栈指针指向待压入位置入栈：栈指针top“先压后加”:S[top++]=ai出栈：栈指针top

6、“先减后弹”:e=S[--top]顺序栈的基本操作构造一个空顺序栈SeqStack*InitStack(){SeqStack*S;S=(SeqStack*)malloc(sizeof(SeqStack));if(!S)/*空间申请失败*/{printf(“空间不足”)；returnNULL;}else{S->top=0;returnS;}}取顺序栈栈顶元素datatypeGetTop(SeqStack*S){if(S->top==0){printf("栈是空的!");returnFALSE;}elsereturn

7、S->stack[S->top-1];}该函数返回一个datatype类型的值判别空栈intStackEmpty(SeqStack*S){if(S->top==0)returnTRUE;elsereturnFALSE;}顺序栈的入栈操作——例如用堆栈存放（A，B，C，D）AACBABAtop核心语句：顺序栈入栈函数PUSH（）SeqStack*Push(SeqStack*S，datatypex){if(S->top==Maxsize)returnNULL;   else{S->stack[S->top]=x;S->t

8、op++;returns;}}Push(s,B);Push(s,C);Push(s,D);toptoptoptop低地址LPush(s,A);高地址MBCD顺序栈出栈操作——例如从栈中取出‘B’DCBAtoptopDCABDCBAtopDCBAtop低地址L高地址MD核心语句：pop();顺序栈出栈函数POP()datatypepop(SeqS