线性表、栈、队列.ppt

* 线性表、栈、队列 一、线性表 线性表的定义： 线性表是最常用且最简单的一种数据结构，它是由有限个数据元素组成的有序集合。 每个数据元素有一个数据项或者含多个数据项。 如：全班60位同学的数学成绩。 1、顺序存储结构 顺序存储结构是指用一组地址连续的存贮单元依次存储线性表的元素，通常用数组实现。数组的物理实现是一块连续的存储空间，它是按首址（表中第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 2、链式存储结构 在链式存储结构的线性表中，逻辑上相邻的两元素，其物理位置不要求相邻。采用动态指针。数组元素和动态变量的类型一般采用记录类型，数据域存储结点的值，指针域存储后件的数组下标或地址。最后一个结点的指针域的值为0或nil。 考题: 线性表若采用链表存贮结构，要求内存中可用存贮单元地址（　　）(NOIP6)A.必须连续　　B. 部分地址必须连续　　C. 一定不连续　　D. 连续不连续均可 二、栈 1、栈的定义 栈是一种线性表，对它的插入和删除都限制地表的同一端进行。这一端叫做栈的“顶”，另一端则叫做栈的“底”。 特点:后进先出(LIFO)、或者先进后出（FILO） 通常栈可以用顺序的方式存储(数组)，分配一块连续的存储区域存放栈中的表目，并用一个变量t指向当前栈顶（如下图）。 Const m=栈的上限； Var 　s： array[1‥m] of stype ；{栈} 　　 t： integer； {栈顶指针，初始值为０} 　注意：不一定进栈结束后才出栈，进出栈可交叉进行。 2、栈的基本操作 栈的基本操作包括初始化（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； 　　　s[t]←x； {x入栈} end；{Push} 3)、函数pop—从栈中弹出一个元素 function pop