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

第12讲: 数据结构之 线性结构;数据结构之：线性结构;线性结构: 线性表、栈、队列;线性表的两种存储方式;数组与链表;数组的插入与删除;链表的插入与删除;顺序存储结构的元素访问 顺序存储结构是指用一组地址连续的存贮单元依次存储线性表的元素，通常用数组实现。 它是按首址（表中第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))*k k—每个数据元素的长度； 首址 位移 先列后行: loc(b[i，j])=loc(b[1，1])+(n*(j-1)+(i-1))*k k—每个数据元素的长度； 首址 位移 ;①一个向量第一个元素的存储地址是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+141　　B. SA+180　　C. SA+222　　D. SA+225 ③一个文本屏幕有25列及80行，屏幕的左上角以（1，1）表示，而右下角则以（80，25）表示，屏幕上每一个字符占用两字节（byte），整个屏幕则以线性方式存储在电脑的存储器内，从屏幕左上角开始，位移为0，然后逐列逐列存储。求位於屏幕（X，Y）的第一个字节的位移是（　　）(NOIP6)A.（Y*80+X）*2-1　　B.（（Y-1）*80+X-1）*2C.（Y*80+X-1）*2　　D.（（Y-1）*80+X）*2-1;(4)、设有一个10阶的对称矩阵A，采用压缩存储方式按行将矩阵中下三角部分的元素存入一维数组B[ ]中，A[0][0]存入B[0]中，则A[8][5]在B[ ]中（ ）位置。 A．32 B．33 C．41 D．65;应用举例：;二、栈;栈底;不一定进栈结束后才出栈，进出栈可交叉进行;3、设有一个顺序栈S，元素S1, S2, S3, S4, S5, S6依次进栈，如果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： array[1‥m] of stype ；{栈} 　　 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；