资源描述：
《数据结构基础总览》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、数据结构基础总览四川省泸县第二中学：李波线性表线性表的类型定义：一、线性结构的特点：在数据元素的非空有限集中，（1）存在唯i的一个被称做“第一个”的数据元素；（2）存在唯一的一个被称做“最后一个”的数据元素；（3）除第一个Z外，集合中的每个数据元素均只有一个前驱；（4）除最后一个之外，集合屮毎个数据元素均只有一个后继。二、线性表的定义：线性表是最常用且最简单的一种数据结构。-•个线性表是n个数据元素的有限序列。数据元索可以是一个数、一个符号、也可以是一幅图、一页帖或更复杂的信息。线性表例：1、12345672、学号姓名语文数学C语言6201001张三8554926201002李四928
2、4646201003T7T8774736201004•••数据元素也可由若干个数据项组成（如上例2）o这吋常把数据元素称为记录。含有大量记录的线性表乂称文件。线性表中的数据元素类型多种多样，但同一线性表屮的元素必立具有相同特性,即属同一数据对象，相邻数据元索之间存在着序偶关系。ai•••ai-iaiai+i•••anat是aw的直接前驱元索，&+1是的直接后继元索。线性表屮元素的个数n圧义为线性表的长度，为0时称为空表。在非空表屮的每个数据元素都有一个确定的位置。ai是第i个元素，把i称为数据元素ai在线性中的位序。线性表的顺序表示：一、线性表的顺序表示用一组地址连续的存储单元依次存储
3、线性表的数据元索。HBB+La?…b+（i・dl•••B+（NJ）L•••——空闲假设线性表的毎个元素需占用0个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。则存在如下关系：Loc（ai+i）=Loc（ai）+zLOC（ai）=LOC（ai）+（/-i）*z,式中Loc（ai）是线件表的第一•个数据元素的存储位置，通常称做线件表的起始位置或基地址。常用方表示。线性表的这种机内表示称做线性表的顺序存储结构或顺序映象。称顺序存储结构的线性表为顺序表。顺序表的特点是以元索在计算机内物理位置相邻来表示线性表中数据元素Z间的逻辑关系。例1：一个向量第一个元索的存储地址是100,
4、每个元素的长度是2,则第5个元索的地址是（）°（NOI2002初赛试题（提高组））A)110B)108C)100D)109二、顺序存储结构的线件表操:顺序表的插入与删除操作：序号数据兀索<-25I1I121213321424525
5、628
6、73018429177序号：据元12213M21424528630742877f19fIr11J序号数据元索一>24112213321428530427789序号数据元索插入liyn=8;插入后”9;删除就n=&删除后n=7;线性表的链式表示：二、线性链表的概念：以链式结构存储的线性表称之为线性链表。特点是该线性表中的数据元索可以用任意的存储单元来存
7、储。线性表中逻辑相邻的两元索啲存储空间可以是不连续的。为表示逻辑上的顺序关系，对表的每个数据元素除存储本身的信息Z外，还需存储一个指示其直接片继的信息。这两部分信息组成数据元素的存储映象,称为结点。2000:1000头指针2000:1(X)62000:10302000:1010a32000:10402000:1020a6NULLV-数据域+指针域2000:1030al2000:10602000:10402000:10502000:1060a42000:1050a52000:1020a22000:10102000:4000数据域指针域川线性链表表示线性表时，数据元索Z间的逻辑关系是山结点
8、屮的指针指示的r+>[例2：线性表若采用链表存贮结构，要求内存屮町用存贮单元地址（）（第六届初赛试题）A.必须连续B.部分地址必须连续C.一定不连续D.连续不连续均可栈栈的表示：一、栈的定义：栈是限圧仅在表尾进行插入或删除操作的线性表。栈的表尾称为栈顶，表头称为栈底，不含元素的空表称为空栈。岀栈进栈由上图可以看击，栈又称为后进先出的线性表（简称LIFO结构）二、栈的表示：栈的存储方式：1、顺序栈:利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元索在顺序栈中的位置。2、链栈:利用链表实现例3：若已知一个栈的入栈顺序是1,2,3,…，n»其输出序列为P
9、l,P2,P3,…，Pn,若Pl是n,则Pi是（）（第七届初赛试题）A）iB）n-1C）n-i+lD）不确定仮！J4：以下哪-•个不是栈的基木运算（）（第七届初赛试题）A）删除栈顶元素B）删除栈底的元素C）判断栈是否为空D）将栈置为空栈例5：已知元素（8,25,14,87,51,90,6,19,20）,问这些元素以怎样的顺序进入栈，才能使出栈的顺序满足:8在51前面;90在87的后面;20在14的后面;25在6的前面；19在90的后面。（）。（
