North China Electric Power University 线性表基本运算的应用示例: 例1设有两个线性表La和Lb,现将La和Lb合并成一个 新表存于La中。 Procedure Union(Var La: Linear list Lb: Linear list); {将所有在Lb中存在而在La中不存在的数据元素插入到La中} B n:=Length(La) For i:=l to Length (Lb) Do I X:=Get(Lb, i); k:=Locate(La, x); if ke0 then Insert (La, n+1, x) n:=n+1; End;
North China Electric Power University 线性表基本运算的应用示例： 例1.设有两个线性表La和Lb，现将La 和Lb合并成一个 新表存于La中。 Procedure Union(Var La:Linear_list ; Lb:Linear_list); {将所有在Lb中存在而在La中不存在的数据元素插入到La中} Begin n:=Length(La); For i:=1 to Length(Lb) Do [ x:=Get(Lb,i); k:=Locate(La,x); if k=0 then [ Insert(La,n+1,x); n:=n+1; ] ] End;
North China Electric Power University 例2判断两个集合A和B是否相等 Function Compare La: Linear list Lb: Linear list): Boolean {若La和Lb不仅长度相等,而且所含元素也相同则返回True Begin Len la: =Length (La) Len lb:Length(Lb) if Len la< >Len Ib then return(false) dse I For k:=l to Len la do I X:=Get(La, k); m:=Locate(Lb, x); if m=0 then Return(False); Return(True) End;
例2.判断两个集合A和B是否相等。 Function Compare(La:Linear_list ; Lb:Linear_list):Boolean; {若La和Lb不仅长度相等，而且所含元素也相同则返回True} Begin Len_la:=Length(La); Len_lb:=Length(Lb); if Len_la< >Len_lb then Return(False) else [ For k:=1 to Len_la Do [ x:=Get(La,k); m:=Locate(Lb,x); if m=0 then Return(False); ] ] Return(True); End; North China Electric Power University
North China Electric Power University 线性表的顺序存储:用一块连续的存储单元依次 存放线性表的各个元素。 存储地址内存状态元素在线性表中的次序 b=Loc(a1) a b+c a 2 b+(i-) a b+(n-1)*c a 空闲 b+(max-1)六c
North China Electric Power University 线性表的顺序存储：用一块连续的存储单元依次 存放线性表的各个元素。 存储地址 内存状态 元素在线性表中的次序 b=Loc(a1 ) b+c b+(i-1)*c b+ (n-1)*c b+(max-1)*c 1 2 i n 空闲 a1 a2 … ai … an
North China Electric Power University 顺序存储的线性表的寻址公式: Loc(a-)=oc(a)+(i-1)*c1≤i≤n Loc(a1)为线性表的第一个元素a1的存储地址 c为每个元素所占的存储单元 线性表的顺序存储可以借用数组类型来实现 顺序存储的优点 1.可以随机存取 2.空间利用率高 3.结构简单
顺序存储的线性表的寻址公式： 顺序存储的优点： 1.可以随机存取 2.空间利用率高 3.结构简单 Loc(ai)=Loc(a1)+(i-1)*c 1≤i≤n Loc(a1)为线性表的第一个元素a1的存储地址 c为每个元素所占的存储单元 线性表的顺序存储可以借用数组类型来实现 North China Electric Power University
North China Electric Power University 线性表的基本运算的实现: 1)在线性表L的第i个位置上插入一个新元素x 插入前:元素[114202528314378 序号12345678 入27 插入后:元素111420252728314378 序号123456789 主要操作:1将第i到n个元素依次后移一个位置 2将新元素x放到线性表的第个位置上 3将线性表的表长由n修改为n+1
线性表的基本运算的实现： 1)在线性表L的第i个位置上插入一个新元素x 插入前：元素 序号 1 2 3 4 5 6 7 8 插入27 插入后：元素 序号 1 2 3 4 5 6 7 8 9 主要操作：1.将第i到n个元素依次后移一个位置 2.将新元素x放到线性表的第i个位置上 3.将线性表的表长由n修改为n+1 11 14 20 25 28 31 43 78 11 14 20 25 27 28 31 43 78 North China Electric Power University