顺序表揭秘：掌握数据存储的基础艺术

一、引言

在计算机科学中，数据结构是存储和组织数据以使插入、删除和访问更高效的重要方式。顺序表（Array List）是一种基本且常用的数据结构，其利用内存的连续性来存储元素，为我们提供了简洁高效的数据操作手段。在学习数据结构时，顺序表是非常适合初学者的一个起点，因为它简明的实现可以帮助我们更好地理解数组的底层机制和数据的操作过程。

本文将详细介绍顺序表的基本概念、实现方法、应用场景，并展示如何用 C 语言编写动态顺序表代码。你将了解顺序表的不同类型以及如何高效地执行插入、删除等操作。如果你想更加深入地理解顺序表，并掌握它的实现细节，这篇文章会是你的好帮手。

二、顺序表的基本概念与结构

1.概念

顺序表（也称为线性表）是一种线性数据结构，其中元素按照顺序在内存中连续存储。

顺序表的底层结构是数组，它对数组进行了封装，提供了常用的增、删、改、查接口。这种结构的优点在于能够高效地实现随机访问，但也存在插入和删除操作效率较低的缺点，尤其是在数组中间进行操作时。

它的主要特点包括：
连续存储：所有元素在内存中占据一块连续的空间。
索引访问：可以通过索引快速访问任意元素。
固定大小：在静态实现中，顺序表的大小在创建时确定，无法动态调整。

2.基本结构

在C语言中，顺序表通常用一个数组来实现。以下是一个顺序表的基本结构：

//静态顺序表
typedef int DataType;重定义类型名字
#define MAX_SIZE 100
typedef struct {
    DataType data[MAX_SIZE];//定长数组
    int size; // 有效数据个数
} SL;

三、顺序表的分类

顺序表可以根据存储方式和动态变化的特性进行分类，包括静态顺序表和动态顺序表。静态顺序表在编译时分配固定的存储空间，而动态顺序表则允许在运行时根据需要调整大小，从而提供更大的灵活性。

1.静态顺序表

定义：使用静态数组实现的顺序表，其存储空间在编译时分配，大小固定不变。
特点：
空间分配在栈区或全局数据区。
容量固定，不易扩展。

2.动态顺序表

定义：使用动态数组实现的顺序表，其存储空间在运行时动态分配，可以根据需要进行扩展或缩减。
特点：
空间分配在堆区。
容量可变，通过 malloc 、 realloc 和 free 等操作进行管理。

四、动态顺序表的实现

1.结构定义

动态顺序表的结构定义如下：

typedef struct SeqList
{
    DataType* arr;
    int size;//有效数据个数
    int capacity;//容量
}SL;

在这个定义中，

arr

是一个指向动态数组的指针，

size

记录当前已存储的数据数量，而

capacity

则表示数组的总容量。通过这种方式，动态顺序表能够根据实际存储情况灵活调整内存使用。

2.相关功能实现

1.初始化

初始化函数用于设置动态顺序表的初始状态：

// 初始化顺序表
void SLInit(SL* p)
{
    // 初始化顺序表，使其容量和大小均为0，数据指针为NULL
    p->arr = NULL;
    p->size = p->capacity = 0;
}

该函数将顺序表的

arr

指针初始化为

NULL

，并将

size

和

capacity

设置为0，以便在后续操作中动态分配内存。

2.销毁

销毁函数用于释放动态顺序表占用的内存：

// 销毁顺序表
void SLDestroy(SL* p)
{
    // 如果数组存在，释放内存
    if (p->arr)
    {
        free(p->arr);
    }
    // 将指针和容量大小重置为0，防止野指针
    p->arr = NULL;
    p->size = p->capacity = 0;
}

在销毁过程中，首先检查

arr

是否指向有效内存，如果是，则调用

free

释放内存，最后将所有相关参数重置。

3.扩容

扩容功能是动态顺序表的核心，确保在需要时能够增加数组的容量：

// 检查并扩充容量
void checkcapacity(SL* p)
{
    // 如果当前容量等于大小，说明需要扩充
    if (p->size == p->capacity)
    {
        // 新容量为原来的两倍，如果当前容量为0，则初始为4
        int newcapacity = p->capacity == 0 ? 4 : 2 * p->capacity;
        // 重新分配内存空间
        DataType* tmp = (DataType*)realloc(p->arr, newcapacity * sizeof(DataType));
        if (tmp == NULL)
        {
            // 重新分配失败，打印错误信息并退出程序
            perror("realloc fail");
            exit(1);
        }
        // 空间申请成功，更新数组指针和容量
        p->arr = tmp;
        p->capacity = newcapacity;
    }
}

在扩容时，首先判断当前

size

是否等于

capacity

，若相等则需要扩容。新容量设定为当前容量的两倍，初始时为4。使用

realloc

函数动态调整内存并更新指针。

**4.打印 **

打印功能用于输出动态顺序表中的所有数据：

