【数据结构】带你轻松拿捏顺序表(内附源码)

简介: 【数据结构】带你轻松拿捏顺序表(内附源码)

前言

ps:顺序表中难以理解的点应该就是malloc以及realloc的使用了,这是有关C语言的动态内存管理的知识,我们主要目的是介绍顺序表的因此不做缀叙,如果你感兴趣之后我也会更新有关博客并且把链接贴在这里哒!

一.线性表

我们知道,顺序表是最基础的线性表,那么什么是线性表呢?

1.线性表的概念

  • 线性表(linear list)是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构,常见的线性表:顺序表、链表、栈、队列、字符串…

线性表在逻辑上是线性结构,也就说是连续的一条直线。但是在物理结构上并不一定是连续的,线性表在物理上存储时,通常以数组和链式结构的形式存储


二.顺序表

2.1 概念及结构

  • 顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用数组存储。在数组上完成数据的增删查改。
  • 注意:这里我们要知道的是,顺序表存放的数据是连续的并且在内存中是真正依次存放的,这一点是与链表最大的区别!

2.2 顺序表的分类

  • 顺序表一般有两种形式
  • 1. 静态顺序表:使用定长数组存储元素。
// 静态顺序表
#define N 1000
typedef int SLDataType;
struct SeqList
{
  SLDataType a[N];
  int size;
};
  • 静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了,空间开多了浪费,开少了不够用。所以现实中基本都是使用第二种顺序表——动态顺序表,根据需要动态的分配空间大小。
  • 2.动态顺序表
// 动态顺序表
typedef int SLDataType;//重命名数据类型,方便以后直接修改
typedef struct SeqList
{
  SLDataType* a;//指向动态开辟的数组
  int size;        // 存储有效数据个数
  int capacity;    // 容量空间大小
}SL;
  • 顾名思义,动态顺序表使用动态开辟的数组储存,这样更方便我们实时根据数据的多少调整数组的大小。。
  • 以下是上面这段代码要提醒的几处要点:
  • 1.我们在上面这段代码中使用了两个typedef,但是用处却不相同

第一处的typedef实际是为了方便我们的使用,因为我们也不知道我们的顺序表是用来存储什么类型的数据的,因此我们这里就定义一个SLDataType,下面的代码中统一把数据类型用它来代替,这样一来,我们以后想要改变存储的数据类型,只需要改动这里即可,比如我们现在想要存储double类型的数据

typedef double SLDataType;
  • 第二处的typedef是将这个结构体重命名,方便我们接下来的使用,接下来的结构体直接写出‘SL’就行。

接下来我们来具体实现一下动态顺序表的各种功能以及使用方法


2.3 动态顺序表的实现

顺序表的初始化

  • 我们确定了顺序表内的基本内容,我们得把顺序表先初始化一下,不然连空间都还没开辟咋使用呢?
//初始化顺序表
void SLInit(SL* ps)
{
    ps->a = (SLDataType*)malloc(sizeof(SLDataType) * 4);//申请四个字节的空间,如果不够再进行增容
    if (ps->a == NULL)
    {
        perror("malloc failed");
        exit (-1);
    }
    ps->size = 0;
    ps->capacity = 4;
}
  • 我们通过malloc为我们的顺序表申请了四个字节的空间,同时此时我们还未填入数据,因此size初始化为0,容量空间大小为4.
  • 但是我们只是申请了空间,还不知道是否成功,因此我们又通过分辨动态数组是否为NULL并通过perror报错来判断我们开辟内存的操作是否成功。

顺序表的扩容

  • 我们初始化了一个顺序表,但是我们并不知道我们申请的空间是否够用,如果不够用,我们就得扩容一下。因此我们这里的逻辑应该是先判断容量是否够用,够用就不用做多余的操作,如果不够用,就申请扩容
//检查空间,如果顺序表满了,就进行增容操作
void SLCheckCapacity(SL* ps)
{
    assert(ps);//断言防止传入ps为空
    //判断一下是否空间满了,如果满了就把容量增加到原来的2倍
    if (ps->size == ps->capacity)//有效数据是否占满所有空间
    {
        SLDataType* tmp = (SLDataType*)realloc(ps->a, ps->capacity * 2 * (sizeof(SLDataType)));//利用realloc扩容
        if (tmp == NULL)
        {
            perror("realloc failed");
            exit(-1);
        }
        ps->a = tmp;
        ps->capacity *= 2;
    }
}

我们这里通过realloc将空间扩容到原来的2倍,当我们通过perror判断扩容成功后将扩容赋给我们的动态数组,由于扩容到原来的两倍,这里的容量空间大小也要变为原来的2倍。

