线性表

2.1 线性表的定义和基本操作

定义

具有相同数据类型的$n$个数据元素的有限序列，$n$为表长
$n=0$时为空表
可表示为 $L = (a_1, a_2, …, a_n)$

1. $a_i$时是线性表中的第$i$个元素
2. $a_1$为表头元素，$a_n$为表尾元素
3. 除了第一个元素外，每个元素有且只有一个直接前驱；除了最后一个元素外，每个元素有且只有一个直接后继

基本操作

创建、销毁、增删改查

2.2_1 顺序表的定义

用顺序存储的方式实现线性表
顺序存储：逻辑上相邻的元素存储在物理位置上也相邻的存储单元中
元素之间的关系由存储单元的邻接关系来体现

1. 由于元素类型相同，所以每个数据元素所占空间大小相同。因此如果知道其中一个元素的地址，可以很容易的得到每个元素的内存地址
2. sizeof(ElemType)可以得到不同类型变量占据内存空间大小

顺序表的实现——静态分配

#define MaxSize 10;
typedef struct{
    ElemType data[MaxSize];
    int length;
}SqList;

// 初始化一个顺序表
void InitList(SqList& L){
    // for(int i=0;i<MaxSize;++i){
    //     L.data[i] = 0;
    // }
    L.length = 0;
}

顺序表的实现——动态分配

#define InitSize 10
typedef struct{
    ElemType* data;
    int MaxSize;
    int length;
}SeqList;

// 初始化顺序表
void InitList(SqList& L){
    L.data = (ElemType*) malloc(sizeof(ElemType)*InitSize); // malloc 函数 + 强制类型转换
    L.length = 0;
    L.MaxSize = InitSize;
}

顺序表的特点

1. 随机访问：可以在O(1)时间内找到第i个元素
2. 存储密度高
3. 扩展容量不方便；插入删除元素不方便

2.2_2 顺序表的插入和删除

ListInsert(&L, i, e)

赏

谢谢你请我吃糖果

支付宝

微信