第二章线性表 线性结构特点：在数据元素的非空有限集中 ★存在唯一的一个被称作“第一个”的数据元素 ★存在唯一的一个被称作“最后一个”的数据元素 ★除第一个外，集合中的每个数据元素均只有一个 前驱 ★除最后一个外，集合中的每个数据元素均只有一 个后继
第二章线性表 线性结构特点：在数据元素的非空有限集中 存在唯一的一个被称作“第一个”的数据元素 存在唯一的一个被称作“最后一个”的数据元素 除第一个外，集合中的每个数据元素均只有一个 前驱 除最后一个外，集合中的每个数据元素均只有一 个后继
§2.1线性表的类型定义 ★定义：一个线性表是个数据元素的有限序列 如（a1,a2,..,ai, 例英文字母表（A,B,C,.…是一个线性表 例 学号 姓名 年龄 数据元素 001 张三 18 002 李四 19 ★特征： 必元素个数n一表长度，n=0空表 1<i<n时 ●a的直接前驱是a.1,a1无直接前驱 ●a的直接后继是a+1,an无直接后继 必元素同构，且不能出现缺项
§2.1 线性表的类型定义 定义：一个线性表是n个数据元素的有限序列 如 (a 1 , a 2 ,……, a i , ……a n ) 例 英文字母表（A,B,C,…..Z)是一个线性表 例 学号 姓名 年龄 001 张三 18 002 李四 19 …… …… …… 数据元素 特征： ❖元素个数n—表长度，n=0空表 ❖1<i<n时 ⚫ai的直接前驱是ai-1，a1无直接前驱 ⚫ai的直接后继是ai+1，an无直接后继 ❖元素同构，且不能出现缺项
抽象数据类型线性表的定义如下： ADT List{ 数据对象： D={a:la:∈ElemSet,i=l,2,,n,n≥0} {称n为线性表的表长； 称=0时的线性表为空表。}
抽象数据类型线性表的定义如下： ADT List { 数据对象： D＝{ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 } {称 n 为线性表的表长; 称 n=0 时的线性表为空表。}
数据关系： R1={<a.1,a>la-1,a∈D,i=2,,n} {设线性表为(a1,a2, 称i为a在线性表中的位序}
数据关系： R1＝{ <ai-1 ,ai >|ai-1 ,ai∈D, i=2,...,n } {设线性表为 (a1，a2 , . . . ，ai，. . . ，an ), 称 i 为 ai 在线性表中的位序}
基本操作： 结构初始化操作 结构销毁操作 引用型操作 加工型操作 ADT List
基本操作： 结构初始化操作 结构销毁操作 引用型操作 加工型操作 } ADT List