数据结构之栈对列串课件

数据结构第三章栈对列串要求

熟练掌握以下内容：堆栈的特征、基本运算并能设计简单算法队列、循环队列的特征、基本运算并能设计简单算法串的定义和应用了解以下内容：线性表运算时间复杂性分析堆栈、队列实际应用3.1堆栈(Stack)堆栈也简称为栈，是限定在表的一端进行插入或删除操作的线性表。进行插入或删除操作的一段称为栈顶（top），另一端称为栈底（bottom）。插入元素又称为入栈（push），删除元素操作称为出栈（pop）。不含元素的栈称为空栈。堆栈元素的插入和删除只在栈顶进行，总是后进去的元素先出来，所以堆栈又称为后进先出线性表或LIFO（Last-In-First-Out）表。堆栈的表示堆栈的最简单的表示方法是采用一维数组，为形象起见，一般在图中将堆栈画成竖直的。设数组名为STACK，其下标的下界为1，上界为n。一般需用一个变量top记录当前栈顶的下标值，top也叫做栈指针。本例中top=4topADCB4753216STACK栈的基本运算进栈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，则出栈的函数如下：出栈函数Intpop(stacktypes,elementtype*p){if(s.top==-1)printf(“空栈!\n”);/*栈为空*/p=s.elements[s.top];s.top--;return(0);}例3.1

一个双向栈是将两个栈用一个数组构成，它们的栈底分别设在数组的两端。写出以数组高端为底的栈的入栈和出栈的算法。例3.1解答这个栈的栈顶指针top2是按相反的方向移动的，因此,在操作时要判断： 入栈时：top2-1=top1？ 出栈时：top2=n+1?入栈算法voidpush(S,intn,top1,top2,G){if(top2-1==top1)printf(“溢出!\n”);else{top2=top2-1;S[top2]=G; /*插入新元素*/}}出栈算法voidpop(S,intn,top1,top2,x){if(top2==n+1)printf(“下溢出!\n”);else{x=S[top2];top2=top2+1;}}栈的链式存储结构用一头结点单链表的第一个元素，头结点的指针表示栈顶，若一进栈序列a,b,c,其链式结构如下：headcba^其结构定义如下：typedefstructnode{elementtypedata;Structnode*next;}stacklnode;进栈Intpush(stacklnode*head,elementtypex){stacklnode*p;If((p==malloc(sizeof(structnode)))==nullPrintf(“没有空间”)；P->data=x;P->next=head->next;Head->next=p;Return(0);}出栈Intpop(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不调用其他函数。rtA1A2A3函数嵌套调用A1调用A2，A2调用A3时的返回地址在堆栈中的情况如右图所示。toprtSTACK2.堆栈在表达式计算中的应用

后缀表示法（逆波兰表示法）ab+，abc*+，ab+c*，……逆波兰表达式的特点：无括号，形式简洁，运算符的顺序与运算顺序相同。由于逆波兰表示法以上特点，其处理很方便。建立一个栈，对逆波兰表达式从左到右扫描，遇到运算分量则进栈，遇到运算符号则取其栈顶元素（二目或一目）运算，并把结果进栈。例：求–B*（C+D）的值。(其逆波兰表示：B@CD+*)3.数的转换把进制的数 n转换成八进制的数r。1.n除以r,商为S,输出余数。2.若s=0，则结束，输出序列的逆就是转换后的结果。3.n:=s,转1.例：把进制的数355转换成八进制的数。4.表达式中左右括号的匹配问题基本思想：若遇见左括号，则进栈；若右括号，则退栈，并比较是否匹配。假设下列形式都是合法的：（），[]，（[]），（[][]），（[（）]）；而下列是不合法的：（]，[），（[]]，……栈与递归递归：自己调用自己，分直接递归和间接递归例：阶乘n!=1当n=0时n!=n*(n-1)!当n>0时定义递归时要做到：1.调用必须越来越简单，并且能在有限步内结束。2.调用到最后一步时，必须有非递归的确切的定义。求n!的递归算法：Intfact(n){if(n==0)Return(1);Elsereturn(n*fact(n-1));}递归的执行调用时做以下工作：1.调用时必须保存本层所有的参数和返回地址等；2.给下层参数赋值；3.转移到被调用的函数入口。返回时做以下工作：1.保存被调用函数的计算结果。2.恢复上层参数。3.返回原处。例：阶乘Intfact(intn){if(n==0)return(1);Elsereturn(n*fact(n-1));}Fact(n){Top=1;m=n;While(m>1){S[top]=m;m=m-1top=top+1;}R=1;While(top>1){Top=top-1;R=R*s[top];}}斐波那契（Fibonacci)数的定义;希尔波特（D.Hilbert,1891)曲线的定义；塞平斯基（Sierpinski)曲线的定义；Hanoi塔稳问题；中断处理问题；……3.2队列（Queue）

