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

【数据结构】顺序表

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

​

1. 线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使
用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串...
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，
线性表在物理上存储时，通常以数组和链式结构的形式存储。
3{HKKMQ9GC0~M(2ZJUK)]5C.png
顺序表
image.png
链表

2. 顺序表

2.1 顺序表的概念

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。

2.2 顺序表的分类

（1）静态顺序表：使用定长数组存储元素。
image.png
（2）动态顺序表：使用动态开辟的数组存储。
image.png

静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空
间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间
大小，所以下面我们实现动态顺序表。

3. 顺序表的定义

//动态顺序表
typedef int SLDataType;
#define INIT_CAPACITY 4

typedef struct SeqList
{
   
   
    SLDataType* a; //指向动态开辟的数组
    int size;      //存储有效数据个数
    int capacity;  //空间大小
}SL;

使用结构体构造一个动态顺序表。

用SLDataType替换int，方便对不同类型的数据进行修改。

用SL替代struct SeqList， 方便简洁。

用宏定义INIT_CAPACITY将顺序表的初始容量设置为4。

4. 顺序表的接口实现

顺序表的所有接口函数一览：

//顺序表的初始化
void SLInit(SL* ps);
//销毁顺序表
void SLDestroy(SL* ps);
//打印顺序表
void SLPrint(SL* ps);
//检查顺序表是否需要扩容
void SLCheckCapacity(SL* ps);

//尾插
void SLPushBack(SL* ps, SLDataType x);
//尾删
void SLPopBack(SL* ps);
//头插
void SLPushFront(SL* ps, SLDataType x);
//头删
void SLPopFront(SL* ps);

//返回下标，没有找到返回-1
int SLFind(SL* ps, SLDataType x);
//在pos位置插入x
void SLInsert(SL* ps, int pos, SLDataType x);
//删除pos位置的值
void SLErase(SL* ps, int pos);
//将pos位置的值修改为x
void SLModify(SL* ps, int pos, SLDataType x);

这些接口函数主要实现了顺序表的增删改查等功能，接下来我们一一实现这些函数！

4.1 顺序表的初始化

初始化就是我们给顺序表分配一个动态开辟的空间，将顺序表的元素个数置为0，将顺序表的初始空间大小置为我们宏定义的INIT_CAPACITY。

//初始化顺序表
void SLInit(SL* ps)
{
   
   
    assert(ps);
    ps->a = (SLDataType*)malloc(sizeof(SLDataType) * INIT_CAPACITY);
    if (ps->a == NULL)
    {
   
   
        perror("malloc failed");
        exit(-1);  //让整个程序异常退出。
                   //不是return，return只是让这个函数结束
    }
    ps->size = 0;
    ps->capacity = INIT_CAPACITY;
}

4.2 销毁顺序表

因为在实现动态顺序表的过程中，我们要使用动态内存分配的操作，如果不及时释放空间，会出现内存泄漏的问题。

//销毁顺序表
void SLDestroy(SL* ps)
{
   
   
    assert(ps);
    free(ps->a);
    ps->a = NULL;
    ps->capacity = ps->size = 0;
}

4.3 打印顺序表

遍历顺序表，依次打印顺序表的元素。

//打印顺序表
void SLPrint(SL* ps)
{
   
   
    assert(ps);
    for (int i = 0; i < ps->size; i++)
    {
   
   
        printf("%d ", ps->a[i]);
    }
    printf("\n");
}

4.4 检查顺序表是否需要扩容

因为顺序表中有可能已经放满元素了，那我们之后如果想插入数据，就得进行扩容的操作。
是否需要扩容，可以通过size和capacity是否相等判断，如果相等，说明放满了。我们就要进行扩容操作。而进行扩容操作，我们就要使用扩容函数realloc函数。我们一般将空间扩容成原来的2倍（当然也可以是3倍,4倍,5倍...）

//检查是否需要扩容
void SLCheckCapacity(SL* ps)
{
   
   
    assert(ps);
    //满了要扩容
    if (ps->size == ps->capacity)
    {
   
   
        SLDataType* tmp = (SLDataType*)realloc(ps->a, ps->capacity * sizeof(SLDataType) * 2);
        if (tmp == NULL)
        {
   
   
            perror("realloc failed");
            exit(-1);
        }
        ps->a = tmp;
        ps->capacity *= 2;
    }
}

