【数据结构】顺序表（c语言实现）（附源码）

2024-11-04 437

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 本文介绍了线性表和顺序表的基本概念及其实现。线性表是一种有限序列，常见的线性表有顺序表、链表、栈、队列等。顺序表是一种基于连续内存地址存储数据的数据结构，其底层逻辑是数组。文章详细讲解了静态顺序表和动态顺序表的区别，并重点介绍了动态顺序表的实现，包括初始化、销毁、打印、增删查改等操作。最后，文章总结了顺序表的时间复杂度和局限性，并预告了后续关于链表的内容。

前言

在我们学习顺序表之前，先引入一个概念：线性表。那么线性表是什么呢？

线性表，是n个具有相同特性的数据元素的有限序列。线性表在数据结构当中广泛使用。常见的线性表有：顺序表、链表、栈、队列、字符串......线性表在逻辑上是线性结构，也就是说数据元素就像一条线一样串联在一起，但是它的每一个数据元素的地址并不一定是连续的。

了解到顺序表是线性表的一种，接下来我们进入正题，开始正式学习顺序表。

1.顺序表的概念与结构

顺序表的概念：顺序表是一段按照连续的内存地址将数据元素依次存储的数据结构。一般情况下，它的底层逻辑是数组。也就是说，顺序表的每个元素的内存地址是连续的。

顺序表和数组的区别：虽然顺序表的底层结构是数组，但是我们在实现顺序表的过程中，对数组进行了封装，在数组的基础上增加了对它的一些方法，例如增删查改等操作。

2.顺序表的分类

顺序表可以分为静态顺序表和动态顺序表。顾名思义，静态顺序表的大小是固定不变的。它的结构定义如下：

#define N 10
 
typedef int SLDataType;
 
//静态顺序表
typedef struct SeqList
{
    SLDataType arr[N];//固定大小的数组
    int size;//有效数据的个数
}SL;

显然，这种结构是有缺陷的。当我们需要存放的数据很多时，它的内存大小是不够的。当存放的数据过少时，又会造成空间的浪费。所以，就有了动态顺序表。动态顺序表的内存大小可以根据数据的数量发生改变。它的结构定义如下：

typedef int SLDataType;
 
//动态顺序表
typedef struct SeqList
{
    SLDataType* arr;//定义起始指针，后续动态开辟内存空间
    int size;//有效数据的个数
    int capacity;//数组的空间大小
}SL;

由于动态顺序表强大的灵活性和实用性，我们平时所谈到的顺序表一般都指的是动态顺序表。接下来我们在以上结构的基础上，一一实现动态顺序表的基本功能。

3.顺序表的实现

3.1 结构定义及方法的声明

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
 
typedef int SLDataType;
 
//动态顺序表
typedef struct SeqList
{
    SLDataType* arr;//定义起始指针，后续动态开辟内存空间
    int size;//有效数据的个数
    int capacity;//数组的空间大小
}SL;
 
//初始化
void SLInit(SL* ps);
 
//销毁
void SLDestroy(SL* ps);
 
//打印顺序表
void SLPrint(SL* ps);
 
//检查空间大小，不够则增容
void SLCheckCapacity(SL* ps);
 
//尾插
void SLPushBack(SL* ps, SLDataType n);
 
//头插
void SLPushFront(SL* ps, SLDataType n);
 
//尾删
void SLPopBack(SL* ps);
 
//头删
void SLPopFront(SL* ps);
 
//指定位置之前插入数据
void SLInsert(SL* ps, int pos, SLDataType n);
 
//指定位置删除数据
void SLErase(SL* ps, int pos);
 
//查找
void SLFind(SL* ps, SLDataType n);

以上就是关于顺序表的定义和一些方法的的声明。接下来，我们尝试一一实现这些方法。

3.2 方法的实现

3.2.1 初始化

初始化时，我们将结构体赋一个初值就可以。代码如下：

