图解数据结构顺序表实战指南：手把手教你详细实现（超详细解析）

在这里插入图片描述
??个人主页：聆风吟
??系列专栏：图解数据结构、算法模板
??少年有梦不应止于心动，更要付诸行动。

文章目录

  • 一. ??线性表
    • 1.1 ??线性表的定义
    • 1.2 ??线性表的存储结构
  • 二. ??顺序表
    • 2.1 ??顺序表定义
    • 2.2 ??顺序表的分类
      • 2.2.1 ??静态顺序表
      • 2.2.2 ??动态顺序表
  • 三. ??顺序表的基本操作实现
    • 3.1 ??动态顺序表结构体构建
    • 3.2 ??初始化顺序表
    • 3.3 ??销毁顺序表
    • 3.4 ??打印顺序表
    • 3.4 ??扩容
    • 3.5 ??尾插
    • 3.6 ??尾删
    • 3.7 ??头插
    • 3.8 ??头删
    • 3.9 ??在下标为pos位置插入x
    • 3.10 ??删除下标为pos位置的数据
    • 3.11 ??查找某个值的下标
  • 四. ??顺序表的完整源代码
    • 4.1 ??SeqList.h 顺序表的函数声明
    • 4.2 ??SeqList.c 顺序表的函数定义
    • 4.3 ??test.c 顺序表功能测试
  • ??总结

一. ??线性表

1.1 ??线性表的定义

线性表（linear list）：线性表是一种数据结构，由n个具有相同数据类型的元素构成一个有限序列。线性表可以用数组、链表、栈等方式实现，常见的线性表有数组、链表、栈、队列等，也可以自定义实现。

这里需要强调一下几点：
????首先它是一个序列。也就是说，元素之间是有顺序的。线性表中的元素称为结点，相邻结点之间的关系称为邻接关系。除第一个结点无前驱和最后一个结点无后继外，其他每个结点有且仅有一个前驱和一个后继。图解如下：
在这里插入图片描述

注意：
线性表元素个数n (n >= 0)定义为线性表的长度，当n=0时，称为空表。

1.2 ??线性表的存储结构

???? 线性表的存储结构有顺序存储结构和链式存储结构两种。前者称为顺序表，后者称为链表：
在这里插入图片描述???? 其中，线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。
在这里插入图片描述
???? 本文主要详细讲解线性表的顺序存储结构 —— 顺序表。线性表的链式存储将在下期讲解，言归正传接下来让我们开始今天的 “主菜" 学习。

二. ??顺序表

2.1 ??顺序表定义

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

在这里插入图片描述

2.2 ??顺序表的分类

顺序表一般可以分为：静态顺序表和动态顺序表。

2.2.1 ??静态顺序表

???? 静态顺序表：指存储空间是固定的并且在程序运行前就已经确定大小的顺序表。它通常使用数组来实现，即通过定义一个固定长度的数组来存储数据元素。

静态顺序表的结构代码：

//静态顺序表 —— 使用定长数组存储元素（不实用）
#define MAXSIZE 7//存储单元初始分配量
typedef int SLDataType;//SLDataType类型根据实际情况而定，这里是int

typedef struct SeqList
{
	SLDataType data[MAXSIZE];//定长数组
	int size;//有效数据的个数
}SeqList;

我们可以发现描述静态顺序表需要三个属性：

  • 存储空间的起始位置：数组data，他的存储位置就是存储空间的存储位置；
  • 线性表的最大存储容量：数组长的MAXSIZE；
  • 线性表的当前位置：size。

在这里插入图片描述静态顺序表的优缺点：

  1. 由于静态顺序表大小是固定的，因此不支持动态插入和删除，但可以通过重新分配空间的方式来增加或减少容量；
  2. 静态顺序表的优点：访问数据快速，由于是连续存储，所以可以直接通过下标访问元素，效率高；
  3. 静态顺序表的缺点：空间利用率低，因为必须预留足够的空间，以防止溢出。

2.2.2 ??动态顺序表

???? 动态顺序表：通过动态分配内存空间，实现随着数据量的增加而不断扩容的效果。它的结构类似于一个数组，数据元素的存储是连续的，支持随机访问和顺序访问。

动态顺序表的结构代码：

//动态顺序表 —— 使用动态开辟的数组存储
typedef int SLDataType;//SLDataType类型根据实际情况而定，这里是int

typedef struct SeqList
{
	SLDataType* a;//指向动态开辟的数组
	int size;//有效数据的个数
	int capacity;//记录容量的空间大小
}SL;

我们可以发现描述动态顺序表也需要三个属性：

  • 存储空间的起始位置：指针a，他里面存储的地址就是存储空间的地址；
  • 线性表当前最大存储容量：capacity，可以通过动态分配的方式进行扩容；
  • 线性表的当前位置：size。