顺序表的销毁

  • 当我们使用完顺序表后,由于我们是用malloc开辟的内存,因此必须把它给销毁并且释放掉
void SLDestroy(SL* ps)
{
    free(ps->a);//释放malloc申请的空间并且将a指向NULL
    ps->a = NULL;
    ps->capacity = ps->size = 0;
}
  • 在销毁并释放内存的同时,我们也需要把size和capacity初始化一下。

顺序表的打印

  • 当我们把数据插入或者删除后,我们就需要打印一下顺序表来看看我们的操作是否执行成功
void SLPrint(SL* ps)
{
    int i =0;
    for (i = 0; i < ps->size; i++)
        printf("%d ", ps->a[i]);//把有效数据通过循环都打印一下
    printf("\n");
}
  • 如果说之前的都是前菜,我们接下来进入今天的正餐,也是顺序表中最难理解的一部分,就是咱们所谓的增删查改

顺序表的尾插与尾删

  • 什么叫尾插和尾删呢?
  • **所谓尾插就是从顺序表的末尾插入数据,而尾删就是把最后一个数据给删除**
//顺序表尾插
void SLPushBack(SL* ps, SLDataType x)
{
    assert(ps);
    SLCheckCapacity(ps);//先判断以下顺序表是否已满,未满才能插入数据
    ps->a[ps->size] = x;//把数组a中size位置的数据赋值为x,size位置即最后一位
    ps->size++;//插入数据成功,有效数据+1
}
  • 其中,尾删时,我们需要检查是否越界,比如你就俩数据,你尾删了10次,那么此时你的有效数据就成负的了,这时你是不是就越界了?
  • 检查是否越界有两种方法我愿称之为温柔检查法和暴力检查法,这又是怎么个回事呢?
//顺序表尾删
void SLPopBack(SL* ps)
{
    assert(ps);
    温柔的检查
    //if (ps->size == 0)
    //    return;
    //暴力检查
    assert(ps->size > 0);
    ps->a[ps->size - 1] = 0;//把最后一个数据抹掉
    ps->size--;//有效数据-1
}
  • 啥叫温柔检查呢?
  • 当我们size已经删没的时候(size == 0),说明有效数据都已经删完了,这时我们就直接return即可。此时程序既不会往下走导致越界,也不会报错。
  • 而暴力检查法就如你的严父一样
  • 我们直接通过assert断言,,如果它发现你越界了,就会直接掏出七匹狼(报错),并且告诫你错在哪里,如下所示
  • 。。。放错了,如下所示:

顺序表的头插与头删

  • 与尾插和尾删类似,顺序表的头插与头删就是在开头进行插入与删除数据操作
/顺序表的头插
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);
    int begin = 0;
    while (begin < ps->size-1)
    {
        ps->a[begin] = ps->a[begin + 1];
        begin++;
    }
    ps->size--;
}
  • 在头删时,与头插类似,我们需要把所有数据都往前挪动一位来弥补头删的空缺,最后再把有效数据减少一位即可。

在顺序表中任意位置的删除与插入

//在顺序表中pos位置插入
void SLInsert(SL* ps, int pos, SLDataType x)
{
    assert(ps);
    SLCheckCapacity(ps);//检查容量空间大小
    assert(pos >= 0 && pos <= ps->size);//判断pos的合法化,避免插入到非法坐标中
    int end = ps->size - 1;
    while (end >= pos)//把pos位置后的数据都朝后挪动一位,给插入的数据腾位置
    {
        ps->a[end + 1] = ps->a[end];
        end--;
    }
    ps->a[pos] = x;//插入数据
    ps->size++;//有效数字+1
}
  • 这里与头插类似,只不过我们需要挪动的数据变成了pos位置后的数据,它们都需要朝后挪动一位
//在顺序表中删除pos位置的值
void SLErase(SL* ps, int pos)
{
    assert(ps);
    assert(pos >= 0 && pos <= ps->size);
    int begin = pos;
    while (begin < ps->size-1)
    {
        ps->a[begin] = ps->a[begin + 1];//pos后的数据都朝前挪动一位
        begin++;
    }
    ps->size--;//有效数据-1
}
  • 与头删类似,pos后面的数据都要朝前挪动一位来填补删除pos位置上数据的空缺

顺序表中数据的查找与修改

  • 顺序表中数据的查找
//查找顺序表中是否有某个数,如果有就返回该数的下标
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;
}
  • 通过遍历数组的形式来查找是否存在某个数据,找到就返回该数据所在的位置,没找到就返回-1。
  • 顺序表中的修改
  • 要想修改,我们需要知道要修改哪个位置的数据以及我们要把该位置上的数据修改成多少
