线性结构及其应用.pptVIP

线性结构及其应用 线性表的概念 线性表（linear_list）是最常用、最简单的一种数据结构。一个线性表是n（n≥0）个具有相同特性的数据元素的有限序列。 它具有以下特性： 存在唯一的被称作“第一个”的数据元素； 存在唯一的被称作“最后一个”的数据元素； 除第一个元素外，线性表中的每个数据元素均只有一个前驱； 除最后一个元素外，每个数据元素均只有一个后继； 线性表中的数据元素可以使多种类型，但同一线性表中的元素必定具有相同特性。即基类型相同。 线性表的存储结构 顺序存储结构：用一维数组来描述 const lmaxlen={线性表可能达到的最大长度}； type lelement={线性表数据元素的数据类型} list=record data:array[1..lmaxlen] of lelement; last:0..lmaxlen end; 线性表的存储结构 链接存储结构：用指针类型来描述 单链表： Type datatype={单链表中结点的数据类型} link=^node; node=record data:dataty; next:link end; 线性表基本操作的实现 顺序存储线性表基本操作的实现 （1）初始化 Procedure initial(a:list); Begin a.last:=0; End; (2)求长度 Function length(a:list):integer; Begin length:=a.last; End; 线性表基本操作的实现 （3）获取元素 Procedure getlist(a:list；i:integer；var x:lelement); Begin if (i=0) or (ia.last) then writeln(‘取数位置不对’) else if a.last=0 then writeln(‘表为空’) else x:=a.data[i] End; (4)定位 Function loclist(a:list; x:lelement):integer; Begin i:=1; while (i=a.last)and(a.data[i]x) do i:=i+1; if i=a.last then loclist:=i else loclist:=0 End; 线性表基本操作的实现 （5）插入元素 Procedure inslist(var a:list；i:integer；x:lelement); Var j：integer； Begin if a.last+1lmaxlen then writeln(‘超出最大长度’)； if (ia.last) or (i0) then writeln(‘插入位置不对’)； if (i=a.last+1)and(i0)and(a.last+1=lmaxlen) then begin for j:=a.last downto i do a.data[j+1]:=a.data[j]; a.data[i]:=x; a.last:=a.last+1 end; End; 线性表基本操作的实现 （6）删除 Procedure dellist(var a:list；i:integer); Var j：integer； Begin if a.last=0 then writeln(‘表为空’)； if (i0) or (ia.last ) then writeln(‘删除位置有错’)； if (a.last0) and (i0)and(i=a.last) then begin for j:=i+1 to a.last do a.data[j-1]:=a.data[j]; a.last:=a.last-1; end; End; 线性表基本操作的实现 顺序存储线性表基本操作的实现 （7）判断线性表是否满 function fulllist(a:list):boolean; Begin if a