《数据结构》-线性表的顺序存储结构

2.1 线性表的类型定义,2.3 线性表的链式表示和实现,2.4 一元多项式的表示及相加,2.2 线性表的顺序表示和实现,第二章 线性表,2.2 线性表的顺序表示和实现,线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。,2.2 线性表的顺序存储结构,（1）线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。如下图2.1所示：,线性表的这种机内表示称做线性表的顺序存储结构或顺序映像(sequential mapping)。通常称这种存储结构的线性表为顺序表。,特点：以元素在计算机内“物理位置相邻”来表示线性表中数据元素之间的逻辑关系,存储地址 内存状态 数据元素在线性表中的位序 ba1 1 b+la22 b+(i-1)l ai i b+(n-1)lann b+nl 空闲 b+(maxlen-1)l,（2）求址公式 假设线性表的每个元素需占用l个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。 线性表中第i1个数据元素的存储位置 和第i个数据元素的存储位置 之间满足下列关系： 线性表的第i个数据元素ai的存储位置为：式中 是线性表的第一个数据元素 的存储位置，通常称做线性表的起始位置或基地址。 只要确定了存储线性表的起始位置，线性表中任一数据元素都可随机存取。线性表的顺序存储结构是一种随机存取的存储结构。,顺序映像的 C 语言描述,typedef struct SqList; / 俗称 顺序表,ElemType *elem; / 存储空间基址,int length; / 当前长度,int listsize; / 当前分配的存储容量 / (以sizeof(ElemType)为单位),#define LIST_INIT_SIZE 100 /线性表存储空间的初始分配量#define LISTINCREMENT 10 /线性表存储空间的分配增量,Status InitList_Sq( SqList& L, int maxsize ) / 构造一个最大容量为 maxsize 的顺序表 / InitList_Sq,算法时间复杂度：,O(1),L.elem = new ElemTypemaxsize; / 为顺序表分配大小为 maxsize 的数组空间if (!L.elem) exit(OVERFLOW);,L.length = 0;L.listsize = maxsize;return OK;,序号 数据元素 序号 数据元素 序号 数据元素 序号 数据元素 1 121 12 1 12 1 12 2 132 13 2 13 2 13 3 21 3 21 3 21 3 21 4 24 4 24 4 24 4 28 5 28 5 25 5 28 5 30 6 30 6 28 6 30 6 42 7 42 7 30 7 42 7 77 8 77 8 42 8 77 9 77 (a) (b) (a) (b)图2.2 线性表插入前后的情况 图2.3 线性表删除前后的情况 (a)插入前n8 (a)删除前n8 (b)插入后n9 (b)删除后n7,插入25,删除24,（4）线性表的插入和删除运算,Status ListInsert_Sq (SqList /ListInsert_Sq,插入运算 算法2.3如下：,Status ListDelete_Sq (SqList /ListDelete_Sq,删除运算 算法2.4如下：,（5）时间复杂度 从上述算法可见，当在顺序存储结构的线性表中某个位置上插入或删除一个数据元素时，其时间主要耗费在移动元素上，而移动元素的个数取决于插入或删除元素的位置。 假设pi是在第i个元素之前插入一个元素的概率，则在长度为n的线性表中插入一个元素时所需移动元素次数的期望值为： 不失一般性，若在线性表的任何位置插入元素都是等概率的，即 ，上式可化简为： 对于删除过程，假设qi是删除第i个元素的概率，则在长度为n的线性表中删除一个元素时所需移动元素次数的期望值为： 同样假设是等概率的情况，即 ，则有： 结论：由此可见，在顺序存储结构的线性表中插入或删除一个数据元素，平均约移动表中一半元素。若表长为n，则算法ListInsert_Sq和ListDelete_Sq的时间复杂度为O(n)。,int LocateElem_Sq(SqList L, ElemType e, Status (*compare)(ElemType, ElemType) / 在顺序表中查询第一个满足判定条件的数据元素， / 若存在，则返回它的位序，否则返回 0 / LocateElem_Sq,O( ListLength(L) ),if (i = L.length) return i; else return 0;,算法的时间复杂度为：,i = 1; / i 的初值为第 1 元素的位序p = L.elem; / p 的初值为第 1 元素的存储位置,while (i = L.length ,(*compare)(*p+, e),/找到满足条件的元