二章 线性表.pptVIP

第二章 线性表 线性表的定义 线性表 n个结点（数据元素）的有限序列。 始结点唯一，即存在一个结点没有前趋结点。 终结点唯一，即存在一个结点没有后继结点。 除始结点外，其它结点均只有一个前趋结点。 除终结点外，其它结点均只有一个后继结点。 线性表举例 简单数据元素 (6, 17, 28, 50, 92, 188) (A, B, D, E, C) 复杂数据元素 学生成绩登记表 线性表中的各个数据元素具有相同（或相容）的类型。 线性表中的元素个数称为线性表的长度。 长度为0的线性表称为空表。 线性表可视为容纳某类对象的容器。 线性表中每个元素有一个表明其位置的编号 始结点编号为0，始结点的直接后继结点编号为1，…，终结点的编号为n-1。（线性表长度为n） 线性表的主要操作： 初始化，即构造一个空表 InitList 求长度，返回线性表的长度 ListLength 判空，判断线性表是否空表 ListEmpty 判满，判断线性表是否已满 ListFull 插入，在线性表的第i个位置插入一个元素 ListInsert 删除，删除线性表中第i个元素 ListDelete 取元素，读取线性表中第i个元素 GetElem 定位，得到满足关系的元素的位序LocateElem 线性表的实现 —顺序存储 顺序映象 以存储位置先后表示元素间的前趋和后继关系。 用一组地址连续的存储单元依次存放线性表中的数据元素。 若每个元素占用 k个存储单元，用其中第一个单元的地址作为元素的存储位置。则元素 ai 的存储位置可以表示为LOC(ai)。 线性表中第 i+1 个元素和第 i 个元素的存储位置间满足下列关系:LOC(ai+1) = LOC(ai) + k 线性表中第 i个元素的存储位置为：LOC(ai) = LOC(a0) + i * k, 1=i=n 其中LOC(a0)是线性表的基地址。 C/C++中，数组元素占据连续存储单元，可用来实现顺序存储的线性表。 LOC(ai) = LOC(a0) + i * k, 1=i=n 线性表的定义为(C语言)： typedef int datatype; //假定线性表元素的类型为整型 #define maxsize 1024 //假定线性表的最大长度为1024。C的宏常量 typedef struct { datatype data[maxsize]; //数组 int length; //当前线性表的长度 } List; 线性表元素的插入 int INSERT(List *L, datatype x, int i) //插入第i个 { int j; if (((*L).length)=maxsize－1) { printf(“overflow\n”); return 1;} //溢出 if((i1)||(i((*L).length+1)) { printf(“error\n”); return 2;} //非法位置 for(j=(*L).length; ji-1; j - -) //挪动后面的元素 (*L).data[j]＝(*L).data[j-1]; (*L).data[i-1]＝x; (*L).length++; return 0; //成功插入 } 线性表元素的删除 int DELETE(List *L, int i) { int j; if ((i1)||(i(*L).length+1)) { printf(“error\n”); return 1;} //非法位置 for(j=i; j(*L).length; j++) (*L).data[j-1]＝(*L).data[j]; (*L).length--; //表长减1 return 0; //成功 } 算法时间复杂度分析 假设在第 i 个位置插入元素的概率为pi ，则在长度为n 的线性表中插入一个元素所需移动元素次数的期望值为： 假定在线性表中任何一个位置上进行插入的概率都是相等的，则移动元素的期望值为： 在线性表中插入一个元素平均需要移动一半元素，时间复杂度是线性阶，即O(n)。 在顺序实现中： insert 和 delete 的时间复杂度是O(n)。 clear、empty、full、size的时间复杂度是O(1)。 顺序表的优点： 无须为表示节点间的逻辑关系而增加额外存储空间 可以方便的随机存取表中的任一节点 顺序表的缺点 插入和删除运算不方便,需移动大量元素 由于要求占用连续的存储空间，存储分配只能预先进行,需要预先估计所需最大空间 表的容量不能动态