(04)王道数据结构-顺序表的定义

顺序表的定义：

定义：用顺序存储的方式实现线性表。顺序存储是把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。
顺序表实现-静态分配：

#define MaxSize 10  //定义最大长度
typedef struct {
    int data[MaxSize];  //用静态的“数组”存放数据元素
    int length;         //顺序表的当前长度
}SqList;                //顺序表的类型定义
//基本操作-初始化顺序表
void InitList(SqList &L);
int main(void) {
    SqList L;     //声明一个顺序表
    InitList(L);  //初始化顺序表
    return 0;
}

void InitList(SqList &L) {
    for (int i = 0; i < MaxSize; i++) {
        L.data[i] = 0;   //将所有数据元素设置为默认初始值
    }                   //顺序表初始长度为0
    L.length = 0;
}

注意事项： (01)静态分配的方式中，需要对数据进行初始化，否则内存中可能存在遗留的脏数据 (02)静态分配的方式无法保证之后添加数据后的操作
顺序表实现-动态分配：

#include<stdio.h>
#include<stdlib.h>
#define InitSize 10   //默认的最大长度
typedef struct {
    int *data;      //指示动态分配数组的指针
    int MaxSize;    //顺序表的最大容量
    int length;     //顺序表的当前长度
} SqList;
void InitList(SqList &L);
void IncreaseSize(SqList &L, int len);
int main(void) {
    SqList L;   //声明一个顺序表
    InitList(L);//初始化顺序表
    
    IncreaseSize(L, 5);  //增加顺序表长度
    return 0;
}

void InitList(SqList &L) {
    //用malloc函数声明一片连续的存储空间
    L.data = (int *)malloc(InitSize*sizeof(int));
    L.length = 0;
    L.MaxSize = InitSize;
}

//增加动态数组的长度
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;
    free(p);
}

顺序表的特点：

(1)随机访问，即可以在O(1)时间内找到第i个元素 (2)存储密度高，每个节点只存储数据元素 (3)扩展容量不方便（即便采用动态分配的方式实现，扩展长度的时间复杂度也比较高）