@[toc]

0. 线性表概念

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

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

1. 顺序表概念及结构

:key:顺序表就是数组，在数组的基础上要求 从头开始，要求数据挨着挨着 连续存储，没有跳跃间隔。

顺序表一般可以分为：

静态顺序表：使用定长数组存储元素。

#define N 1000
typedef int SLDataType;

//静态顺序表
typedef struct SeqList
{
    SLDataType data[N];
    int size;//表示数组中存储多少个数据
}SL;

静态顺序表的缺点：

:snowflake:1. 如果满了，就无法再插入。
:snowflake:2. 数组大小给多少合适？这个很难确定， N给小了不够用， N给大了浪费。

因此现实中我们基本都是使用动态顺序表，动态分配内存空间，所以下面我们实现动态顺序表。

动态顺序表：使用动态开辟的数组存储。

typedef int SLDataType;

//动态顺序表
typedef struct SeqList
{
    SLDataType* a;
    int size;//表示数组中存储多少个有效数据
    int capacity;//数组实际能存数据的容量
}SL;

2. 顺序表的增删查改

函数接口 —— SeqList.h

本文希望展现一套自然而然又理所当然的思路，都配了图，建议复制所有函数接口自己写自己调，感受会很好，至于完整代码也附在后面了。

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>//条件为真--没事，条件为假--终止程序

typedef int SLDataType;

//动态顺序表
typedef struct SeqList
{
    SLDataType* a;
    int size;//表示数组中存储多少个有效数据
    int capacity;//数组实际能存数据的容量
}SL;

//接口函数--命名风格跟着STL走，方便后续学习STL
void SeqListInit(SL* ps);
void SeqListPrint(SL* ps);
void SeqListCeckCapacity(SL* ps);
void SeqListDestroy(SL* ps);
//尾插
void SeqListPushBack(SL* ps, SLDataType x);
//尾删
void SeqListPopBack(SL* ps);
//头插
void SeqListPushFront(SL* ps, SLDataType x);
//头删
void SeqListPopFront(SL* ps);
//指定位置插入
void SeqListInsert(SL* ps,int pos,SLDataType x);
//删除指定位置数据
void SeqListErase(SL* ps,int pos);
//查找
int SeqListFind(SL* ps, SLDataType x);
//若找到--则返回下标
//找不到--返回-1
int SeqListFind(SL* ps, SLDataType x);

2.0 初始化、销毁、打印基本接口

2.0.1 初始化

初始化很有必要。开始时，顺序表中什么数据也没有，甚至也还没有为它动态申请一段空间。

因此，ps->a要置NULL，标识它是野指针。ps->size和ps->capacity都要置0，否则就是随机值了。

void SeqListInit(SL* ps)
{
    assert(ps);
    ps->a = NULL;
    ps->size = ps->capacity = 0;
}

注意：为什么传的是这个顺序表的地址？这是因为函数传参，形参是实参的拷贝，形参的改变不会影响实参。

2.0.2 打印

我们要写一点，就打印出来验证一下正确性，就写一个打印函数，遍历即可很简单。

void SeqListPrint(SL* ps)
{
    assert(ps);
    int i = 0;
    for (i = 0; i < ps->size; i++)
    {
        printf("%d ", ps->a[i]);
    }
    printf("\n");
}

2.0.3 销毁

现在我们写的是动态顺序表，那么malloc/realloc动态申请的空间，要记得释放，否则会发生内存泄漏。

关于此，可以复习一下这篇文章动态内存函数，我顺便也复习了一下，发现有些东西用惯了之后，对于它们是怎么来的会有点淡忘。

void SeqListDestroy(SL* ps)
{
    assert(ps);
    free(ps->a);
    ps->a = NULL;
    ps->size = ps->capacity = 0;
}

2.1 尾插尾删

2.1.1 扩容接口

:key:但凡插入数据就要考虑，空间够不够用是否需要增容的问题

void SeqListCeckCapacity(SL* ps)
{
    assert(ps);
    if (ps->size == ps->capacity)
    {
        //1.没有空间 —— 申请空间
        //2.空间不够 —— 扩容
        int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
        SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity*sizeof(SLDataType));
        if (tmp == NULL)
        {
            printf("扩容失败\n");
            exit(-1);
        }
        ps->a = tmp;
        ps->capacity = newcapacity;
    }
}

这里可能唯一要注意一下的，就是realloc函数，文档中如是写——

在这里插入图片描述

