数据结构与算法之顺序表详解

Love The Way You Lie 2023-09-26 16:54 65阅读 0赞

> ## 标题：顺序表的思路及代码实现 ##
> 
> ## **作者：@Ggggggtm** ##
> 
> ## 寄语：与其忙着诉苦，不如低头赶路，奋路前行，终将遇到一番好风景 ##
> 
> ## **文章目录：** ##
> 
> 一、顺序表的概念与结构
> 
> 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.h
> 
> SeqList.c
> 
> test.c
> 
> --------------------
> 
> ![0b6ff4baa5484ed88c274900613e5c69.png][]

## 一、顺序表的概念与结构 ##

### 1、线性表的解释 ###

> 首先我们在这里引入线性表的概念。线性表是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构。
> 
> 常见的线性表：**顺序表、链表、栈、队列、字符串**……

> 线性表在逻辑上是线性结构，也就是说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数据和链式结构的形式存储。
> 
> 顺序表就是线性表的一种，我们在这里详细解释一下顺序表的实现，后续我们会更新链表等内容。

### 2、顺序表概念解释 ###

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

> 而顺序表一般可分为：
> 
> 1.  静态顺序表：使用定长数组存储。
> 2.  动态顺序表：使用动态开辟的数组存储。

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

### 1、静态顺序表的实现 ###

> 我们先想出来一个静态表整体的模板思路：
> 
> 1.  定义一个结构体，该结构体包含一个可以存放数据的数组和记录数组中有效数字的变量。
> 2.  初始化结构体。
> 3.  打印结构体。
> 4.  头插。
> 5.  尾插。
> 6.  头删。
> 7.  尾删。
> 8.  任意位置插入。
> 9.  任意位置删除。
> 
> 这里需要有一点注意的是，我们在定义结构体中的数组时，我们可以用**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 动态顺序表的整体思路 ####

> 动态顺序表的思路与静态大致相同，但也有所不同，我来给大家详细解释一下。我们先看动态顺序表的整体思路模板：
> 
> 1.  定义一个结构体，该结构体包含一个可以存放数据的动态数组和记录数组中有效数据的变量，两外还需要一个变量记录当前数组的大小。
> 2.  初始化结构体。
> 3.  打印结构体。
> 4.  检查数组容量
> 5.  头插。
> 6.  尾插。
> 7.  头删。
> 8.  尾删。
> 9.  任意位置插入。
> 10. 任意位置删除。
> 11. 释放动态数组空间

> 我们上面提到了动态的数组，需要用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 double SQDataType’即可。极大的提高了代码的维护性。

#### 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[i]);
    	}
    	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[i] = 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[i] == 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[i]);
    	}
    	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[i] = 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[i] == 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;
    }

> 以上就是顺序表的所有内容啦，希望本篇文章会对你有所帮助，感谢阅读。
> 
> 后期会持续更新链表哦ovo~。

[0b6ff4baa5484ed88c274900613e5c69.png]: https://img-blog.csdnimg.cn/0b6ff4baa5484ed88c274900613e5c69.png