第十二讲：线性结构(线形表、栈和队列).ppt

1、第12讲: 数据结构之 线性结构,数据结构之：线性结构,由n个数据元素组成的有限序列 除头元素外，每个元素都有一个前趋 除尾元素外，每个元素都有一个后继,例如: 26个英文字母表(a，b，Z)是一个线性表,线性结构: 线性表、栈、队列,操作方法和要求的不同划分,线性表的两种存储方式,顺序存储结构：数组 连续存储 易于定位，不易于插入和删除 链式存储结构：链表 非连续存储 易于插入和删除，不易于定位,一、线性表,线性表是最常用且最简单的一种数据结构，它是由n个数据元素组成的有序集合。,数组与链表,链表,数组,数组的插入与删除,1,2,3,4,5,6,7,8,9,10,11,12,6.5,数组的插

2、入与删除均需要移动后面的元素,插入： 6.5,删除： 4,1,2,3,4,5,6,7,8,9,10,11,12,1,2,3,4,5,6,7,8,9,10,11,12,1,2,3,4,5,6,7,8,9,10,11,12,链表的插入与删除,无需移动任何元素,插入：,删除：,顺序存储结构的元素访问 顺序存储结构是指用一组地址连续的存贮单元依次存储线性表的元素，通常用数组实现。 它是按首址（表中第1个元素的地址） 十 位移来访问每一个元素。 loc(ai)a表中元素i的内存地址（1in）； loc(bi，j)b表中（i，j）元素的内存地址（1in，1jm）； 一维数组按照下标递增的顺序访问表中元素

3、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每个数据元素的长度； 首址 位移,一个向量第一个元素的存储地址是100，每个元素的长度是2，则第5个元素的地址是（ ）。(NOIP8) A）110 B）108 C）100 D）109 已知数组中A中，每

4、个元素A（I，J）在存贮时要占3个字节，设I从1变化到8，J从1变化到10，分配内存时是从地址SA开始连续按行存贮分配的。试问：A（5，8）的起始地址为（）(NOIP6)A.SA+141B. SA+180C. 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.（Y*80+X

5、-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 13 3、两个多项式的合并。 输入： 1+x+2X2-x3-30X5 2x+x2+x3 输出： 1+3x+3x2-30 x5,二、栈,栈的定义 栈是一种“后进先出”线性表。 对它的插入和删除都限制地表的同一端进行。这

6、一端叫做栈的“顶”，另一端则叫做栈的“底”。 特点:后进先出(LIFO)、或者先进后出（FILO）,3,2,5,进栈,进栈,进栈,出栈,出栈,出栈,不一定进栈结束后才出栈，进出栈可交叉进行,【竞赛试题】 1、一个栈的输入顺序为1、2、3、4、5，下列序列中可能是栈的输出序列是 ( )。 (A)54312 (B)2415 (C)21543 (D)1253,2、若已知一个栈的入栈顺序是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依

7、次进栈，如果6个元素的出栈顺序为S2, S3, S4, S6, S5, S1，则顺序栈的容量至少应为多少？ 3 B) 4 C) 5 D) 6 4、向顺序栈中压入新元素时，应当（ ）。 A先移动栈顶指针，再存入元素 B先存入元素，再移动栈顶指针 C先后次序无关紧要 D同时进行,假设栈中表目数的上限为m，所有表目都具有同一类型stype，则可以用下列方式定义栈： Const m=栈表目数的上限； Var s： array1m of stype ；栈 t： integer； 栈顶指针，初始值为,栈的基本操作,栈的基本操作： 初始化（init）、 进栈（push）、 出栈（pop）和 读取栈顶元素（t

8、op）。 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；Push,3)、函数pop从栈中弹出一个元素 function pop ：stype； begin pop:=st； 栈顶元素出栈 t:=t-1； 指针下移 end；pop,4)、函数top读栈顶元素 function top ：stype； begin if t=0 then writeln (stack empty) el

9、se top:=st； 返回栈顶元素 end；top,栈的应用,1、后缀表达式求值 【问题描述：】 后缀表达式是指这样的一个表达式：式中不再引用括号，运算符号放在两个运算对象之后，所有计算按运算符号出现的顺序，严格地由左而右新进行（不用考虑运算符的优先级）。 如：3*(52)+7对应的后缀表达式为：352-*7+。为表达式的结束符号。.为操作数的结束符号。 352-*7+ =33*7+=97+=16 运算符号：+、-、*、/ / 运算只取整数部分。采用 div 即可 【输入：】 后缀表达式（长度不超过100）。 【输出：】 表达式的值。 说明：运算的中间结果与最后的结果数据范围：-100000

10、0000，1000000000。 【样例输入：】 352-*7+ 【样例输出：】 16,中缀表达式转化为后缀表达式,方法一：不会栈操作 算法分析： 后缀表达式为A:string; 数组S:保存操作数和中间计算结果。s的类型为longint。 1)、从左向右处理a中的每一个字符： 2)、如果遇到一个操作数，就送入数组s中； 如果遇到一个运算符，就从数组s中取出后面的两个操作数进行计算，然后将计算结果重新放入到数组中。 3)、直到遇到处理结束。 这时数组中s剩下唯一的元素即是计算结果。,方法二：利用栈结构 算法分析： 假设后缀的表达式为A，操作数和计算结果存放在栈S中。 1)、从左向右处理a中的每一个字符： 2)、如果遇到一个操作数，就送入栈s中； 如果遇到一个运算符，就从栈s中取出栈顶的两个操作数进行计算，然后将计算结果重新压栈。 3)、直到遇到处理结束。 这时栈s顶的元素即是计算结果。,2、括号匹配 【问题描述：】 判断包含有括号，的字符串是否是合法匹配。 例如以下是合法的括号匹配： (), , (), ( ), () , ()() 以下是不合法括号匹配的： (, , , )(, ( , ()，( ) 【输入：】 一行，字符串（长度范围：1，200）。 【输出：】 如果字符串中括号匹配是合法的输出“yes”，不合法的输出“no”。 【样例1输入：】 a