C语言顺序表的根本构造与实现思路详解

目录

一、顺序表的概念与构造

1.线性表的解释2.顺序表概念解释

二、顺序表的思路及代码实现详解

1.静态顺序表的实现2.动态顺序表思路及代码实现

2.1 动态顺序表的整体思路2.2 定义构造体的实现2.3 初始化构造体2.4 构造体打印2.5 检查数组容量2.6 头插2.7 尾插2.8 头删2.9 尾删2.10 任意删除2.11 任意插入2.12 空间释放



三、顺序表代码整合

SeqList.hSeqList.ctest.c

一、顺序表的概念与构造


1.线性表的解释

首先我们在这里引入线性表的概念。线性表是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据构造。
常见的线性表：顺序表、链表、栈、队列、字符串……
线性表在逻辑上是线性构造，也就是说是连续的一条直线。但是在物理构造上并不一定是连续的，线性表在物理上存储时，通常以数据和链式构造的形式存储。
顺序表就是线性表的一种，我们在这里详细解释一下顺序表的实现，后续我们会更新链表等内容。

2.顺序表概念解释

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

静态顺序表：使用定长数组存储。动态顺序表：使用动态开拓的数组存储。

二、顺序表的思路及代码实现详解


1.静态顺序表的实现

我们先想出来一个静态表整体的模板思路：

定义一个构造体，该构造体包含一个可以寄存数据的数组和记录数组中有效数字的变量。初始化构造体。打印构造体。头插。尾插。头删。尾删。任意位置插入。任意位置删除。

这里需要有一点注意的是，我们在定义构造体中的数组时，我们可以用typedef停止变量名简化，这也方便我们后期更改存储类型的时候直接更改typedef处就行。同时我们会想到数组的大小需要define定义一个宏，这样大大进步了代码后期的可维护性。
但是我们认真想一下，假设我们存储的数据满了，我们想要继续存储的话还要找到源码停止更改大小。每次存储满了，都要更改。那是不是太费事了，且效率很低。这时候我们就联想到了动态的顺序表，可以自动开拓空间，从而大大进步效率。
这里我就给出大家静态顺序表定义及接口的代码，不再详细解释接口的实现了。我们这里详细解释一下动态顺序表的解释。静态顺序表接口的实现与动态顺序表接口实现大同小异，可参考动态顺序表接口的详解。
代码如下：
#define MAX_SIZE 10
typedef int SQDataType;
typedef struct SeqList
{
        SQDataType a[MAX_SIZE];
        int size;
}SL;
//typedef struct SeqList SL;
typedef struct SeqList SL;
//初始化构造体
void SeqListInit(SL* ps);
//打印
void SeqListPrint(SL s);
//尾插
void SeqListPushBack(SL* ps, SQDataType x);
//尾删
void SeqListPopBack(SL* ps);
//头插
void SeqListPushFrint(SL* ps, SQDataType x);
//头删
void SeqListPopFrint(SL* ps);
//查找位置
int SeqListFind(SL s, SQDataType x);
//任意插入
void SeqListInsert(SL* ps, int pos, SQDataType x);
//任意删
void SeqListErase(SL* ps, int pos);
2.动态顺序表思路及代码实现


2.1 动态顺序表的整体思路

动态顺序表的思路与静态大致相同，但也有所不同，我来给大家详细解释一下。我们先看动态顺序表的整体思路模板：

定义一个构造体，该构造体包含一个可以寄存数据的动态数组和记录数组中有效数据的变量，两外还需要一个变量记录当前数组的大小。初始化构造体。打印构造体。检查数组容量头插。尾插。头删。尾删。任意位置插入。任意位置删除。释放动态数组空间

我们上面提到了动态的数组，需要用malloc或realloc动态开拓空间。由于是动态开拓的，我们这里多了一项释放动态开拓的空间。注意，记录数组的有效数据和数组大小并不相同。有效数据是已经存储的数据个数，而数组大小是指最可以存储数组的个数。我们为什么要记录数组的大小呢？这里是用来判断是否存储满了，满了话要开拓空间。
我们来详细看一下每个接口的实现。

2.2 定义构造体的实现

在定义构造体时，我们可以用typedef停止数组类型简化，同时方便我们后期更改存储类型的时候直接更改typedef处即可。同时我们也用typedef停止构造体类型简化，方便我们以后编辑代码。我们来看一下代码的实现：
typedef int SQDataType;
struct SeqList
{
        SQDataType* a;
        int size;
        int capacity;
};
typedef struct SeqList SL;通过上面的代码我们可以发现，当我们不想存储int型数据时，我们只需把‘typedef int SQDataType’改为‘typedef doubleSQDataType’即可。极大的进步了代码的维护性。

2.3 初始化构造体

我们初始化构造体时，可以先将数组置空，我们后期插入数据时可再开拓空间。同时当然有效数据和数组大小都要初始化成零。我们看代码的实现。
void SeqListInit(SL* ps)
{
        ps->a = NULL;
        ps->size = 0;
        ps->capacity = 0;
}我们这里是改变了构造体的内容，所以需要传地址，用指针变量来接收。

