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

【数据结构】顺序表

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

​

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语言
关键词：
数据结构顺序表
是基德吖
目录
相关文章
秋刀鱼不做梦
|
2月前
|
存储
数据结构—顺序表（如果想知道顺序表的全部基础知识点，那么只看这一篇就足够了！）
数据结构—顺序表（如果想知道顺序表的全部基础知识点，那么只看这一篇就足够了！）
秋刀鱼不做梦
35 1
sky_qiyi
|
2月前
|
存储 缓存 算法
数据结构和算法学习记录——总结顺序表和链表（双向带头循环链表）的优缺点、CPU高速缓存命中率
数据结构和算法学习记录——总结顺序表和链表（双向带头循环链表）的优缺点、CPU高速缓存命中率
sky_qiyi
35 0
国中之林
|
4天前
|
存储 算法
【数据结构与算法】顺序表
【数据结构与算法】顺序表
国中之林
5 0
【数据结构与算法】顺序表
aliyun6365824167
|
1天前
|
存储 算法
【初阶数据结构篇】顺序表和链表算法题
此题可以先找到中间节点，然后把后半部分逆置，最近前后两部分一一比对，如果节点的值全部相同，则即为回文。
aliyun6365824167
6 0
aliyun6365824167
|
1天前
|
存储 测试技术
【初阶数据结构篇】顺序表的实现（赋源码）
线性表（linearlist）是n个具有相同特性的数据元素的有限序列。
aliyun6365824167
7 0
睡觉待开机
|
6天前
|
存储 编译器
【数据结构】顺序表(长期维护)
【数据结构】顺序表(长期维护)
睡觉待开机
7 0
大柏怎么被偷了
|
6天前
|
存储 缓存
【数据结构】——顺序表与链表
【数据结构】——顺序表与链表
大柏怎么被偷了
10 0
写代码的大学生
|
2月前
|
存储 C语言
顺序表（数据结构）
顺序表（数据结构）
写代码的大学生
22 1
爱喝兽奶的熊孩子
|
2月前
|
存储 机器学习/深度学习 算法
【数据结构与算法】：手搓顺序表（Python篇）
【数据结构与算法】：手搓顺序表（Python篇）
爱喝兽奶的熊孩子
25 1
爱喝兽奶的熊孩子
|
2月前
|
存储 算法 C++
【数据结构与算法】：带你手搓顺序表（C/C++篇）
【数据结构与算法】：带你手搓顺序表（C/C++篇）
爱喝兽奶的熊孩子
37 1