在这里插入图片描述动态顺序表的优缺点：

  1. 动态顺序表的优点：可以使用指针动态地分配内存，具有高效的存储和访问效率；
  2. 动态顺序表的缺点：在插入和删除元素时需要移动大量的数据，效率较低。

三. ??顺序表的基本操作实现

????通过上面的学习我们已经初步了解静态顺序表和动态顺序表，有同学估计要问了在日常生活中我们应该使用哪种呢？在这里作者推荐大家使用动态顺序表。因为动态顺序表可以使程序更加高效和灵活，可以根据实际数据量动态地调整表的大小，避免在创建静态顺序表时浪费内存空间或者当数据量超出静态顺序表容量时造成数据丢失或程序崩溃等问题。本文也将采用动态顺序表结合图文去实现顺序表的基本操作。

3.1 ??动态顺序表结构体构建

//动态顺序表
#define SLCAPACITY 4
typedef int SLDataType;

typedef struct SeqList
{
	SLDataType* a;//指向动态开辟的数组
	int size;//有效数据的个数
	int capacity;//记录容量的空间大小
}SL;

代码深剖：

  • 结构体中 a 指向的数组类型是我们重定义的SLDataType，这样当我们想创建其它类型的顺序表时只需要对 typedef 后面的类型进行需改即可；
  • size是用来计数的，统计当前顺序表一共有多少个有效元素；
  • capacity是用来表示当前顺序表的容量，当size==capacity时说明当前顺序表已经“装满了”，需要扩容；
  • 定义标识符SLCAPACITY，方便后文对顺寻表进行初始化可以方便改变capacity的初始值。

3.2 ??初始化顺序表

//初始化顺序表
void SLInit(SL* ps)
{
	assert(ps);
	//使用malloc开辟空间
	ps->a = (SLDataType*)malloc(sizeof(SLDataType)*4);
	//判断空间是否开辟成功
	if (NULL == ps->a)
	{
		perror("malloc failed");
		exit(-1);
	}
	ps->size = 0;
	ps->capacity = SLCAPACITY;
}

代码深剖：

  • 在这里我们需要使用assert对ps进行一下断言，以防传入空指针（后文在出现就不多做叙述了）。
  • 使用malloc开辟空间，一定要进行判断是否开辟成功，如果不进行判断直接使用可能会导致程序崩溃。

时间复杂度：

该程序没有循环，根据大O阶的推导方法很容易得出：初始化顺序表的时间复杂度为O(1)

3.3 ??销毁顺序表

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

	free(ps->a);
	ps->a = NULL;
	ps->size = ps->capacity = 0;
}

代码深剖：
????为什么在这里要销毁顺序表呢？因为我们在这里使用的动态顺序表，a是通过malloc进行动态申请的空间，如果使用了malloc分配的内存空间后忘记释放，会导致内存泄漏，浪费系统资源甚至导致程序崩溃。

时间复杂度：

该程序没有循环，根据大O阶的推导方法很容易得出：销毁顺序表的时间复杂度为O(1)

3.4 ??打印顺序表

//打印顺序表
void SLPrint(SL* ps)
{
	assert(ps);

	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->a[i]);
	}
	printf("
");
}

代码深剖：
打印顺序表就是进行简单的遍历循环，此处不多做叙述。

时间复杂度：

该程序有单层循环，根据大O阶的推导方法很容易得出：打印顺序表的时间复杂度为O(n)

3.4 ??扩容

????因为扩容在尾插、头插以及在pos位置插入都需要使用，因此我们可以把扩容单独封装成一个函数，可以降低代码的的冗余。整体思路图解：
在这里插入图片描述

//检查容量是否够，不够进行扩容
void SLCheckCapacity(SL* ps)
{
	assert(ps);

	//满了要扩容
	if (ps->size == ps->capacity)
	{
		//使用realloc进行扩容
		SLDataType* temp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * 2 * (ps->capacity));
		//检查是否扩容成功
		if (temp == NULL)
		{
			perror("realloc failed");
			exit(-1);
		}

		ps->a = temp;
		ps->capacity *= 2;
	}
}

代码深剖：
????realloc是C语言中的一个函数，用于重新分配已经分配的内存空间的大小。它的原型是：

//头文件
#include<stdlib.h>
//原型
extern void *realloc(void *mem_address， unsigned int newsize)

其中，mem_address是指向已分配内存的指针，newsize是新的内存大小。如果内存分配失败，将会会返回NULL。

时间复杂度：

该程序没有循环，根据大O阶的推导方法很容易得出：扩容的时间复杂度为O(1)

3.5 ??尾插

