数据结构初阶：顺序表

数据结构初阶：顺序表

引用

CSDN

1.

https://blog.csdn.net/2401_87194328/article/details/146535021

序言

本文详细介绍了顺序表的基本概念，包括如何定义和初始化顺序表，以及如何进行数据的插入、删除和查找操作。顺序表使用数组实现，插入和删除操作在特定情况下可能需要移动大量元素，时间复杂度为O(n)。

1.线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。线性表是⼀种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串...

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

特点：逻辑上是线性结构，物理结构上不一定是连续的

2.顺序表

2.1 概念与结构

概念：顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，⼀般情况下采用数组存储。

那我们提出一个问题：顺序表和数组的关系是什么？

顺序表是在计算机内存中以数组的形式保存的线性表。数组是一组相同类型元素的集合，具有固定的大小和连续的存储位置。顺序表利用数组的特性来实现线性表的存储和操作。

通俗的理解就是：

可以说，顺序表是对数组的一种应用，它将数组的连续存储特性用于存储线性表中的元素，并通过一定的算法实现对元素的插入、删除、查找等操作。

2.2 分类

2.2.1 静态顺序表

概念：使用定长数组存储元素

静态顺序表的缺陷：空间给少了不够用，给多了造成浪费

2.2.2 动态顺序表

动态顺序表优点：空间可控可增容

2.3 顺序表的实现

头文件的包含

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
//顺序表的结构
typedef int SLDataType;
typedef struct SeqList
{
    SLDataType* arr;
    int size;      //有效数据个数
    int capacity;  //空间大小
}SL;
//typedef struct SeqList SL;
//初始化
void SLInit(SL* ps);
//销毁
void SLDesTroy(SL* ps);
//尾插
void SLPushBack(SL* ps, SLDataType x);
//头插
void SLPushFront(SL* ps, SLDataType x);
//尾删
void SLPopBack(SL* ps);
//头删
void SLPopFront(SL* ps);

2.3.1 尾插

在主函数中的实现：

源代码：

void SLCheckCapacity(SL* ps)
{
    if (ps->size == ps->capacity)
    {
        int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
        //增容
        //realloc第二个参数，单位是字节
        SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));
        if (tmp == NULL)
        {
            perror("realloc fail!");
            exit(1);
        }
        ps->arr = tmp;
        ps->capacity = newCapacity;
    }
}
//尾插
void SLPushBack(SL* ps, SLDataType x)
{
    assert(ps);
    //判断空间是否足够
    SLCheckCapacity(ps);
    //空间足够的情况下
    ps->arr[ps->size++] = x;
}

尾插逻辑：

这段代码主要实现了顺序表的尾插操作以及检查容量的功能。

顺序表是在计算机内存中以数组的形式保存的线性表，空间是连续的。在进行尾插操作时，需要先检查顺序表的空间是否足够。如果当前顺序表的大小（size）等于容量（capacity），则需要进行扩容操作。

扩容的逻辑如下：

• 如果当前容量为 0，则新容量设置为 4；否则，新容量设置为当前容量的 2 倍。
• 使用realloc函数重新分配内存空间，如果分配失败，会输出错误信息并退出程序。

在尾插操作中，先调用检查容量的函数SLCheckCapacity，确保有足够的空间。然后，将新元素插入到顺序表的末尾（ps->arr[ps->size++] = x），同时更新顺序表的大小。

2.3.2 头插

//头插
void SLPushFront(SL* ps, SLDataType x)
{
    //温柔的处理方式
    //if (ps == NULL)
    //{
    //    return;
    //}
    assert(ps != NULL);
    //判断空间是否足够
    SLCheckCapacity(ps);
    //将顺序表中所有数据向后挪动一位
    for (int i = ps->size; i > 0; i--)
    {
        ps->arr[i] = ps->arr[i - 1];
    }
    ps->arr[0] = x;
    ++ps->size;
}

头插逻辑：

这段代码定义了一个在顺序表头部插入元素的函数SLPushFront。

首先，通过assert断言确保指针ps不为空。然后，调用SLCheckCapacity函数检查顺序表的空间是否足够。

接下来，通过一个循环将顺序表中所有数据向后挪动一位，为头部插入元素腾出位置。最后，将新元素x插入到顺序表的头部（索引为 0 的位置），并更新顺序表的大小。

2.3.4 尾删

//尾删
void SLPopBack(SL* ps)
{
    //ps：限制参数不能直接给NULL
    //ps->size：顺序表为空
    assert(ps && ps->size);
    --ps->size;
}

尾删逻辑：

这段代码实现了顺序表的尾删操作。

首先，通过assert断言确保指针ps不为空且顺序表的大小ps->size不为 0 。然后，直接将顺序表的大小减 1，实现尾删的效果。

简单来说，这个函数通过检查参数的有效性，然后通过修改顺序表的大小来完成尾元素的删除操作。

2.3.5 头删

//头删
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;
}

头删逻辑：

这段代码定义了一个在顺序表头部删除元素的函数`SLPopFront。

首先，通过assert断言确保指针ps不为空且顺序表的大小ps->size不为 0 。

然后，通过一个循环将顺序表中除第一个元素外的所有元素向前移动一位，覆盖原来的第一个元素的位置。

最后，将顺序表的大小减 1，完成头部元素的删除操作。

总的来说，这个函数通过检查参数的有效性，然后通过数据移动和修改顺序表的大小来实现头元素的删除功能。

3.小结

以上便是本篇博客的所有内容，如果这篇博客能给诸君带来知识，还请大家多多点赞评论，谢谢大家的支持。