因此我们把第一次申请空间与后期的调整空间完美融合写在一起了，同时处理了没有空间和空间不够两种情况。

2.1.2 尾插

void SeqListPushBack(SL* ps, SLDataType x)
{
    assert(ps);
    SeqListCheckCapacity(ps);
    ps->a[ps ->size] = x;
    ps->size++;
}

2.1.3 尾删

:key: 删除数据就要考虑是不是删空了，没的删了，却还在调用这个函数，那就不对了

推荐直接断言暴力终止掉程序，毕竟，就是你用错了。

在这里插入图片描述

void SeqListPopBack(SL* ps)
{
    assert(ps);
    assert(ps->size);//断言暴力终止掉程序。若出现删多了的情况，就蹦出窗口终止程序
    ps->size--;
}

断言效果 ——
在这里插入图片描述

2.2 头插头删

2.2.1 头插

插入数据依然要考虑扩容问题
无论是头插还是头删，为了保证顺序表从开始位置连续，都需要挪动数据 —— 想好是从尾还是从头开始挪动，保证数据不会被覆盖丢失。
画好图，时刻注意边界

在这里插入图片描述

void SeqListPushFront(SL* ps, SLDataType x)
{
    assert(ps);
    SeqListCheckCapacity(ps);
    int end = ps->size - 1;
    while (end >= 0)
    {
        ps->a[end + 1] = ps->a[end];
        end--;
    }
    ps->a[0] = x;
    ps->size++;
}

2.2.2 头删

删除数据依然要考虑删空时，越界访问的情况
画图注意边界

void SeqListPushFront(SL* ps, SLDataType x)
{
    assert(ps);
    SeqListCheckCapacity(ps);
    int end = ps->size - 1;
    while (end >= 0)
    {
        ps->a[end + 1] = ps->a[end];
        end--;
    }
    ps->a[0] = x;
    ps->size++;
}

2.3 指定位置插入、删除指定位置数据、查找

查找常和指定位置插入、指定位置删除搭配使用。

2.3.1 查找

//查找--找到了则返回x位置下标，没有找到则返回-1
int SeqListFind(SL* ps, SLDataType x)
{
    int i = 0;
    for (i = 0; i < ps->size; i++)
    {
        if (ps->a[i] == x)
        {
            return i;
        }
    }
    return -1;
}

2.3.2 指定位置插入

与头插完全类似

void SeqListInsert(SL* ps, int pos, SLDataType x)
{
    assert(ps);
    SeqListCheckCapacity(ps);
    int end = ps->size - 1;
    while (end >= pos)
    {
        ps->a[end + 1] = ps->a[end];
        end--;
    }
    ps->a[pos] = x;
    ps->size++;
}

2.3.3 删除指定位置数据

与头删完全类似

void SeqListErase(SL* ps, int pos)
{
    assert(ps);
    assert(ps->size);
    int start = pos + 1;
    while (start < ps->size)
    {
        ps->a[start - 1] = ps->a[start];
        start++;
    }
    ps->size--;
}

2.3.4 复用

有了指定位置插入和指定位置删除，就可以复用这些接口，完成头插头删尾插尾删 ——

//尾插
void SeqListPushBack(SL* ps, SLDataType x)
{
    SeqListInsert(ps, ps->size, x);
}

//尾删
void SeqListPopBack(SL* ps)
{
    SeqListErase(ps, ps->size - 1);
} 

//头插
void SeqListPushFront(SL* ps, SLDataType x)
{
    SeqListInsert(ps, 0, x);
}   

//头删
void SeqListPopFront(SL* ps)
{
    SeqListErase(ps, 0);
}

分分钟搞定。

3. 顺序表的问题及思考

[ ] 顺序表优点 ——
支持随机访问，方便做查找。
[ ] 顺序表缺陷 ——

空间不够需要增容，增容是要付出代价的。
为了避免频繁扩容，我们基本都是按倍数去扩（扩2倍），可能会造成一定的空间浪费。
顺序表要求数据从开始位置保持连续，那么中间和头部的插入，就需要挪动数据，时间复杂度为O(N)，效率不高。

针对顺序表的缺陷，引出了下一节 —— 链表

未完待续@边通书

附：源代码

`SeqList.h`

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>//条件为真-没事，条件为假-终止程序

typedef int SLDataType;


//动态顺序表
typedef struct SeqList
{
    SLDataType* a;
    int size;        //表示数组中存储多少个数据
    int capacity;    //数组实际能存数据的容量
}SL;