队列是一种运算受限制的线性表，元素的添加在表的一端进行，而元素的删除在表的另一端进行。允许添加元素的一端称为队尾（Rear）；允许删除元素的一端称为队头（Front）。向队列添加元素称为入队，从队列中删除元素称为出队。新入队的元素只能添加在队尾，出队的元素只能是删除队头的元素，队列的特点是先进入队列的元素先出队，所以队列也称作先进先出表或FIFO（First-In-First-Out）表。队列的表示与堆栈类似，队列也可以简单的用一维数组表示。设数组名为Queue，其下标下界为1，上界为n。一般使用一个变量r指示队尾的下标值，叫做队尾指针；用另一个变量f指示队头的下标值，称为队头指针。队列中元素的数目等于零称为空队列。对列的顺序存储结构假定有A～F6个元素先后进入队列，但A、B,C三个元素已出队了，故队尾指针r=6，而队头指针f=3。对列的形式定义#definemaxsize<允许数组元素的最大个数>Typedefstruct{elementtypeelements[maxsize];Intfront;Intrear;}quetype;插入操作若Q.rear<>maxsize-1;/*对列不满*/则插入：Q.rear++:/*插入*/Q.elements[Q.rear]=x;删除操作若Q.front<>Q.rear/*对列非空*/则删除：Q.front++;/*删除*/return(Q.elements[Q.front])1.入队（insert）

当给队列插入元素时，队尾指针r后移而队头指针不动，但有一个情况例外，即当向空队列插入第一个元素时，队头指针与队尾指针同时由0变为1。

设用下标从1到n的数组Q表示队列，且已知待添加的元素在变量x中。入队函数voidinsert(Q,intn,front,rear,x){if(Q.rear==n-1)printf(“溢出!\n”);/*判断是否已到数组末端*/else{Q.rear++;Q.elementr[Q.rear]=x; /*插入元素*/}}2.出队（Delete）