????尾插时需要先判断顺序表是否满了，满了要先进行扩容才能继续进行扩容。size表示有效元素个数，同时也是顺序表中最后一个元素后一个位置的下标。成功插入后要对有效数据个数size进行加1操作。整体思路图解：
在这里插入图片描述

//尾插
void SLPushBack(SL* ps, SLDataType x)
{
	assert(ps);

	//检查是否需要扩容
	SLCheckCapacity(ps);
	
	ps->a[ps->size] = x;
	ps->size++;
}

时间复杂度：

该程序没有循环，根据大O阶的推导方法很容易得出：尾插的时间复杂度为O(1)

3.6 ??尾删

整体思路图解：
在这里插入图片描述

//尾删
void SLPopBack(SL* ps)
{
	assert(ps);

	//温柔检查
	/*if (ps->size == 0)
		return;*/
		
	//暴力检查
	assert(ps->size > 0);
	ps->size--;
}

代码深剖：
????在代码中我们提供两种检查顺序表是否为空的办法。第一种是比较温柔的检查，如果顺序表为空直接返回，返回之后仍然可以进行其他操作。第二种是比较暴力的检查方法，直接提示错误并打印出错误位置的行号。
在这里插入图片描述
时间复杂度：

该程序没有循环，根据大O阶的推导方法很容易得出：尾删的时间复杂度为O(1)

3.7 ??头插

整体思路图解：
在这里插入图片描述

//头插
void SLPushFront(SL* ps, SLDataType x)
{
	assert(ps);

	//检查是否需要扩容
	SLCheckCapacity(ps);
	
	//挪动数据
	int end = ps->size - 1;
	while (end >= 0)
	{
		ps->a[end + 1] = ps->a[end];
		--end;
	}

	ps->a[0] = x;
	ps->size++;
}

时间复杂度：

该程序需要执行单层循环，根据大O阶的推导方法很容易得出：头插的时间复杂度为O(n)

3.8 ??头删

整体思路图解：
在这里插入图片描述

//头删
void SLPopFront(SL* ps)
{
	assert(ps);

	//判断顺序表是否为空
	assert(ps->size > 0);
	
	//挪动元素向前覆盖
	int begin = 1;
	while (begin < ps->size)
	{
		ps->a[begin - 1] = ps->a[begin];
		++begin;
	}

	ps->size--;
}

时间复杂度：

该程序需要执行单层循环，根据大O阶的推导方法很容易得出：头插的时间复杂度为O(n)

3.9 ??在下标为pos位置插入x

整体思路图解：
在这里插入图片描述

//在下标为pos的位置插入x
void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	//检查pos是否在有效范围内
	assert(pos >= 0 && pos <= ps->size);
	//检查是否需要扩容
	SLCheckCapacity(ps);

	//挪动数据
	int end = ps->size - 1;
	while (end >= pos) 
	{
		ps->a[end + 1] = ps->a[end];
		--end;
	}

	//插入元素
	ps->a[pos] = x;
	ps->size++;
}

时间复杂度：

该程序需要执行单层循环，根据大O阶的推导方法很容易得出：pos位置插入的时间复杂度为O(n)

3.10 ??删除下标为pos位置的数据

整体思路图解：
在这里插入图片描述

//删除下标为pos位置的数据
void SLErase(SL* ps, int pos)
{
	assert(ps);
	//检查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--;
}

时间复杂度：

该程序需要执行单层循环，根据大O阶的推导方法很容易得出：pos位置删除的时间复杂度为O(n)

3.11 ??查找某个值的下标

//查找某个值的下标,没找到返回-1
int SLFind(SL* ps, SLDataType x)
{
	assert(ps);

	for (int i = 0; i < ps->size; i++)
	{
		if (ps->a[i] == x)
			return i;
	}

	return -1;
}

时间复杂度：

该程序需要执行单层循环，根据大O阶的推导方法很容易得出：查找的时间复杂度为O(n)

四. ??顺序表的完整源代码

4.1 ??SeqList.h 顺序表的函数声明

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

//动态顺序表
#define SLCAPACITY 4
typedef int SLDataType;

typedef struct SeqList
{
	SLDataType* a;//指向动态开辟的数组
	int size;//有效数据的个数
	int capacity;//记录容量的空间大小
}SL;


//管理数据 —— 增删查改

//初始化
void SLInit(SL* ps);
//销毁顺序表
void SLDestroy(SL* ps);
//打印顺序表
void SLPrint(SL* ps);
//检查容量是否够，不够进行扩容
void SLCheckCapacity(SL* ps);

//尾插尾删
void SLPushBack(SL* ps, SLDataType x);
void SLPopBack(SL* ps);

