数据结构—顺序表的实现【C语言】

前言

    *阅前提醒：本篇只是写出了顺序表里主要的算法代码，并没有以某种具体系统为轮廓来进行介绍。但是我想信，只要你**掌握**了这些主要的算法，你就**能够拥有**写出类似于“图书管理系统”此类系统的**能力**。（阅读前请先深呼吸，静下心来阅读哟，不管文章的质量如何，在当今碎片化信息泛滥的年代，能够静下心来也是一种能力！！！）*

..........................................................小白上路，不喜勿喷................................................................

一、顺序表是什么？

    顺序表其实是线性表的线性表示，线性表是数据结构里众多中的一种，当然链表也是线性表，关于链表我会在后面持续进行更新。

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

二、顺序表的实现

1.顺序表存储结构

            在实现之前，我们需要写出顺序表的存储结构，而它的存储有静态存储与动态存储。

• 静态存储：

//静态顺序表
#define N 200
typedef int SLDataType;
typedef struct SeqList
{
    SLDataType data[N];
    int len;//数据个数
}SL;

    这里顺序表的大小就是“200*int”，但是静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表。

• 动态存储：

//动态顺序表
typedef int SLDataType;//每个数据的数据类型
typedef struct SeqList
{
    SLDataType* data;//指向动态数组指针
    int len;//数据个数
    int capacity;//容量
}SL;

    注意：这里“int capacity”的值在大部分时间下都不会与“len”的值相等，这里开辟空间是多个内存一次性地开辟，当“capacity==len”时，就代表顺序表空间满了。

    当然，这顺序表的每个数据的数据类型也是可以改变的。这里定义的是“int”类型（“typedef int SLDataType”），你自己也可以定义一个结构体，替换“int”，那么每个数据的类型就是你定义的那个结构体。

2.接口

            我们需要实现的接口：

// 顺序表初始化
void SeqListInit(SeqList* psl);

// 检查空间，如果满了，进行增容
void CheckCapacity(SeqList* psl);

// 顺序表尾插
void SeqListPushBack(SeqList* psl, SLDataType x);

// 顺序表尾删
void SeqListPopBack(SeqList* psl);

// 顺序表头插
void SeqListPushFront(SeqList* psl, SLDataType x);

// 顺序表头删
void SeqListPopFront(SeqList* psl);

// 顺序表查找
int SeqListFind(SeqList* psl, SLDataType x);

// 顺序表在pos位置插入x
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x);

// 顺序表删除pos位置的值
void SeqListErase(SeqList* psl, size_t pos);

//修改pos位置的数据
void SLModify(SL* ps, int pos, SLDataType x)；

// 顺序表打印
void SeqListPrint(SeqList* psl);

// 顺序表销毁
void SeqListDestory(SeqList* psl);

...........................................................................................................................................................

提示：上述接口的代码是写在同一个源文件中，如“SeqList.c”，我会将其拆分，对关键部分进行详讲。

• 顺序表初始化：

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

//初始化
void SeqListInit(SL* ps)
{
    assert(ps);
    ps->data =NULL;
    ps->capacity = 0;
    ps->len = 0;
}

    这里**assert的作用**就是判断进入函数的指针是否为空指针，如果是空指针就结束当前程序运行。（此函数的头文件是“assert.h”）

    “assert(x)”  x为真，就能通过。

• 检查空间，如果满了，进行增容：

