《数据结构C语言 栈和队列.pptx》由会员分享，可在线阅读，更多相关《数据结构C语言 栈和队列.pptx（48页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第三章 栈和队列栈和队列是两种重要的线性结构栈和队列是操作受限的线性表出进排队买票汉诺塔进出第1页/共48页第三章 栈和队列1.栈的概述2.栈的应用3.栈和递归的实现4.队列5.队列的应用第2页/共48页栈的概述1.栈的定义栈是限定仅在表尾进行插入或删除操作的线性表。通常，表头端称为栈底，表尾端称为栈顶。出栈进栈a1为栈底元素an为栈顶元素按a1、a2、an顺序进栈按an、a2、a1顺序出栈栈称为后进先出线性表(LIFO)a1a2an.表头表尾栈底栈顶第3页/共48页1.栈的定义主要基本操作包括:InitStack(&S)初始化StackEmpty(S)判空GetTop(S，&e)取栈顶Pus
2、h(&S，x)入栈Pop(&S,&e)出栈栈的概述第4页/共48页2.栈的表示和实现 顺序栈；链式栈。1）顺序栈ABCbasetop栈底指针base栈顶指针top栈容量顺序栈类型数据结构的表示：typedef struct dataType *base；dataType *top；int stacksize；SqStack；栈的概述第5页/共48页空栈ABCbasetop栈中有三个元素ABCbasetopDE满栈top=base第6页/共48页用数组来描述栈的结构：typedef struct datatype datamaxsize;int top;int base;seqstack;seq
3、stack *s;第7页/共48页例1 栈的初始化top=baseInitStack（seqstack&s）stop0;sbase0;第8页/共48页例2 判断栈空top=baseInt StackEmpty（seqstack s）if（stopsbase）return true；else return false；第9页/共48页例3 在栈中插入元素 Atop=baseAbasetop=top+1datatype Push(seqstack*s,datatype x)if(s-top=maxsize)printf(“overflow”);return NULL;else s-datas-to
4、p=x;s-top+;return true;第10页/共48页例4 删除栈顶元素 AbaseAtoptop=top-1 datatype Pop(seqstack&s,datatype x)if(StackEmpty(s)printf(“underflow”);return NULL;else s-top-;x=s-datas-top;return(x);第11页/共48页栈的概述当需要使用多个栈时，在数组空间允许的情况下，可以使多个栈共享同一个数组空间。其结构定义形式如下：typedef datatype int;#define maxsize 64 typedef struct data
5、type datamaxsize;int top1,top2;dstack;第12页/共48页2.栈的表示和实现2）链式栈typedef struct node datatype data；struct node *next；*Linkstack；anan-10a1栈底base栈顶top空栈:top=base=NULL;栈的概述第13页/共48页栈的概述2.栈的表示和实现2）链式栈 进栈：linkstack*PushLinkStack(linkstack*top,datatype w)linkstack*p;p=(linkstack*)malloc(sizeof(linkstack);p-da
6、ta=w;p-next=top;top=p;return p;第14页/共48页栈的概述2.栈的表示和实现2）链式栈 出栈：dataType PopLinkStack(linkstack*top,datatype x)linkstack*p;if(top=NULL)printf(“空栈！”);return NULL;else x=top-data;p=top;top=top-next;free(p);return x;第15页/共48页栈的概述2.栈的表示和实现2）链式栈 置空栈：void InitStack(linkstack*S)S=NULL;判空栈：Int StackEmpty(link
7、stack*S)if(S=NULL)return 1;else return 0;取栈顶元素：datatype StackTop(linkstack*S)if(StackEmpty(S)Error(“空栈！”);retrun NULL;return S-data;返回第16页/共48页栈的应用常见的栈应用问题：数制转换括号匹配的检验行编辑迷宫问题算术表达式求值返回第17页/共48页栈和递归的实现一、递归的定义递归：一个事件或对象的部分由自己组成，或者按它自己来定义。递归算法的组成：递推：将问题推到比原来问题简单的问题上求解；回归：当简单问题得解后再回归到原来的问题上。常见递归算法：直接递归：函
8、数直接调用本身。间接递归：函数在调用其它函数的过程中又调用其本身。第18页/共48页栈和递归的实现二、常见的递归问题1.汉诺塔问题 要求：将大小不同的n个盘子移动到另外一根轴上，移动过程中必须保证小的盘子在大的盘子的上方。算法思想：将放在下面的n-1个盘子从当前轴移动到目的轴上；（即递归过程）将最小的1个盘子移动到目的轴上。p 5558第19页/共48页栈和递归的实现二、常见的递归问题2.八皇后问题要求：在88的棋盘上放置八颗棋子，任意两颗不能在同一行或同一列或同一对角线上。算法思想：先在棋盘中确定一个棋子的位置；在剩下可以下子的位置里面再确定一个棋子的位置，要求位置满足上述规则；如果此时棋子
9、还没有放完，则继续上述第二步直到所有棋子放完位置；如果棋子顺利放完，则该算法成功；反之，则要回溯，改变上一颗棋子的位置，直到所有 棋子均成功放置为止。第20页/共48页栈和递归的实现二、递归的实现1.递归的基本条件：待解决的问题可以转化为与原始问题解决方法相同的另一个问题来处理；具有终止递归的条件。2.递归的调用机制：递归调用之前，将算法所有参数、局部变量的当前值和调用后的返回地址等压入递归工作栈；执行递归调用；每次递归结束后，将栈定元素弹出，分别赋给相应的参数和变量。第21页/共48页栈和递归的实现说明：递归函数比非递归函数更容易理解；但递归函数的时间复杂度和空间复杂度都高于相应的非递归函数
10、；递归的层次不能太深，否则会影响机器运行的速度。返回第22页/共48页队 列队列是一种先进先出(FIFO)的线性表。队列只允许在一端进行插入，而在另一端进行删除。出队列入队列a1 a2 a3 an 队头队尾1.队列的定义第23页/共48页1.队列的定义 主要基本操作包括:InitQueue（&Q）构造空队列DestroyQueue（&Q）队列销毁QueueEmpty(linkqueue *q)判队空ClearQueue（&Q）队列清空GetHead(Q，&e)取头元素EnQueue(&Q，e)队列插入DeQueue(&Q，&e)队头删除 队 列第24页/共48页1.队列的定义 特殊的队列：双端
11、队列 可以在队列两边同时进行插入和删除操作输出受限的双端队列 有一个端点只允许插入输入受限的双端队列 有一个端点只允许输出队 列第25页/共48页2 队列的表示和实现 链队列；顺序队列；循环队列1）链队列链式存储结构 必须具备指示队头和队尾的指针(头指针、尾指针)。a1a20anfrontrearQ.frontQ.rear0空队列队 列第26页/共48页2 队列的表示和实现队列的表示和实现1）链队列）链队列链式存储结构链式存储结构 链队列的结构类型定义：链队列的结构类型定义：typedef struct QNode datatype data;struct QNode *next;QNode,
12、*QueuePtr;typedef struct QNode*front,*rear;linkqueue;队 列第27页/共48页2 2 队列的表示和实现队列的表示和实现1 1）链队列）链队列链式存储结构链式存储结构链队列的基本运算算法：链队列的基本运算算法：初始化：初始化：p62p62销毁队列：销毁队列：p62p62入队：入队：p62p62出队：出队：p62p62队 列第28页/共48页p=(QNode*)malloc(sizeof(QNode)；if(!p)exit(OVERFLOW)；p-data=e；p-next=NULL；/申请新结点Q.rear-next=p；Q.rear=p；/插
13、入在队尾return OK；InQueue(LinkQueue *Q，datatype e)第29页/共48页sunpzhoujin0 xin Q.front Q.rear0Q.rear例题1：入队操作：第30页/共48页例题：出队操作if(Q.front=Q.rear)return ERROR；p=Q.front-next；e=p-data；/取第一个结点free(p)；return OK；Status DeQueue(LinkQueue *Q,dataType&e)Q.front-next=p-next；/删除第一个结点if(Q.rear=p)Q.rear=Q.front；/若需要删除的队
14、头结点就是尾结点第31页/共48页zhoujin0 xin SQ.frontQ.rear pe=p-data=zhou pe=p-data=jin pe=p-data=xinQ.rear0例题2：出队操作第32页/共48页用一组地址连续的存储单元依次存放队头到队尾的元素。指针 front、rear 分别指示队头和队尾下一个元素。令 front=rear=0 表示空队列，rear=MAXSIZE 表示队满。每插入一新元素，rear 增 1，每删除一元素，front 增 1。2）顺序队列顺序存储结构Q.rearQ.front543210队尾队头ABCD第33页/共48页2）顺序队列顺序存储结构顺序
15、队列的类型描述：#define maxsize 66Typedef structdatatype datamaxsize;int front,rear;sequeue;Sequeue *q;第34页/共48页2）顺序队列顺序存储结构顺序队列的基本操作：初始化删除插入第35页/共48页插入、删除操作过程：543210Q.rearQ.front队尾队头插入元素 J1；J1Q.rear插入元素 J2、J3；J2J3Q.rear删除元素 J1、J2；Q.front插入元素 J4、J5、J6；J4J5J6Q.rear此时，队满，无法再插入新的元素，但实际队列中的可用空间并未真的被占满。第36页/共48页
16、3）循环队列顺序存储结构将顺序队列改造为一个环状的空间。01maxsize-1Q.frontQ.rear指针 front、rear 分别指示队头和队尾下一个元素。令 front=rear=0 表示空队列。每插入一新元素，rear=(rear+1)%maxsize，每删除一元素，front=(front+1)%maxsize。/%:求余第37页/共48页插入、删除操作01Q.frontQ.rear2345初始，Q.front=Q.rear=0，空队列。插入元素 J0、J1、J2、J3、J4；删除元素 J0、J1；插入元素 J5、J6 ；maxsize=6J0J1J2J3J4Q.rearQ.fro
17、ntJ5J6Q.rear第38页/共48页01Q.frontQ.rear2345初始，Q.front=Q.rear=0，空队列。插入元素 J0、J1、J2、J3、J4、J5；J0J1J2J3J4J5Q.rearQ.rearQ.rearQ.rearQ.rearQ.rearQ.front=Q.rear=0，满队列。maxsize=6问题:第39页/共48页故无法通过 front=rear=0 来分辨队空或队满。解决方案:特殊空间，规定 front 与rear 之间总空出一个空间。队空:Q.front=Q.rear队满:Q.front=(Q.rear+1)%maxsize 01Q.front2345
18、J0J1J2J3J4Q.rear第40页/共48页01Q.frontQ.rear2345初始，Q.front=Q.rear=0，空队列。插入元素 J0、J1、J2、J3、J4；Q.front=(Q.rear+1)%maxsize 队满删除元素 J0、J1；插入元素 J5、J6 ；Q.front=(Q.rear+1)%maxsize 队满maxsize=6J0J1J2J3J4Q.rearQ.frontJ5J6Q.rear第41页/共48页3 3）循环队列顺序结构基本操作算法：初始化（置空队）：p64求队列长度：p64入队：p65出队：p65第42页/共48页4）循环队列链式存储结构空队列：基本操
19、作：插入删除队首结点队尾结点第43页/共48页5）优先队列1.也是一种队列2.特征：插入元素的顺序是以优先级为依据的。3.主要应用：堆排序返回第44页/共48页队列的应用1.解决设备速度不匹配问题：利用队列先进先出的特性，设置缓冲队列；2.舞伴问题：先入队的男士和女士先配成舞伴；3.离散事件模拟：p6569返回第45页/共48页作 业若依次输入数据元素序列a,b,c,d,e,f,g进栈，出栈操作可以和入栈操作间隔进行。则下列哪些元素序列可以由出栈序列得到：A）d,e,c,f,b,g,aB）f,e,g,d,a,c,bC）e,f,d,g,b,c,aD）c,d,b,e,f,a,g第46页/共48页上机实验：链栈的建立及出栈内容与要求：建立链栈并进行元素的出栈，实现链栈的建立及出栈的基本操作；使用函数initiate()实现链栈的初始化；使用函数pushls()实现链栈的入栈；使用函数popls()实现链栈的出栈。第47页/共48页感谢您的观看！第48页/共48页