数据结构C语言栈和队列学习教案.pptx

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