// 打印顺序表
void SLPrint(SL s)
{
    // 遍历顺序表并打印每个元素
    for (int i = 0; i < s.size; i++)
    {
        printf("%d ", s.arr[i]);
    }
    printf("\n");  // 换行，方便观察输出
}

5.头插

头插：在表头插入新元素。

// 顺序表头插入元素
void SLPushHead(SL* p, DataType x)
{
    assert(p);  // 确保顺序表不为空
    checkcapacity(p);  // 检查容量是否足够，不足则扩展
    // 从后向前移动元素，空出头部位置
    for (int i = p->size; i >= 1; i--)
    {
        p->arr[i] = p->arr[i - 1];
    }
    // 插入新元素到头部
    p->arr[0] = x;
    p->size++;
}

**6.尾插 **

尾插：在表尾添加新元素。

// 顺序表尾插入元素
void SLPushBack(SL* p, DataType x)
{
    assert(p);  // 确保顺序表不为空
    checkcapacity(p);  // 检查容量是否足够，不足则扩展
    // 插入新元素到尾部
    p->arr[p->size++] = x;
}

**7.头删 **

头删：删除表头元素。

// 顺序表头删除元素
void SLDelHead(SL* p)
{
    assert(p);  // 确保顺序表不为空
    assert(p->size > 0);  // 确保顺序表中有元素可以删除
    // 从前向后移动元素，覆盖掉头部元素
    for (int i = 1; i <= p->size - 1; i++)
    {
        p->arr[i - 1] = p->arr[i];
    }
    p->size--;  // 减少顺序表的大小
}

**8.尾删 **

尾删：删除表尾元素。

// 顺序表尾删除元素
void SLDelBack(SL* p)
{
    assert(p);  // 确保顺序表不为空
    assert(p->size > 0);  // 确保顺序表中有元素可以删除
    p->size--;  // 直接减少顺序表的大小
}

**9.指定插入 **

指定位置插入：在指定位置进行插入操作。

// 在指定位置前插入数据
void SLInsert(SL* p, int pos, DataType x)
{
    assert(p);  // 确保顺序表不为空
    assert(pos >= 0 && pos <= p->size);  // 确保插入位置合法
    checkcapacity(p);  // 检查容量是否足够，不足则扩展
    // 从后向前移动元素，空出指定位置
    for (int i = p->size - 1; i >= pos; i--)
    {
        p->arr[i + 1] = p->arr[i];
    }
    // 插入新元素到指定位置
    p->arr[pos] = x;
    p->size++;
}

**10.指定删除 **

指定位置删除：在指定位置进行删除操作。

// 删除指定位置的数据
void SLErase(SL* p, int pos)
{
    assert(p);  // 确保顺序表不为空
    assert(pos >= 0 && pos < p->size);  // 确保删除位置合法
    // 从前向后移动元素，覆盖掉指定位置的数据
    for (int i = pos; i <= p->size - 2; i++)
    {
        p->arr[i] = p->arr[i + 1];
    }
    p->size--;  // 减少顺序表的大小
}

**11.查找 **

查找操作用于在顺序表中寻找特定元素：

// 顺序表的查找
int SLFind(SL* p, DataType x)
{
    assert(p);  // 确保顺序表不为空
    // 遍历顺序表查找指定元素
    for (int i = 0; i < p->size; i++)
    {
        if (p->arr[i] == x)
        {
            return i;  // 找到了，返回元素的位置
        }
    }
    return -1;  // 没有找到，返回-1
}

该函数遍历顺序表的所有有效元素，若找到匹配项则返回其索引，未找到则返回-1。

五、完整代码

1.SeqList.h

该部分放顺序表结构定义、函数的声明

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int DataType;
//动态顺序表
typedef struct SeqList
{
    DataType* arr;
    int size;//有效数据个数
    int capacity;//容量
}SL;

//初始化顺序表
void SLInit(SL* p);
//销毁顺序表
void SLDestroy(SL* p);
//打印顺序表
void SLPrint(SL s);
//顺序表头插
void SLPushHead(SL* p, DataType x);
//顺序表尾插
void SLPushBack(SL* p, DataType x);
//顺序表头删
void SLDelHead(SL* p);
//顺序表尾删
void SLDelBack(SL* p);
//在指定位置前插入数据
void SLInsert(SL* p, int pos, int x);
//删除指定位置的数据
void SLErase(SL* p, int pos);
//顺序表的查找
int  SLFind(SL* p, DataType x);

2.SeqList.c

该部分是函数功能的实现，也就是上述第四点的代码

#define _CRT_SECURE_NO_WARNINGS
#include"SeqList.h"

// 初始化顺序表
void SLInit(SL* p)
{
    // 初始化顺序表，使其容量和大小均为0，数据指针为NULL
    p->arr = NULL;
    p->size = p->capacity = 0;
}

// 销毁顺序表
void SLDestroy(SL* p)
{
    // 如果数组存在，释放内存
    if (p->arr)
    {
        free(p->arr);
    }
    // 将指针和容量大小重置为0，防止野指针
    p->arr = NULL;
    p->size = p->capacity = 0;
}

