AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

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

2024-11-04 46
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 本文介绍了线性表和顺序表的基本概念及其实现。线性表是一种有限序列，常见的线性表有顺序表、链表、栈、队列等。顺序表是一种基于连续内存地址存储数据的数据结构，其底层逻辑是数组。文章详细讲解了静态顺序表和动态顺序表的区别，并重点介绍了动态顺序表的实现，包括初始化、销毁、打印、增删查改等操作。最后，文章总结了顺序表的时间复杂度和局限性，并预告了后续关于链表的内容。

前言

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


线性表，是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语言
存储
关键词：
C语言源码
数据结构C语言源码
数据结构源码
数据结构c语言
数据结构顺序表
ephemerals__
目录
相关文章
ephemerals__
|
14天前
|
C语言
【数据结构】栈和队列（c语言实现）（附源码）
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表，遵循“先进后出”原则；队列则在一端插入、另一端删除，遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现，并提供了完整的代码示例。栈和队列在实际应用中非常广泛，如二叉树的层序遍历和快速排序的非递归实现等。
ephemerals__
90 9
ephemerals__
|
13天前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现（c语言）（附源码）
本文介绍了树和二叉树的基本概念及结构，重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树，常用于实现优先队列和高效的排序算法（如堆排序）。文章详细描述了堆的性质、存储方式及其实现方法，包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容，读者可以全面了解堆的原理和应用。
ephemerals__
56 16
ephemerals__
|
8天前
|
搜索推荐 算法 C语言
【排序算法】八大排序（上）（c语言实现）（附源码）
本文介绍了四种常见的排序算法：冒泡排序、选择排序、插入排序和希尔排序。通过具体的代码实现和测试数据，详细解释了每种算法的工作原理和性能特点。冒泡排序通过不断交换相邻元素来排序，选择排序通过选择最小元素进行交换，插入排序通过逐步插入元素到已排序部分，而希尔排序则是插入排序的改进版，通过预排序使数据更接近有序，从而提高效率。文章最后总结了这四种算法的空间和时间复杂度，以及它们的稳定性。
ephemerals__
49 8
ephemerals__
|
8天前
|
搜索推荐 算法 C语言
【排序算法】八大排序（下）（c语言实现）（附源码）
本文继续学习并实现了八大排序算法中的后四种：堆排序、快速排序、归并排序和计数排序。详细介绍了每种排序算法的原理、步骤和代码实现，并通过测试数据展示了它们的性能表现。堆排序利用堆的特性进行排序，快速排序通过递归和多种划分方法实现高效排序，归并排序通过分治法将问题分解后再合并，计数排序则通过统计每个元素的出现次数实现非比较排序。最后，文章还对比了这些排序算法在处理一百万个整形数据时的运行时间，帮助读者了解不同算法的优劣。
ephemerals__
36 7
疯狂的猿
|
6天前
|
C语言 Windows
C语言课设项目之2048游戏源码
C语言课设项目之2048游戏源码，可作为课程设计项目参考，代码有详细的注释，另外编译可运行文件也已经打包，windows电脑双击即可运行效果
疯狂的猿
18 1
ephemerals__
|
13天前
|
C语言
【数据结构】二叉树（c语言）（附源码）
本文介绍了如何使用链式结构实现二叉树的基本功能，包括前序、中序、后序和层序遍历，统计节点个数和树的高度，查找节点，判断是否为完全二叉树，以及销毁二叉树。通过手动创建一棵二叉树，详细讲解了每个功能的实现方法和代码示例，帮助读者深入理解递归和数据结构的应用。
ephemerals__
62 8
ephemerals__
|
15天前
|
C语言
【数据结构】双向带头循环链表（c语言）（附源码）
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点：双向、带头和循环。与单链表相比，它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1)，提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现，包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
ephemerals__
35 0
那年春天
|
5天前
|
存储 算法
非递归实现后序遍历时，如何避免栈溢出？
后序遍历的递归实现和非递归实现各有优缺点，在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
那年春天
14 1
德国都芳最好
|
7天前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构，在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈，可以有效地解决许多与数据存储和操作相关的问题。
德国都芳最好
45 21
html的七十二变
|
10天前
|
存储 JavaScript 前端开发
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境，每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用，每当调用一个函数，就会在栈中添加一个新的执行上下文。
html的七十二变
24 2