当从队列删除元素时，队头指针f后移而队尾指针r不动，但也有一个情况例外，即当删除了最后一个元素，队列成为了空队列时，队头指针与队尾指针同时变为0。假设要求将出队的元素值赋给变量x。出队函数voidDelete(Q,intfront,rear,n,x){if(Qfront==Q.rear)printf(“下溢出!\n”);/*判断是否为空队列*/else{Q.front++:x=Q. elements[Q.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循环队列入队函数Intinsert(QuetypeQ,elementtypex){if((Q.rear+1)%maxsize==Q.front){printf(“队列溢出”);return(-1);}Q.rear=(Q.rear+1)%maxsize;Q.elements[Q.rear]=x;return(0);}

循环队列出队函数{if(Q.front==Q.rear){printf(“是空队列！\n”);return(-1);}Q.front=(Q.front+1)%maxsize;Return(Q.elements[Q.front];}

队列的应用

对于各种具有“先进先出”需排队处理的问题，都可以应用队列来解决。例如，操作系统在管理和分配系统资源时，大量的应用了队列这种数据结构。1)队列在输入/输出管理中的应用2)对CPU的分配管理返回例3.2对于循环队列，试写出求队列长度的算法。解1：设队列的最大元素个数为n，设一个计数器，将其初始值设为0。从队头开始，沿着队列顺序搜索，每搜索一个元素，计数器加1，直到队尾，计数器的最终值即为队列的长度。解2：利用队头指针与队尾指针也可求出队列的长度：当r≥f时，length=r-f当r<f时，length=n-(f-r)例3.2算法1intQue_Length(Queue,intf,r,n){intlength,k;length=0;k=f;while(k!=r){length++;k=(k+1)%n}return(length);}例3.2算法2intQue_lenrth(Queue,f,r,n){intlength=0;if(r>=f)length=r-f;else length=n-(f-r);return(length);}返回队列的链式存储结构增设两个指针，分别指向队列的头和尾，Head……

rear队列空时:head

rear

^^结点的定义Typedefstructnode{elementtypedata;Structnode*next;}Qlnode;插入结点：

Phead

rearrear

^x^删除结点：

Headrear

^插入算法Intinsertque(head,rear,x){p=malloc(sizeof(Qlnode));If(p=null){printf(“队列溢出”);Return(-1);}P->data=x;p->next=null;rear->next=p;rear=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)是由有限个字符组成的序列，又称为字符串(characterstring)，一般记为:s=ˊa1a2a3…anˊ其中s是串名，用单引号括起来的字符序列是串的值。ai(1<=i<=n)可以是字母、数字或其他字符；n为串中字符的个数，称为串的长度。一个长度为零的串称为空串，表示为s=ˊˊ。空格也是合法字符，它可以出现在较长的字符串中，也可以单独出现。例如A=ˊabcdefˊ就是长度为7的字符串，因为abc和def中间有一个空格字符。子串主串子串在主串中的位置两个串相等串的基本运算1.串赋值assignstring(t,chars)2.求串的长度lenstring(s)；3.判断两个串是否相等equalstring(s,t)；4.两个串的连接concatstring(s，t)；5.求子串在主串中的位置indexstring(s,t);6.求子串substring(s，pos，len)；返回4.2串的存储结构1.串的顺序存储:用一个一维数组存放串。

0123456……abcde.…..数据结构的定义：#definemax<允许串的最大长度>typedefstruct{charstring[max];intlen;}stringtype;或去掉变量len，在串的尾部放入一个特殊符号。例:求串s和t连接stringtypeconcatstring(stringtypes,t){inti;If(s.len+t.len>maxlen){printf(“连接后太长”);return(-1);}for(i=0;i<t.len;i++)s.string[s.len+i]=t.string[i];s.len=s.len+t.len;s.string[s.len]=‘\0’;return(0);}求子串：substring(s,pos,len,t)：求从串S的pos位置开始，长度为len的子串，并存放在t中。2。串的动态存储结构又分为链式存储结构和堆式存储结构

串的链式存储形式与一般的链表类似，是将存储区分成许多结点，每个结点有一个存放字符的域和一个存放指向下一个结点的指针域。一个存储结点可以存储1个或多个字符，通常一个结点为一块。单字符结点的串的链式存储结构多字符结点的串的链式存储结构结点类型定义如下：typedefstructLnode{chardata;structlnode*next；}stringnode例：设每个结点只含一个字符，串的连接算法如下：Blstringconcatstring(stringnode*s,*t){stringnode*p;/*把串t链到s的尾部*/p=s;If(p==null){p=t;return(s);}while(p->next<>null)p=p->next;p->next=t;return(s);}串的堆式存储结构基本思想：首先系统开辟一个足够大，连续的空间共串使用，串的堆式存储结构仍以一维数组的形式存放，但它们是在程序执行过程中动态分配的。在C语言中，用malloc和free来管理。当建立一个新串时，用malloc来申请一块空，成功，则返回其首地址；当不再使用时，用free来释放。typedefstruct{charstring;/*按串的长度分配*/Intstrlen;}Hstring;

两个串S和T连接算法Hstring*concat(s,t){char*p;intI,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;j<s->strlen;j++)/*复制S到P中*/p[i++]=s->string[j];for(j=0;j<t->strlen;j++)/*复制t到P中*/p[i++]=t->string[j];p[i]=‘\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。匹配算法intindexstring(stringtypes,t){inti=0;j=0;/*Brute-force算法*/while(i<s.len)&&(j<t.len){if(s.string[i]==t.string[j]){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’怎样判断一个串是中心对称呢？

基本思想：把串的前半部分入栈，扫描后半部分的每一符号，并与栈顶元素比较，若均相等，则为中心对称，否则，不是中心对称。算法如下：intsymstring(chars[],intn){stacktypestack;charc;intj;setstacknull(stack);/*将栈置空*/for(j=0;j<n/2;j++)/*S的前半部分进栈*/push(stack,s[j]）;for(j=n/2;j<n;j++){c=pop(stack);ifc<>s[j]return(false);}return(true);}2.从链接存储的串r1中的第i个字符开始，把连续j个字符组成的子串赋给r。linkstring*substring(linkstring*r1，inti，j){intk;linkstring*p，*q，*s，*r;p=r1;k=1;while(k<i&&p!=NULL){p=p->link;