线性表（顺序存储结构）

线性表：包含零个或多个数据元素的有限序列。

线性表的顺序存储结构，指的是用一段连续的存储单元存储线性表的数据元素。

线性表特性：

• 是一个序列，元素直接是有顺序的。
• 表中元素个数叫表长，元素个数可以有多个，也可以为0。
• 某个元素的上一个元素叫直接前驱元素，下一个元素叫直接后继元素。

顺序存储结构特点
使用数组对元素进行存储。
优点：

• 可以快速存储表中任意位置的元素的值。
• 无需为表中的逻辑关系增加额外的存储空间。

缺点：

• 插入和删除元素需移动大量的元素。
• 容易生成存储空间"碎片"。

时间复杂度

• 读取时的时间复杂度为O(1)。
• 插入、删除时的时间复杂度为O(n)。

线性表示意图 线性表插入元素示意图.png 线性表删除元素示意图.png

实现代码如下：

// 线性表（顺序存储结构）
#include <stdio.h>

#define OK 1      // 执行成功
#define ERROR 0   // 执行失败
#define TRUE 1    // 返回值为真
#define FALSE 0   // 返回值为假

#define MAXSIZE 20 // 初始分配存储空间

typedef int Status; // 函数返回结果类型
typedef int ElemType; // 元素类型

// 线性表结构
typedef struct {
    ElemType data[MAXSIZE]; // 存放线性表元素的数组
    int length; // 线性表长度
} SqList;

/**
 * 初始化线性表
 * @param L 线性表
 * @return 执行状态
 */
Status InitList(SqList *L) {
    L->length = 0;
    return OK;
}

/**
 * 判断线性表是否为空
 * @param L 线性表
 * @return 执行状态
 */
Status ListEmpty(SqList L) {
    if (L.length == 0) {
        return TRUE;
    } else {
        return FALSE;
    }
}

/**
 * 清空线性表
 * @param L 线性表
 * @return 执行状态
 */
Status ClearList(SqList *L) {
    // 设置线性表长度为0
    L->length = 0;
    return OK;
}

/**
 * 获取线性表长度
 * @param L 线性表
 * @return 线性表长度
 */
int ListLength(SqList L) {
    return L.length;
}

/**
 * 获取线性表中指定位置的元素值
 * @param L 线性表
 * @param i 获取元素位置下标
 * @param e 获取元素值
 * @return 执行状态
 */
Status GetElem(SqList L, int i, ElemType *e) {
    // 数组长度为空，或下标不在数组范围内
    if (L.length == 0 || i < 1 || i > L.length) {
        return ERROR;
    }
    // 获取对应下标元素的值，赋值给e
    *e = L.data[i - 1];
    return OK;
}

/**
 * 定位元素e在线性表中的位置
 * 找到的该元素返回元素下标，未找到该元素返回0
 * @param L 线性表
 * @param e 元素
 * @return 元素在线性表中的下标
 */
int LocateElem(SqList L, ElemType e) {
    int i; // 元素下标
    // 线性表长度为空
    if (L.length == 0) {
        return 0;
    }

    // 遍历线性表，寻找元素e
    for (i = 0; i < L.length; i++) {
        // 找到元素e，退出循环
        if (L.data[i] == e) {
            break;
        }
    }

    // 下标大于线性表长度，未找到该元素
    if (i >= L.length) {
        return 0;
    }

    // 返回元素在线性表中的下标
    return i + 1;
}

/**
 * 在线性表中指定位置插入新元素
 * @param L 线性表
 * @param i 插入位置
 * @param e 插入的值
 * @return 执行状态
 */
Status ListInsert(SqList *L, int i, ElemType e) {
    int k; // 用于遍历元素的下标

    // 线性表已满，插入失败
    if (L->length == MAXSIZE) {
        return ERROR;
    }

    // 插入位置不在线性表范围内，插入失败
    if (i < 1 || i > L->length + 1) {
        return ERROR;
    }

    // 插入的位置在线性表范围内
    if (i <= L->length) {
        // 从倒数第二个元素开始到插入位置的元素，全都向后移动一个位置
        for (k = L->length - 1; k >= i - 1; k--) {
            L->data[k + 1] = L->data[k];
        }
    }

    L->data[i - 1] = e; // 将新元素插入
    L->length++; // 线性表长度加1
    return OK;
}

/**
 * 删除线性表中指定位置的元素
 * 删除位置的值，将存到元素e中
 * @param L 线性表
 * @param i 删除位置的下标
 * @param e 删除位置的值
 * @return 执行状态
 */
Status ListDelete(SqList *L, int i, ElemType *e) {
    int k; // 用于遍历元素的下标

    // 线性表长度为空，删除失败
    if (L->length == 0) {
        return ERROR;
    }

    // 删除位置不在线性表范围内，删除失败
    if (i < 1 || i > L->length) {
        return ERROR;
    }

    // 将删除位置元素的值赋值给e
    *e = L->data[i - 1];

    // 删除位置在线性表范围内
    if (i < L->length) {
        // 从删除位置的下一个元素到线性表最后一个元素，全都向前移动一个位置
        for (k = i; k < L->length; k++) {
            L->data[k - 1] = L->data[k];
        }
    }
    // 线性表长度减1
    L->length--;
    return OK;
}

