资源描述：
《精品资源（清华版教材）数据结构第3章课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第三章栈和队列第三章栈和队列本章介绍在程序设计中常用的两种数据结构——栈和队列第三章栈和队列3.1栈3.2栈的应用举例3.3栈与递归3.4队列学习要点1理解掌握栈的结构特征和操作特点； 2掌握栈的顺序存储结构和链式存储结构，以及如何用C语言描述它们的类型定义；3掌握在两种存储结构下，栈的基本操作的算法；重点掌握顺序存储结构栈的基本操作的算法；4理解栈的后进先出的特点及在程序设计中的应用；5理解递归算法执行过程中栈的作用及栈的状态变化；基本内容:1栈的概念，栈的基本操作；， 2栈的两类存储结构和它们的类型定义； 3在栈的存储结构下，栈的基本操作
2、的算法； 4栈在程序设计中的应用；3.1栈3.1栈3.1.1栈的概念3.1.2栈的顺序存储和实现3.1.3栈的链式存储和实现3.1栈栈是限定仅能在表尾一端进行插入、删除操作的线性表（a1,a2,...,ai-1,ai,ai+1,…,an）插入删除3.1.1栈的概念一 什么是栈3.1栈4）栈的元素具有后进先出的特点,所以栈又称为后进先出表（LIFO表） 5）由于进栈、出栈操作总是在栈顶一端进行，通常设置称为栈顶指针的变量指示栈顶的位置。（a1,a2,...,ai-1,ai,ai+1,…,an）栈底栈顶进栈出栈说明：设（a1,a2,a3,…,
3、an）是一个栈1）表尾称为栈顶，表头称为栈底，即a1为栈底元素，an为栈顶元素， 2）在表尾插入元素的操作称进栈操作，在表头删除元素的操作称为出栈操作; 3）元素按a1,a2,a3,…,an的次序进栈,第一个进栈的元素一定在栈底，最后一个进栈的元素一定在栈顶,第一个出栈的元素为栈顶元素；3.1栈栈的示意图出栈进栈栈的特点后进先出第一个进栈的元素在栈底， 最后一个进栈的元素在栈顶，第一个出栈的元素为栈顶元素，最后一个出栈的元素为栈底元素栈顶栈底ana2a13.1栈栈的基本操作:1） 初始化操作InitStack((&S)功能：构造一个空栈S；2
4、）销毁栈操作DestroyStack(&S)功能：销毁一个已存在的栈;3）置空栈操作ClearStack(&S)功能：将栈S置为空栈;4）取栈顶元素操作GetTop(S,&e)功能：取栈顶元素，并用e返回;5）进栈操作Push(&S,e)功能：元素e进栈;6）退栈操作Pop(&S,&e)功能：栈顶元素退栈，并用e返回;7）判空操作StackEmpty(S)功能：若栈S为空，则返回True，否则返回False;3.1栈topbasebasetopbasetopbasetopAABCDEAB栈操作图示空栈A进栈BCDE进栈ED出栈3.1栈栈的顺序
5、存储结构也是利用一组连续的内存单元依次存放自栈底到栈顶的数据元素，栈顶元素的位置由一个称为栈顶指针的变量指示。栈的顺序存贮结构也称为顺序栈3.1.2栈的顺序存储和实现与线性表类似，栈也可以用顺序结构或链式结构存储。一、栈的顺序存储结构1栈的顺序存储结构3.1栈SqStack:：结构类型名；SqStack类型的变量是结构变量，它的三个域分别是：base：称为栈底指针，指向栈底位置；top：称为栈顶指针，约定栈顶指针指向栈顶元素的下（后面）一个位置；Stacksize：用于存放当前分配（存放栈元素）的存储空间的大小；#defineSTACK_IN
6、IT_SIZE100//栈存储空间的初始分配量 #defineSTACKINCREMENT10//栈存储空间的分配增量typedefstruct{SElemType*base;//栈空间基址SElemType*top//栈顶指针intstacksize;//当前分配的栈空间大小//（以sizeof(SElemType)为单位） }SqStack;2．顺序栈的类型定义3.1栈3顺序栈的图示anaiai-1a2a1S.topS.stacksizeS.baseSTACK_INIT_SIZEnn-1i-1i-2103.1栈当栈用顺序结构存储时，栈的基
7、本操作如建空栈、进栈、出栈等操作如何实现？3.1栈算法StatusInitStack_Sq(SqStack&S){ //构造一个空栈S S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));//为顺序栈动态分配存储空间if(!S.base)exit(OVERFLOW);//存储分配失败S.top=S.base; S.stacksize=STACK_INIT_SIZE; returnOK; }//InitStack_Sq初始化操作演示二顺序栈基本操作的算法 1）初始化操作Ini
8、tStack_Sq((SqStack&S)参数：S是存放栈的结构变量；功能：建一个空栈S；nn-1i-1i-2103.1栈S.topS.stacksizeS.bas
