【数据结构】二、顺序表的定义和基本操作的实现

数据结构 DATA STRUCTURE

二、线性表

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

2.2 线性表的顺序表示

顺序表：线性表的顺序存储。（顺序存储≠顺序存取）

用一组地址连续的存储单元依次存储线性表中的数据元素，使得逻辑上相邻的两个元素在物理位置上也相邻。

特点：

1. 逻辑相邻，物理也相邻。
2. 任一数据元素可 随机存取。

通常用数组来描述线性表的顺序存储结构。
注意：线性表中元素的位序是从1开始的，而数组中元素的下标是从0开始的。

2.2.1 顺序表存储结构描述和特点

1. 静态存储方式

#define MaxSize 50				// 定义线性表的最大长度的值
// 静态分配数组顺序表的类型定义
typedef struct{
    ElemType data[MaxSize];		// 顺序表的元素类型、长度
    int length;					// 顺序表当前长度
}SqList;						

2. 动态存储方式

#define InitSize 100
// 动态分配数组顺序表的类型定义
typedef struct{
    ElemType *data;				// 指示动态分配数组的指针
    int MaxSize, length;		// 数组的最大容量和当前个数
}SeqList;						

// C 的初始动态分配语句
L.data = (ElemType*)malloc(sizeof(ElemType) * InitSize);

// C++的初始动态分配语句
L.data = new ElemType[InitSize];

一维数组是可以静态分配，也可以是动态分配的。（不管是哪种分配方式，都属于顺序存储结构，物理结构没有变化，依然是随机存取方式，只是分配的空间大小可以在运行时动态决定。）

• 静态分配当空间占满的时候，容易产生溢出；
• 动态分配中存储数组的空间是在程序执行过程中通过动态存储分配语句分配的，空间占满，还可以开辟一块更大的存储空间替换原来的存储空间，不需要一次性划分所有空间。

静态动态的区别也就是用不用指针，指针就是为了间接访问，方便动态操作而设计的。用指针来指向数据域并且用指针进行动态分配即可实现“动态存储”。

关于malloc、free函数：

malloc会在内存中申请一整片连续的存储空间，并且返回指针。

动态分配基本操作实现：

初始化：

// 动态分配顺序表的初始化
void InitList(SqList &L) {
    L.data = (int *)malloc(InitSize * sizeof(int));
    L.length = 0;
    L.MaxSize = InitSize;
}

对 L 的三个成员变量进行赋值。

增加动态数组的长度：

void IncreaseSize(SqList &L, int len) {
    int *p = L.data;
    L.data = (int *)malloc((L.MaxSize+len)*sizeof(int));
    for (int i=0; i<L.length; i++) {
        L.data[i] = p[i];  // 将数据复制到新区域
    }
    L.MaxSize = L.MaxSize+len;  // 顺序表最大长度增加len
    free(p);  // 释放原来的内存空间
}

重新找到另外一块更大的区域，并且把之前的空间拿来，而且删除原来的空间。

1. 时间开销大❗❗
2. realloc 函数也可实现，malloc和free更底层。

3. 顺序表的优缺点

总是和表长length以及数组打交道（毕竟人家存储结构就是这俩