/**
 * 打印单个元素
 * @param c 元素值
 * @return 执行状态
 */
Status visit(ElemType c) {
    printf("%d ", c);
    return OK;
}

/**
 * 遍历输出线性表中所有元素
 * @param L 线性表
 * @return 执行状态
 */
Status ListTravel(SqList L) {
    int i; // 用于遍历元素的下标

    printf("[ ");
    // 遍历线性表所有元素
    for (i = 0; i < L.length; i++) {
        visit(L.data[i]); // 打印单个元素
    }
    printf("]\n");
    return OK;
}

/**
 * 合并两个线性表的值到La中
 * @param La 线性表1
 * @param Lb 线性表2
 */
void unionL(SqList *La, SqList Lb) {
    int i; // 用于遍历元素的下标
    int La_len, Lb_len; // 线性表La、Lb的长度
    ElemType e; // 用于存放Lb中元素的值

    // 获取线性表La和Lb的长度
    La_len = ListLength(*La);
    Lb_len = ListLength(Lb);

    // 遍历线性表Lb中的元素
    for (i = 1; i <= Lb_len; i++) {
        // 获取Lb中i位置元素的值到元素e中
        GetElem(Lb, i, &e);
        // 元素e中的值在La中不存在
        if (!LocateElem(*La, e)) {
            // 将元素e插入La的最后
            ListInsert(La, ++La_len, e);
        }
    }
}

int main() {
    SqList L; // 线性表
    SqList Lb;
    Status status; // 执行状态
    ElemType e; // 线性表元素
    int result; // 运行结果
    int j, k; // 用于遍历元素的下标

    InitList(&L); // 初始化线性表
    printf("初始化线性表L后，L的长度为：%d\n", L.length);

    result = ListEmpty(L); // 获取线性表是否为空
    printf("L是否为空：%s\n", result == TRUE ? "是" : "否");

    /*** 给L的表头插入5个元素 ***/
    for (j = 1; j <= 5; j++) {
        status = ListInsert(&L, 1, j); // 向线性表表头插入值
    }
    printf("在L表头依次插入1~5后，L中的值为：");
    ListTravel(L); // 遍历线性表

    printf("插入5个元素后，L的长度为：%d\n", L.length);

    result = ListEmpty(L); // 获取线性表是否为空
    printf("L是否为空：%s\n", result == TRUE ? "是" : "否");

    /*** 清空L中的元素 ***/
    status = ClearList(&L); // 清空线性表
    printf("清空线性表L后，L的长度为：%d\n", L.length);

    result = ListEmpty(L); // 获取线性表是否为空
    printf("L是否为空：%s\n", result == TRUE ? "是" : "否");

    /*** 给L的表尾插入10个元素 ***/
    for (j = 1; j <= 10; j++) {
        ListInsert(&L, j, j); // 向线性表表尾插入值
    }
    printf("在L表尾依次插入1~10后，L中的值为：");
    ListTravel(L); // 遍历线性表

    printf("插入10个元素后，L的长度为：%d\n", L.length);

    /*** 给L的表头插入一个元素 ***/
    ListInsert(&L, 1, 33); // 向线性表表头插入元素33

    printf("在L表头插入元素33后，L中的值为：");
    ListTravel(L); // 遍历线性表

    printf("插入元素33后，L的长度为：%d\n", L.length);

    /*** 获取第5个元素的值 ***/
    GetElem(L, 5, &e); // 获取L中下标为5的元素到e中
    printf("L中第5个元素的值为：%d\n", e);

    /*** 获取下标为3、4元素的值 ***/
    for (j = 3; j <= 4; j++) {
        k = LocateElem(L, j); // 获取L中下标为j的元素的值
        if (k) {
            printf("第%d个元素的值为：%d\n", k, j);
        } else {
            printf("没有值为%d的元素\n", j);
        }
    }

    /*** 删除表中多个元素 ***/
    k = ListLength(L); // k为表长
    for (j = k + 1; j >= k; j--) {
        status = ListDelete(&L, j, &e); // 删除L中第j个元素，并把删除元素的值赋值给e
        if (status == ERROR) {
            printf("删除第%d个元素失败\n", j);
        } else {
            printf("删除第%d个元素的值为：%d\n", j, e);
        }
    }
    printf("删除表中元素后，L中的值为：");
    ListTravel(L); // 遍历线性表

    /*** 删除L中第5个元素 ***/
    j = 5;
    ListDelete(&L, j, &e); // 删除L中第j个元素，并把删除元素的值赋值给e
    printf("删除第%d个元素的值为：%d\n", j, e);

    printf("删除第%d个元素后，L中的值为：",j);
    ListTravel(L); // 遍历线性表

    /*** 初始化线性表Lb，给Lb的表头插入10个元素 ***/
    status = InitList(&Lb); // 初始化线性表Lb
    for (j = 6; j <= 15; j++) {
        status = ListInsert(&Lb, 1, j); // 向Lb表头插入10个元素
    }
    printf("插入10个元素后，Lb中的值为：");
    ListTravel(Lb);

    /*** 合并L和Lb的值到L中 ***/
    unionL(&L, Lb); // 合并两个线性表的值到L中

    printf("合并L和Lb到L后，L中的值为：");
    ListTravel(L); // 遍历线性表

    return 0;
}

运行结果.png