// 检查并扩充容量
void checkcapacity(SL* p)
{
    // 如果当前容量等于大小，说明需要扩充
    if (p->size == p->capacity)
    {
        // 新容量为原来的两倍，如果当前容量为0，则初始为4
        int newcapacity = p->capacity == 0 ? 4 : 2 * p->capacity;
        // 重新分配内存空间
        DataType* tmp = (DataType*)realloc(p->arr, newcapacity * sizeof(DataType));
        if (tmp == NULL)
        {
            // 重新分配失败，打印错误信息并退出程序
            perror("realloc fail");
            exit(1);
        }
        // 空间申请成功，更新数组指针和容量
        p->arr = tmp;
        p->capacity = newcapacity;
    }
}

// 打印顺序表
void SLPrint(SL s)
{
    // 遍历顺序表并打印每个元素
    for (int i = 0; i < s.size; i++)
    {
        printf("%d ", s.arr[i]);
    }
    printf("\n");  // 换行，方便观察输出
}

// 顺序表头插入元素
void SLPushHead(SL* p, DataType x)
{
    assert(p);  // 确保顺序表不为空
    checkcapacity(p);  // 检查容量是否足够，不足则扩展
    // 从后向前移动元素，空出头部位置
    for (int i = p->size; i >= 1; i--)
    {
        p->arr[i] = p->arr[i - 1];
    }
    // 插入新元素到头部
    p->arr[0] = x;
    p->size++;
}

// 顺序表尾插入元素
void SLPushBack(SL* p, DataType x)
{
    assert(p);  // 确保顺序表不为空
    checkcapacity(p);  // 检查容量是否足够，不足则扩展
    // 插入新元素到尾部
    p->arr[p->size++] = x;
}

// 顺序表头删除元素
void SLDelHead(SL* p)
{
    assert(p);  // 确保顺序表不为空
    assert(p->size > 0);  // 确保顺序表中有元素可以删除
    // 从前向后移动元素，覆盖掉头部元素
    for (int i = 1; i <= p->size - 1; i++)
    {
        p->arr[i - 1] = p->arr[i];
    }
    p->size--;  // 减少顺序表的大小
}

// 顺序表尾删除元素
void SLDelBack(SL* p)
{
    assert(p);  // 确保顺序表不为空
    assert(p->size > 0);  // 确保顺序表中有元素可以删除
    p->size--;  // 直接减少顺序表的大小
}

// 在指定位置前插入数据
void SLInsert(SL* p, int pos, DataType x)
{
    assert(p);  // 确保顺序表不为空
    assert(pos >= 0 && pos <= p->size);  // 确保插入位置合法
    checkcapacity(p);  // 检查容量是否足够，不足则扩展
    // 从后向前移动元素，空出指定位置
    for (int i = p->size - 1; i >= pos; i--)
    {
        p->arr[i + 1] = p->arr[i];
    }
    // 插入新元素到指定位置
    p->arr[pos] = x;
    p->size++;
}

// 删除指定位置的数据
void SLErase(SL* p, int pos)
{
    assert(p);  // 确保顺序表不为空
    assert(pos >= 0 && pos < p->size);  // 确保删除位置合法
    // 从前向后移动元素，覆盖掉指定位置的数据
    for (int i = pos; i <= p->size - 2; i++)
    {
        p->arr[i] = p->arr[i + 1];
    }
    p->size--;  // 减少顺序表的大小
}

// 顺序表的查找
int SLFind(SL* p, DataType x)
{
    assert(p);  // 确保顺序表不为空
    // 遍历顺序表查找指定元素
    for (int i = 0; i < p->size; i++)
    {
        if (p->arr[i] == x)
        {
            return i;  // 找到了，返回元素的位置
        }
    }
    return -1;  // 没有找到，返回-1
}

3.test.c

该部分用来测试我们写的函数(函数的调用)，可以随便改

#define _CRT_SECURE_NO_WARNINGS
#include"SeqList.h"
void SLtest01()//测试
{
    SL sl;
    SLInit(&sl);
    //增删查改操作
    SLPushHead(&sl,1);//头插1      1
    SLPushHead(&sl,3);//头插3      31
    SLPushBack(&sl, 5);//尾插5     315
    SLInsert(&sl,3,7);//在下标为3的位置插入7    3157
    SLErase(&sl,2);//删除下标为2的数据     317
    SLPrint(sl);
    int find = SLFind(&sl, 3);
    if (find>=0)
    {
        printf("找到了，下标为%d\n", find);
    }
    else
    {
        printf("没有找到");
    }
    SLDestroy(&sl);
}
int main()
{
    SLtest01();
    return 0;
}

六、总结

顺序表是一种简单而强大的数据结构，通过使用连续内存存储实现高效的随机访问。根据不同的需求，开发者可以选择静态顺序表或动态顺序表以适应各种应用场景。动态顺序表的灵活性和效率使其在实际应用中更具优势。希望本文能帮助您更好地理解顺序表及其实现方式，从而在未来的学习和项目中得心应手。