4.5 尾插数据

image.png

因为要插入数据，所以我们得检查一下是否满了，满了就要进行扩容操作。

//尾插
void SLPushBack(SL* ps, SLDataType x)
{
   
   
    assert(ps);
    SLCheckCapacity(ps);
    ps->a[ps->size] = x;
    ps->size++;
}

4.6 尾删数据

尾删实现起来比较简单，就是将数组的长度减一，但是我们不能在顺序表是空（即size==0）的情况下删除数据。

我们得保证size>0的情况下才尾删，这里有两种检查方法：

（1）温柔的检查：使用if语句，如果size为0，直接return

（2）暴力的检查：如果size为0，直接用assert()断言

两种方法都可行，比较推荐第二种。

//尾删
void SLPopBack(SL* ps)
{
   
   
    assert(ps);
    //温柔的检查
    //if (ps->size == 0)
        //return;

    //暴力的检查
    assert(ps->size > 0);

    ps->size--;  //不能局部释放
}

4.7 头插数据

头插就是将数组的整体数据向后挪动一格，然后用指定数据替换第一个数据。

比如这里我们将6插入到第一个位置。
image.png

但是注意在挪动的时候，我们要从后向前挪，因为如果从前往后挪，会导致数据的覆盖！！！
image.png

//头插
void SLPushFront(SL* ps,SLDataType x)
{
   
   
    assert(ps);
    SLCheckCapacity(ps);
    //挪动数据(从后往前挪，因为从前往后挪会覆盖）
    int end = ps->size - 1;
    while (end>=0)
    {
   
   
        ps->a[end + 1] = ps->a[end];
        --end;
    }
    ps->a[0] = x;
    ps->size++;
}

4.8 头删数据

和头插类似，只不过头删是将数组的整体往前挪动一格。和头插不同的是，头删得从前往后挪动，不然也会出现覆盖问题。
image.png

//头删
void SLPopFront(SL* ps)
{
   
   
    assert(ps);
    assert(ps->size > 0);
    int begin = 1;
    while (begin < ps->size)
    {
   
   
        ps->a[begin - 1] = ps->a[begin];
        ++begin;
    }
    ps->size--;

}

4.9 在指定位置插入数据

将指定位置pos后面的所有数据整体往后挪动一格，再给指定位置pos赋新值，要保证指定位置pos的合理性和是否放满了，要从后往前挪动。

//在pos位置插入x
void SLInsert(SL* ps, int pos, SLDataType x)
{
   
   
    assert(ps);
    assert(pos >= 0 && pos <= ps->size);
    SLCheckCapacity(ps);
    int end = ps->size - 1;
    while (end >= pos)
    {
   
   
        ps->a[end + 1] = ps->a[end];
        --end;
    }
    ps->a[pos] = x;
    ps->size++;
}

头插代码可以复用这个代码：

void SLPushFront(SL* ps,SLDataType x)
{
   
   
    assert(ps);
    SLInsert(ps, 0, x);
}

尾插代码可以复用这个代码：

void SLPushBack(SL* ps, SLDataType x)
{
   
   
    assert(ps);
    SLInsert(ps, ps->size, x);
}

4.10 删除指定位置的数据

将指定位置后面的所有数据整体往前挪动一格，要保证指定位置pos的合理性，要从前往后挪动，同时让size减一。

//删除pos位置的值
void SLErase(SL* ps, int pos)
{
   
   
    assert(ps);
    assert(pos >= 0 && pos < ps->size);
    int begin = pos + 1;
    while (begin < ps->size)
    {
   
   
        ps->a[begin - 1] = ps->a[begin];
        ++begin;
    }
    ps->size--;
}

头删代码可以复用这个代码：

void SLPopFront(SL* ps)
{
   
   
    assert(ps);
    SLErase(ps, 0);
}

尾删代码可以复用这个代码：

void SLPopBack(SL* ps)
{
   
   
    assert(ps);
    SLErase(ps, ps->size-1);
}

4.11 查找指定数据

查找的代码实现起来非常简单，找到了就返回下标，找不到返回-1。

