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

《第十二讲：线性结构(线形表、栈和队列)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、1126.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）；一维数组按

3、照下标递增的顺序访问表中元素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—每个数据元素的长度；首址位移①一个向量第一个元

4、素的存储地址是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

5、），整个屏幕则以线性方式存储在电脑的存储器内，从屏幕左上角开始，位移为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、插入排序。

6、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、

7、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，则顺序栈的容量至少应为多少？3B)4C)5D)64、向顺序栈中压入新元素时，应当（）。A．先移动栈顶指针，

8、再存入元素B．先存入元素，再移动栈顶指针C．先后次序无关紧要D．同时进行假设栈中表目数的上限为m，所有表目都具有同一类型stype，则可以用下列方式定义栈：Constm=栈表目数的上限；Vars：array[1‥m]ofstype；{栈}t：integer；{栈顶指针，初始值为０}栈的基本操作栈的基本操作：初始化（init）、进栈（push）、出栈（pop）和读取栈顶元素（top）。1）过程init(s,t)procedu