//初始化
void SLInit(SL* ps)
{
    assert(ps);//断言一下，确保传入的不是空指针
    ps->arr = NULL;
    ps->capacity = ps->size = 0;
}

初始情况下，arr是一个空指针，结构的空间大小和数据个数都为0。

3.2.2 销毁

销毁顺序表时，我们将arr的内存释放掉，然后将空间大小和数据个数调整为0就好了。代码如下：

//销毁
void SLDestroy(SL* ps)
{
    assert(ps);//防止传空指针
    if (ps->arr != NULL)//防止多次释放
    {
        free(ps->arr);
        ps->arr = NULL;
    }
    ps->capacity = ps->size = 0;
}

3.2.3 打印顺序表

//打印顺序表
void SLPrint(SL* ps)
{
    assert(ps);//防止传空指针
    for (int i = 0; i < ps->size; i++)//遍历打印
    {
        printf("%d ", ps->arr[i]);
    }
    printf("\n");
}

3.2.4 检查空间大小，不够则增容

在我们插入数据的时候，数据的总数有可能会超出顺序表的空间大小，此时我们就需要检查空间大小，如果不够就需要增容。我们将增容封装为一个函数来实现：

//检查空间大小，不够则增容
void SLCheckCapacity(SL* ps)
{
    assert(ps);
    if (ps->capacity == ps->size)//空间大小与数据个数相等则说明空间已满
    {
        int NewCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;//设定一个新空间大小，第一次增容时大小为4，之后每次以2倍的形式增容
        SLDataType* tmp = (SLDataType*)realloc(ps->arr, NewCapacity * sizeof(SLDataType));//防止内存丢失，创建局部变量暂时接收起始地址
        if (tmp == NULL)//内存开辟失败退出程序
        {
            perror("realloc");
            exit(1);
        }
        ps->arr = tmp;//将调整好的内存赋值给arr
        ps->capacity = NewCapacity;
    }
}

3.2.5 尾插

//尾插
void SLPushBack(SL* ps, SLDataType n)
{
    assert(ps);
    SLCheckCapacity(ps);//检查空间大小
    ps->arr[ps->size++] = n;//在下标为size的位置插入元素，然后size自增
}

3.2.6 头插

在头插的过程中，我们需要先将所有的数据全部后移一位，然后在第一个位置插入数据。

代码如下：

//头插
void SLPushFront(SL* ps, SLDataType n)
{
    assert(ps);
    SLCheckCapacity(ps);//检查空间大小
    for (int i = ps->size; i > 0; i--)
    {
        ps->arr[i] = ps->arr[i - 1];//所有元素后移一位
    }
    ps->arr[0] = n;//第一个位置插入数据
    ps->size++;//元素个数加1
}

3.2.7 尾删

//尾删
void SLPopBack(SL* ps)
{
    assert(ps);
    assert(ps->size);//若数据为空，则不能删除
    ps->size--;//size自减，则最后一个元素无法被访问到，相当于删除了最后一个元素
}

这里只需要将size自减，使得最后一个元素无法被访问，相当于完成了删除操作。

3.2.8 头删

头删时，我们将第一个元素之后的所有元素向前移动一位即可。代码如下：

//头删
void SLPopFront(SL* ps)
{
    assert(ps && ps->size);//合并两个断言语句
    for (int i = 0; i < ps->size - 1; i++)
    {
        ps->arr[i] = ps->arr[i + 1];//整体向前移动一位，覆盖第一个元素
    }
    ps->size--;//元素个数减1
}

3.2.9 指定位置之前插入

在我们实现指定位置插入时，需要将该位置及之后的所有元素整体向后移动一位，然后再插入元素即可。代码如下：

//指定位置之前插入数据
void SLInsert(SL* ps, int pos, SLDataType n)//这里的参数pos是下标
{
    assert(ps && pos >= 0 && pos <= ps->size);//确保pos在合理范围内
    SLCheckCapacity(ps);
    for (int i = ps->size; i > pos; i--)
    {
        ps->arr[i] = ps->arr[i - 1];//将pos位置后的元素整体向后移动一位
    }
    ps->arr[pos] = n;//插入
    ps->size++;//元素个数加1
}