2.4 构造体打印

构造体打印方便我们观察对动态数组的操作。打印的时数组的有效数据的内容。我们来看代码的实现。
void SeqListPrint(SL s)
{
        int i = 0;
        for (i = 0; i < s.size; i++)
        {
                printf("%d ", s.a);
        }
        printf("\n");
}
2.5 检查数组容量

我们认真想一想，是不是在插入每个数据之前都要检查数组是否已经满了。假设满了，则需要增容。假设没有满，就插入数据即可。在这里我们需要实现头插、尾插、任意插入三个接口，所以我们就把检查数组容量单独分装一个函数，这样进步代码的简洁性。我们看一下代码的实现。
void SQLCheckCapacity(SL* ps)
{
        if (ps->size == ps->capacity)
        {
                int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
                SQDataType* tmp =(SQDataType*)realloc(ps->a, sizeof(SQDataType) * newcapacity);
                if (tmp == NULL)
                {
                        printf("realloc failed\n");
                        exit(-1);
                }
                ps->capacity = newcapacity;
                ps->a = tmp;
        }
}当我们检查增容时，我们还要判断一下之前的数组大小是否为零，假设是零的话，我们要给其赋一个值。因为我们刚开端初始化数组的时候把数组指针置空了。在动态顺序表中我们增容一般会扩大到原来的2倍。

2.6 头插

在插入之前要判断数组是否已经满了。头插的思想就是把数组的内容整体后移一位，我们把要插入的数据放在第一位。我们结合着代码一起理解。
void SeqListPushFrint(SL* ps, SQDataType x)
{
        SQLCheckCapacity(ps);
        int end = ps->size - 1;
        while (end >= 0)
        {
                ps->a[end+1] = ps->a[end];
                end--;
        }
        ps->a[0] = x;
        ps->size++;
}
2.7 尾插

同样， 在插入之前要判断数组是否已经满了。尾插的思想很简单。就是直接在数组尾部插入一个数据即可。我们看一下代码的实现。
void SeqListPushBack(SL* ps, SQDataType x)
{
        SQLCheckCapacity(ps);
        ps->a[ps->size] = x;
        ps->size++;
}
2.8 头删

删除时我们也有要注意的一点，就是检查数组中是否有元素给我们删除。头删的思想就是除去数组的第一个元素，我们将后面的元素整体向前挪动一位，将第一位给覆盖了。我们来看代码。
void SeqListPopFrint(SL* ps)
{
        assert(ps->size > 0);
        int i = 0;
        for (i = 0; i < ps->size - 1; i++)
        {
                ps->a = ps->a[i + 1];
        }
        ps->size--;
}
2.9 尾删

同样，在尾删之前，我们要检查数组中是否有元素给我们删除。尾删的思想非常简单，就是把数组的有效数据减一即可。我们看一下代码的实现。
void SeqListPopBack(SL* ps)
{
        assert(ps->size > 0);
        ps->size--;
}
2.10 任意删除

在任意删除时，我们首先要判断删除的位置是否合理，不能违犯顺序表的规则。同样，在尾删之前，我们要检查数组中是否有元素给我们删除。任意删除就是我们指出删除位置的下标停止删除。当然，我们想要删除数组中指定元素时，我们可以先查出元素下标在停止删除。这个相对来说较复杂一点，我们结合着代码理解一下。
//查找位置
int SeqListFind(SL s, SQDataType x)
{
        int i = 0;
        for (i = 0; i < s.size; i++)
        {
                if (s.a == x)
                {
                        return i;
                }
        }
        return -1;
}
void SeqListErase(SL* ps, int pos)
{
        assert(pos >= 0 && pos < ps->size);
        int begin = pos + 1;
        while (begin < ps->size)
        {
                ps->a[begin - 1] = ps->a[begin];
                begin++;
        }
        ps->size--;
}
2.11 任意插入

在任意插入时时，我们也要判断插入的位置是否合理，不能违犯顺序表的规则。插入时，我们不能忘记检查数组是否满了。任意插入的思想与任意删除的思想根本相同。任意插入的思想就是在我们指出删除位置的下标停止插入。我们看一下代码实现。
void SeqListInsert(SL* ps, int pos, SQDataType x)
{
        assert(pos >= 0 && pos <= ps->size);
        SQLCheckCapacity(ps);
        int end = ps->size-1;
        while (end >= pos)
        {
                ps->a[end+1] = ps->a[end];
                end--;
        }
        ps->a[pos] = x;
        ps->size++;
}
2.12 空间释放

由于我们的数组是动态开拓的，所以当我们不用时，我们要及时释放掉动态开拓的空间，防止内存泄漏。同时我们要把数组指针再次置空，防止产生野指针。我们看代码实现。
void SeqListDestory(SL* ps)
{
        free(ps->a);
        ps->a = NULL;
        ps->capacity = ps->size = 0;
}
三、顺序表代码整合

