第 3 讲 线性表（一）

教学目标 了解线性表的特点； 了解线性表在逻辑结构层次上的定义及其抽象数据类型表示； 掌握线性表的顺序存储结构及两种不同存储类型的描述； 熟练掌握在顺序存储结构上实现线性表的插入和删除等操作。 2/16

线性结构的特点 存在唯一的一个首元素，该元素没有直接前驱； 存在唯一的一个尾元素，该元素没有直接后续； 除第一个元素外，有且仅有一个直接前驱； 除最后一个元素之外，有且仅有一个直接后继。 3/13

线性表的类型定义 线性表的定义 线性表是具有相同数据类型的 n (n>=0)个数据元素的有限序列，记为 (a1，a2，… ai-1，ai，ai+1，…an)。 其中n为表长， n＝0 时称为空表；i为数据元素ai在线性表中的位序，ai是ai+1的直接前驱， ai+1是ai 的直接后继。 举例说明 La=（34，89，765，12，90，-34，22） Ls=(Hello,World, China, Welcome) Lb=(book1,book2,...,book100) ，其中 struct bookinfo{ int No; char *name; char *auther; …} 4/13

抽象数据类型线性表的定义 }ADT List ADT List{ 数据对象：D={ai|ai∈ElemSet，i=1,2,…,n，n≥0} 　　数据关系：R={R1} R1={<ai-1,ai>|ai-1,ai∈D，i=2,…,n} 　　基本操作： InitList(&L) 操作结果：构造一个空的线性表Ｌ DestroyList(&L) 初始条件：线性表Ｌ已存在 操作结果：销毁线性表Ｌ ClearList(&L) 操作结果：将线性表Ｌ清为空表 … }ADT List 5/13

线性表的顺序表示和实现 静态顺序表 动态顺序表 顺序存储结构 物理地址计算公式 Loc(ai)=Loc(a１)+(i-1)*d 1<=i<=n 顺序存储结构分类 静态顺序表 动态顺序表 6/16

说明 预定义常量和类型 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 typedef in Status;

顺序表的类C语言描述 #define MAXSIZE 1000 静态顺序表 ElemType elem[MAXSIZE]; typedef struct{ ElemType elem[MAXSIZE]; int length; } SqList; 动态顺序表 ElemType *elem; int length; // 当前长度 8/16

初始化操作 #define MAXSIZE 1000 // 线性表存储空间的初始分配量 Status InitList_Sq(SqList &L) {// 构造一个空的线性表L。 L.elem= (ElemType*)malloc(MAXSIZE *sizeof(ElemType)); if (!L.elem) exit(OVERFLOW); // 存储分配失败 L.length = 0; // 长度为0 return OK; } // InitList_Sq 9/16

取值操作 Status GetElem (SqList L, int i, ElemType & e) { if(i<1||i>L.length) return error; e = L.elem[i-1]; return OK; } 10/16

查找操作 Status LocateElem (SqList L, ElemType e) { for(int i=0; i<L.length; i++) if(L.elem[i]==e) return i+1; return error; } 11/16

插入 定义：线性表的插入是指在第i（1i  n+1）个元素之前插入一个新的数据元素x，使长度为n的线性表 变成长度为n+1的线性表 需将第i至第n共（n-i+1)个元素后移

e 内存 a1 a2 ai ai+1 an 1 i-1 数组下标 n-1 i n 2 元素序号 i+1 n+1 内存 a1 a2 ai 1 i-1 数组下标 n-1 i n 2 元素序号 i+1 n+1 内存 a1 a2 ai ai+1 an 1 i-1 数组下标 n-1 i n 2 元素序号 i+1 n+1 an-1 e

插入算法 Status insertsqlist(SqList L, int i, ElemType e ) int j; if(L.length+1> MAXSIZE ) return error; else if(i<1||i>L.length+1) else { for(j=L.length-1; j>=i-1; j--) L.elem[j+1] = L. elem[j]; L. elem[i-1] = e; L.length = L.length+1; } return OK;

算法时间复杂度T(n) 设Pi是在第i个元素之前插入一个元素的概率，则在长度为n的线性表中插入一个元素时，所需移动的元素次数的平均次数为：

删除 定义：线性表的删除是指将第i（1i  n）个元素删除，使长度为n的线性表 变成长度为n-1的线性表 需将第i+1至第n共（n-i)个元素前移

内存 a1 a2 ai ai+1 an 1 i-1 数组下标 n-1 i n 2 元素序号 i+1 n+1 内存 a1 a2 ai+1 数组下标 1 i-1 n-2 i n-1 2 元素序号 i+1 n an ai+2

删除算法 Status ListDelete(SqList &L, int i) {//删除顺序表第i个位置元素 int j; if(i<1||i>L.length) return error; else { for(j=i; j<=L.length-1; j++) L. elem[j-1] = L. elem[j]; L.length = L.length-1; } return OK;

故在顺序表中插入或删除一个元素时，平均移动表的一半元素，当n很大时，效率很低 算法评价 设Qi是删除第i个元素的概率，则在长度为n的线性表中删除一个元素所需移动的元素次数的平均次数为： 故在顺序表中插入或删除一个元素时，平均移动表的一半元素，当n很大时，效率很低

顺序存储结构的优缺点 优点 逻辑相邻，物理相邻 可随机存取任一元素 存储空间使用紧凑 缺点 插入、删除操作需要移动大量的元素 预先分配空间需按最大空间分配，利用不充分

小结 本讲主要介绍了线性表的两种顺序存储结构以及顺序线性表初化、取值、查找、插入和删除操作的实现。重点介绍插入和删除操作在顺序表上的实现。 21/16

作业 编写程序实现线性表顺序存储结构的基本操作：初始化、插入、删除、打印、求长度等操作。 22/16