3.2.10 指定位置删除

指定位置删除时，将该位置之后的元素整体向前移动一位，覆盖该元素即可。代码如下：

//指定位置删除数据
void SLErase(SL* ps, int pos)
{
    assert(ps && ps->size && pos >= 0 && pos < ps->size);//确保pos在合理范围内
    for (int i = pos; i < ps->size - 1; i++)
    {
        ps->arr[i] = ps->arr[i + 1];//pos之后的元素整体向前移动一位，覆盖pos位置元素
    }
    ps->size--;//元素个数减1
}

3.2.11 查找

查找元素时，我们只需要遍历顺序表，找到符合的元素即可。

//查找
void SLFind(SL* ps, SLDataType n)
{
    assert(ps);
    for (int i = 0; i < ps->size; i++)//遍历顺序表
    {
        if (ps->arr[i] == n)
        {
            return i;//匹配成功则返回对应下标
        }
    }
    return -1;//找不到返回-1
}

4.程序全部代码

程序全部代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
 
typedef int SLDataType;
 
//动态顺序表
typedef struct SeqList
{
    SLDataType* arr;//定义起始指针，后续动态开辟内存空间
    int size;//有效数据的个数
    int capacity;//数组的空间大小
}SL;
 
//初始化
void SLInit(SL* ps);
 
//销毁
void SLDestroy(SL* ps);
 
//打印顺序表
void SLPrint(SL* ps);
 
//检查空间大小，不够则增容
void SLCheckCapacity(SL* ps);
 
//尾插
void SLPushBack(SL* ps, SLDataType n);
 
//头插
void SLPushFront(SL* ps, SLDataType n);
 
//尾删
void SLPopBack(SL* ps);
 
//头删
void SLPopFront(SL* ps);
 
//指定位置之前插入数据
void SLInsert(SL* ps, int pos, SLDataType n);
 
//指定位置删除数据
void SLErase(SL* ps, int pos);
 
//查找
void SLFind(SL* ps, SLDataType n);
 
//初始化
void SLInit(SL* ps)
{
    assert(ps);//断言一下，确保传入的不是空指针
    ps->arr = NULL;
    ps->capacity = ps->size = 0;
}
 
//销毁
void SLDestroy(SL* ps)
{
    assert(ps);//防止传空指针
    if (ps->arr != NULL)//防止多次释放
    {
        free(ps->arr);
        ps->arr = NULL;
    }
    ps->capacity = ps->size = 0;
}
 
//打印顺序表
void SLPrint(SL* ps)
{
    assert(ps);
    for (int i = 0; i < ps->size; i++)
    {
        printf("%d ", ps->arr[i]);
    }
    printf("\n");
}
 
//检查空间大小，不够则增容
void SLCheckCapacity(SL* ps)
{
    assert(ps);
    if (ps->capacity == ps->size)//空间大小与数据个数相等则说明空间已满
    {
        int NewCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;//设定一个新空间大小，第一次增容时大小为4，之后每次以2倍的形式增容
        SLDataType* tmp = (SLDataType*)realloc(ps->arr, NewCapacity * sizeof(SLDataType));//防止内存丢失，创建局部变量暂时接收起始地址
        if (tmp == NULL)//内存开辟失败退出程序
        {
            perror("realloc");
            exit(1);
        }
        ps->arr = tmp;//将调整好的内存赋值给arr
        ps->capacity = NewCapacity;
    }
}
 
//尾插
void SLPushBack(SL* ps, SLDataType n)
{
    assert(ps);
    SLCheckCapacity(ps);//检查空间大小
    ps->arr[ps->size++] = n;//在下标为size的位置插入元素，然后size自增
}
 
