资源描述：
《数据结构 线性表.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、线性结构的定义：如果一个数据元素序列满足：（1）除第一个和最后一个数据元素外，每个数据元素只有一个前驱数据元素和一个后继数据元素；（2）第一个数据元素没有前驱数据元素；（3）最后一个数据元素没有后继数据元素。则称这样的数据结构为线性结构。简言之，线性结构反映结点间的逻辑关系是的。线性结构包括：线性表、堆栈、队列、字符串、数组等，其中最典型、最常用的是------线性表一对一(1:1)第2章线性表2.1线性表2.2顺序表2.3单链表2.4循环单链表2.5双向链表2.6仿真链表2.1线性表2.1.1线性表的定义线性表是一种可以在任意位
2、置进行插入和删除数据元素操作的、由n（n≥0）个相同类型数据元素a0,a1,a2,...,an-1组成的线性结构。（a0,a1,…ai-1，ai,ai＋1，…,an-1）线性表的逻辑结构：n=0时称为数据元素线性起点ai的直接前趋ai的直接后继下标，是元素的序号，表示元素在表中的位置n为元素总个数，即表长。n≥0空表线性终点用符号（）表示（A,B,C,D,……,Z）学号姓名性别年龄班级012003010622陈建武男192003级电信0301班012003010704赵玉凤女182003级电信0302班012003010813王泽
3、男192003级电信0303班012003010906薛荃男192003级电信0304班012003011018王春男192003级电信0305班：：：：：例2分析学生情况登记表是什么结构。分析：数据元素都是同类型（记录），元素间关系是线性的。注意：同一线性表中的元素必定具有相同特性！例1分析26个英文字母组成的英文表是什么结构。分析：数据元素都是同类型（字母），元素间关系是线性的。数据集合线性表的数据元素集合可以表示为序列a0,a1,a2,...,an-1，每个数据元素的数据类型可以是任意的类类型。操作集合（1）求当前数据元素个
4、数getSize()（2）插入数据元素insert(i,obj)（3）删除数据元素delete(i)（4）取数据元素getData(i)（5）线性表是否空isEmpty()2.1.2线性表抽象数据类型在线性表的第i个数据元素前插入数据元素obj。删除线性表的第i个数据元素。线性表抽象数据类型的接口定义如下：interfaceList{voidinsert(inti,Objectobj);//插入Objectdelete(inti);//删除ObjectgetData(inti);//取数据元素intgetSize();//求元素个
5、数boolisEmpty();}2.2.1顺序表2.2顺序表用一组地址连续的存储单元依次存储线性表的各个数据元素。即采用顺序存储结构的线性表。它通常采用数组实现数据元素的存储。注意：在C#中数组的下标是从0开始，即：listArray[n]的有效范围是从listArray[0]～listArray[n-1](1)逻辑上相邻的数据元素，其物理上也相邻；(2)若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出（利用数组的下标）。设首元素a0的存放地址为LOC(a0)（称为首地址），设每个数据元素占用L个存储空间，则表中任一数
6、据元素的存放地址为：LOC(ai+1)=LOC(ai)+LLOC(ai)=LOC(a0)+L*i对上述公式的解释如图所示线性表顺序存储特点：an-1……ai+1ai……a1a0地址内容元素在表中的位序0i1n-1空闲区i+1Lb=LOC(a0)b+Lb+iLb+(n-1)Lb+(maxSize-1)LLOC(ai)=LOC(a0)+L*i线性表的顺序存储结构示意图设有一维数组Ｍ，下标的范围是０到９，每个数组元素用相邻的５个存储单元存储。设存储数组元素Ｍ[０]的首地址是8，则Ｍ[３]的地址是多少？23LOC(M[3])=8+5×3=
7、23解：已知地址计算通式为：LOC(ai)=LOC(a0)+L*i例12.2.2顺序表类类包含成员变量和成员函数。成员变量用来表示抽象数据类型中定义的数据集合成员函数用来表示抽象数据类型中定义的操作集合顺序表类实现接口List。顺序表类的public成员函数主要是接口List中定义的成员函数。classSeqList:List{constintdefaultSize=10;intmaxSize;intsize;Object[]listArray;publicSeqList(){initiate(defaultSize);}publ
8、icSeqList(intsize){initiate(size);}存储数据元素的数组数组中当前存储的数据元素的个数构造函数构造函数privatevoidinitiate(intsz){maxSize=sz;size=0;listArray=ne
