【精品数据结构】栈和队列3.ppt

《【精品数据结构】栈和队列3.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、DATA1065865姓名学号成绩班级李红976105995机97.6ABCDEFG数据结构第二章 数据结构与算法(续)2.3栈和队列栈和队列是两种特殊的线性表，它们是运算时要受到某些限制的线性表，故也称为限定性的数据结构。２.3.1栈2.3.1.1栈的定义栈：限定只能在表的一端进行插入和删除的特殊的线性表设栈s=（a1，a2，...,ai，...，an），其中a1是栈底元素，an是栈顶元素。a1a2….an进栈出栈栈顶栈底２.3.1栈2.3.1.1栈的定义栈：限定只能在表的一端进行插入和删除的特殊的线性表设栈s=（a1，a2，...,ai，...，an），其中a1是栈底元素，a

2、n是栈顶元素。栈顶（top)：允许插入和删除的一端；约定top始终指向新数据元素将存放的位置。栈底（bottom):不允许插入和删除的一端。a1a2….an进栈出栈栈顶栈底栈中的运算：1.设置空栈；2.插入一个新的栈顶元素3.删除栈顶元素；4.读取栈顶元素。设数组S是一个顺序栈，栈的最大容量stacksize=4，初始状态top=010S[4]2310bases[top]=xtop=top+1top102530S[4]2310topbasetop=top-1x=s[top]栈空10进栈30出栈S[4]2310Top=0top栈满top=stacksize10253040S[4]2

3、310top=4base2.3.1.2栈的存储结构顺序栈、链栈a2a1a1a2top顺序栈：用顺序存储结构表示的栈。顺序栈用一组连续的存储单元存放自栈底到栈顶的数据元素，一般用一维数组表示，设置一个简单变量top指示栈顶位置，称为栈顶指针，它始终指向待插入元素的位置。·进栈算法#definestatcksize100intpush(ints[],intx,int*ptop){inttop;top=*ptop;if(top==stacksize){printf(“overflow”);return(0);}else{s[top]=x;*ptop=++top;/*实际栈顶指针加1*/

4、return(1);}}通过地址传递，用ptop带回实际栈顶指针a2a3a4987654321a10top出栈算法：intpop(ints[],int*ptop,int*py){inttop;top=*ptop;if(top==0){printf(“stackempty”);return(0);}else{--top;*py=s[top];/*返回出栈元素*/*ptop=top;return(1);}}通过地址传递，用ptop带回实际栈顶指针通过指针变量py带回出栈元素栈sa2a3a4987654321a10topx∧top栈底（2）链栈用指针来实现的栈叫链栈。栈的容量事先不能

5、估计时采用这种存储结构。链栈的类型说明如下：Typedefstructlnode{intdata；structlnodenext；}lnode，Lstack；进栈算法intlpush(Lstacks,inte){p=(Lstack)malloc(sizeof(lnode));p->data=e;p->next=s;s=p;return(1);}∧baseS栈s进栈元素e进栈算法intlpush(Lstacks,inte){p=(Lstack)malloc(sizeof(lnode));p->data=e;p->next=s;s=p;return(1);}∧PbaseS进栈算法

6、intlpush(Lstacks,inte){p=(Lstack)malloc(sizeof(lnode));p->data=e;p->next=s;s=p;return(1);}∧PbaseSe进栈算法intlpush(Lstacks,inte){p=(Lstack)malloc(sizeof(lnode));p->data=e;p->next=s;s=p;return(1);}∧PbaseSe进栈算法intlpush(Lstacks,inte){p=(Lstack)malloc(sizeof(lnode));p->data=e;p->next=s;s=p;return(1);

7、}∧PbaseSSer主程序srrrs子程序1rst子程序2rst子程序32.3.1.3栈的应用(1)  过程的嵌套(2)递归算法：1(n=0,1)n!=n(n-1)！(n>1)函数的递归调用1.定义：在调用一个函数的过程中直接或间接地调用该函数本身。直接调用intf(x)intx;{inty,z;…..z=f(x);……return(2*z);}f函数调用f函数intf1(x)intx;{inty,z;…..z=f2(y);……return(2*z);}intf2(t)intt