//接口函数--命名风格跟着STL走，方便后续学习STL
void SeqListInit(SL* ps);
void SeqListPrint(SL* ps);
void SeqListDestroy(SL* ps);
void SeqListCheckCapacity(SL* ps);
//尾插
void SeqListPushBack(SL* ps, SLDataType x);
//尾删
void SeqListPopBack(SL* ps);
//头插
void SeqListPushFront(SL* ps, SLDataType x);
//头删
void SeqListPopFront(SL* ps);
//指定位置插入
void SeqListInsert(SL* ps, int pos, SLDataType x);
//删除指定位置的数据
void SeqListErase(SL* ps, int pos);

//查找--找到了则返回x位置下标，没有找到则返回-1
int SeqListFind(SL* ps, SLDataType x);

`SeqList.c`

#define _CRT_SECURE_NO_WARNINGS 1

#include"SeqList.h"

void SeqListInit(SL* ps)
{
    assert(ps);
    ps->a = NULL;
    ps->size = ps->capacity = 0;
}

void SeqListPrint(SL* ps)
{
    assert(ps);
    int i = 0;
    for (i = 0; i < ps->size; i++)
    {
        printf("%d ", ps->a[i]);
    }
    printf("\n");
}

void SeqListDestroy(SL* ps)
{
    assert(ps);
    free(ps->a);
    ps->a = NULL;
}

void SeqListCheckCapacity(SL* ps)
{
    assert(ps);
    if (ps->size == ps->capacity)
    {
        int newcapacity = (ps->capacity == 0) ? 4 : ps->capacity * 2;
        SLDataType* tmp = (SLDataType*)realloc(ps->a,sizeof(SLDataType)*newcapacity);
        if (tmp == NULL)
        {
            printf("realloc failed\n");
            exit(-1);
        }
        ps->a = tmp;
        ps->capacity = newcapacity;
    }
}

void SeqListPushBack(SL* ps, SLDataType x)
{
    SeqListInsert(ps, ps->size, x);
    //assert(ps);
    //SeqListCheckCapacity(ps);
    //ps->a[ps->size] = x;
    //ps->size++;
}

void SeqListPopBack(SL* ps)
{
    SeqListErase(ps, ps->size - 1);
    //assert(ps);
    //assert(ps->size);
    //ps->size--;
}

void SeqListPushFront(SL* ps, SLDataType x)
{
    SeqListInsert(ps, 0, x);
    /*assert(ps);
    SeqListCheckCapacity(ps);
    int end = ps->size - 1;
    while (end >= 0)
    {
        ps->a[end + 1] = ps->a[end];
        end--;
    }
    ps->a[0] = x;
    ps->size++;*/
}

void SeqListPopFront(SL* ps)
{
    SeqListErase(ps, 0);
    //assert(ps);
    //assert(ps->size);
    //int start = 1;
    //while (start < ps->size)
    //{
    //    ps->a[start - 1] = ps->a[start];
    //    start++;
    //}
    //ps->size--;
}

void SeqListInsert(SL* ps, int pos, SLDataType x)
{
    assert(ps);
    SeqListCheckCapacity(ps);
    int end = ps->size - 1;
    while (end >= pos)
    {
        ps->a[end + 1] = ps->a[end];
        end--;
    }
    ps->a[pos] = x;
    ps->size++;
}

void SeqListErase(SL* ps, int pos)
{
    assert(ps);
    assert(ps->size);
    int start = pos + 1;
    while (start < ps->size )
    {
        ps->a[start - 1] = ps->a[start];
        start++;
    }
    ps->size--;
}

int SeqListFind(SL* ps, SLDataType x)
{
    assert(ps);
    int i = 0;
    for (i = 0; i < ps->size; i++)
    {
        if (ps->a[i] == x)
            return i;
    }
    return -1;
}

`test.c`

关于测试文件，就是随写随测，把每种情况都测到，这里主要是增容呀，删空时的越界访问呀，还有就是基本的逻辑，把我自己的贴出来

#define _CRT_SECURE_NO_WARNINGS 1

#include"SeqList.h"

//测试尾插尾删
void TestSeqList1()
{
    SL sl;
    SeqListInit(&sl);

    SeqListPushBack(&sl, 1);
    SeqListPushBack(&sl, 2);
    SeqListPushBack(&sl, 3);
    SeqListPushBack(&sl, 4);
    SeqListPushBack(&sl, 5);

    SeqListPrint(&sl);

    SeqListPopBack(&sl);
    SeqListPopBack(&sl);
    SeqListPopBack(&sl);
    SeqListPopBack(&sl);
    //SeqListPopBack(&sl);
    //SeqListPopBack(&sl);

    SeqListPrint(&sl);
    SeqListDestroy(&sl);
}

