数据结构之栈对列串课件.ppt

单击此处编辑母版标题样式,*,*,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,数据结构,第,三,章 栈 对列 串,要 求,熟练掌握以下内容：,堆栈的特征、基本运算并能设计简单算法,队列、循环队列的特征、基本运算并能设计简单算法,串的定义和应用,了解以下内容：,线性表运算时间复杂性分析,堆栈、队列实际应用,3.1,堆栈(Stack),堆栈也简称为栈，是限定在表的一端进行插入或删除操作的线性表。,进行插入或删除操作的一段称为栈顶（top），另一端称为栈底（bottom）。,插入元素又称为入栈（push），删除元素操作称为出栈（pop）。,不含元素的栈称为空栈。,堆栈元素的插入和删除只在栈顶进行，总是后进去的元素先出来，所以堆栈又称为后进先出线性表或LIFO（Last-In-First-Out）表。,堆栈的表示,堆栈的最简单的表示方法是采用一维数组，为形象起见，一般在图中将堆栈画成竖直的。,设数组名为STACK，其下标的下界为1，上界为n。,一般需用一个变量top记录当前栈顶的下标值，top也叫做栈指针。,本例中top=4,top,A,D,C,B,4,7,5,3,2,1,6,STACK,栈的基本运算,进栈 push(s,x),出栈 pop(s),取栈顶元素 gettop(s),判断栈空 emptystack(s),置空栈 setstacknull,求栈的长度 stacklen(s),栈的遍历 stacktraverse(s),1.入栈（push）,入栈的主要操作是先将栈顶指针加1；,然后将入栈元素放到栈顶指针所指示下标值的位置上。,设用下标从1到n的数组ST表示堆栈，入栈的元素值为G，则可得到入栈函数如下：,2.出栈（Pop）,出栈运算时，先将栈顶的元素值赋给某个变量，以备后面的运算应用；,然后栈顶指针减1，将栈顶位置下移。,假设已指定的变量为*p，则出栈的函数如下：,出栈,函数,Int pop(stacktype s,elementtype*p),if(s.top=-1),printf(“空栈!n”);/*栈为空*/,p=s.elementss.top;,s.top-;,return(0);,例3.1,一个双向栈是将两个栈用一个数组构成，它们的栈底分别设在数组的两端。写出以数组高端为底的栈的入栈和出栈的算法。,例,3.1解答,这个栈的栈顶指针top2是按相反的方向移动的，因此,在操作时要判断：,入栈时：top2-1=top1？,出栈时：top2=n+1?,入栈算法,void push(S,int n,top1,top2,G),if(top2-1=top1),printf(“溢出!n”);,else,top2=top2-1;,Stop2=G;/*插入新元素*/,出栈算法,void pop(S,int n,top1,top2,x),if(top2=n+1),printf(“下溢出!n”);,else,x=Stop2;,top2=top2+1;,栈的链式存储结构,用一头结点单链表的第一个元素，头结点的指针表示栈顶，若一进栈序列a,b,c,其链式结构如下：,head,c,b,a,其结构定义如下：,typedef struct node,elementtype data;,Struct node*next;,stacklnode;,进栈,Int push(stacklnode*head,elementtype x),stacklnode*p;,If(p=malloc(sizeof(struct node)=null,Printf(“没有空间”)；,P-data=x;,P-next=head-next;,Head-next=p;,Return(0);,出栈,Int pop(stacklnode*head,elementtype*x),stacklnode*p;,p=head-next;,if(p=null),printf(“栈已空”);,head-next=p-next;/*删除P*/,*x=p-data;,free(p),Return(0);,堆栈的应用,1.,堆栈在函数调用中的应用:,设有三个函数A1，A2，A3，这三个函数有如下的调用关系：函数A1在其函数体的某处r调用函数A2，函数A2又在其函数体某处t调用函数A3，函数A3不调用其他函数。,r,t,A1,A2,A3,函数嵌套调用A1调用A2，A2调用A3时的返回地址在堆栈中的情况如右图所示。,top,r,t,STACK,2.,堆栈在,表达式计算,中的应用,后缀表示法（逆波兰表示法）,ab+，abc*+，ab+c*，,逆波兰表达式的特点：无括号，形式简洁，运算符的顺序与运算顺序相同。,由于逆波兰表示法以上特点，其处理很方便。建立一个栈，对逆波兰表达式从左到右扫描，遇到运算分量则进栈，遇到运算符号则取其栈顶元素（二目或一目）运算，并把结果进栈。,例：求 B*（C+D）的值。,(其逆波兰表示：BCD+*),3.数的转换,把进制的数n转换成八进制的数r。,1.n除以r,商为S,输出余数。,2.若s=0，则结束，输出序列的逆就是转,换后的结果。,3.n:=s,转1.,例：把进制的数355转换成八进制的数。,4.表达式中左右括号的匹配问题,基本思想：若遇见左括号，则进栈；若右括号，则退栈，并比较是否匹配。,假设下列形式都是合法的：,（），（），（），（）；,而下列是不合法的：,（，），（，,栈与递归,递归：自己调用自己，分直接递归和间接递归,例：阶乘,n!=1 当n=0时,n!=n*(n-1)!当n0时,定义递归时要做到：,1.调用必须越来越简单，并且能在有限步内结束。,2.调用到最后一步时，必须有非递归的确切的定,义。,求n!的递归算法：,Int fact(n),if(n=0),Return(1);,Else return(n*fact(n-1);,递归的执行,调用时做以下工作：,1.调用时必须保存本层所有的参数和返回地址,等；,2.给下层参数赋值；,3.转移到被调用的函数入口。,返回时做以下工作：,1.保存被调用函数的计算结果。,2.恢复上层参数。,3.返回原处。,例：阶乘,Int fact(int n),if(n=0)return(1);,Else return(n*fact(n-1);,Fact(n),Top=1;m=n;,While(m1),Stop=m;,m=m-1,top=top+1;,R=1;,While(top1),Top=top-1;,R=R*stop;,斐波那契（Fibonacci)数的定义;,希尔波特（D.Hilbert,1891)曲线的定义；,塞平斯基（Sierpinski)曲线的定义；,Hanoi塔稳问题；,中断处理问题；,3.2 队列（Queue）,队列是一种运算受限制的线性表，元素的添加在表的一端进行，而元素的删除在表的另一端进行。,允许添加元素的一端称为队尾（Rear）；允许删除元素的一端称为队头（Front）。,向队列添加元素称为入队，从队列中删除元素称为出队。,新入队的元素只能添加在队尾，出队的元素只能是删除队头的元素，队列的特点是先进入队列的元素先出队，所以队列也称作先进先出表或FIFO（FirstIn-First-Out）表。,队列的表示,与堆栈类似，队列也可以简单的用一维数组表示。,设数组名为Queue，其下标下界为1，上界为n。,一般使用一个变量r指示队尾的下标值，叫做队尾指针；用另一个变量 f 指示队头的下标值，称为队头指针。,队列中元素的数目等于零称为空队列。,对列的顺序存储结构,假定有AF 6个元素先后进入队列，但A、B,C三个元素已出队了，故队尾指针r=6，而队头指针f=3。,对列的形式定义,#define maxsize,Typedef struct,elementtype elementsmaxsize;,Int front;,Int rear;,quetype;,插入操作,若 Q.rearmaxsize-1;/*对列不满*/,则插入：Q.rear+:/*插入*/,Q.elementsQ.rear=x;,删除操作,若 Q.frontQ.rear /*对列非空*/,则删除：Q.front+;/*删除*/,return(Q.elementsQ.front),1.入队（insert）,当给队列插入元素时，队尾指针r后移而队头指针不动，但有一个情况例外，即当向空队列插入第一个元素时，队头指针与队尾指针同时由0变为1。,设用下标从1到n的数组Q表示队列，且已知待添加的元素在变量x中。,入队函数,void insert(Q,int n,front,rear,x),ifQ.rear=n-1),printf(“溢出!n”);/*判断是否已到数组末端*/,else,Q.rear+;,Q.elementrQ.rear=x;/*插入元素*/,2.出队（Delete）,当从队列删除元素时，队头指针f后移而队尾指针r不动，但也有一个情况例外，即当删除了最后一个元素，队列成为了空队列时，队头指针与队尾指针同时变为0。,假设要求将出队的元素值赋给变量x。,出队函数,void Delete(Q,int front,rear,n,x),if(Qfront=Q.rear),printf(“下溢出!n”);/*判断是否为空队列*/,else,Q.front+:,x=Q.elementsQ.front;/*取队头元素给x赋值*/,if(Q.front=Q.rear),Q.front=Q.rear=0 /*置成空对列,“假溢出”问题,在插入时，由条件Q.rear=maxsize-1,判断对列是否满，,在删除时，由条件Q.front=Q.rear,判断对列是否空。,其中的判断条件是不科学的。实际上，当,Q.rear=maxsize-1,时，对列未必满，出现了,“假溢出”现象。,采用循环对列可以解决这一问题。,循环队列,循环队列就是把顺序队列的头和尾相连，构成一个闭环。,（见图）,当尾指针 Q.rear=max-1 时，若要插入(删除）一个元素，则要插入到第0个位置，,即 (max-1)+1%max=0 （取余数）。,若 max=8 时，要插入一个元素，应插入到第0个位置，即(Q.rear+1)%max=(7+1)%8=0,如何判断循环队列的“空”和“满”呢？,先看一个例子。,例：一循环队列 max=6，队列中已有3个元素，研究其插入3个元素后和删除3个元素后的状态。,可以看出，不管队列是“满”还是“空”，都有front=rear。那么，如何判断是“空”还是“满”呢？,解决方法：,1.另设一标记，以区分队列是“空”还是“满”；,2.不设标记，把,尾指针加1后等于头指针,作为队,满的条件。,这样,队满的条件：(Q.rear+1)%max=Q.front,队空的条件：Q.rear=Q.front,循环队列入队函数,Int insert(Quetype Q,elementtype x),if(Q.rear+1)%maxsize=Q.front),printf(“队列溢出”);,return(-1);,Q.rear=(Q.rear+1)%maxsize;,Q.elementsQ.rear=x;,return(0);,循环队列出队函数,if(Q.front=Q.rear),printf(“是空队列！n”);,return(-1);,Q.front=(Q.front+1)%maxsize;,Return(Q.elementsQ.front;,队列的应用,对于各种具有“先进先出”需排队处理的问题，都可以应用队列来解决。,例如，操作系统在管理和分配系统资源时，大量的应用了队列这种数据结构。,1)队列在输入/输出管理中的应用,2)对CPU的分配管理,返回,例,3.2,对于循环队列，试写出求队列长度的算法。,解1：设队列的最大元素个数为n，设一个计数器，将其初始值设为0。从队头开始，沿着队列顺序搜索，每搜索一个元素，计数器加1，直到队尾，计数器的最终值即为队列的长度。,解2：利用队头指针与队尾指针也可求出队列的长度：,当 rf 时，length=r-f,当 r=f),length=r-f;,else,length=n-(f-r);,return(length)返回,队列的链式存储结构,增设两个指针，分别指向队列的头和尾，,Head ,rear,队列空时:head,rear,结点的定义,Typedef struct node,elementtype data;,Struct node*next;,Qlnode;,插入结点：,P,head,rear,rear,x,删除结点：,Head,rear,插入算法,Int insertque(head,rear,x),p=malloc(sizeof(Qlnode);,If(p=null),printf(“队列溢出”);,Return(-1);,P-data=x;p-next=null;,rear-next=prear=p;,Return(0);,删除算法,Deleteque(head,rear),if(head-next=null),printf(“队列空”);,Return(-1);,P=head-next;head-next=p-next;,x=p-data;,If(p=rear)rear=head;/*若只有一个结点，,Free(p);return(0);/*删除后队列为空*/,第4章 串,知 识 点,串的有关概念和术语,串的基本运算功能,串的顺序存储方法（包括紧缩格式和非紧缩格式）和链接存储方法,串的匹配运算,4.1,串的定义及基本运算,串(string)是由有限个字符组成的序列，又称为字符串(character string)，一般记为:,s=a,1,a,2,a,3,a,n,其中s是串名，用单引号括起来的字符序列是串的值。a,i,(1=i maxlen),printf(“连接后太长”);return(-1);,for(i=0;inext null),p=p-next;,p-next=t;,return(s);,串的堆式存储结构,基本思想：,首先系统开辟一个足够大，连续的空间共串使用，串的堆式存储结构仍以一维数组的形式存放，但它们是在程序执行过程中动态分配的。在C语言中，用malloc和free来管理。,当建立一个新串时，用malloc来申请一块空，,成功，则返回其首地址；当不再使用时，用free来释放。,typedef struct,char string;/*按串的长度分配*/,Int strlen;,Hstring;,两个串S和T连接算法,Hstring*concat(s,t),char*p;int I,j,t_len;,t_len=s-strlen+t-strlen;,if(p=malloc(sizeof(char*t_len)=null),printf(“空间不足”);,return(null);,i=0;,for(j=0;jstrlen;j+)/*复制S到P中*/,pi+=s-stringj;,for(j=0;jstrlen;j+)/*复制t到P中*/pi+=t-stringj;,pi=0;/*加结束标记*/,free(s-string);,free(t-string);,s-string=p;,s-string=t_len;,return(s);,4。3 模式匹配,模式匹配就是判断某串是否是另一个已知串的子串。如是其子串，则给出该子串的起始点（即从已知串的哪个字符开始），故此运算又称为子串的定位。,设已知串s和t，要求判断t是否是s的子串，如果是其子串则给出起始点。显然t是s的子串的一个必要条件是，t的长度一定要小于或等于s的长度。,基本思想,首先将t的第1个字符与s的第1个字符比较，如二者匹配，则将t的第二个字符与r1的第二个字符比较这样比较下去，若直至t的末尾一个字符都与s的相应字符匹配，则整个运算结束，返回子串的起始位置为1；,当进行中遇到两串的相应字符不匹配时，则返回来将t的第一个字符与s的第二个比较，将t的第二个字符与s的第三个字符进行比较，若整个t的各个字符都与s的相应字符匹配，则运算结束，返回子串的起始位置为2；,依此类推，如出现不匹配，再返回来将t的第一个字符与s的第三个字符比较。,如此逐轮做下去，直至匹配成功，给出子串的起始位置或失败返回起始位置为0。,例：s=abafabcg,t=abc,子串t在s中的起始位置为5。,匹配算法,int indexstring(stringtype s,t),int i=0;j=0;/*Brute-force算法*/,while(is.len)&(jt.len),if(s.stringi=t.stringj),i+;j+;,else i=i-j+1;j=0;,if(j=t.len),return(i-t.len+1);/*成功返回在主串中*/,return(-1);/*的位置*/,以上算法称为布鲁-福斯（Brute-Force)算法，是由两人完成的，但其效率不高，knuth,Pratt,Morris三人同时发现了其中的不足，并对其进行了改进，改进后的算法称为,KMP,算法。,4.4 串的应用举例,1.中心对称问题,满足下列条件的串称为中心对称串：,字符的个数为偶数；,第1个字符和最后一个字符相等，第2个字符和,倒数第二2个字符相等，。,如串 texttxet,怎样判断一个串是中心对称呢？,基本思想,：把串的前半部分入栈，扫描后半部分的每一符号，并与栈顶元素比较，若均相等，则为中心对称，否则，不是中心对称。,算法如下：,int symstring(char s,int n),stacktype stack;char c;int j;,setstacknull(stack);/*将栈置空*/,for(j=0;jn/2;j+)/*S的前半部分进栈*/,push(stack,sj）;,for(j=n/2;jn;j+),c=pop(stack);,if csj return(false);,return(true);,2.从链接存储的串r1中的第i个字符开始，把连续j个字符组成的子串赋给r。,linkstring*substring(linkstring*r1，int i，j),int k;,linkstring*p，*q，*s，*r;,p=r1;,k=1;,while(klink;/*寻找第i个结点*/,k+;,if(p=NULL),printf(“出错n”);,else,r=(linkstring*)malloc(sizeof(linkstring);,q=r;,k=1;,while(kch=p-ch;,q-link=s;,/*q总是指向r的最后一个结点*/,q=s;,p=p-link;,k+;,q-link=NULL;,q=r;,r=r-link;,free(q);,return(r);,返回,小 结,串,串的存储结构,顺序存储结构,链接存储结构,串的匹配运算,返回,习题与练习,一、基本知识题,1.空串与空格串有何区别？,2.已知两个串为,Aac cab cabcbbca,Babc,判断B串是否是A串的子串，如果是其子串，说明起始点是A串的第几个字符。,3.串是一种特殊的线性表，其特殊性体现在什么地方？,4.串的两种最基本的存储方式是什么？,5.两个串相等的充分必要条件是什么？,二、算法设计题,1.对于采用顺序结构存储的串r，编写一个函数删除其值等于ch的所有字符。,2.对于采用顺序结构存储的串r，编写一个函数删除r中第i个字符开始的j个字符。,3.对于采用顺序结构存储的串r，设计一算法将串逆置。,4.采用单链表结构存储的串r，编写一个函数将其中所有的c字符替换成s字符。,5.已知两个采用单链表结构存储的串A和B。试编写一个函数将串B插入到串A中第k个字符之后。,返回,习题与练习,一、基本知识题,1.什么是数组？数组的主要特点是什么？,2.什么是线性表？线性表的主要运算有哪些？,3.什么是栈？什么是队列？它们各自的特点是什么？,4.线性表、栈、队列有什么异同？,5.简述栈的入栈、出栈操作的过程。,6.在循环队列中简述入队、出队操作的过程。,7.在什么情况下，才能使用栈、队列等数据结构？,8.有A、B、C三个数组：A8，B47，C586，试计算它们的元素个数是多少？,二、算法设计题,1.设有一n个元素的线性表，用一维数组An表示。试设计一个算法，使此线性表元素的排队次序颠倒过来但仍存储于原数组中。,2.设用一维数组stackn表示一个堆栈，若堆栈中一个元素需占用length个数组单元（length 1），试写出其入栈、出栈操作的算法。,3.试编写一个遍历及显示队列中元素的算法。,4.设一循环队列Queue，只有头指针front，不设尾指针，另设一个内含元素个数的计数器，试写出相应的入队、出队算法。,5.设计一算法能判断一个算术表达式中的圆括号配对是否正确。（提示：对表达式进行扫描，凡遇到“（”就进栈，遇到“）”就退出栈顶的“（”，表达式扫描完毕时栈若为空则圆括号配对正确。）,返回,