//头插
void SLPushFront(SL* ps, SLDataType n)
{
    assert(ps);
    SLCheckCapacity(ps);//检查空间大小
    for (int i = ps->size; i > 0; i--)
    {
        ps->arr[i] = ps->arr[i - 1];//所有元素后移一位
    }
    ps->arr[0] = n;//第一个位置插入数据
    ps->size++;//元素个数加1
}
 
//尾删
void SLPopBack(SL* ps)
{
    assert(ps);
    assert(ps->size);//若数据为空，则不能删除
    ps->size--;//size自减，则最后一个元素无法被访问到，相当于删除了最后一个元素
}
 
//头删
void SLPopFront(SL* ps)
{
    assert(ps && ps->size);//合并两个断言语句
    for (int i = 0; i < ps->size - 1; i++)
    {
        ps->arr[i] = ps->arr[i + 1];//整体向前移动一位，覆盖第一个元素
    }
    ps->size--;//元素个数减1
}
 
//指定位置之前插入数据
void SLInsert(SL* ps, int pos, SLDataType n)//这里的参数pos是下标
{
    assert(ps && pos >= 0 && pos <= ps->size);//确保pos在合理范围内
    SLCheckCapacity(ps);
    for (int i = ps->size; i > pos; i--)
    {
        ps->arr[i] = ps->arr[i - 1];//将pos位置后的元素整体向后移动一位
    }
    ps->arr[pos] = n;//插入
    ps->size++;//元素个数加1
}
 
//指定位置删除数据
void SLErase(SL* ps, int pos)
{
    assert(ps && ps->size && pos >= 0 && pos < ps->size);//确保pos在合理范围内
    for (int i = pos; i < ps->size - 1; i++)
    {
        ps->arr[i] = ps->arr[i + 1];//pos之后的元素整体向前移动一位，覆盖pos位置元素
    }
    ps->size--;//元素个数减1
}
 
//查找
void SLFind(SL* ps, SLDataType n)
{
    assert(ps);
    for (int i = 0; i < ps->size; i++)//遍历顺序表
    {
        if (ps->arr[i] == n)
        {
            return i;//匹配成功则返回对应下标
        }
    }
    return -1;//找不到返回-1
}

总结

以上就是我们顺序表的概念及功能实现。不难发现，它的许多方法都需要遍历数组，时间复杂度为O(N)，运行效率不是很高。之后博主将会介绍链表的相关知识和功能，他会弥补顺序表的一些不足。如果你觉得博主讲的还不错，就请留下一个小小的赞在走哦，感谢大家的支持❤❤❤

【数据结构】顺序表（c语言实现）（附源码）

前言

1.顺序表的概念与结构

2.顺序表的分类

3.顺序表的实现

3.1 结构定义及方法的声明

3.2 方法的实现

3.2.1 初始化

3.2.2 销毁

3.2.3 打印顺序表

3.2.4 检查空间大小，不够则增容

3.2.5 尾插

3.2.6 头插

3.2.7 尾删

3.2.8 头删

3.2.9 指定位置之前插入

3.2.10 指定位置删除

3.2.11 查找

4.程序全部代码

总结

热门文章

最新文章

相关课程

相关电子书

探索云世界

热门

云计算

大数据

云原生

人工智能

数据库

开发与运维

活动广场

任务中心

训练营

直播

乘风者计划

下载

镜像站

技术资料

【数据结构】顺序表（c语言实现）（附源码）

前言

1.顺序表的概念与结构

2.顺序表的分类

3.顺序表的实现

3.1 结构定义及方法的声明

3.2 方法的实现

3.2.1 初始化

3.2.2 销毁

3.2.3 打印顺序表

3.2.4 检查空间大小，不够则增容

3.2.5 尾插

3.2.6 头插

3.2.7 尾删

3.2.8 头删

3.2.9 指定位置之前插入

3.2.10 指定位置删除

3.2.11 查找

4.程序全部代码

总结

热门文章

最新文章

相关课程

相关电子书