//测试头插头删
void TestSeqList2()
{
    SL sl;
    SeqListInit(&sl);

    SeqListPushBack(&sl, 1);
    SeqListPushBack(&sl, 2);
    SeqListPushBack(&sl, 3);
    SeqListPushBack(&sl, 4);
    SeqListPushBack(&sl, 5);
    SeqListPrint(&sl);

    SeqListPushFront(&sl, 0);
    SeqListPushFront(&sl, -1);
    SeqListPushFront(&sl, -2);
    SeqListPrint(&sl);

    SeqListPopFront(&sl);
    SeqListPopFront(&sl);
    SeqListPrint(&sl);

    printf("%d\n", SeqListFind(&sl,3));

    SeqListDestroy(&sl);
}

//测试指定位置的插入删除
void TestSeqList3()
{
    SL sl;
    SeqListInit(&sl);

    SeqListPushBack(&sl, 1);
    SeqListPushBack(&sl, 2);
    SeqListPushBack(&sl, 3);
    SeqListPushBack(&sl, 4);
    SeqListPushBack(&sl, 5);

    SeqListInsert(&sl, 2, 30);
    SeqListInsert(&sl, 0, 0);
    SeqListInsert(&sl, sl.size, 80);

    SeqListPrint(&sl);
    
    //配合使用
    int pos = SeqListFind(&sl, 4);
    if (pos != -1)
    {
        SeqListInsert(&sl, pos, 40);
    }

    SeqListPrint(&sl);

    SeqListDestroy(&sl);

}

//复用SeqListInsert测试头插尾插
void TestSeqList4()
{
    SL sl;
    SeqListInit(&sl);

    SeqListPushBack(&sl, 1);
    SeqListPushBack(&sl, 2);
    SeqListPushBack(&sl, 3);
    SeqListPushBack(&sl, 4);
    SeqListPushBack(&sl, 5);

    SeqListPushFront(&sl, 1);
    SeqListPushFront(&sl, 2);
    SeqListPushFront(&sl, 3);
    SeqListPushFront(&sl, 4);
    SeqListPushFront(&sl, 5);
    SeqListPrint(&sl);

    SeqListPopFront(&sl);
    SeqListPopFront(&sl);

    SeqListPopBack(&sl);
    SeqListPopBack(&sl);

    SeqListPrint(&sl);

    //假如我要删3
    int pos = SeqListFind(&sl, 3);
    if (pos != -1)
    {
        SeqListErase(&sl, pos);
    }
    SeqListPrint(&sl);

    SeqListDestroy(&sl);
}
int main()
{
    //TestSeqList1();
    //TestSeqList2();
    //TestSeqList3();
    TestSeqList4();

    return 0;
}

【DS】顺序表@线性表 —— 增删查改

0. 线性表概念

1. 顺序表概念及结构

2. 顺序表的增删查改

2.0 初始化、销毁、打印基本接口

2.0.1 初始化

2.0.2 打印

2.0.3 销毁

2.1 尾插尾删

2.1.1 扩容接口

2.1.2 尾插

2.1.3 尾删

2.2 头插头删

2.2.1 头插

2.2.2 头删

2.3 指定位置插入、删除指定位置数据、查找

2.3.1 查找

2.3.2 指定位置插入

2.3.3 删除指定位置数据

2.3.4 复用

3. 顺序表的问题及思考

附：源代码

`SeqList.h`

`SeqList.c`

`test.c`

热门文章

最新文章

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

【DS】顺序表@线性表 —— 增删查改

0. 线性表概念

1. 顺序表概念及结构

2. 顺序表的增删查改

2.0 初始化、销毁、打印基本接口

2.0.1 初始化

2.0.2 打印

2.0.3 销毁

2.1 尾插尾删

2.1.1 扩容接口

2.1.2 尾插

2.1.3 尾删

2.2 头插头删

2.2.1 头插

2.2.2 头删

2.3 指定位置插入、删除指定位置数据、查找

2.3.1 查找

2.3.2 指定位置插入

2.3.3 删除指定位置数据

2.3.4 复用

3. 顺序表的问题及思考

附：源代码

SeqList.h

SeqList.c

test.c

热门文章

最新文章

相关电子书

`SeqList.h`

`SeqList.c`

`test.c`