两种存储结构比较线性表

第三章栈与队列两种重要的，限定操作的线性结构。第三章栈与队列两种重要的，限定操作的线性结构。1§3.1栈栈的例子：操作系统中中断现场的保留等。一、定义：限定只能在表尾进行插入或删除操作的线性表。修改原则：后进先出（LIFO）§3.1栈栈的例子：操作系统中中断现场的保留等。2练习：设进栈顺序为1、2、3、4，请说出以下的出栈顺序是否可能？A、1234B、4312C、2143D、3214E、3421F、3412练习：设进栈顺序为1、2、3、4，请说出以下的出栈顺序是否可3二、栈的基本操作进栈、出栈、清空、求栈顶元素……

接下来学习线索：存储方式：顺序，链式行为特征应用实例二、栈的基本操作进栈、出栈、清空、求栈顶元素……4三、栈的顺序存储结构数组定义栈：stack[max]max-1

…10规定：top指向栈顶元素所在位置初始：top=-1（空栈）空栈：top=-1，出栈下溢栈满：top=max-1，进栈上溢三、栈的顺序存储结构数组定义栈：stack[max]max-5进栈：开始top==max-1?top=top+1stack[top]=x结束上溢处理NY栈的顺序存储结构有栈满的情况，有可能出现上溢的致命错误。多栈共享空间是解决问题的折中方法，但不能完全解决。进栈：开始top==max-1?top=top+1stack6出栈：开始top==-1?x=stack[top]top=top-1结束下溢处理NY出栈：开始top==-1?x=stack[top]top=t7四、栈的链式存储结构规定：top指向栈顶元素地址datalink设指针域指向次顶结点四、栈的链式存储结构规定：top指向栈顶元素地址datali8判断空栈进栈出栈利用链式存储结构存储栈，可解决栈的致命错误——上溢基本操作：判断空栈基本操作：9五、栈的应用1、递归调用一个子程序调用自身，称为递归调用。例：阶乘的计算n!=1(n=0,1)n*(n-1)!(n>1)五、栈的应用1、递归调用n!=1(n=0,1)n*(n-10五、栈的应用2、计算表达式（1）由计算规则得算符优先关系表3+5*33+5+5θ1：先来的算符θ2：后来的算符=<<<>>>>><>>><>>（\-+）*-+θ1

θ2五、栈的应用2、计算表达式=<<<>>>>><>>><>>（11（2）原理两工作栈：一个算符栈，一个操作数栈a.读取到操作数，直接入操作数栈b.读取到运算符，取运算符栈栈顶元素与该算符比较优先级：

“<”：读取符号入运算符栈；

“>”：运算符栈出一元素，操作数栈出两元素，运算后，结果放回操作数栈；

“=”：运算符栈出一元素，与之相抵消。（2）原理两工作栈：一个算符栈，一个操作数栈12（2）原理

算法结束标志：运算符栈为空，操作数栈有一元素，即为结果。（2）原理算法结束标志：运算符栈为空，操作数13上机：输入一包含“(”和“)”的字符串，检测括号是否匹配（其中括号中能嵌套括号），并输出括号是否匹配的信息（匹配、缺少左括号、缺少右括号）；上机：输入一包含“(”和“)”的字符串，检测括号是否匹配（其14分析：gets(fun)while(fun[i]!=’\0’){if(fun[i]==’(‘)：入栈；if(fun[i]==‘)’)：if栈空：错，缺左边，return；else出栈；i=i+1;}如栈空对！！！否则错，缺少右边分析：gets(fun)15§3.2队列队列的例子：排队等。一、定义：限定只能在表的一端进行插入，在表的另一端进行删除的线性表。修改原则：先进先出（FIFO）§3.2队列队列的例子：排队等。16二、队列的基本操作进队、出队、清空、求队头元素……

接下来学习线索：存储方式：链式，顺序行为特征二、队列的基本操作进队、出队、清空、求队头元素……17三、队列的链式存储结构需设两个指针：front：头结点地址rear：队尾结点地址c∧dba……frontrear三、队列的链式存储结构需设两个指针：c∧dba……front18基本操作：rear=front；front->link=NULL;∧frontrear1、初始化队列2、进队从队尾进队列基本操作：rear=front；∧frontrear1、初始19基本操作：2、进队从队尾进队列3、出队只要队列不空，从队头出；被删除结点如为队尾结点，队列置空。基本操作：2、进队20四、队列的顺序存储结构数组定义队列：queue[max]max-1

…10规定：front指向队头元素位置rear指向队尾元素的下一个空位初始：front=rear=0队空：front=rear队满：rear=max四、队列的顺序存储结构数组定义队列：queue[max]ma21四、队列的顺序存储结构假溢出的问题：用循环队列来解决下一个rear计算公式：rear=（rear+1）modmax循环队列队空队满标志冲突的问题：以牺牲一个存储空间为代价，当判断到（下一个rear==front）时，即认为队满。实际上，max个空间只存放了（max-1）个元素四、队列的顺序存储结构假溢出的问题：用循环队列来解决循环队列22循环队列队空、队满标志：队满：（rear+1）modmax==front队空：front=rear

冲突解决！！循环队列队空、队满标志：23练习：设循环队列容量为70（序号0~69），现经过一系列的入队和出队后，问下列情况下循环队列中各有几个元素？（1）front=14，rear=21（2）front=23，rear=12练习：设循环队列容量为70（序号0~69），现经过一系列的入24§3.3两种存储结构比较（线性表）：顺序存储（数组）：思想简单，静态管理，定位方便；但会有溢出问题，有时会有大量冗余，系统开销大。链式存储（链表）：操作方便，无冗余，解决溢出问题。§3.3两种存储结构比较（线性表）：顺序存储（数组）：25两个限定操作、用途广泛的线性表：堆栈：LIFO队列：FIFO两个限定操作、用途广泛的线性表：26设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次入栈，如果出栈顺序为s2,s3,s4,s6,s5,s1，栈的容量至少为（）。A.2 B.3C.5 D.6练习:B设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次入27设有一栈已有a1,a2,a3三个元素,栈顶为a3,a4正等待入栈,则以下序列是不可能的出栈序列是()。A.a3,a1,a4,a2 B.a3,a2,a4,a1C.a3,a4,a2,a1 D.a4,a3,a2,a1A设有一栈已有a1,a2,a3三个元素,栈顶为a3,a4正等待28()在链队中,即使不设置尾指针也能进行入队操作;()在带头结点的链队中进行出队操作,不会改变头结点地址front的值;()循环队列中元素个数为rear-frontTTF()在链队中,即使不设置尾指针也能进行入队操作;TTF29以S和X分别代表入栈和出栈，对输入序列a、b、c、d、e进行一系