首先来看线性表定义:
线性表 (List): 零个或多个数据元素的有序排列.
关于线性表的基本操作:
Data: 线性表的数据对象集合为 {a1, a2, ......, an}, 每个元素的 类型均为 DataType . 其中, 除第一个元素 a1 外, 每一个元素有且只有一个直接前驱元素, 除了 最后一个元素 an 外, 每一个元素都有且只有一个直接后继元素. 数据元素之间的关系是一一对应的.
InitList( *L ): 初始化操作, 建立一个空的线性表 L .
ListEmpty( L ): 若线性表为空, 返回 true , 否则返回 false .
ClearList ( *L ): 将线性表清空.
GetElem( L, i, *e ): 将线性表 L 中第 i 个位置的元素值返回给 e .
LocateElem( L, e ): 在线性表 L 中查找与给定值 e 相等的元素, 如果查找成功, 返回该元素在表中序号表示成功; 否则, 返回 0 表示失败.
ListInsert( *L, i, e ): 在线性表 L 中的第 i 个位置插入新元素 e .
ListDelete( *L, i, *e): 删除线性表 L 中第 i 个位置元素, 并用 e 返回其值.
ListLength( L ): 返回线性表 L 的元素个数.
关于线性表集合 A(La) 和 B(Lb) 的并集操作:
- /* 将所有的在线性表 Lb 中但不在 La 中的数据元素插入到 La 中 */
- void union( List *La, List Lb ){
- int La_len, Lb_len, i;
- ElemType e; /* 声明与 La 和 Lb 相同的数据元素 e */
- La_len = ListLength( La );
- Lb_len = ListLength( Lb );
- for( i = 0 ; i <= Lb_len ; i++ ){
- GetElem( Lb, i, e); /* 取 Lb 中第 i 个数据元素赋给 e */
- if( !LocateElem( La, e, equal)) /* La 中不存在和 e 相同数据元素 */
- ListInsert( La, ++La_len, e); /* 插入 */
- }
- }
顺序储存方式
顺序储存方式是在一定的内存空间中, 把相同的数据类型的数据依次存放在这块内存空间中.
线性表顺序储存的结构代码:
- #define MAXSEZE 20 /* 存储空间初始分配量 */
- typedef int ElemType; /* ElemType 类型根据实际情况而定, 这里假设为 int */
- typedef struct{
- ElemType data[MAXSIZE]; /* 数组存储数据元素, 最大值为 MAXSEZE */
- int length; /* 线性表当前长度 */
- }SqList;
在这里我们发现描述顺序储存结构需要三个属性:
存储空间的起始位置: 数组 data, 它的存数位置就是存储空间的存储位置.
线性表的最大储存容量: 数组长度 MAXSIZE.
线性表的当前长度: length.
数组长度与线性表长度区别:
数组的长度是存放线性表的储存空间的长度, 存储分配后这个量一般是不变的. 线性表的长度是线性表黄总数据元素的个数, 随着线性表插入和删除操作的进行, 这个量是变化的.
地址计算方法:
假设每个数据元素占 c 个存储单元 (LOC 表示获取存储位置的函数.
LOC( a(i+1) ) = LOC( ai ) + c;
所以对于第 i 个数据元素 ai 的地址可以由 a1 推算得出:
LOC( ai ) = LOC( a1 ) + (i-1) * c
顺序存储结构的插入与删除操作
插入操作:
算法思路:
如果插入位置不合理, 抛出异常;
如果线性表长度大于等于数组长度, 则抛出异常或动态增加容量;
从最后一个元素开始向前遍历到第 i 个位置, 分别将他们都像后移动一个位置;
将要插入元素填入位置 i 处;
表长增加 1 .
- #define OK 1
- #define ERROR 0
- #define TRUE 1
- #define FALSE 0
- typedef int Status;
- /* Status 是函数的类型, 其值是函数结果状态码, 如 OK 等 */
- /* 初始条件: 顺序线性表 L 已存在, 1 <= i <= ListLength( L ) */
- /* 操作结果: 在 L 中第 i 个位置之前插入新的数据元素 e,L 的长度加 1 */
- Status ListInsert(SqList *L, int i, ElemType e){
- int k;
- if(L.length == MAXSEZE)
- return ERROR;
- if(i < 1 || i > L.length + 1)
- return ERROR;
- if(i <= L.length){
- for(k = L.length - 1; k > i - 1; k--){
- L.data[k+1] = L.data[k];
- }
- }
- L.data[i-1] = e; /* 将新元素插入 */
- L.length++;
- }
删除操作:
算法思路:
如果删除位置不合理, 抛出异常;
取出删除元素;
从删除元素位置开始遍历到最后一个元素位置, 分别将他们向前移动一个位置;
表长减 1 .
- /* `` */
- /* 操作结果: 删除 L 的第 i 个元素, 并用 e 返回其值, L 的长度减 1 */
- Status ListDelete (SqList *L, int i, ElemType *e){
- int k;
- if(L.length == 0) /* 线性表为空 */
- return ERROR;
- if(i < 1 || i > L.length)
- return ERROR;
- *e = L.data[i-1];
- if(i < L.length){
- for( k = i ; k < L.length ; k++){
- L.data[k-1] = l.data[k];
- }
- }
- L.length--;
- return OK;
- }
时间复杂度:
根据上次学习, 可以推导出 线性表的顺序储存结构在存, 读数据时, 不管哪个位置时间复杂度都是 O(1); 而插入删除时时间复杂度都是 O(n). 这就说明, 它比较适合元素个数不太变化, 而更多的是存取数据的应用. 当然, 它的优缺点还不仅这些...
线性表顺序存储结构的优缺点:
优点:
无须为表示表中元素之间的逻辑关系而增加额外的存储空间
可以快速的存取表中任一位置的元素
缺点:
插入和删除操作需要移动大量元素
当线性表长度变化较大时, 难以确定储存空间的容量
造成存储空间的 "碎片"
来源: http://stor.51cto.com/art/201806/575488.htm