数据结构3栈和队列.ppt

第三章 栈和队列 内容提要 本课主题： 栈的表示与实现，栈的应用，队列的表示与实现，队列的应用 教学目的： 栈的数据类型定义、栈的顺序存储表示与实现，掌握栈的应用方法，理解栈的重要作用，掌握队列的类型定义，掌握链队列的表示与实现方法 教学重点： 顺序栈的表示与实现，栈与递归，顺序队列的表示与实现 教学难点： 栈的定义，栈与递归，栈的应用，顺序队列的表示与实现 3.1 栈 栈的由来 函数调用、中断的计算机实现(P56) 3.1.1栈的概念 ★一、栈的定义 栈:限定仅在表尾进行插入或删除操作的线性表。 形象的例子：仓库物流，车辆进出只有一对铁轨、一个出口的火车站，建房。 典型应用：函数调用、递归调用的实现、递归问题的非递归法求解、括号匹配、表达式求值、语句编译、迷宫问题求解 3.1.1栈的概念 栈的表尾称为栈顶，表头称为栈底，不含元素的空表称为空栈。 栈的特点 栈的特点：后进先出(last in first out, LIFO) 提问：向某栈输入了三个元素，已知元素输入的先后顺序是A、B、C，那么该栈的输出序列可能有哪些？？反过来，如果输出序列是A、B、C呢？ CBA, ABC, ACB, BAC, BCA，无CAB 3.1.2栈的抽象数据类型定义 ADT Stack{ 数据对象: D={ai|ai∈ElemSet,i=1,2,...,n,n=0} 数据关系: R={ai-1, ai|ai∈D,i=2,...,n} 基本操作: InitStack(S)//构造一个空栈S DestroyStack(S)//栈S存在，则栈S被销毁 ClearStack(S)//栈S存在，则清为空栈 StackEmpty(S)//栈S存在，栈空则返回TRUE，否则返回FALSE StackLength(S)//栈S存在，则返回S的元素个数，即栈的长度 GetTop(S,e)//栈S存在且非空，则返回S的栈顶元素 Push(S,e)//插入元素e为新的栈顶元素，俗称推入操作或压入操作 Pop(S,e)//删除栈顶元素并用e返回其值，俗称弹出操作 StackTraverse(S,visit())//遍历栈S }ADT Stack ★3.1.3顺序栈：栈的顺序存储及其实现 1.顺序栈：利用一组地址连续的存储单元依次存放从栈底到栈顶的所有数据元素，同时附设栈底指针和栈顶指针指示栈底元素和栈顶元素的位置。 顺序栈的类C语言实现 2.顺序栈的类C语言实现 #define STACK_INIT_SIZE 100 //注意P46页多出分号 #define STACKINCREMENT 10 struct SqStack { ????ElemType *base; //栈底指针，指向栈底元素，也即数组基地址。 ??ElemType *top; //栈顶指针，指向栈顶元素的下一个位置(有的书上表示的是当前栈顶元素的位置)，便于判断栈空、栈满和计算表长 ????int stacksize; //栈当前可使用的最大容量。 }; 顺序栈的类C语言实现 栈底元素：*base，栈顶元素：*(top-1) 栈空判断条件： top==base;或top-base==0; 栈满判断条件： top-base==stacksize; 栈的长度： top-base 注意不同的课本上top的含义略有不同，导致判断条件也略有不同！ 初始化 Status InitStack(SqStack S) //构造空栈 { ???? S.base=(ElemType*)malloc(STACK_INIT_SIZE* sizeof(ElemType)); ???? if(S.base==NULL) exit(OVERFLOW); ???? S.top=S.base; //不是S.top=0或S.length=0 ???? S.stacksize=STACK_INI_SIZE; ???? return OK; }//InitStack 插入 Status Push(SqStack S, ElemType e) //插入元素 { ???? if(S.top - S.base = S.stacksize) //栈满则追加存储空间 ???? { ???????? S.base=(ElemType *) realloc(S.base, (S.stacksize + STACKINCREMENT) * sizeof(ElemType)); ???????? if(S.base==NULL)exit(OVERFLOW); ???????? S.top=S.base+S.stacksize; //栈长不变，但栈顶指针会变 ???????? S.stacksize+=STACKINCREMENT; ???? }