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。 线性表的其它运算： 如求任一元素的直接前驱或直接后继；合并两个线性表； 线性表的拆分；线性表的复制；对线性表按照值的大小进行排 序等操作