【数据结构】手写顺序表【纯C语言版】

摘要：本章主要讲述线性表，以及用C语言代码实现动态的顺序表

<hr/>

@TOC

正文开始

<hr>

1. 什么是线性表

1.1 概念

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

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

1.2 线性表的特点

我们知道，由n（n≥0）个数据特性相同的元素构成的有限序列称为线性表，所以线性表中元素的个数n（n≥0）就是线性表的长度，n=0 是称为空表

对于非空线性表或线性结构，有以下几个特点：

存在唯一的一个被称作“第一个”的数据元素；
存在唯一的一个被称作“最后一个”的数据元素；
除第一个数据元素外，结构中的每个数据元素均只有一个前驱；
除最后一个元素之外，结构中的每个数据元素均只有一个后继。

3. 什么是顺序表

3.1 概念

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

顺序表的特点：逻辑上相邻的数据元素，在物理上也是相邻的；顺序表是一种随机存取的存储结构

随机存取：可以通过下标直接操作数据元素，与存储位置无关

顺序存取：与随机存取相反，不能通过下标操作数据元素，与存储位置有关

顺序存取就是如果我们要操作第N个元素时，必须把该元素之前的所有元素访问一遍；而随机存取就是直接操作就行了。

3.2 顺序表的分类

1.静态顺序表：使用定长数组存储。

2.动态顺序表：使用动态开辟的数组存储，容量不受限制,支持数据插入,删除,修改等一系列操作。（接下来着重介绍）

4. 动态顺序表的代码实现

4.1 定义顺序表及其数据元素类型

// 定义顺序表中的数据元素的类型
typedef int SLDataType;

// 定义顺序表
typedef struct SeqList
{
    SLDataType* datas; // 数据序列
    size_t size; // 顺序表的有效数据个数
    size_t capacity; // 属性表的最大存储空间,即最多可以保存多少个数据
} SeqList;

使用 typedef 定义顺序表及其数据元素的类型是为了代码的可扩展性，大家想一想，如果有一天我们的数据元素不用 int 了，而是使用double或结构体，那么此时我们只需要修改这里就可以了，这样是不是就避免很多麻烦了呢？

思考：为什么数据序列要使用指针类型？

大家注意，我们这里实现的是动态顺序表，要使用顺序表为动态，我们就需要动态开辟内存，使用指针是为了让其容量不受限；如果我们将数据序列修改为 SLDataType data[50]，那么这样就是一个静态的顺序表了，因为它的长度已经被限定了

4.2 顺序表的初始化

【算法步骤】：

为顺序表 SeqList 动态分配一个预定义大小的数组空间，是数据序列datas 指向这段空间的基地址
将表的当前长度设为0，存储空间设为预定义大小

【算法描述】

#define DEFAULT_SIZE 4
// 初始化顺序表
void SeqListInit(SeqList* ps)
{
    assert(ps);
    // 默认开辟4个SLDataType大小的空间
    ps->data = (SLDataType*)malloc(sizeof(SLDataType) * DEFAULT_SIZE);
    if (ps->datas == NULL)
    {
        perror("申请内存失败");
        exit(-1);
    }
    ps->size = 0;
    ps->capacity = DEFAULT_SIZE;
}

这里我们为顺序表的容量设置了一个常量DEFAULT_SIZE，其常量值为4

【使用】

int main()
{
    SeqList plist;
    SeqListInit(&plist);
}

思考：为什么要传递指针？

因为我们这里需要改变线性表 plist 中的内容，所以需要传址；如果传值的话ps只是 plist 的一份临时拷贝，在 SeqListInit 函数内对 ps 的修改并不会对 plist 有任何影响。当然也可以将 SeqListInit 改造为下面这个：
#define DEFAULT_SIZE 4
SeqList SeqListInit()
{
// 默认开辟4个SLDataType大小的空间
SLDataType* ps = (SLDataType*)malloc(sizeof(SLDataType) * DEFAULT_SIZE);
if (ps == NULL)
{
perror("申请内存失败");
exit(-1);
}
SeqList list = { 0 };
list.datas = ps;
list.size = 0;
list.capacity = DEFAULT_SIZE;
return list;
}           

