数据结构栈、查找、串和队列ppt

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

1、版权所有,1997(c)DaleCarnegie&Associates,Inc.数据结构朱振元1版权所有,1997(c)DaleCarnegie&Associates,Inc.数据结构栈朱振元2栈的初步认识栈是限定只能在表的一端进行操作的线性表。特点：’后进先出’，栈又称作后进先出表（LIFO，即LastInFirstOut）。ana2a1入栈出栈栈顶栈底3一般表示及基本术语栈是限定只能在表的一端进行操作的线性表。S=(a1,a2,……ai-1,ai,ai+1,……an)栈顶（top）在表中允许插入和删

2、除的一端栈底（botton）不允许插入和删除的一端入栈（push）向栈顶插入一个元素的操作出栈（pop）从栈顶取出一个元素的操作栈一经确定，则栈底便固定不变，而栈顶随入栈、出栈操作的执行不断地变化。特点：’后进先出’，栈又称作后进先出表（LIFO，即LastInFirstOut）。4主要的基本操作入栈push（s）向栈s的栈顶插入一个元素出栈pop(s）从栈s的栈顶取出一个元素取元素gettop(s）返回栈s的栈顶元素求长度current-size(s）求栈s的元素个数判空empty(s）判栈s是否为空

3、栈清空clear(s）将栈s清空5栈的主要应用实现递归过程。必须设置一个数据栈来存放递归过程中的参数与局部变量等信息回塑法求解问题。为了达到正确的目的地，必须设置一个栈来记录已走过的路径上的每一点的有关信息表达式的翻译。必须设置一个栈来存放暂不能处理的那些符号或被用于检查表达式中的各种括号是否配对。6栈的存储方式栈在计算机中的存储方式可分为顺序存储方式和链式存储方式二种。栈的存储方式顺序顺序栈链式链栈7顺序栈的结构形式用一组地址连续的存储单元来依次存储栈中的各个元素。Top与栈的状态的关系ana1Ele

4、m[0..max-1]Max-1top0Top＝2Top＝4Top=-18顺序栈的类型定义constintmax＝栈中允许存放元素个数的最大值；typedefstruct{elemtpelem[max];inttop;}sqstktp;sqstktps;s.top表示栈顶指示器，s.elem[s.top]表示栈顶元素9链栈结构形式及特点顺序栈的不足之处:难以为它确定适当的存储空间的大小链栈的结构特点:使用一个链表来表示一个栈，Datanext栈顶NULL栈底10链栈结构形式及特点使用一个链表来表示一个栈

5、，链和栈之间存在以下的对应关系：链尾元素相当于栈底元素链头元素相当于栈顶元素，链头指针相当于栈顶指针。入栈操作相当于从链头插入一个元素出栈操作相当于从链头删除一个元素11链栈的类型定义structnode{elemtpdata;structnode*next;}；typedefstructnodenodetp;typedefstructnode*link;typedeflinklinked_stack;链栈可以用一个指向栈顶的指针型变量top来表示，其定义如下：linked_stacktop;当top＝

6、NULL时，这个栈就成为空栈，当top不等于NULL时，就可以通过top指针来访问栈顶元素。datanext12顺序栈的类定义constintdeflen=10;templateclassTsxz{private:elemtp*elem;inttop,maxlen;public:Tsxz(intmaxsz=deflen);~Tsxz(){delete[]elem;};boolpush(elemtpel);elemtppop();elemtpgettop();boolfull()

7、{returntop==-1;};boolempt(){returntop==maxlen-1;};};13顺序栈的构造函数及析构函数templateTsxz::Tsxz(intmaxsz){maxlen=maxsz;top=-1;elem=newelemtp[maxlen];};功能：按指定的长度分配顺序表空间，并设置maxlen及top变量初值~Tsxz(){delete[]elem;};功能：释放已分配的存储空间14顺序栈的入栈操作操作的表示形式templ

8、ateboolTsxz::push(elemtpel);参数：el表示入栈的元素，其类型为元素类型elemtp功能：在顺序栈中插入元素el，并使el成为栈顶。处理过程：（1）判是否栈满，若栈满则返回false，否则：（2）栈顶指针加1，将el送入栈顶并返回true。15入栈操作处理过程：(1)判是否栈满，若栈满则返回false，否则：(2)栈顶指针加1，将X送入栈顶并返回trueS.topS.ele