void SLModify(SL* ps, int pos, SLDataType x)
{
    assert(ps);
    assert(pos >= 0 && pos < ps->size);//判断要修改数据的坐标是否合法
    ps->a[pos] = x;//修改数据
}

2.4 测试一下我们的动态顺序表

  • 好了,我们顺序表的基本功能都已经通过代码实现了,我们现在来挑选几个重要的功能测试一下
int main()
{
    SL s1;
    SLInit(&s1);
    SLPushBack(&s1, 1);
    SLInsert(&s1, 1, 50);
    SLPushFront(&s1, 20);
    SLPrint(&s1);
    int ret=SLFind(&s1, 50);
    if(ret!=-1)
    printf("找到了,下标是%d\n", ret);
    SLErase(&s1, 0);
    SLPopBack(&s1);
    SLPrint(&s1);
    SLModify(&s1, 0, 666);
    SLPrint(&s1);
    return 0;
}

  • 仔细对比一下我们要实现的功能,发现雀氏没有问题

2.5顺序表的优缺点

  • 存在的问题:
  • 1. 中间/头部的插入删除,时间复杂度为O(N)
  • 2. 增容需要申请新空间,拷贝数据,释放旧空间。会有不小的消耗。(尤其是异地扩容)
  • 3. 增容一般是呈2倍的增长,势必会有一定的空间浪费。
  • 例如当前容量为100,满了以后增容到200,我们再继续插入了5个数据,后面没有数据插入了,那么就浪费了95个数据空间
  • 优点
  • 1.尾删和尾插足够快
  • 2.能通过下标实现随机访问和修改(这点是非常重要的)

总结

  • 今天的内容到这里就结束了,我们带大家具体的实现了顺序表的编写。由于篇幅原因,在顺序表编写中存在的易错点以及各种细节的知识我们放到下一篇再讲,同时也会讲几个相关的面试题目加深大家对这些易错点的理解。
  • ps:其实是熬夜写博客有点太晚了,博主有点顶不住了,看在博主这么努力的份上真的不留下你的三连吗?!!
  • 好了,如果你有任何疑问欢迎在评论区或者私信我提出,大家下次再见啦!


目录
相关文章
|
1月前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
137 9
|
1月前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现(c语言)(附源码)
本文介绍了树和二叉树的基本概念及结构,重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树,常用于实现优先队列和高效的排序算法(如堆排序)。文章详细描述了堆的性质、存储方式及其实现方法,包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容,读者可以全面了解堆的原理和应用。
68 16
|
1月前
|
C语言
【数据结构】二叉树(c语言)(附源码)
本文介绍了如何使用链式结构实现二叉树的基本功能,包括前序、中序、后序和层序遍历,统计节点个数和树的高度,查找节点,判断是否为完全二叉树,以及销毁二叉树。通过手动创建一棵二叉树,详细讲解了每个功能的实现方法和代码示例,帮助读者深入理解递归和数据结构的应用。
108 8
|
1月前
|
存储 C语言
【数据结构】手把手教你单链表(c语言)(附源码)
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构,每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作,如头插、尾插、头删、尾删、查找、指定位置插入和删除等,并提供了完整的C语言代码示例。通过学习单链表,可以更好地理解数据结构的底层逻辑,提高编程能力。
62 4
|
1月前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之顺序表【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找等具体详解步骤以及举例说明
|
1月前
|
存储 C语言
【数据结构】顺序表(c语言实现)(附源码)
本文介绍了线性表和顺序表的基本概念及其实现。线性表是一种有限序列,常见的线性表有顺序表、链表、栈、队列等。顺序表是一种基于连续内存地址存储数据的数据结构,其底层逻辑是数组。文章详细讲解了静态顺序表和动态顺序表的区别,并重点介绍了动态顺序表的实现,包括初始化、销毁、打印、增删查改等操作。最后,文章总结了顺序表的时间复杂度和局限性,并预告了后续关于链表的内容。
65 3
|
1月前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之顺序表习题精讲【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找习题精讲等具体详解步骤以及举例说明
|
1月前
|
C语言
【数据结构】双向带头循环链表(c语言)(附源码)
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点:双向、带头和循环。与单链表相比,它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1),提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现,包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
43 0
|
2月前
|
存储
数据结构(顺序表)
数据结构(顺序表)
28 0
|
2月前
|
存储 算法
【数据结构】新篇章 -- 顺序表
【数据结构】新篇章 -- 顺序表
16 0