数据结构.ppt

第二章线性表 2 .1 线性表的定义和操作线性表(linear list) 是具有相同属性的数据元素的一个有限序列。该序列中所含元素的个数叫做线性表的长度,用 n表示, n≥0。当 n=0 时, 表示线性表是一个空表,即表中不包含任何元素。设序列中第 i个元素为 ai(1 ≤i≤ n),则线性表的一般表示为: (a1,a2, …,ai,ai+1, …,an) ?其中 a1 为线性表的第一个元素,又称为表头元素, a2 为第二个元素, an 为最后一个元素,又称为表尾元素。一个线性表可以用一个标识符来命名,如用 L命名上面的线性表,则 L=(a1,a2, …,ai,ai+1, …,an) 线性表中的元素在逻辑上是先后有序的,即第 i个元素 ai是第 i-1 个元素 ai-1 的后继,是第 i+1 个元素 ai+1 的前驱,其中第一个元素 a1 只有后继没有前驱,最后一个元素 an 只有前驱没有后继。所以线性表是一种线性结构,用二元组表示为: linear_list=(A,R), 其中 A={ai|1 ≤i≤ n, n ≥ 0, ai∈ ElemType} R={<ai,ai+1>|1 ≤i≤ n-1} 对应的逻辑图如图 2-1 所示。图 2-1 线性表的逻辑结构示意图(1) 初始化线性表 L,即置 L为一个空表 void InitList(L) (2) 清除线性表 L中的所有元素,使之成为一个空表 void ClearList(L) (3) 返回线性表 L的长度,若 L为空则返回 0 int SizeList(L) (4) 判断线性表 L是否为空,若为空则返回 1,否则返回 0 int EmptyList(L) (5) 返回线性表 L中第 pos 个元素的值,若 pos 超出范围,则停止程序运行 ElemType GetElem(L,pos) (6) 顺序扫描(即遍历)输出线性表 L中的每个元素 void TraverseList(L) (7) 从线性表 L中查找其值与 x相等的元素,若查找成功则返回其位置,否则返回-1 int FindList(L,x) (8) 把线性表 L中第 pos 个元素的值修改为 x的值,若修改成功返回 1,否则返回 0 int UpdatePosList(L,pos,x) (9) 向线性表 L的表头插入元素 x void InsertFirstList(L,x) (10) 向线性表 L的表尾插入元素 x void InsertLastList(L,x) (11) 向线性表 L中第 pos 个元素位置插入元素 x,若插入成功返回 1,否则返回 0 int InsertPosList(L,pos,x) (12) 向有序线性表 L中插入元素 x,使得插入后仍然有序 void InsertOrderList(L,x) (13) 从线性表 L中删除表头元素并返回它,若删除失败则停止程序运行 ElemType DeleteFirstList(L) (14) 从线性表 L中删除表尾元素并返回它,若删除失败则停止程序运行 ElemType DeleteLastList(L) (15) 从线性表 L中删除第 pos 个元素并返回它,若删除失败则停止程序运行 ElemType DeletePosList(L,pos) (16) 从线性表 L中删除值为 x的第一个元素,若删除成功返回 1否则返回 0 int DeleteValueList(L,x) 线性表的顺序存储结构和操作实现 线性表的顺序存储在定义一个线性表的顺序存储类型时,需要定义一个数组来存储线性表中的所有元素和定义一个整型变量来存储线性表的长度。假定数组用 list[MaxSize] 表示,整型变量用 size 表示,则元素类型为 ElemType 的线性表的顺序存储类型可描述为: ElemType list[MaxSize]; int size; 为了便于进行线性表的操作,可以把用于存储线性表元素的数组和存储线性表长度的变量同时说明在一个记录类型中,假定该记录类型用 List 表示,则定义如下: struct List { ElemType list[MaxSize]; int si