int main()
{
    SeqList plist = SeqListInit();

}

这是方式是使用返回值完成顺序表的初始化，当然是利用指针还是返回值都是可以的。

4.3 顺序表的增容

【算法步骤】

当顺序表满了的时候进行增容，每次增加原有容量的2倍
判断顺序表是否满了：如果有效数据长度等于最大容量则表面表满

// 检查增容
void SeqListCheckCapacity(SeqList* ps)
{
    assert(ps);
    if ((ps->size) >= (ps->capacity))
    {
        // 两倍增容
        ps->capacity *= 2;
        ps->datas = (SLDataType*)realloc(ps->datas, ps->capacity * sizeof(SLDataType));
        if (ps->datas == NULL)
        {
            perror("增容失败");
            exit(-1);
        }
    }
}

4.4 顺序表尾插法

检查是否需要增容
在下标为size位置处插入数据
有效数据个数加1

// 顺序表的尾插
void SeqListPushBack(SeqList* ps, SLDataType* data)
{
    assert(ps);

    // 1.检查扩容
    SeqListCheckCapacity(ps);
    // 2.插入数据
    ps->datas[ps->size] = *data;
    // 3.有效数据个数加1
    (ps->size) ++;
}

4.5 顺序表尾删法

判断是否是空表，空表则中断
有效数据个数减1即可

// 顺序表的尾删
void SeqListPopBack(SeqList* ps) 
{
    assert(ps);
    // 空表时中断
    assert(ps->size > 0);
    // 有效数据减1
    (ps->size)--;
}

4.6 打印顺序表

void SeqListPrint(SeqList* ps)
{
    assert(ps);

    for (int i = 0; i < ps->size; i++)
    {
        printf("%d ", ps->datas[i]);
    }
    putchar('\n');
}

int main()
{
    SeqList sl = SeqListInit();
    SLDataType a[] = { 0,1,2,3,4,5,6,7,8,9 };
    // 尾插
    SeqListPushBack(&sl, &a[1]);
    SeqListPushBack(&sl, &a[2]);
    // 打印
    SeqListPrint(&sl);              // 1 2 
}

4.7 顺序表头插法

所有元素整体后移
在头插入数据

// 顺序表的头插
void SeqListPushFront(SeqList* ps, SLDataType* data)
{
    // 顺序表的头插
void SeqListPushFront(SeqList* ps, SLDataType* data)
{
    assert(ps);
    // 1.检查增容
    SeqListCheckCapacity(ps);
    // 2.整体元素后移一个位置
    for (int i = ps->size - 1; i >= 0; i--)
    {
        // 后移
        ps->datas[i + 1] = ps->datas[i];
    }
    // 3.插入数据
    ps->datas[0] = *data;
    // 4.有效数据个数加1
    (ps->size) ++;
}}

4.8 顺序表头删法

判断是否为空表，如果是函数执行结束
整体元素前移一个单位

// 顺序表的头删
void SeqListPopFront(SeqList* ps)
{
    assert(ps);
    if (ps->size == 0)
    {
        printf("顺序表元素为空,删除失败!");
        return;
    }
    // 1.整体元素前移一个位置 要移动的元素-->[1,size]
    for (int i = 0; i < ps->size - 1; i++)
    {
        ps->datas[i] = ps->datas[i + 1];
    }
    // 有效数据个数减1
    (ps->size)--;
}

4.9 顺序表的插入

判断插入位置pos是否合法（pos值的合法范围时0≤pos＜size），若不合法则程序中断。
判断顺序表是否需要增容。
将第pos个至第size-1个元素依次向后移动一个位置，空出第pos个位置。
将要插入的新元素data放入第pos处。
顺序表有效数据个数加1。

