《第十二讲：线性结构(线形表、栈和队列)》由会员分享，可在线阅读，更多相关《第十二讲：线性结构(线形表、栈和队列)（27页珍藏版）》请在金锄头文库上搜索。
1、第第12讲讲: 数据结构之数据结构之 线性结构线性结构数据结构之：线性结构数据结构之：线性结构v由由n个数据元素组成的有限序列个数据元素组成的有限序列v除头元素外，每个元素都有一个前趋除头元素外，每个元素都有一个前趋v除尾元素外，每个元素都有一个后继除尾元素外，每个元素都有一个后继例如例如: 26个英文字母表个英文字母表(a，b，Z)是一个线性表是一个线性表线性结构线性结构: 线性表、栈、队列线性表、栈、队列操作方法和要求的不同划分操作方法和要求的不同划分线性表的两种存储方式线性表的两种存储方式v顺序存储结构：顺序存储结构：数组数组连续存储连续存储易于定位，不易于插入和删除易于定位，不易于插入
2、和删除v链式存储结构：链式存储结构：链表链表非连续存储非连续存储易于插入和删除，不易于定位易于插入和删除，不易于定位一、线性表一、线性表 线性表是最常用且最简单的一种数据结构，它是由线性表是最常用且最简单的一种数据结构，它是由n个数个数据元素组成的有序集合。据元素组成的有序集合。数组与链表数组与链表链表链表数组数组数组的插入与删除数组的插入与删除123456789 10 11 126.5数组的插入与删除均需要移动后面的元素数组的插入与删除均需要移动后面的元素插入：插入：6.5删除：删除：4123456789 10 11 121234567891011121234567891011 12链表的插
3、入与删除链表的插入与删除无需移动任何元素无需移动任何元素插入：插入：删除：删除：顺序存储结构的元素访问顺序存储结构的元素访问 顺顺序序存存储储结结构构是是指指用用一一组组地地址址连连续续的的存存贮贮单单元元依依次次存存储储线线性性表表的的元元素素，通常用数组实现。通常用数组实现。 它是按首址（表中第它是按首址（表中第1个元素的地址）个元素的地址） 十十 位移来访问每一个元素。位移来访问每一个元素。loc(ai)a表中元素表中元素i的内存地址（的内存地址（1in）；）； loc(bi，j)b表中（表中（i，j）元素的内存地址（元素的内存地址（1in，1jm）；）；一维数组按照下标递增的顺序访问表
4、中元素一维数组按照下标递增的顺序访问表中元素 a1a2an loc(ai)=loc(a1)+(i-1)*k /k每个数据元素的长度每个数据元素的长度(字节或机器字字节或机器字)； 首址首址 位移位移 二维数组有按照二维数组有按照先行后列先行后列和和先列后行先列后行的顺序访问表中元素：的顺序访问表中元素： b1.n，1.m先行后列先行后列: loc(bi，j)=loc(b1，1)+(m*(i-1)+(j-1)*k k每个数据元素的长度；每个数据元素的长度； 首址首址 位移位移 先列后行先列后行: loc(bi，j)=loc(b1，1)+(n*(j-1)+(i-1)*k k每个数据元素的长度；每个
5、数据元素的长度； 首址首址 位移位移 一一个个向向量量第第一一个个元元素素的的存存储储地地址址是是100，每每个个元元素素的的长长度度是是2，则则第第5个个元素的地址是（元素的地址是（ ）。）。(NOIP8)A）110 B）108 C）100 D）109已知数组中已知数组中A中，每个元素中，每个元素A（I，J）在存贮时要占在存贮时要占3个字节，设个字节，设I从从1变变化到化到8，J从从1变化到变化到10，分配内存时是从地址，分配内存时是从地址SA开始连续按行存贮分配的。开始连续按行存贮分配的。试问：试问：A（5，8）的起始地址为（）的起始地址为（）(NOIP6)A.SA+141B. SA+18
6、0C. SA+222D. SA+225一个文本屏幕有一个文本屏幕有25列及列及80行，屏幕的左上角以（行，屏幕的左上角以（1，1）表示，而右下）表示，而右下角则以（角则以（80，25）表示，屏幕上每一个字符占用两字节（）表示，屏幕上每一个字符占用两字节（byte），），整个屏整个屏幕则以线性方式存储在电脑的存储器内，从屏幕左上角开始，位移为幕则以线性方式存储在电脑的存储器内，从屏幕左上角开始，位移为0，然后逐列逐列存储。求位於屏幕（然后逐列逐列存储。求位於屏幕（X，Y）的第一个字节的位移是（）的第一个字节的位移是（）(NOIP6)A.（Y*80+X）*2-1B.（Y-1）*80+X-1）*2C
7、.（Y*80+X-1）*2D.（Y-1）*80+X）*2-1(4)、设有一个、设有一个10阶的对称矩阵阶的对称矩阵A，采用压缩存储方式按行将矩阵中下三，采用压缩存储方式按行将矩阵中下三角部分的元素存入一维数组角部分的元素存入一维数组B 中，中，A00存入存入B0中，则中，则A85在在B 中（中（ ）位置。）位置。A32 B33 C41 D65应用举例：应用举例：1、插入排序。、插入排序。2、两个有序线性表的合并。、两个有序线性表的合并。 输入输入: 1 4 8 10 2 3 7 9 11 13 输出：输出： 1 2 3 4 7 8 9 10 11 133、两个多项式的合并。、两个多项式的合并。
8、 输入：输入： 1+x+2X2-x3-30X5 2x+x2+x3 输出：输出： 1+3x+3x2-30x5二、栈二、栈栈的定义栈的定义 栈是一种栈是一种“后进先出后进先出”线性表。线性表。 对它的插入和删除都限制地表的同一端进行。这一端叫做栈的对它的插入和删除都限制地表的同一端进行。这一端叫做栈的“顶顶”，另一端则叫做栈的，另一端则叫做栈的“底底”。 特点特点:后进先出后进先出(LIFO)、或者先进后出（、或者先进后出（FILO）栈底栈底325进栈进栈进栈进栈进栈进栈出栈出栈出栈出栈出栈出栈不一定进栈结束后才出栈，进出栈可不一定进栈结束后才出栈，进出栈可交叉交叉进行进行【竞赛试题竞赛试题】 1
9、、一一个个栈栈的的输输入入顺顺序序为为1、2、3、4、5，下下列列序序列列中中可可能能是是栈栈的的输出序列是输出序列是 ( )。 (A)54312 (B)2415 (C)21543 (D)12532、若已知一个栈的入栈顺序是、若已知一个栈的入栈顺序是1，2，3，n，其输出序列其输出序列为为P1，P2，P3，Pn，若，若P1是是n，则，则Pi是是( ) (NOIP7)A)i B)n-1 C)n-i+1 D)不确定不确定3、设有一个顺序栈、设有一个顺序栈S，元素元素S1, S2, S3, S4, S5, S6依次依次进栈，如果进栈，如果6个元素的出栈顺序为个元素的出栈顺序为S2, S3, S4,
10、S6, S5, S1，则顺序栈的容量至少应为多少？则顺序栈的容量至少应为多少？A)3 B) 4 C) 5 D) 64、向顺序栈中压入新元素时，应当（、向顺序栈中压入新元素时，应当（ ）。）。A先移动栈顶指针，再存入元素先移动栈顶指针，再存入元素 B先存入元素，再移动栈顶指针先存入元素，再移动栈顶指针C先后次序无关紧要先后次序无关紧要 D同时进行同时进行假假设设栈栈中中表表目目数数的的上上限限为为m，所所有有表表目目都都具具有有同同一一类类型型stype，则可以用下列方式定义栈：则可以用下列方式定义栈： Const m=栈表目数的上限；栈表目数的上限；Var s： array1m of styp
11、e ；栈栈 t： integer； 栈顶指针，初始值为栈顶指针，初始值为栈的基本操作栈的基本操作栈的基本操作：栈的基本操作： 初始化（初始化（init）、）、 进栈（进栈（push）、）、 出栈（出栈（pop）和）和 读取栈顶元素（读取栈顶元素（top）。）。1） 过程过程init(s,t)procedure init; begin t:=0; end;2)、过程过程push(x)往栈往栈s中压入一个值为中压入一个值为x的数据：的数据： procedure push（ x：stype)； begin t:=t+1； st:=x； x入栈入栈 end；Push3)、函数、函数pop从栈中弹出一个
12、元素从栈中弹出一个元素 function pop ：stype； begin pop:=st； 栈顶元素出栈栈顶元素出栈 t:=t-1； 指针下移指针下移 end；pop4)、函数、函数top读栈顶元素读栈顶元素 function top ：stype； begin if t=0 then writeln (stack empty) else top:=st； 返返回回栈栈顶顶元元素素 end；top栈的应用栈的应用1、后缀表达式求值、后缀表达式求值【问题描述：问题描述：】 后缀表达式是指这样的一个表达式：式中不再引用括号，运算符号放在两个后缀表达式是指这样的一个表达式：式中不再引用括号，运算
13、符号放在两个运算对象之后，所有计算按运算符号出现的顺序，严格地由左而右新进行（不用运算对象之后，所有计算按运算符号出现的顺序，严格地由左而右新进行（不用考虑运算符的优先级）。考虑运算符的优先级）。如：如：3*(52)+7对应的后缀表达式为：对应的后缀表达式为：352-*7+。为表达式的结为表达式的结束符号。束符号。.为操作数的结束符号。为操作数的结束符号。352-*7+ =33*7+=97+=16 运算符号：运算符号：+、-、*、/ / 运算只取整数部分。采用运算只取整数部分。采用 div 即可即可【输入：输入：】后缀表达式（长度不超过后缀表达式（长度不超过100）。）。【输出：输出：】表达式
14、的值。表达式的值。说明：运算的中间结果与最后的结果数据范围：说明：运算的中间结果与最后的结果数据范围：-1000000000，1000000000。【样例输入：样例输入：】352-*7+【样例输出：样例输出：】16中缀表达式转化为后缀表达式中缀表达式转化为后缀表达式方法一：不会栈操作方法一：不会栈操作算法分析：算法分析：后缀表达式为后缀表达式为A:stringA:string; ;数组数组S:S:保存操作数和中间计算结果。保存操作数和中间计算结果。s s的类型为的类型为longintlongint。 1)1)、从左向右处理、从左向右处理a a中的每一个字符：中的每一个字符： 2)2)、如果遇到
15、一个操作数，就送入、如果遇到一个操作数，就送入数组数组s s中；中； 如如果果遇遇到到一一个个运运算算符符，就就从从数数组组s s中中取取出出后后面面的的两两个个操操作作数进行计算，然后将计算结果重新放入到数组中。数进行计算，然后将计算结果重新放入到数组中。 3)3)、直到遇到、直到遇到 处理结束。处理结束。这时数组中这时数组中s s剩下唯一的元素即是计算结果。剩下唯一的元素即是计算结果。方法二：利用栈结构方法二：利用栈结构算法分析：算法分析：假设后缀的表达式为假设后缀的表达式为A A，操作数和计算结果存放在栈操作数和计算结果存放在栈S S中。中。 1)1)、从左向右处理、从左向右处理a a中
16、的每一个字符：中的每一个字符： 2)2)、如果遇到一个操作数，就送入栈、如果遇到一个操作数，就送入栈s s中；中； 如如果果遇遇到到一一个个运运算算符符，就就从从栈栈s s中中取取出出栈栈顶顶的的两两个个操操作作数数进行计算，然后将计算结果重新压栈。进行计算，然后将计算结果重新压栈。 3)3)、直到遇到、直到遇到 处理结束。处理结束。 这时栈这时栈s s顶的元素即是计算结果。顶的元素即是计算结果。2、括号匹配、括号匹配【问题描述：问题描述：】判断包含有括号判断包含有括号，的字符串是否是合法匹配。的字符串是否是合法匹配。例如以下是合法的括号匹配：例如以下是合法的括号匹配：(), , (), (
17、), () , ()()以下是不合法括号匹配的：以下是不合法括号匹配的：(, , , )(, ( , ()，( )【输入：输入：】一行，字符串（长度范围：一行，字符串（长度范围：1，200）。）。【输出：输出：】如果字符串中括号匹配是合法的输出如果字符串中括号匹配是合法的输出“yes”，不合法的输出，不合法的输出“no”。【样例样例1输入：输入：】abcabbmaa【样例样例1输出：输出：】yes【样例样例2输入：输入：】abcabbmaa【样例样例2输出：输出：】no分析：分析：遇到左括号进栈；遇到左括号进栈；遇到右括号，出栈，看是否和右括号匹配，如果匹配继续遇到右括号，出栈，看是否和右括号匹配，如果匹配继续看下一个括号，否则停止，输出看下一个括号，否则停止，输出no即可。即可。栈底栈底325进栈进栈进栈进栈进栈进栈出栈出栈出栈出栈出栈出栈352栈顶栈顶加入一个数加入一个数4取出栈顶元素取出栈顶元素再取出栈顶元素再取出栈顶元素6栈底栈底
