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

第12讲:数据结构之线性结构数据结构之：线性结构由n个数据元素组成的有限序列除头元素外，每个元素都有一个前趋除尾元素外，每个元素都有一个后继例如:26个英文字母表(a，b，……，Z)是一个线性表线性结构:线性表、栈、队列操作方法和要求的不同划分线性表的两种存储方式顺序存储结构：数组连续存储易于定位，不易于插入和删除链式存储结构：链表非连续存储易于插入和删除，不易于定位一、线性表线性表是最常用且最简单的一种数据结构，它是由n个数据元素组成的有序集合。数组与链表链表数组数组的插入与删除1234567891011126.5数组的插入与删除均需要移动后面的元素插入：6.5删除：4123456789101112123456789101112123456789101112链表的插入与删除无需移动任何元素插入：删除：顺序存储结构的元素访问顺序存储结构是指用一组地址连续的存贮单元依次存储线性表的元素，通常用数组实现。它是按首址（表中第1个元素的地址）十位移来访问每一个元素。loc(a[i])—a表中元素i的内存地址（1≤i≤n）；loc(b[i，j])—b表中（i，j）元素的内存地址（1≤i≤n，1≤j≤m）；一维数组按照下标递增的顺序访问表中元素a[1]→a[2]→……→a[n]loc(a[i])=loc(a[1])+(i-1)*k//k—每个数据元素的长度(字节或机器字)；首址位移二维数组有按照先行后列和先列后行的顺序访问表中元素：b[1..n，1..m]先行后列:loc(b[i，j])=loc(b[1，1])+(m*(i-1)+(j-1))*kk—每个数据元素的长度；首址位移先列后行:loc(b[i，j])=loc(b[1，1])+(n*(j-1)+(i-1))*kk—每个数据元素的长度；首址位移①一个向量第一个元素的存储地址是100，每个元素的长度是2，则第5个元素的地址是（）。(NOIP8)A）110B）108C）100D）109②已知数组中A中，每个元素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-1）*2D.（（Y-1）*80+X）*2-1(4)、设有一个10阶的对称矩阵A，采用压缩存储方式按行将矩阵中下三角部分的元素存入一维数组B[]中，A[0][0]存入B[0]中，则A[8][5]在B[]中（）位置。A．32B．33C．41D．65应用举例：1、插入排序。2、两个有序线性表的合并。输入:1481023791113输出：12347891011133、两个多项式的合并。输入：1+x+2X^2-x^3-30X^52x+x^2+x^3输出：1+3x+3x^2-30x^5二、栈栈的定义栈是一种“后进先出”线性表。对它的插入和删除都限制地表的同一端进行。这一端叫做栈的“顶”，另一端则叫做栈的“底”。特点:后进先出(LIFO)、或者先进后出（FILO）栈底325进栈进栈进栈出栈出栈出栈不一定进栈结束后才出栈，进出栈可交叉进行【竞赛试题】1、一个栈的输入顺序为1、2、3、4、5，下列序列中可能是栈的输出序列是()。(A)54312(B)24３15(C)21543(D)125４32、若已知一个栈的入栈顺序是1，2，3，…，n，其输出序列为P1，P2，P3，…，Pn，若P1是n，则Pi是()(NOIP7)A)iB)n-1C)n-i+1D)不确定3、设有一个顺序栈S，元素S1,S2,S3,S4,S5,S6依次进栈，如果6个元素的出栈顺序为S2,S3,S4,S6,S5,S1，则顺序栈的容量至少应为多少？A)3B)4C)5D)64、向顺序栈中压入新元素时，应当（）。A．先移动栈顶指针，再存入元素B．先存入元素，再移动栈顶指针C．先后次序无关紧要D．同时进行假设栈中表目数的上限为m，所有表目都具有同一类型stype，则可以用下列方式定义栈：Constm=栈表目数的上限；Vars：array[1‥m]ofstype；{栈}t：integer；{栈顶指针，初始值为０}栈的基本操作栈的基本操作：初始化（init）、进栈（push）、出栈（pop）和读取栈顶元素（top）。1）过程init(s,t)procedureinit;begint:=0;end;2)、过程push(x)—往栈s中压入一个值为x的数据：procedurepush（x：stype)；begint:=t+1；s[t]:=x；{x入栈}end；{Push}3)、函数pop—从栈中弹出一个元素functionpop：stype；beginpop:=s[t]；{栈顶元素出栈}t:=t-1；{指针下移}end；{pop}4)、函数top—读栈顶元素functiontop：stype；beginift=0thenwriteln(’stackempty’)elsetop:=s[t]；{返回栈顶元素}end；{top}栈的应用1、后缀表达式求值【问题描述：】后缀表达式是指这样的一个表达式：式中不再引用括号，运算符号放在两个运算对象之后，所有计算按运算符号出现的顺序，严格地由左而右新进行（不用考虑运算符的优先级）。如：3*(5–2)+7对应的后缀表达式为：3．5．2．-*7．+@。’@’为表达式的结束符号。‘.’为操作数的结束符号。3．5．2．-*7．+@=3．3．*7．+@=9．7．+@=16运算符号：+、-、*、//运算只取整数部分。采用div即可【输入：】后缀表达式（长度不超过100）。【输出：】表达式的值。说明：运算的中间结果与最后的结果数据范围：[-1000000000，1000000000]。【样例输入：】3．5．2．-*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输入：】abc{a[bb]m}aass【样例1输出：】yes【样例2输入：】abc{a[bb]maass【样例2输出：】no分析：遇到左括号进栈；遇到右括号，出栈，看是否和右括号匹配，如果匹配继续看下一个括号，否则停止，输出no即可。栈底325进栈进栈进栈出栈出栈出栈352栈顶加入一个数4取出栈顶元素再取出栈顶元素6栈底