// 任意位置插入
void SeqListInsert(SeqList* ps, int pos, SLDataType* data)
{
    assert(ps);
    size_t size = ps->size;
    // pos需要在[0,size]范围中
    assert( (pos <= size) && (pos >= 0) );

    // 检查增容
    SeqListCheckCapacity(ps);

    // [pos,size-1]处的元素后移一个位置
    for (int i = size - 1; i >= pos; i--)
    {
        ps->datas[i + 1] = ps->datas[i];
    }
    // 插入元素
    ps->datas[pos] = *data;
    // 有效数据个数加1
    (ps->size) ++;
}

4.10 顺序表的删除

判断插入位置pos是否合法（pos值的合法范围时0≤pos≤size），若不合法则程序中断。
将第pos个至第size-1个元素依次向前移动一个位置。
顺序表有效数据个数减1

// 任意位置删除
void SeqListErase(SeqList* ps, int pos)
{
    assert(ps);
    size_t size = ps->size;
    assert((pos <= size) && (pos >= 0));

    // 检查增容
    SeqListCheckCapacity(ps);
    // [pos+1,size-1] 的元素整体前移一个位置
    for (int i = pos; i < size -1; i++)
    {
        ps->datas[i] = ps->datas[i + 1];
    }
    (ps->size) --;
}

4.11 顺序表的销毁

将数据序列释放掉
将数据序列置为NULL
将数据有效个数和最大容量置为0

void SeqListDestory(SeqList* ps)
{
    assert(ps);
    // 释放资源
    free(ps->datas);
    ps->datas = NULL;
    ps->size = ps->capacity = 0;
}

4.12 思考

大家思考一下，为什么我在对顺序进行增容、插入等这些操作时，传递的数据采用传址的方式，而不是传值的方式呢？欢迎各位在评论区留言。

5. 源码链接

点击跳转

【文件说明】	文件名	说明
SeqList.h	类型定义和函数声明
SeqList.c	具体函数的实现
test.c	测试代码

后记

我水平有限，错误难免，还望各位加以指正。

【数据结构】手写顺序表【纯C语言版】

1. 什么是线性表

1.1 概念

1.2 线性表的特点

3. 什么是顺序表

3.1 概念

3.2 顺序表的分类

4. 动态顺序表的代码实现

4.1 定义顺序表及其数据元素类型

4.2 顺序表的初始化

4.3 顺序表的增容

4.4 顺序表尾插法

4.5 顺序表尾删法

4.6 打印顺序表

4.7 顺序表头插法

4.8 顺序表头删法

4.9 顺序表的插入

4.10 顺序表的删除

4.11 顺序表的销毁

4.12 思考

5. 源码链接

后记

继续阅读

CQ V1.0分词bates(基于双数组tire树)—应该是目前最快的中文分词算法

【数据结构】医院选址

CRC32和CRC8校验代码，C语言版

241 Different Ways to Add Parentheses（C代码版）

[转]ISUP信令的IAM消息详细内容

C语言：初学者必定看懂的注释！！！猴子吃桃问题。猴子第一天摘下若干个桃子，每天都吃了前一天剩下的一半零一个，到第10天早上想再吃的时候，就剩下一个桃子. 求第一天共摘多少个桃子。

[转]九大排序算法——C语言实现及详解

C++实现简单顺序表

笔试面试题目：滑动窗口(二)

while 循环、do- while 循环和 for 循环之间的那点事C语言自学之三种循环比较

交通/城市相关的公开的数据集上学时整理的Xie et al., 2020收集的

数据结构与算法（27）——排序（二）

结构体：typedef与struct的区别

GitHub连夜封杀！这份阿里 10W 字内部 Java 字面试手册到底有多强？

Linux设备模型（中）之上层容器

hdu7108哈希