//查找
int SLFind(SL* ps, SLDataType x)
{
   
   
    assert(ps);
    for (int i = 0; i < ps->size; i++)
    {
   
   
        if (ps->a[i] == x)
            return i;
    }
    return -1;
}

4.12 将指定位置的数据进行修改

在保证pos合理性的情况下，对pos位置的数据可以进行修改。

//将pos位置的值修改为x
void SLModify(SL* ps, int pos, SLDataType x)
{
   
   
    assert(ps);
    assert(pos >= 0 && pos < ps->size);
    ps->a[pos] = x;
}

5. 顺序表的完整代码

5.1 SeqList.h

#pragma once

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

//动态顺序表
typedef int SLDataType;
#define INIT_CAPACITY 4

typedef struct SeqList
{
   
   
    SLDataType* a; //指向动态开辟的数组
    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 x);
//尾删
void SLPopBack(SL* ps);
//头插
void SLPushFront(SL* ps, SLDataType x);
//头删
void SLPopFront(SL* ps);

//返回下标，没有找到返回-1
int SLFind(SL* ps, SLDataType x);
//在pos位置插入x
void SLInsert(SL* ps, int pos, SLDataType x);
//删除pos位置的值
void SLErase(SL* ps, int pos);
//将pos位置的值修改为x
void SLModify(SL* ps, int pos, SLDataType x);

5.2 SeqList.c

#define _CRT_SECURE_NO_WARNINGS 1

#include"SeqList.h"

//初始化顺序表
void SLInit(SL* ps)
{
   
   
    assert(ps);
    ps->a = (SLDataType*)malloc(sizeof(SLDataType) * INIT_CAPACITY);
    if (ps->a == NULL)
    {
   
   
        perror("malloc failed");
        exit(-1);  //让整个程序异常退出。
                   //不是return，return只是让这个函数结束
    }
    ps->size = 0;
    ps->capacity = INIT_CAPACITY;
}

//销毁顺序表
void SLDestroy(SL* ps)
{
   
   
    assert(ps);
    free(ps->a);
    ps->a = NULL;
    ps->capacity = ps->size = 0;
}

//打印顺序表
void SLPrint(SL* ps)
{
   
   
    assert(ps);
    for (int i = 0; i < ps->size; i++)
    {
   
   
        printf("%d ", ps->a[i]);
    }
    printf("\n");
}

//检查是否需要扩容
void SLCheckCapacity(SL* ps)
{
   
   
    assert(ps);
    //满了要扩容
    if (ps->size == ps->capacity)
    {
   
   
        SLDataType* tmp = (SLDataType*)realloc(ps->a, ps->capacity * sizeof(SLDataType) * 2);
        if (tmp == NULL)
        {
   
   
            perror("realloc failed");
            exit(-1);
        }
        ps->a = tmp;
        ps->capacity *= 2;
    }
}

//尾插
void SLPushBack(SL* ps, SLDataType x)
{
   
   
    assert(ps);
    SLCheckCapacity(ps);
    ps->a[ps->size] = x;
    ps->size++;
}

//尾删
void SLPopBack(SL* ps)
{
   
   
    assert(ps);
    //温柔的检查
    //if (ps->size == 0)
        //return;

    //暴力的检查
    assert(ps->size > 0);

    ps->size--;  //不能局部释放
}

//头插
void SLPushFront(SL* ps,SLDataType x)
{
   
   
    assert(ps);
    SLCheckCapacity(ps);
    //挪动数据(从后往前挪，因为从前往后挪会覆盖）
    int end = ps->size - 1;
    while (end>=0)
    {
   
   
        ps->a[end + 1] = ps->a[end];
        --end;
    }
    ps->a[0] = x;
    ps->size++;
}

//头删
void SLPopFront(SL* ps)
{
   
   
    assert(ps);
    assert(ps->size > 0);
    int begin = 1;
    while (begin < ps->size)
    {
   
   
        ps->a[begin - 1] = ps->a[begin];
        ++begin;
    }
    ps->size--;
}