//头插头删 
void SLPushFront(SL* ps, SLDataType x);
void SLPopFront(SL* ps);

//查找某个值的下标,没找到返回-1
int SLFind(SL* ps, SLDataType x);

//在pos位置插入x
void SLInsert(SL* ps, int pos, SLDataType x);
//删除pos位置的数据
void SLErase(SL* ps, int pos);

4.2 ??SeqList.c 顺序表的函数定义

#include "SeqList.h"

//初始化顺序表
void SLInit(SL* ps)
{
	assert(ps);
	//使用malloc开辟空间
	ps->a = (SLDataType*)malloc(sizeof(SLDataType)*4);
	//判断空间是否开辟成功
	if (NULL == ps->a)
	{
		perror("malloc failed");
		exit(-1);
	}
	ps->size = 0;
	ps->capacity = SLCAPACITY;
}


//销毁顺序表
void SLDestroy(SL* ps)
{
	assert(ps);
	//释放动态开辟的空间
	free(ps->a);
	ps->a = NULL;
	ps->size = ps->capacity = 0;
}


//打印顺序表
void SLPrint(SL* ps)
{
	assert(ps);

	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->a[i]);
	}
	printf("
");
}


//检查容量是否够，不够进行扩容
void SLCheckCapacity(SL* ps)
{
	assert(ps);

	//满了要扩容
	if (ps->size == ps->capacity)
	{
		//使用realloc进行扩容
		SLDataType* temp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * 2 * (ps->capacity));
		//检查是否扩容成功
		if (temp == NULL)
		{
			perror("realloc failed");
			exit(-1);
		}

		ps->a = temp;
		ps->capacity *= 2;
	}
}


//尾插
void SLPushBack(SL* ps, SLDataType x)
{
	assert(ps);

	//检查是否需要扩容
	SLCheckCapacity(ps);
	
	ps->a[ps->size] = x;
	ps->size++;
}


//尾删
void SLPopBack(SL* ps)
{
	assert(ps);
	
	//暴力检查
	assert(ps->size > 0);
	ps->size--;
}


//头插
void SLPushFront(SL* ps, SLDataType x)
{
	assert(ps);

	//检查是否需要扩容
	SLCheckCapacity(ps);
	
	//挪动数据
	int end = ps->size - 1;
	while (end >= 0)
	{
		ps->a[end + 1] = ps->a[end];
		--end;
	}

	ps->a[0] = x;
	ps->size++;
}


//头删
void SLPopFront(SL* ps)
{
	assert(ps);
	//判断顺序表是否为空
	assert(ps->size > 0);
	
	//挪动元素向前覆盖
	int begin = 1;
	while (begin < ps->size)
	{
		ps->a[begin - 1] = ps->a[begin];
		++begin;
	}

	ps->size--;
}


//查找某个值的下标
int SLFind(SL* ps, SLDataType x)
{
	assert(ps);

	for (int i = 0; i < ps->size; i++)
	{
		if (ps->a[i] == x)
			return i;
	}

	return -1;
}


//在下标为pos的位置插入x
void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	//检查pos是否在有效范围内
	assert(pos >= 0 && pos <= ps->size);
	//检查是否需要扩容
	SLCheckCapacity(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 SLErase(SL* ps, int pos)
{
	assert(ps);
	//检查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--;
}

4.3 ??test.c 顺序表功能测试

????在这里作者只给出头插头删这组测试样例，因为只需要调用前面的函数，所以就不给大家挨个测试了，下来之后大家可以自行尝试，多敲多练大家一块进步。

#include "SeqList.h"


//尾插尾删检测
void TestSeqList1()
{
	
	SL s;//创建顺序表
	SLInit(&s);//初始化

	//尾插
	SLPushBack(&s, 1);
	SLPushBack(&s, 2);
	SLPushBack(&s, 3);
	SLPrint(&s);//打印

	//尾删
	SLPopBack(&s);
	SLPopBack(&s);
	SLPrint(&s);//打印

	//销毁顺序表
	SLDestroy(&s);
}

int main()
{
	TestSeqList1();
	return 0;
}

??总结

本文主要讲解：

  1. 线性表的定义：由n个具有相同数据类型的元素构成一个有限序列；
  2. 线性表的存储结构：顺序存储结构、链式存储结构；
  3. 顺序表的定义：用一段物理地址连续的存储单元依次存储数据元素的线性结构；
  4. 顺序表的分类：静态顺序表、动态顺序表；
  5. 顺序表的增删查改的实现。

???? 今天的干货分享到这里就结束啦！如果觉得文章还可以的话，希望能给个三连支持一下，聆风吟的主页还有很多有趣的文章，欢迎小伙伴们前去点评，您的支持就是作者前进的最大动力！
在这里插入图片描述