C语言线性表顺序存储结构实例详解

线性表的定义

线性表是数据结构中最基本的结构之一。它们是由相同数据类型的一组数据元素组成的序列。线性表具有唯一的首元素和唯一的末元素，除第一个元素之外的每个元素都有唯一的前继，除最后一个元素之外的每个元素都有唯一的后继。

线性表的存储方式

线性表有两种存储方式: 顺序存储和链式存储。

顺序存储采用一段连续的内存空间来存储线性表中的各元素。该结构的优点是可以随机访问元素，查找和访问速度较快，但是插入和删除操作需要移动大量元素，时间复杂度较高。

链式存储通过指针连接线性表中各元素，每个元素都包含指向下一元素的指针。链式结构的优点是插入和删除操作比较方便，不需要移动其他元素，缺点是链式结构不支持快速随机访问元素。

顺序存储结构的实现

顺序存储结构的实现需要先定义一个线性表的结构体，并定义存储线性表数据的数组。

下面是一个线性表结构体的定义：

#define MAXSIZE 20 //线性表的最大长度
typedef struct{
    int data[MAXSIZE];  //存储线性表数据的数组
    int length; //线性表的长度
}SeqList;

其中，MAXSIZE表示线性表的最大长度。data数组表示存储线性表数据的数组。length表示线性表的当前长度。

线性表的基本操作

初始化操作

初始化操作主要是将线性表的长度设置为0。代码如下：

void InitList(SeqList *L){
    L->length = 0; //设置线性表的长度为0
}

插入操作

插入操作主要是向线性表中插入一个元素。该操作有两个参数：要插入的线性表和要插入的元素。通常情况下，线性表的下标从1开始。

插入操作需要考虑两个方面：是否能够插入元素；插入的位置是否合法。插入元素的位置需要满足1<=pos<=L->length+1。插入元素的位置为pos，需要将pos之后的元素位置依次向后移动一位。

插入操作的代码如下：

bool InsertList(SeqList *L, int pos, int elem){
    if (pos < 1 || pos > L->length + 1) //插入位置不合法
        return false;
    if (L->length >= MAXSIZE) //线性表已满
        return false;
    for (int i = L->length; i >= pos; i--) //将指定位置之后的元素向后移动一位
        L->data[i+1] = L->data[i];
    L->data[pos] = elem; //插入元素
    L->length++; //线性表长度增加1
    return true;
}

在上述代码中，需要注意插入位置不合法和线性表已满的处理。

删除操作

删除操作主要是删除线性表中的一个元素。该操作有两个参数：要删除的线性表和要删除的元素位置。

删除操作需要考虑两个方面：删除的位置是否合法；删除元素后是否需要将其他元素位置依次向前移动一位。

删除操作的代码如下：

bool DeleteList(SeqList *L, int pos){
    if (pos < 1 || pos > L->length) //删除位置不合法
        return false;
    for (int i = pos; i < L->length; i++) //将指定位置之后的元素依次向前移动一位
        L->data[i] = L->data[i+1];
    L->length--; //线性表长度减少1
    return true;
}

在上述代码中，需要注意删除位置不合法的处理。

线性表的示例

示例一：往线性表中插入元素

#include <stdio.h>

#define MAXSIZE 20

//线性表的结构体
typedef struct{
    int data[MAXSIZE]; //存储线性表数据的数组
    int length; //线性表的长度
}SeqList;

//线性表的基本操作

//初始化操作
void InitList(SeqList *L){
    L->length = 0; //设置线性表的长度为0
}

//插入操作
bool InsertList(SeqList *L, int pos, int elem){
    if (pos < 1 || pos > L->length + 1) //插入位置不合法
        return false;
    if (L->length >= MAXSIZE) //线性表已满
        return false;
    for (int i = L->length; i >= pos; i--) //将指定位置之后的元素向后移动一位
        L->data[i+1] = L->data[i];
    L->data[pos] = elem; //插入元素
    L->length++; //线性表长度增加1
    return true;
}

//删除操作
bool DeleteList(SeqList *L, int pos){
    if (pos < 1 || pos > L->length) //删除位置不合法
        return false;
    for (int i = pos; i < L->length; i++) //将指定位置之后的元素依次向前移动一位
        L->data[i] = L->data[i+1];
    L->length--; //线性表长度减少1
    return true;
}

int main(){
    SeqList L; //定义线性表结构体
    int i, pos, elem;

    //初始化线性表
    InitList(&L);

    //往线性表中插入6个元素
    for (i = 1; i <= 6; i++)
        L.data[i] = i;
    L.length = 6;

    //输出线性表中的元素
    printf("原始线性表中的元素为:");
    for (i = 1; i <= L.length; i++)
        printf("%d ", L.data[i]);
    printf("\n");

    //向线性表中插入一个元素
    pos = 4; //插入的位置
    elem = 10; //插入的元素
    if (InsertList(&L, pos, elem) == true){
        printf("成功向线性表中插入元素%d，插入后线性表中的元素为:", elem);
        for (i = 1; i <= L.length; i++)
            printf("%d ", L.data[i]);
        printf("\n");
    }
    else{
        printf("插入元素失败\n");
    }

    return 0;
}

运行结果：

原始线性表中的元素为:1 2 3 4 5 6
成功向线性表中插入元素10，插入后线性表中的元素为:1 2 3 10 4 5 6

示例二：删除线性表中指定位置的元素

#include <stdio.h>

#define MAXSIZE 20

//线性表的结构体
typedef struct{
    int data[MAXSIZE]; //存储线性表数据的数组
    int length; //线性表的长度
}SeqList;

//线性表的基本操作

//初始化操作
void InitList(SeqList *L){
    L->length = 0; //设置线性表的长度为0
}

//插入操作
bool InsertList(SeqList *L, int pos, int elem){
    if (pos < 1 || pos > L->length + 1) //插入位置不合法
        return false;
    if (L->length >= MAXSIZE) //线性表已满
        return false;
    for (int i = L->length; i >= pos; i--) //将指定位置之后的元素向后移动一位
        L->data[i+1] = L->data[i];
    L->data[pos] = elem; //插入元素
    L->length++; //线性表长度增加1
    return true;
}

//删除操作
bool DeleteList(SeqList *L, int pos){
    if (pos < 1 || pos > L->length) //删除位置不合法
        return false;
    for (int i = pos; i < L->length; i++) //将指定位置之后的元素依次向前移动一位
        L->data[i] = L->data[i+1];
    L->length--; //线性表长度减少1
    return true;
}

int main(){
    SeqList L; //定义线性表结构体
    int i, pos;

    //初始化线性表
    InitList(&L);

    //往线性表中插入6个元素
    for (i = 1; i <= 6; i++)
        L.data[i] = i;
    L.length = 6;

    //输出线性表中的元素
    printf("原始线性表中的元素为:");
    for (i = 1; i <= L.length; i++)
        printf("%d ", L.data[i]);
    printf("\n");

    //删除线性表中指定位置的元素
    pos = 3;
    if (DeleteList(&L, pos) == true){
        printf("成功删除线性表中位置为%d的元素，删除后线性表中的元素为:", pos);
        for (i = 1; i <= L.length; i++)
            printf("%d ", L.data[i]);
        printf("\n");
    }
    else{
        printf("删除元素失败\n");
    }

    return 0;
}

运行结果：

原始线性表中的元素为:1 2 3 4 5 6
成功删除线性表中位置为3的元素，删除后线性表中的元素为:1 2 4 5 6