第三章 特殊线性表一栈、队、串
1
§31栈 §3.1.1栈的逻辑结构 )基本概念 栈是一种限定仅在表的一端进行插入与删除的线性表 允许进行插入与删除的这一端称为栈顶,而另一端称为栈底 不含元素的空表称为空栈 插入与删除分别称进栈与出栈。 栈也称作先进后出( First in last out)的线性表,简称FILO表 a1 a a3 a 进栈 4 出栈 栈底 栈 顶 图栈示意图 2
2 §3.1 栈 • (一)基本概念 • 栈是一种限定仅在表的一端进行插入与删除的线性表 • 允许进行插入与删除的这一端称为栈顶，而另一端称为栈底 • 不含元素的空表称为空栈 • 插入与删除分别称进栈与出栈。 • 栈也称作先进后出（First In Last Out）的线性表，简称FILO表 §3.1.1 栈的逻辑结构 a1 a2 a3 a4 … an 栈 底 栈 顶 进栈 出栈 图 -栈示意图
§311栈的逻辑结构 (一)基本概念 ·栈应用的例子 火车扳道站 进入单车道死胡同的汽车 记录中断返回地址(断点)的结构
3 • (一)基本概念 • 栈应用的例子 –火车扳道站 –进入单车道死胡同的汽车 –记录中断返回地址（断点）的结构 §3.1.1 栈的逻辑结构
s311栈的逻辑结构 ()基本概念 ·可能的出栈次序 ·设n=3,按1,2,3的次序进栈,则可能的出栈 次序为 123、132、213、231、321 不可能的次序是: 312 对任意元素k,若它后面有小于它的元素,则 这些小于它的元素必须以“逆序”出现
4 §3.1.1 栈的逻辑结构 • (一)基本概念 • 可能的出栈次序 • 设n=3，按1,2，3的次序进栈，则可能的出栈 次序为 1 2 3、1 3 2、2 1 3、2 3 1、3 2 1 不可能的次序是： 3 1 2 • 对任意元素k，若它后面有小于它的元素，则 这些小于它的元素必须以“逆序”出现
s311栈的逻辑结构 (二)基本操作 ·Init(s):初始化栈s。设定一个空栈,栈的所有其它操作仅在此 操作执行(或隐含执行)之后才能进行。 Empty(s):判定函数。若栈s为空,返回“真”,否则返回 假 Push(s,x):入栈函数。将元素x放到栈顶上,栈溢出时应返回特 殊标志。 Pop(S):出栈函数。栈sS不空时,将栈顶元素摘除,并返回该元 素。否则触发异常。 GetTop(s):读栈顶元素函数。与Pop(s)类似,但不摘取栈顶元素 · Clear(s):清除操作。使栈s重新变为一个空栈。这里,s是个已 存在的栈。 Len(s):求长度函数。返回栈s中元素个数
5 §3.1.1 栈的逻辑结构 • (二) 基本操作 • Init(s)：初始化栈s。设定一个空栈，栈的所有其它操作仅在此 操作执行（或隐含执行）之后才能进行。 • Empty(s)：判定函数。若栈s为空，返回“真” ，否则返回 “假”。 • Push(s,x)：入栈函数。将元素x放到栈顶上，栈溢出时应返回特 殊标志。 • Pop(S)：出栈函数。栈s不空时，将栈顶元素摘除，并返回该元 素。否则触发异常。 • GetTop(s)：读栈顶元素函数。与Pop(s)类似，但不摘取栈顶元素。 • Clear(s)：清除操作。使栈s重新变为一个空栈。这里，s是个已 存在的栈。 • Len(s)：求长度函数。返回栈s中元素个数
s311栈的逻辑结构 (三)基本操作使用示例 编写一个带编辑功能的从终端上接收字符的程序 若依次输入 “#代表退格; Cgf# HIna##NA “@”表示作废 则相当于输入 CHINA 若依次输入 chiachina ·则相当于输入CHNA
6 §3.1.1 栈的逻辑结构 • (三) 基本操作使用示例 • 编写一个带编辑功能的从终端上接收字符的程序 • 若依次输入： Cg#HIna##NA 则相当于输入CHINA • 若依次输入 chi@CHINA • 则相当于输入CHINA “#”代表退格； “@”表示作废
Init(s) ch= getcho,∥读入一个字符 while(ch=EOF)∥当未读入结束符时,一直循环 switch(ch) case '# Pop(s); break case(a Clear(s); break default Push(s, ch ch=getcho
7 … … Init(s); ch = getch(); //读入一个字符 while (ch!=EOF) //当未读入结束符时，一直循环 { switch(ch) { case '#' : Pop(s); break; case '@' : Clear(s); break; default: Push(s, ch); } ch = getch(); }
§3.11栈的逻辑结构 (四)栈抽象类 template class STacke protected long len ublic long getLen(void)return len;) char IsEmpty(return (len<=0)? 1: 0;) virtual TElem& push(telem &elem)=0 virtual TElem& pop (void)=0 virtual TElem& GetTop(void)=0
8 §3.1.1 栈的逻辑结构 • (四)栈抽象类 template class TStack0 { protected: long len; public: long GetLen (void) {return len; }; char IsEmpty ( ) {return (len<=0)? 1:0; }; virtual TElem& Push (TElem &elem) =0; virtual TElem& Pop (void) =0; virtual TElem& GetTop (void) =0;
s311栈的逻辑结构 (四)栈抽象类 virtual TElem& rollDown(=0 virtual TElem& rollup (=0 virtual void Clear(=0;
9 §3.1.1 栈的逻辑结构 • (四)栈抽象类 virtual TElem& RollDown ( ) =0; virtual TElem& RollUp ( ) =0; virtual void Clear ( ) =0; }
s3.12栈的顺序存贮结构 (-)存贮方法 ·栈是一种特殊的线性表,本节先介绍顺序存贮方式 用一维数组模拟连续的存贮空间 ·用一个量指示插入/删除端的位置,一般称该量为栈顶 指针 元素空间: al a az a 栈顶指示器: 图栈顺序存储结构 假设栈底在地址小的一端
10 §3.1.2 栈的顺序存贮结构 • (一) 存贮方法 • 栈是一种特殊的线性表，本节先介绍顺序存贮方式 • 用一维数组模拟连续的存贮空间 • 用一个量指示插入/删除端的位置，一般称该量为栈顶 指针 a1 a2 a3 a4 … … an 元素空间： 栈顶指示器： 图 - 栈顺序存储结构 假设栈底在地址小的一端