//在pos位置插入x
void SLInsert(SL* ps, int pos, SLDataType x)
{
   
   
    assert(ps);
    assert(pos >= 0 && pos <= ps->size);
    SLCheckCapacity(ps);
    int end = ps->size - 1;
    while (end >= pos)
    {
   
   
        ps->a[end + 1] = ps->a[end];
        --end;
    }
    ps->a[pos] = x;
    ps->size++;
}

//删除pos位置的值
void SLErase(SL* ps, int pos)
{
   
   
    assert(ps);
    assert(pos >= 0 && pos < ps->size);
    int begin = pos + 1;
    while (begin < ps->size)
    {
   
   
        ps->a[begin - 1] = ps->a[begin];
        ++begin;
    }
    ps->size--;
}

//查找
int SLFind(SL* ps, SLDataType x)
{
   
   
    assert(ps);
    for (int i = 0; i < ps->size; i++)
    {
   
   
        if (ps->a[i] == x)
            return i;
    }
    return -1;
}

//将pos位置的值修改为x
void SLModify(SL* ps, int pos, SLDataType x)
{
   
   
    assert(ps);
    assert(pos >= 0 && pos < ps->size);
    ps->a[pos] = x;
}

5.3 Test.c

#define _CRT_SECURE_NO_WARNINGS 1

#include"SeqList.h"

void TestSeqList()
{
   
   
    SL sl;
    SLInit(&sl);
    SLPushBack(&sl, 1);
    SLPushBack(&sl, 2);
    SLPushBack(&sl, 3);
    SLPushBack(&sl, 4);
    SLPushBack(&sl, 5);
    SLPushBack(&sl, 6);
    SLPushBack(&sl, 6);
    SLPrint(&sl);

    SLPopBack(&sl);
    SLPopBack(&sl);
    SLPrint(&sl);

    SLPushFront(&sl , 0);
    SLPushFront(&sl, -1);
    SLPrint(&sl);

    SLPopFront(&sl);
    SLPrint(&sl);

    int x;
    printf("请选择要查询的数字:>");
    scanf("%d", &x);
    int pos = SLFind(&sl, x);
    if (pos != -1)
    {
   
   
        printf("x=%d的下标是%d\n", x,pos);
    }
    else
        printf("x不存在\n");

    SLInsert(&sl, 3, 8);
    SLPrint(&sl);

    SLErase(&sl, 4);
    SLPrint(&sl);

    SLModify(&sl, 1, 10);
    SLPrint(&sl);

    SLDestroy(&sl);
}


int main()
{
   
   
    TestSeqList();
    return 0;
}

image.png

6. 顺序表的优点和缺点

6.1 顺序表优点

（1）尾插尾删足够快。
（2）下标的随机访问和修改。

6.2 顺序表缺点

（1）头部和中部插入删除效率都不行，时间复杂度为O(N)
（2）空间不够了，扩容有一定的消耗(尤其是异地扩容)。
（3）扩容逻辑，可能还存在空间。（比如申请的空间能存100个数据，满了，但是我们要存110个数据，空间就会扩容到能存200个数据，这样浪费了90个空间）。

7. 总结

到这里，我们就用C语言实现了数据结构中的动态顺序表。有什么问题欢迎在评论区讨论。如果觉得文章有什么不足之处，可以在评论区留言。如果喜欢我的文章，可以点赞收藏哦！

​

