1. 顺序表

顺序表(顺序存储结构) 存储数据时，会提前申请一整块足够大小的物理空间，然后将数据依次存储到一整块连续的存储空间内，存储时做到数据元素之间不留一丝缝隙。

使用顺序表存储集合 {1,2,3,4,5}，数据最终的存储状态如图所示：

2. 顺序表的初始化

使用顺序表存储数据之前，除了要申请足够大小的物理空间之外，为了方便后期使用表中的数据，顺序表还需要实时记录以下 2 项数据：

• 顺序表申请的存储容量；
• 顺序表的长度，也就是表中当前存储数据元素的个数；

因此，我们需要自定义顺序表，C 语言实现代码如下：

typedef struct List
{
    int *head;  //声明了一个名为head的长度不确定的数组，也叫“动态数组”
    int length; //记录当前顺序表的长度
    int size;   //记录顺序表分配的存储容量
}SqList;

接下来初始化顺序表，即初步建立一个顺序表。建立顺序表需要做如下工作：

• 给 head 动态数组申请足够大小的物理空间；
• 给 size 和 length 赋初值；

C 语言初始化顺序表(创建空表)的代码如下：

#define SIZE 5  //对SIZE进行宏定义，表示顺序表申请空间的大小
SqList InitList()
{
    SqList L;

    L.head = (int *)malloc(SIZE * sizeof(int));  //构造一个空的顺序表，动态申请存储空间
    
    if(!(L.head))   //如果申请失败，作出提示并直接退出程序
    {
        printf("初始化失败");
        exit(0);
    }

    L.size = SIZE; //空表的初始存储空间为SIZE
    L.length = 0;   //空表的长度初始化为0

    return L;
}

通过在主函数中调用 InitList 函数，就可以成功创建一个空的顺序表，然后我们可以试着向顺序表中添加一些元素再打印出来，C 语言完整代码清单如下：

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

#define SIZE 5  //对SIZE进行宏定义，表示顺序表申请空间的大小

typedef struct List
{
    int *head;  //声明了一个名为head的长度不确定的数组，也叫“动态数组”
    int length; //记录当前顺序表的长度
    int size;   //记录顺序表分配的存储容量
}SqList;

SqList InitList();
void DisplayList(SqList L);

int main()
{
    SqList L = InitList();
    //向顺序表中添加元素
    for(int i = 0; i < L.size; i++)
    {
        L.head[i] = (i+1);
        L.length++;
    }
    printf("顺序表中存储的元素分别是：\n");
    DisplayList(L);
}

SqList InitList()
{
    SqList L;

    L.head = (int *)malloc(SIZE * sizeof(int));  //构造一个空的顺序表，动态申请存储空间
    
    if(!(L.head))   //如果申请失败，作出提示并直接退出程序
    {
        printf("初始化失败");
        exit(0);
    }

    L.size = SIZE; //空表的初始存储空间为SIZE
    L.length = 0;   //空表的长度初始化为0

    return L;
}

//输出顺序表中元素的函数
void DisplayList(SqList L)
{
    for(int i = 0; i < L.length; i++)
    {
        printf("%d ", L.head[i]);
    }
    printf("\n");
}

程序运行结果如下：

顺序表中存储的元素分别是：
1 2 3 4 5