02_linear_list.pdfVIP

第2章 线性表 . § 2.1 线性表的类型定义 . § 2.2 线性表的顺序表示和实现 . § 2.3 线性表的链式表示和实现 ? § 2.3.1 线性链表 ? § 2.3.2 循环链表 ? § 2.3.3 双向链表 . § 2.4 一元多项式的表示及相加 线性表是一种最简单的线性结构 线性结构的特点是: 在数据元素的非空有限集中： 1．存在唯一的一个“第一元素”； 2．存在唯一的一个 “最后元素” ； 3．除最后元素在外，均有 唯一的后继； 4．除第一元素之外，均有 唯一的前驱。 §2.1 线性表的类型定义 定义：线性表是n(n=0)个数据元素的 有限序列。 n是线性表的长度，n=0时为空表 表示：(a1,a2,…,ai,…,an) 相邻的元素之间存在着序偶关系 §2.2 线性表的顺序表示和实现 顺序表（向量）：用一组地址连 续的存储单元依次存放线性表中 的数据元素。 特点： 1 逻辑上相邻的元素，物理上也相邻； 2 支持随机存取。 a1 a2 … ai-1 ai … an 线性表的起始地址 称作线性表的基地址LOC(a1) 地址公式： 所有数据元素的存储位置均取决于第一 个数据元素的存储位置（随机存取） LOC(ai) = LOC(a1) + (i-1)×L ↑基地址 顺序映像的 C 语言描述 #define LIST_INIT_SIZE 100 // 线性表存储空间的初始分配量 #define LISTINCREMENT 10 // 线性表存储空间的分配增量 typedef struct { ElemType *elem; // 存储空间基址 int length; // 当前长度 int listsize; // 当前分配的存储容量 sizeof(ElemType) } SqList; // 俗称 顺序表 线性表的基本操作在顺序表中的实现 InitList(L) // 结构初始化 LocateElem(L, e, compare()) // 查找 ListInsert(L, i, e) // 插入元素 ListDelete(L, i) // 删除元素 Status InitList_Sq( SqList L ) { // 构造一个空的线性表 L.elem = (ElemType*) malloc (LIST_ INIT_SIZE?sizeof (ElemType)); if (!L.elem) exit(OVERFLOW); L.length = 0; L.listsize = LIST_INIT_SIZE return OK; } // InitList_Sq 算法时间复杂度： O(1) 图示：顺序表LocateElem_Sq L.elem L.listsize 23 75 41 38 54 62 17 pp p p p L.lengthp =7 i 12348 可见，基本操作是： 将顺序表中的元素逐个和给 e = 38 50 定值 e 相比较。 int LocateElem_Sq(SqList L, ElemType e, Status (*compare)(ElemType, ElemType)) { // 在顺序表中查询第一个满足判定条件的数据元素， // 若存在，则返回它的位序，否则返回 0 i = 1; // i 的初值为第 1 元素的位序 p = L.elem; // p 的初值为第 1 元素的存储位置 while (i = L.length !(*compare)(*p++, e))e) ++i; if (i = L.length) return i; else return 0; } // LocateElem_Sq 算法的时间复杂度为： O( ListLength(L) ) 线性表操作 ListInsert(L, i, e)的