资源描述：
《第2章线性表分析解析ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第二章线性表线性结构是n个数据元素的有序（次序）集线性结构的基本特征为(两个“只有”两个“唯一”):在数据元素的非空有限集中1．集合中必存在唯一的一个“第一元素”；2．集合中必存在唯一的一个“最后元素”；3．除第一元素之外，集合中每个数据元素只有一个唯一的前驱。4．除最后元素在外，集合中每个数据元素只有一个后继；2.1线性表的类型定义2.3线性表类型的实现链式映象2.2线性表类型的实现顺序映象1.线性表的定义：是由n(n>=0)个数据元素（结点）a1,a2,a3,……an组成的有限序列。其中：a1为表头，an为表尾，n为数据
2、元素的个数，也称为表的长度。当n=0时，称为空表。非空的线性表(n>0)记作：（a1,a2,a3,……an）2.1线性表的类型定义2.线性表（a1,a2,a3,……an）的逻辑特征：（1）有且仅有一个开始结点a1(无直接前趋）；（2）有且仅有一个终端结点an(无直接后继）；（3）其余的结点ai都有且仅有一个直接前趋ai-1和一个直接后继ai+1。（4）ai是属于某个数据对象的元素，它可以是一个数字、一个字母或一个记录。3.线性表的特性（1）同一性：同一线性表中的元素必须是同一类型的；（2）ai是线性表的第i个元素，称i为数据元
3、素ai的位序，每一个元素在线性表中的位置，仅取决于它的位序。（3）有序性：结点间的逻辑关系是线性的，相邻数据元素之间存在着序偶关系。（4）有穷性：线性表由有限个数据元素组成，表长度就是表中数据元素的个数。例1、26个英文字母组成的字母表（A，B，C，…，Z）例2、某校从1978年到1983年各种型号的计算机拥有量的变化情况。（6，17，28，50，92，188）例3、学生健康情况登记表如下：姓名学号性别年龄健康情况王小林790631男18健康陈红790632女20一般刘建平790633男21健康张立立790634
4、男17神经衰弱……..……..…….…….…….4.线性表的抽象数据类型定义ADTLinearList{数据元素：D={ai
5、ai∈D0,i=1,2,…,nn≥0为表长,n=0为空表i为ai在线性表中的位序。D0为某一数据对象}关系:S={
6、ai,ai+1∈D0，i=1,2,…,n-1}基本操作：InitList(&L)操作前提:L为未初始化线性表操作结果:将L初始化为空表DestroyList(&L)操作前提:线性表L已存在操作结果:将L销毁引用型操作加工型操作}ADTLinearListListEmpty(L
7、)若L为空表,则返回TRUE,否则FALSE。ListLength(L)返回L中元素个数。PriorElem(L,e,&pre_e)返回L中元素e的前驱,无则返回空元素。NextElem(L,e,&next_e)返回L中元素e的后继,无则返回空元素GetElem(L,i,&e）返回L中i号元素值,1≤i≤Length(L)。LocateElem(L,e,compare())返回L中第1个与e相等的元素的位序。若没有与e相等的元素,则返回值为0。Traverse(L,visit())依次对L的每个元素调用函数visit()。一旦vi
8、sit()失败,则操作失败。引用型操作加工型操作ClearList(&L)将L置为空表。PutElem(&L,i,&e)将e的值赋给L的i号元素。(1≤i≤Length(L))ListInsert(&L,i,e)在L的i号元素(1≤i≤Length(L)+1)之前插入新的元素e,L的长度增1。ListDelete(&L,i,&e)删除L的i号元素(1≤i≤Length(L)),并用e返回其值，L的长度减1。上面我们定义了线性表的逻辑结构和基本操作。在计算机内，线性表有两种基本的存储结构：顺序存储结构和链式存储结构。下面我们分别讨论
9、这两种存储结构以及对应存储结构下实现各操作的算法。为了存储线性表，至少要保存两类信息： 1）线性表中的数据元素； 2）线性表中数据元素的顺序关系；如何在计算机中存储线性表？如何在计算机中实现线性表的基本操作？线性表的顺序存储结构（顺序映像）：用一组地址连续的存储单元依次存放线性表中的数据元素顺序表：采用顺序存储结构的线性表通常称为顺序表a1a2…ai-1ai…an线性表的起始地址称作线性表的基地址2.2线性表的顺序表示和实现1.线性表的顺序存储结构—顺序表以“存储位置相邻”表示有序对即：LOC(ai)=LOC(a
10、i-1)+C一个数据元素所占存储量所有数据元素的存储位置均取决于第一个数据元素的存储位置LOC(ai)=LOC(a1)+(i-1)×C基地址顺序表的特点是：1.逻辑位置相邻，其物理位置也相邻。2.实现随机存取存储地址内存空间状态逻辑地址Loc(a1
