数据结构入门之顺序表（SeqList）

数据结构入门之顺序表（SeqList）

引用

CSDN

1.

https://m.blog.csdn.net/wuge041118/article/details/144123183

一、顺序表

顺序表的底层其实就是数组，那有了数组，为什么还要创建顺序呢？

举个例子：假设我创建一个数组int arr[100] = {1, 2, 3, 4, 5}，我想要插入删除或者查找某个数据就需要先查找数组中已有元素个数，再进行增删查，就使用循环，顺序表由此而生，顺序表是线性表的一种。
注：线性表是具有n个相同特性的数据元素的有限序列，主要从物理结构和逻辑结构两个方面有相同特性。在物理结构上不一定连续，即储存方式，如果储存方式是以数组的形式储存，则连续，如果以链式结构的方式储存则不连续；在逻辑结构上是连续的，也就是线性的。
由上可知顺序表在物理结构上是连续的，在逻辑结构上也是连续的。

二、顺序表的分类

（一）、静态顺序表

#define N 100  //使用宏定义N为100
//静态顺序表的定义
struct SeqList
{
    int arr[N];//定长数组
    int size; //顺序表当前有效的数据个数
};  

（二）、动态顺序表

typedef int SLDataType;//方便对于存储其他类型数据时的更改
typedef struct SeqList
{
    SLDataType* arr;
    int size;//有效数据的个数
    int capacity;//记录空间大小，方便后续对数组进行扩容
}SL;//使用typedef对顺序表重命名  

typedef int SLDataType;//方便对于存储其他类型数据时的更改
struct SeqList
{
    SLDataType* arr;
    int size;//有效数据的个数
    int capacity;//记录空间大小，方便后续对数组进行扩容
};
typedef struct SeqList SL;//使用typedef对顺序表重命名  

以上两种对顺序表重命名的方式都可以

（三）、静态顺序表与动态顺序表的比较

显而易见，静态顺序表的空间大小不可变，在实际使用中很不方便，如果空间给小了会不够用，而给大了就会出现空间浪费的情况。所以可以动态开辟空间的动态顺序表更加符合我们日常的使用，在创建顺序表时，往往也都创建动态顺序表，所以接下来的代码，也都将基于动态顺序表来实现。

三、顺序表的实现（先看源文件的实现过程，再看头文件）

（一）头文件（.h文件）

#pragma once
#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 SLCheckCapacity(SL* ps);
//打印查看
void SLPrint(SL s);
//尾插
void SLPushBack(SL* ps, SLDataType x);
//头插
void SLPushFront(SL* ps, SLDataType x);
//尾删
void SLPopBack(SL* ps);
//头删
void SLPopFront(SL* ps);
//在指定位置之前插入数据
void SLInsert(SL* ps, int pos, SLDataType x);
//删除指定位置的数据
void SLErase(SL* ps, int pos);
//顺序表的查找
int SLFind(SL* ps, SLDataType x);  

（二）源文件（.c文件）

导入库只有SeqList.h

1.顺序表的初始化

//顺序表的初始化
void SLInit(SL* ps)
{
    assert(ps);//防止传进空指针
    ps->arr = NULL;
    ps->size = ps->capacity = 0;
}  

2.顺序表的销毁

//顺序表的销毁
void SLDestroy(SL* ps)
{
    assert(ps);//防止传进空指针
    if (ps->arr)
    {
        free(ps->arr);
    }
    ps->arr = NULL;
    ps->size = ps->capacity = 0;
}
  

3.顺序表的尾插（有扩容）

频繁增容会使程序的运行效率大大降低，经过数学计算（感兴趣的话可自行上网搜索，2倍或3倍的增长更适合）

//尾插
void SLPushBack(SL* ps, SLDataType x)
{
    assert(ps);//防止传进空指针
    if (ps->size == ps->capacity)//空间满了，要申请空间
    { 
        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 fail!");
            exit(1);
        }
        //空间申请成功
        ps->arr = tmp;
        ps->capacity = newCapacity;
    }
    ps->arr[ps->size++] = x;
}  

我们对尾插进行调试
可以看到前四次插入都成功，且此时空间大小为4
空间扩容成功，第五次插入也成功

4.顺序表的头插（将扩容分装成一个函数）

在头插时我们发现，还需要检验空间大小以及扩容，所以此时我们将上面实现扩容的代码分装成一个函数。

void SLCheckCapacity(SL* ps)
{
    if (ps->size == ps->capacity)//空间满了，要申请空间
    {
        int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
        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;
}  

接下来开始实现头插

//头插
void SLPushFront(SL* ps, SLDataType x)
{
    assert(ps);//防止传进空指针
    SLCheckCapacity(ps);
    //先让顺序表中已有的数据整体往后移一位
    for (int i = ps->size; i > 0; i--)
    {
        ps->arr[i] = ps->arr[i - 1];//最后一次赋值arr[1] = arr[0]
    }
    ps->arr[0] = x;
    ps->size++;
}
  

在检验头插时，觉得调试看起来太麻烦了，这时候我们需要一个新的函数来显示我们的结果。

//打印查看
void SLPrint(SL s)
{
    for (int i = 0; i < s.size; i++)
    {
        printf("%d ", s.arr[i]);
    }
    printf("\n");
}  

5.顺序表的尾删

//尾删
void SLPopBack(SL* ps)
{
    assert(ps && ps->size);
    //顺序表现在不为空
    --ps->size;
}
  

删空之后再删就会报错

6.顺序表的头删

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

删空之后再删就会报错

7.在指定位置之前插入数据

//在指定位置之前插入数据
void SLInsert(SL* ps, int pos, SLDataType x)
{
    assert(ps);
    assert(pos >= 0 && pos <= ps->size);
    SLCheckCapacity(ps);
    //让pos和pos以后的数据整体往后移动一位
    for (int i = ps->size; i > pos; i--)
    {
        ps->arr[i] = ps->arr[i - 1];
    }
    ps->arr[pos] = x;
    ps->size++;
}
  

8.删除指定位置之前的数据

//删除指定位置的数据
void SLErase(SL* ps, int pos)
{
    assert(ps);
    assert(ps->size > 0);//顺序表不为空
    assert(pos >= 0 && pos < ps->size);
    //让pos之后的数据整体往前挪动一位
    for (int i = pos; i < ps->size - 1; i++)
    {
        ps->arr[i] = ps->arr[i + 1];
    }
    ps->size--;
}  

9.顺序表的查找

//顺序表的查找
int SLFind(SL* ps, SLDataType x)
{
    assert(ps);
    for (int i = 0; i < ps->size; i++)
    {
        if (ps->arr[i] == x)
        {
            //找到了
            return i;
        }
    }
    //没找到
    return -1;
}