//检查、增加容量
void SLCheckCapacity(SL* ps)
{
    assert(ps);
    if (ps->len == ps->capacity)
    {
        int newCapacity = （ps->capacity == 0） ? 4 : ps->capacity * 2;//开辟多少空间。
        SLDataType* tmp = (SLDataType*)realloc(ps->data, newCapacity * sizeof(SLDataType));
        if (tmp == NULL)//确保reallc函数开辟内存成功。
        {
            printf("realloc fail\n");
            exit(-1);
        }

        ps->data = tmp;
        ps->capacity = newCapacity;
    }
}

    “realloc”与“exit”函数头文件都是“stdlib.h”；

    “realloc”函数就是动态内存开辟函数。（大佬的详解->【C语言】realloc函数_SouLinya的博客-CSDN博客_realloc）

    “exit”函数的功能是关闭所有文件，终止正在执行的进程。有“exit(x)”，只要x不为0，都表示异常退出。（大佬的详解->C语言中的exit()函数_春卷同学的博客-CSDN博客_c语言exit函数用法）

• 顺序表尾插：

//尾插
void SLPushBack(SL* ps, SLDataType x)
{
    assert(ps);
    SLCheckCapacity(ps);//检查、增加容量
    ps->data[ps->len] = x;
    ps->len++;
}

    只要是涉及到插入数据就得调用“SLCheckCapacity()”函数检查顺序表的内存剩余情况。(下同)

• 顺序表尾删：

//尾删
void SLPopBack(SL* ps)
{
    assert(ps);
    assert(ps->len > 0);
    ps->len--;
}

    删除只需要移动下标，并不需要太复杂的操作。

• 顺序表头插：

//头插
void SLPushFront(SL* ps, SLDataType x)
{
    assert(ps);
    SLCheckCapacity(ps);
    int end = ps->len - 1;//确保不对len进行修改
    while (end>=0)
    {

        ps->data[end + 1] = ps->data[end];
        --end;
    }
    ps->data[0] = x;
    ps->len++;

}

• 顺序表头删：

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

• 顺序表查找：

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

    }
    return -1;
}

    这里返回的是下标，如果返回值为-1，表示查找失败。

• 顺序表在pos位置插入x：

//插入(可以用于头插、尾插)
void SLInsert(SL* ps, int pos, SLDataType x)
{
    SLCheckCapacity(ps);
    assert(ps);
    assert(pos>=0 && pos<=ps->len);

    int end = ps->len - 1;
    while (pos<=end)
    {
        ps->data[end+1] = ps->data[end];
        end--;
    }

    ps->data[pos] = x;
    ps->len++;
}

• 顺序表删除pos位置的值：

//删除(可以用于头删、尾删)
void SLErase(SL* ps, int pos)
{
    assert(ps);
    assert(pos>0 && pos<ps->len);

    int begin = pos;
    while (begin<ps->len-1)
    {
        ps->data[begin] = ps->data[begin + 1];
        begin++;
    }
    ps->len--;
}

• 顺序表打印：

//打印
void SLprintf(SL* ps)
{
    assert(ps);
    for (int i=0;i<ps->len;i++)
    {
        printf("%d ",ps->data[i]);
    }
    printf("\n");
}

• 修改pos位置的数据：

//修改
void SLModify(SL* ps, int pos, SLDataType x)
{
    assert(ps);
    assert(pos>0 && pos<ps->len);

    ps->data[pos] = x;
}

• 顺序表销毁：

//顺序表销毁
void SLDestory(SL* ps)
{
    assert(ps);

    if (ps->data)
    {
        free(ps->data);
        ps->data = NULL;
        ps->capacity = ps->len = 0;
    }
}

    凡是动态开辟的空间最后都需要用free进行销毁。

总结

顺序表存储结构：静态存储、动态存储。

顺序表的接口：

• 顺序表初始化

• 检查空间，如果满了，进行增容

• 顺序表尾插

• 顺序表尾删

• 顺序表头插

• 顺序表头删

• 顺序表查找

• 顺序表在pos位置插入x

• 顺序表删除pos位置的值

• 修改pos位置的数据

• 顺序表打印

• 顺序表销毁

    以上这些你会了吗，你可能会说：“现在理解了、记住了，但过了一段时间就忘了”。没关系，这很正常，知识就是要不断地巩固，才能克服艾宾浩斯遗忘曲线，加油！！！（记得点点关注哦）