North China Electric Power University 数据结构 Data Structure 华北电力大喾计算机斛学与工程柰 Dept of Computer Science& Engineering of North China Electric Power University
数据结构 North China Electric Power University Data Structure 华北电力大学计算机科学与工程系 Dept. of Computer Science&Engineering of North China Electric Power University
North China Electric Power University 第二章线性表 ★线性表 ★栈 ★队列
第二章 线性表 ★ 线性表 ★ 栈 ★ 队列 North China Electric Power University
North China Electric Power University ★疯性森 线性表的逻辑结构 线性表是0个或多个元素的有穷序列,通常可 表示成a1,a2,a3, ■■ ,an(n≥0) n:线性表的表长 n=0时称为空表 n≥1时,a1称为第一个元素,an称为最后一个元素 a1称为a的前驱,a1+1称为a的后继,i称为序号或索引 特点:除第一个和最后一个元素外,每个元素有 且只有一个直接前驱和一个直接后继
线性表的逻辑结构： 线性表是0个或多个元素的有穷序列，通常可 表示成 a1 ,a2 , a3 , … ,ai , … ,an(n≥0) ★ 线性表 n:线性表的表长 n=0时称为空表 n≥1时，a1称为第一个元素， an称为最后一个元素 ai称为ai+1的前驱，ai+1称为ai的后继，i称为序号或索引 特点：除第一个和最后一个元素外，每个元素有 且只有一个直接前驱和一个直接后继。 North China Electric Power University
North China Electric Power University 线性表的例子 例1.一副扑克牌中同一花色的13张牌组成一个线性表 (A,2,3,4,5,6,7,8,9,10,J,Q,K) 例2.人民币面值的所有种类组成一个线性表 (1角,2角,5角,1元,2元,5元,10元,20元,50元,100元) 例3.一本书可以看成是一个线性表,每一页是一数据元素 例4学生的学籍档案构成一个线性表 学号 姓名 入学总分数学分析程序设计离散数学 981201王国强 435 65 98I2U2 赵济实 429 8 数据元素 981203 刘晔 512 97 95 981204 叶桑林)4893 91 85 数据项 981250田华月 501 89 95 87
North China Electric Power University 线性表的例子： 例1.一副扑克牌中同一花色的13张牌组成一个线性表 (A,2,3,4,5,6,7,8,9,10,J,Q,K) 例2.人民币面值的所有种类组成一个线性表 (1角，2角，5角，1元，2元，5元，10元，20元，50元，100元) 例3.一本书可以看成是一个线性表，每一页是一数据元素 例4.学生的学籍档案构成一个线性表 学号 姓名 入学总分 数学分析 程序设计 离散数学 … 981201 王国强 435 88 65 82 … 981202 赵济实 429 85 90 78 … 981203 刘晔 512 97 88 95 … 981204 叶桑林 488 93 91 85 … … … … … … … … 981250 田华月 501 89 95 87 … 数据元素 数据项
North China Electric Power University 线性表的基本运算 1. Initia1(L):初始化操作,设定一个空的线性表L。 2 Length(L):返回线性表的表长。 3.Get(L,i):若1≤i≤ Length(L),返回线性表的第个元素 4. Locate〔U,x)若L中存在一个或多个值和x相等,运算 结果为这些元素序号的最小值,否则返回0。 5. Insert(,i,x):在线性表的第个位置插入一新元素x 6. Delete(L,i):删除线性表L的第i个元素。 7. Empty(L):若线性表L为空返回True,否则返回 False 线性表的其它运算: 如求任一元素的直接前驱或直接后继;合并两个线性表; 线性表的拆分;线性表的复制;对线性表按照值的大小进行排 序等操作
线性表的基本运算： North China Electric Power University 1.Initial(L):初始化操作，设定一个空的线性表L。 2.Length(L):返回线性表的表长。 3.Get(L,i):若1≤i≤Length(L),返回线性表的第i个元素。 4.Locate(L,x):若L中存在一个或多个值和x相等，运算 结果为这些元素序号的最小值，否则返回0。 5.Insert(L,i,x):在线性表的第i个位置插入一新元素x。 6.Delete(L,i):删除线性表L的第i个元素。 7.Empty(L):若线性表L为空返回True,否则返回False。 线性表的其它运算： 如求任一元素的直接前驱或直接后继；合并两个线性表； 线性表的拆分；线性表的复制；对线性表按照值的大小进行排 序等操作
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 laLen 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_laLen_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