由于代码量相对来说有一点多，所以我们就将函数的声明的定义分开，这样有利于进步代码的可读性，同时会坚持一个良好的思路，且方便编写代码。
我们将函数的声明放在单独的一个SeqList.h的头文件，函数的实现放在一个单独的SeqList.c源文件，函数的主方法及调用放在另一个单独的test.c源文件。

SeqList.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SQDataType;
struct SeqList
{
        SQDataType* a;
        int size;
        int capacity;
};
typedef struct SeqList SL;
//初始化构造体
void SeqListInit(SL* ps);
//打印
void SeqListPrint(SL s);
//尾插
void SeqListPushBack(SL* ps, SQDataType x);
//尾删
void SeqListPopBack(SL* ps);
//头插
void SeqListPushFrint(SL* ps, SQDataType x);
//头删
void SeqListPopFrint(SL* ps);
//查找位置
int SeqListFind(SL s, SQDataType x);
//任意插入
void SeqListInsert(SL* ps, int pos, SQDataType x);
//任意删
void SeqListErase(SL* ps, int pos);
//销毁空间
void SeqListDestory(SL* ps);
SeqList.c

#include"SeqList.h"
//初始化构造体
void SeqListInit(SL* ps)
{
        ps->a = NULL;
        ps->size = 0;
        ps->capacity = 0;
}
//打印
void SeqListPrint(SL s)
{
        int i = 0;
        for (i = 0; i < s.size; i++)
        {
                printf("%d ", s.a);
        }
        printf("\n");
}
//查容增容
void SQLCheckCapacity(SL* ps)
{
        if (ps->size == ps->capacity)
        {
                int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
                SQDataType* tmp =(SQDataType*)realloc(ps->a, sizeof(SQDataType) * newcapacity);
                if (tmp == NULL)
                {
                        printf("realloc failed\n");
                        exit(-1);
                }
                ps->capacity = newcapacity;
                ps->a = tmp;
        }
}
//尾插
void SeqListPushBack(SL* ps, SQDataType x)
{
        SQLCheckCapacity(ps);
        ps->a[ps->size] = x;
        ps->size++;
}
//尾删
void SeqListPopBack(SL* ps)
{
        assert(ps->size > 0);
        ps->size--;
}
//头插
void SeqListPushFrint(SL* ps, SQDataType x)
{
        SQLCheckCapacity(ps);
        int end = ps->size - 1;
        while (end >= 0)
        {
                ps->a[end+1] = ps->a[end];
                end--;
        }
        ps->a[0] = x;
        ps->size++;
}
//头删
void SeqListPopFrint(SL* ps)
{
        assert(ps->size > 0);
        int i = 0;
        for (i = 0; i < ps->size - 1; i++)
        {
                ps->a = ps->a[i + 1];
        }
        ps->size--;
}
//查找位置
int SeqListFind(SL s, SQDataType x)
{
        int i = 0;
        for (i = 0; i < s.size; i++)
        {
                if (s.a == x)
                {
                        return i;
                }
        }
        return -1;
}
//任意插——在下标为pos的位置插入数据
void SeqListInsert(SL* ps, int pos, SQDataType x)
{
        assert(pos >= 0 && pos <= ps->size);
        SQLCheckCapacity(ps);
        int end = ps->size-1;
        while (end >= pos)
        {
                ps->a[end+1] = ps->a[end];
                end--;
        }
        ps->a[pos] = x;
        ps->size++;
}
//任意删——删除下标为pos的数据
void SeqListErase(SL* ps, int pos)
{
        assert(pos >= 0 && pos < ps->size);
        int begin = pos + 1;
        while (begin < ps->size)
        {
                ps->a[begin - 1] = ps->a[begin];
                begin++;
        }
        ps->size--;
}
//销毁空间
void SeqListDestory(SL* ps)
{
        free(ps->a);
        ps->a = NULL;
        ps->capacity = ps->size = 0;
}
test.c

#include"SeqList.h"
void test()
{
        SL s1;
        SeqListInit(&s1);
        SeqListPushBack(&s1, 1);
        SeqListPushFrint(&s1, 1);
        SeqListPushFrint(&s1, 2);
        SeqListPushFrint(&s1, 3);
        SeqListPushFrint(&s1, 4);
        SeqListPushBack(&s1, 5);
        SeqListPrint(s1);
        SeqListPopFrint(&s1);
        SeqListPrint(s1);
        int pos = SeqListFind(s1, 1);
        SeqListInsert(&s1, pos, 10);
        SeqListInsert(&s1, 0, 20);
        SeqListPrint(s1);
        SeqListErase(&s1, 0);
        SeqListPrint(s1);
        SeqListDestory(&s1);
}
int main()
{
        test();
        return 0;
}到此这篇关于C语言顺序表的根本构造与实现思路详解的文章就介绍到这了,更多相关C语言顺序表内容请搜索网站以前的文章或继续阅读下面的相关文章希望大家以后多多支持网站！