文章标签：
存储
C语言
关键词：
数据结构顺序表
是基德吖
目录
相关文章
禁默
|
1月前
|
存储 编译器 C语言
数据结构-顺序表详解（看这篇就足够了，哈哈哈）
数据结构-顺序表详解（看这篇就足够了，哈哈哈）
禁默
51 2
肾透侧视攻城狮
|
21天前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之顺序表【无论是王道考研人还真爱粉都能包会的；不然别给我家鸽鸽丢脸好嘛？】
顺序表的定义和基本操作之插入；删除；按值查找；按位查找等具体详解步骤以及举例说明
肾透侧视攻城狮
24 3
ephemerals__
|
21天前
|
存储 C语言
【数据结构】顺序表（c语言实现）（附源码）
本文介绍了线性表和顺序表的基本概念及其实现。线性表是一种有限序列，常见的线性表有顺序表、链表、栈、队列等。顺序表是一种基于连续内存地址存储数据的数据结构，其底层逻辑是数组。文章详细讲解了静态顺序表和动态顺序表的区别，并重点介绍了动态顺序表的实现，包括初始化、销毁、打印、增删查改等操作。最后，文章总结了顺序表的时间复杂度和局限性，并预告了后续关于链表的内容。
ephemerals__
55 3
肾透侧视攻城狮
|
21天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之顺序表习题精讲【无论是王道考研人还真爱粉都能包会的；不然别给我家鸽鸽丢脸好嘛？】
顺序表的定义和基本操作之插入；删除；按值查找；按位查找习题精讲等具体详解步骤以及举例说明
肾透侧视攻城狮
18 1
小强在此
|
1月前
|
存储 Java
数据结构第二篇【关于java线性表（顺序表）的基本操作】
数据结构第二篇【关于java线性表（顺序表）的基本操作】
小强在此
30 6
GuGuStudy
|
1月前
|
存储 安全 Java
【用Java学习数据结构系列】探索顺序表和链表的无尽秘密（附带练习唔）pro
【用Java学习数据结构系列】探索顺序表和链表的无尽秘密（附带练习唔）pro
GuGuStudy
24 3
GuGuStudy
|
1月前
|
存储 C语言
探索C语言数据结构：利用顺序表完成通讯录的实现
本文介绍了如何使用C语言中的顺序表数据结构实现一个简单的通讯录，包括初始化、添加、删除、查找和保存联系人信息的操作，以及自定义结构体用于存储联系人详细信息。
GuGuStudy
20 2
努力学习的小廉
|
1月前
|
存储 算法 索引
【数据结构】——顺序表
【数据结构】——顺序表
努力学习的小廉
66 1
椰椰椰耶
|
1月前
|
存储
【数据结构】线性表和顺序表
【数据结构】线性表和顺序表
椰椰椰耶
22 1
徐霞客320
|
1月前
|
存储
数据结构1——顺序表
数据结构1——顺序表
徐霞客320
17 1

热门文章

最新文章

  • 1
    我花了一夜用数据结构给女朋友写个H5走迷宫游戏
  • 2
    数据结构学习笔记【持续更新】
  • 3
    基于OHCI的USB主机 —— OHCI（自定义数据结构）
  • 4
    【数据结构7】查找
  • 5
    数据结构（2）：栈的原理和实现
  • 6
    算法导论第十四章 数据结构的扩张
  • 7
    学数据结构，只需要基本的编程体验
  • 8
    基于OHCI的USB主机 —— UFI数据结构2
  • 9
    R语言学习笔记（一）数据结构
  • 10
    初学python数据结构-切片
  • 1
    `geopandas`是一个开源项目，它为Python提供了地理空间数据处理的能力。它基于`pandas`库，并扩展了其对地理空间数据（如点、线、多边形等）的支持。`GeoDataFrame`是`geopandas`中的核心数据结构，它类似于`pandas`的`DataFrame`，但包含了一个额外的地理列（通常是`geometry`列），用于存储地理空间数据。
    70
  • 2
    “解锁Python高级数据结构新姿势：图的表示与遍历，让你的算法思维跃升新高度
    44
  • 3
    Redis数据结构—跳跃表 skiplist 实现源码分析
    65
  • 4
    逆袭之路！用 Python 玩转图的 DFS 与 BFS，让数据结构难题无处遁形
    65
  • 5
    Python中的列表（List）和元组（Tuple）是两种重要的数据结构
    56
  • 6
    【数据结构OJ题】链表分割
    32
  • 7
    【数据结构常见七大排序（三）上】—交换排序篇【冒泡排序】And【快速排序】
    45
  • 8
    【数据结构常见七大排序（二）】—选择排序篇【直接选择排序】And【堆排序】
    33
  • 9
    【数据结构常见七大排序（一）】—插入排序篇【直接插入排序】And【希尔排序】
    46
  • 10
    【数据结构OJ题】链表的回文结构
    39

    • 相关课程

    更多
  • Go语言核心编程 - 数据结构和算法

    • 相关电子书

    更多
  • 如何使用Tair增强数据结构构建丰富在线实时场景
  • Apache Flink 流式应用中状态的数据结构定义升级
  • 低代码开发师（初级）实战教程
    • 下一篇
    阿里云OSS设置跨域访问