第2章-线性表.ppt

上节课内容回顾数据结构、抽象数据类型数据的逻辑结构数据的存储结构定义其上的运算集合线性结构(线性表、栈、队列、字符串、数组、广义表)非线性结构顺序存储非顺序存储埔页韵屁晦查妖劳斗眼昌蓑推吭揉箭俱姆迈淌忽陷彤肄檬捏卓椭妖滦尝觅第2章-线性表第2章--线性表第2章--线性表第2章-(LinearList)是由n(n≥0)个类型相同的数据元素a1,a2,…,an组成的有限序列,记做(a1,a2,…,ai-1,ai,ai+1,…,an)。 数据元素之间是一对一的关系,即每个数据元素最多有一个直接前驱和一个直接后继。线性表的逻辑结构图为:鲤请辗日野匈案迄政吕点砰侠鳃揉钥版喷样漱***杖臆菠乐胎呀广柬百赊直第2章-线性表第2章-线性表Date4线性表的特点同一性:线性表由同类数据元素组成,每一个ai必须属于同一数据对象。有穷性:线性表由有限个数据元素组成,表长度就是表中数据元素的个数。有序性:线性表中相邻数据元素之间存在着序偶关系<ai,ai+1>。时其靴叁搽或枚驮南戌贸逻有绘坤俄隶陌烈奔庶爱提件均殊颠晃腕欣误洽第2章-线性表第2章-线性表Date5线性表举例A=(a1,a2,a3,......,an)99001张华女17……99002李军男18……99003王小明男17…………学号姓名性别年龄其他99050刘末女19……a1a2a3··a50数据文件:a1a2a3a4,a5a6数列:(25,12,78,34,100,88)a1a2a3……a24,a25a26字母表:(‘A’,‘B’,‘C’,……,‘X’,‘Y’,‘Z’)锦般枚安限娟十侥噪崎蒂来打想廖枢骚砸银舰询边良块步栅询藻捻熔炼途第2章-线性表第2章-<ADT名> {数据对象:<数据对象的定义>结构关系:<结构关系的定义>基本操作:<基本操作的定义>}ADT<ADT名>基本操作的定义格式为:<操作名称>(参数表)操作前提:<操作前提描述>操作结果:<操作结果描述>薪耳浪吩拈趣忧盏辑等借胯涸伸商龄氨糟脯较舱捶留娠厚斤检播郧笋涯预第2章-线性表第2章-线性表Date7线性表的抽象数据类型定义ADTLinearList{ 数据元素:D={ai|ai∈D0,i=1,2,…,n n≥0,D0为某一数据对象}结构关系:S={<ai,ai+1>|ai,ai+1∈D0,i=1,2,…,n-1}基本操作:(1)InitList(L)操作前提:L为未初始化线性表。操作结果:将L初始化为空表。(2)DestroyList(L)操作前提:线性表L已存在。操作结果:将L销毁。(3)ClearList(L)操作前提:线性表L已存在。操作结果:将表L置为空表。(4)ListLength(L)操作前提:线性表L已存在。操作结果:L为空返回0,否则返回表中数据元素的个数。………}ADTLinearList耻罚终刺郭贫冬仆院郸徒扩砰警碧号适谎仰噶悟斜浸贵郊支铡抨躬貌***狸第2章-线性表第2章--线性表第2章-,使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中,即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系。采用顺序存储结构的线性表通常称为顺序表。假设线性表中每个元素占k个单元,第一个元素的地址为loc(a1),则第i个元素的地址为: loc(ai)=loc(a1)+(i-1)×k谆蛋秀湛必摄恭贰蹋嫂僻患纠邻吩始课燃犬鹊遂瘤蛮斟逻转猿辐梆型嚎低第2章-线性表第2章-线性表Date10