顺序表的定义

顺序表：用顺序存储的方式实现线性表，每个结点中只存放数据元素

顺序表的特点：

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

顺序表的实现（静态分配）：

//顺序表的静态分配

#include <stdio.h>

#define MaxSize 10  //定义最大长度

typedef struct{
    int data[MaxSize];  //用静态的“数组”存放数据元素
    int length;  //顺序表的当前长度
}SqList;  //顺序表的类型定义

//基本操作：初始化一个顺序表
void InitList(SqList *L){
    for(int i=0;i<MaxSize;i++){
        L->data[i]=0;  //将所有数据元素设置为默认初始值
    }
    L->length=0;  //顺序表初始长度为0
}

int main(){
    
    SqList L;  //声明一个顺序表
    InitList(&L);  //初始化顺序表
    
    //...未完待续，后续操作
    return 0;
}

顺序表的实现（动态分配）：

//顺序表的动态分配

#include <stdio.h>
#include <stdlib.h>

#define InitSize 10  //默认的最大长度

typedef struct{
    int *data;  //指示动态分配数组的指针
    int MaxSize;  //顺序表的最大容量
    int length;  //顺序表的当前长度
}SeqList;

void InitList(SeqList *L){
    //用malloc函数申请一片连续的存储空间
    L->data=(int *)malloc(InitSize*sizeof(int));
    L->length=0;
    L->MaxSize=InitSize;
}

//增加动态数组的长度
void IncreaseSize(SeqList *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);  //释放原来的内存空间
}

int main(){
    SeqList L;  //声明一个顺序表
    InitList(&L);  //初始化顺序表
    //往顺序表加入几个元素，加满
    IncreaseSize(&L,5);
    return 0;
}