数据结构 线性表.pptx

1第二章线性表线性表是最简单、最基本也是最常用的一种线性结构。线性表有两种存储方法:顺序存储和链式存储。线性表的基本操作是插入、删除和检索等。(0)个数据元素的有限序列。记作(a1,a2,…ai-1,ai,ai+1,…,an)ai是表中数据元素,n是表长度。3线性表的特点除第一个元素外,其他每一个元素有一个且仅有一个直接前驱。除最后一个元素外,其他每一个元素有一个且仅有一个直接后继。a1a2a3a4a5a64特别注意设A=(a1,a2,...,ai-1,ai,ai+1,…,an)是一线性表1)线性表的数据元素可以是各种各样的,但同一线性表中的元素必须是同一类型的;2)在表中ai-1领先于ai,ai领先于ai+1,称ai-1是ai的直接前驱,ai+1是ai的直接后继;3)在线性表中,除第一个元素和最后一个元素之外,其他元素都有且仅有一个直接前驱,有且仅有一个直接后继,具有这种结构特征的数据结构称为线性结构。线性表是一种线性数据结构;4)线性表中元素的个数n称为线性表的长度,n=0时称为空表;5)ai是线性表的第i个元素,称i为数据元素ai的序号,每一个元素在线性表中的位置,仅取决于它的序号。5姓名电话号码蔡颖63214444陈红63217777刘建平63216666王小林63218888张力63215555...线性表举例例1、数学中的数列(11,13,15,17,19,21)例2、英文字母表(A,B,C,D,E,,Z)。例3、某单位的电话号码簿。(1) 线性表初始化:Init_List(L)操作结果是构造一个空的线性表。(2)求线性表的长度:Length_List(L)操作结果是返回线性表中所含元素的个数。(3)取表元:Get_List(L,i)操作结果是返回线性表L中的第i个元素的值或地址。(4)按值查找:Locate_List(L,x)(x为给定一个数据元素)线性表L存在,操作结果是在表L中查找值为x的数据元素,其结果返回在L中首次出现的,值为x的那个元素的序号或地址,称为查找成功。否则,未找到,返回一个特殊值表示查找失败。7(5)插入操作:Insert_List(L,i,x)线性表L存在,插入位置1in+1(n为插入前的表长),操作结果是在线性表L的第i个位置上插入一个值为x的新元素。(6)删除操作:Delete_List(L,i)操作结果是在线性表L中删除序号为i的数据元素,新表长=原表长—1。线性表的基本操作8说明:(1)基本运算并不是它的全部运算。(2)数据结构的运算是定义在逻辑结构层次上,而运算的具体实现是建立在存储结构基础上,上面的运算是逻辑结构的一部分。(3)上述各操作中定义的线性表L仅仅是一个抽象在逻辑结构层次的线性表,尚未涉及到它的存储结构,还不能用程序设计语言写出具体的算法,而每个操作的算法只有在存储结构确立之后才能实现。(顺序存储的线性表)线性表的顺序存储是指在内存中用地址连续的一块存储空间对线性表中的各元素按其逻辑顺序依次存放,用这种存储形式存储的线性表称为顺序表。物理关系与逻辑关系一样,显得既简单,又自然。10顺序表(线性表的顺序存储结构)设a1的存储地址为Loc(a1),每个数据元素占d个存储位置,则第i个元素的地址为:Loc(ai)=Loc(a1)+(i-1)*d(1<=i<=n)a1a2ai+1an……01n-1ia1a2ai+1an……Loc(a1)Loc(a1)+dLoc(a1)+i*dLoc(a1)+(n-1)*d