【数据结构】顺序表：与时俱进的结构解析与创新应用

 欢迎来到白刘的领域   Miracle_86.-CSDN博客

         系列专栏   数据结构与算法

先赞后看，已成习惯

   创作不易，多多支持！

目录

一、数据结构的概念

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。数据结构反映数据的内部构成，即数据由哪部分构成，以什么方式构成，以及数据之间存在的相互关系。

数据结构可以分为两类：线性数据结构和非线性数据结构。线性数据结构以线性的方式组织数据，例如数组、链表和栈。非线性数据结构是一种通过多个节点之间的关联来组织数据的方式，例如树和图。数据结构的选取和设计对于解决特定问题和提高算法效率非常重要。

我们可以将这个词拆分成“数据”和“结构”两部分。

什么是数据？数据可以是数字、文字、图像等。比如超市购物时的价格、数量，天气预报中的温度、湿度，或是社交媒体上的浏览量、点赞数，都是数据。它们为我们提供信息，帮助我们做出决策，让生活更加便捷。

什么是结构？当我们想要使用大量使用同类型的数据时，通过手动定义大量的独立的变量对于程序来说，可读性非常差，我们可以借助数组这样的数据结构将大量的数据组织在一起，结构也可以理解为组织数据的方式。

比如，想要在世界上找到“喜羊羊”的这只羊很难，但是我告诉你在青青草原找，那就特别好找。青青草原这一块地方就可以看成一个结构，有效地将羊群组织起来。

总结：

1.数据结构可以存储数据。

2.存储的数据能够方便查找。

那为什么我们需要数据结构呢？

在生活中，假如我们开了个餐馆，不借助排队的方式来管理客户，会导致客户就餐感受差、等餐时间长、餐厅营业混乱等情况。同理，程序中如果不对数据进行管理，可能会导致数据丢失、操作数据困难、野指针等情况。

良好的数据结构和算法设计对于确保程序的稳定性和效率至关重要。通过合理地组织和管理数据，我们可以提高程序的性能，减少错误，并为用户提供更好的体验。

我们曾学过最基础的数据结构：数组。

C语言中的百宝箱——数组（1）-CSDN博客

C语言中的百宝箱——数组（2）-CSDN博客

既然我们已经学过数组这种数据结构了，那我们还需要学其它的数据结构嘛？存在即合理，显然数组是有一定的局限性的。

假定数组有10个空间，已经使用了5个，向数组中插入数据的步骤应该是：

1. 求数组的长度（这里是10）。

2. 求数组的有效数据个数（这里是5）。

3. 判断数组是否已满（如果有效数据个数等于数组长度，则数组已满）。

4. 如果数组未满，向下标为有效数据个数的位置插入数据。

注意：在插入数据之前，必须判断数组是否已满。如果数组已满，则不能再继续插入数据，否则可能会导致数据覆盖或程序崩溃等严重问题。

假设数据量非常大，频繁的获取数组有效数据个数确实可能会影响程序执行效率。

所以我们可以得出结论：最基础的数据结构能提供的操作不能满足复杂算法的实现。

二、顺序表（Sequence List）

2.1 线性表的概念以及结构

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

线性表在逻辑上是线性结构，也就是说它表现为一条连续的直线。然而，在物理结构上，线性表并不一定是连续的。线性表在物理上存储时，通常以数组和链式结构的形式存在。数组存储方式使得元素在内存中连续排列，便于通过下标快速访问；而链式存储方式则通过指针或引用将元素链接在一起，允许在动态环境中灵活地进行插入和删除操作。

如何来理解逻辑结构和物理结构呢？

简单来说，逻辑结构关注的是数据元素之间的逻辑关系，它描述的是数据应该如何被组织，而不关心数据具体是如何在计算机内存中存放的。例如，我们可以说一个列表是一系列有序的元素，这就是它的逻辑结构。

而物理结构，或者叫存储结构，则关心数据在计算机内存中的具体存放方式。比如，这个列表是用数组的形式连续存储在内存中，还是用链表的形式分散存储在内存中，这就是物理结构所关心的问题。

2.2 顺序表分类

2.2.1 顺序表和数组的区别

其实顺序表的底层逻辑是数组，对数组进行了封装，并且实现了常用的增删查改等接口。

2.2.2 顺序表的分类

顺序表分为静态顺序表和动态顺序表，顾名思义，一个静态动不了，一个动态可调节。

• 静态顺序表：

刚刚我们说了，顺序表是基于数组实现的，那静态顺序表就是基于定长数组实现的。

//静态顺序表
typedef int SLDataType;
#define N 7
typedef struct SeqList{
    SLDataType a[N];
    int size;
}SL;

• 动态顺序表：

动态一词，我们不由得想起之前提到的动态内存管理，没错动态顺序表确实是需要动态申请的。

内存地产风云录：malloc、free、calloc、realloc演绎动态内存世界的楼盘开发与交易大戏-CSDN博客

// 动态顺序表 -- 按需申请
typedef struct SeqList
{
 SLDataType* a;
 int size; // 有效数据个数
 int capacity; // 空间容量
}SL;

2.3 顺序表的实现

还记得扫雷嘛各位，当时我们创建了三个文件，分别是：game.c，game.h和test.c。game.c用来存放函数的实现，game.h用来存放头文件以及宏，而test.c用来测试。写完函数进行测试，这是一个良好的习惯，今天我们实现顺序表也会这样操作，但这里不介绍test.c文件，着重讲解函数的实现。

首先，我们需要定义一个动态顺序表，我们将定义放在头文件中。

//定义顺序表中的数据类型，可以随时修改int
typedef int SLDataType;

//动态
typedef struct SeqList
{
	SLDataType *arr;
	int size; //有效数据个数
	int capacity; //空间大小
}SL;

2.3.1 初始化

接下来我们需要对这个顺序表进行初始化（initialize）。

这个函数没什么好解释的，只需要将顺序表的成员，指针指向NULL，数变成0。唯一一点重要的是：我们传参的时候，需要传顺序表的地址。

要区别传值和传址，我们在这篇文章中解释过：

灵魂指针，教给（一）-CSDN博客

实参传递给形参的时候，形参会单独创建⼀份临时空间来接收实参，对形参的修改不影响实参。如果我们想修改顺序表里的值，那必然得传它的地址。代码如下：

//初始化,注意传址
void SLInit(SL* ps)
{
	ps->arr = NULL;
	ps->capacity = ps->size = 0;

}

 2.3.2 销毁

这个函数也很简单，我们既然是动态申请的空间，就需要将其free掉。

函数实现：

//销毁
void SLDestroy(SL* ps)
{
	if (ps->arr)
	{
		free(ps->arr);
	}
	ps->arr = NULL;
	ps->capacity = ps->size = 0;
}

2.3.3 尾插

我们在尾插的时候，试想一下，如果空间不够，是不是就没位置插了，这个时候我们要重新开辟空间，并且，我们在初始化后，空间是0，肯定需要申请。所以这里我们需要一个函数来进行扩容：

//扩容
void SLCheckCapacity(SL* ps)
{
	assert(ps);
	//先判断空间是否足够，不够需要扩容

	if (ps->capacity == ps->size) //不够扩容
	{
		//申请空间
		//三目判断初始空间大小
		int NewCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SLDataType* tmp = (SLDataType*)realloc(ps->arr, NewCapacity * sizeof(SLDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(1);
		}
		ps->arr = tmp;
		ps->capacity = NewCapacity;
	}
}

首先我们用assert断言防止空指针，之后我们用到了if语句来判断空间是否足够，如果不够则进入if扩容。判断条件我们仔细想想，什么情况是空间不够，是不是当空间大小和有效数据个数相等时，就没法插入了，所以我们将这个作为判断条件。

扩容搞定后，我们就可以进行插入操作了，在尾插中，我们需要传入两个参数：一个是顺序表的地址，另一个是要插入的元素。

尾插其实很简单，我们只需要将最后的位置赋值为要插入的元素就可以了，最后别忘了既然插进去了一个元素，有效数据个数肯定要++。

//尾插
void SLPushBack(SL* ps, SLDataType x)
{
	SLCheckCapacity(ps);
	 //足够尾插
	ps->arr[ps->size++] = x;
	/*ps->arr[ps->size] = x;
	ps->size++;*/
	
}

2.3.4 头插

尾插我们直接在尾巴后面插入元素即可，头插意味着我们要在头部插入一个元素，那么我们就需要在头部为其留出位置，同时原有元素还不可以改变。有了位置再进行插入，思路清晰，直接上代码。

//头插
void SLPushFront(SL* ps, SLDataType x)
{
	SLCheckCapacity(ps);
	//整体挪动，再插入
	for (int i = ps->size; i > 0; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[0] = x;
	ps->size++;
}

这里注意，for循环遍历时，从后往前遍历，防止覆盖。

2.3.5 尾删

大家想想，怎么删，将最后一个元素置为-1？还是别的什么数字？其实我们根本不需要管最后一个元素，我们直接将size进行 – – 即可。因为不影响其它功能，所以我们不用考虑那么复杂。

//尾删
void SLPopBack(SL* ps)
{
	assert(ps);
	assert(ps->size);
	//删完数据，size--
	//ps->arr[ps->size - 1] = -1;要不要这行都可以
	ps->size--;
}

2.3.6 头删

头删也很简单，直接覆盖即可。

//头删
void SLPopFront(SL* ps)
{
	assert(ps);
	assert(ps->size);
	//直接覆盖即可
	for (int i = 1; i < ps->size; i++)
	{
		ps->arr[i - 1] = ps->arr[i];
	}
	ps->size--;
}

2.3.7 在指定位置插入

我们效仿头插遍历，为元素留位置，在指定位置插入也是如此。

//在指定位置插入
void SLInsert(SL* ps, int pos, SLDataType x)//注意pos是下标
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);
	SLCheckCapacity(ps);
	for (int i = ps->size; i > pos; i--)
	{
		ps->arr[i] = ps->arr[i - 1];//arr[pos+1]=arr[pos];
	}
	ps->arr[pos] = x;
	ps->size++;
}

2.3.8 在指定位置删除

同样是遍历，同样是覆盖，不多解释，直接上代码。

//在指定位置删除
void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	for (int i = pos; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];//arr[size-2]=arr[size-1]
	}
	ps->size--;
}

2.3.9 查找

其实查找也是遍历，我们可以发现，但凡我们弄清原理之后，顺序表还是蛮简单的。

//查找
int SLFind(SL* ps, SLDataType x)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == x)
		{
			return i;
		}
	}
	return -1;
}

 2.4 总代码

2.4.1 SeqList.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
//定义顺序表的结构

//#define N 100


//静态顺序表
//struct SeqList
//{
//	int arr[N];
//	int size;//有效数据个数
//};

//定义顺序表中的数据类型，可以随时修改int
typedef int SLDataType;

//动态
typedef struct SeqList
{
	SLDataType *arr;
	int size; //有效数据个数
	int capacity; //空间大小
}SL;

//typedef struct SeqList SL;

//初始化
void SLInit(SL* ps);
//销毁
void SLDestroy(SL* ps);
//打印
void SLPrint(SL* ps);
//扩容
void SLCheckCapacity(SL* ps);
//尾部插入删除 / 头部插入删除
void SLPushBack(SL* ps, SLDataType x);
void SLPushFront(SL* ps, SLDataType x);

void SLPopBack(SL* ps);
void SLPopFront(SL* ps);
//指定位置之前插入/删除数据
void SLInsert(SL* ps, int pos, SLDataType x);
void SLErase(SL* ps, int pos);
//查找
int SLFind(SL* ps, SLDataType x);

2.4.2 SeqList.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"SeqList.h"

//初始化,注意传址
void SLInit(SL* ps)
{
	ps->arr = NULL;
	ps->capacity = ps->size = 0;

}
//销毁
void SLDestroy(SL* ps)
{
	if (ps->arr)
	{
		free(ps->arr);
	}
	ps->arr = NULL;
	ps->capacity = ps->size = 0;
}
//打印
void SLPrint(SL* ps)
{
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->arr[i]);
	}
	printf("\n");
}
//扩容
void SLCheckCapacity(SL* ps)
{
	assert(ps);
	//先判断空间是否足够，不够需要扩容

	if (ps->capacity == ps->size) //不够扩容
	{
		//申请空间
		//三目判断初始空间大小
		int NewCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SLDataType* tmp = (SLDataType*)realloc(ps->arr, NewCapacity * sizeof(SLDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(1);
		}
		ps->arr = tmp;
		ps->capacity = NewCapacity;
	}
}
//尾插
void SLPushBack(SL* ps, SLDataType x)
{
	SLCheckCapacity(ps);
	 //足够尾插
	ps->arr[ps->size++] = x;
	/*ps->arr[ps->size] = x;
	ps->size++;*/
	
}
//头插
void SLPushFront(SL* ps, SLDataType x)
{
	SLCheckCapacity(ps);
	//整体挪动，再插入
	for (int i = ps->size; i > 0; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[0] = x;
	ps->size++;
}
//尾删
void SLPopBack(SL* ps)
{
	assert(ps);
	assert(ps->size);
	//删完数据，size--
	//ps->arr[ps->size - 1] = -1;要不要这行都可以
	ps->size--;
}
//头删
void SLPopFront(SL* ps)
{
	assert(ps);
	assert(ps->size);
	//直接覆盖即可
	for (int i = 1; i < ps->size; i++)
	{
		ps->arr[i - 1] = ps->arr[i];
	}
	ps->size--;
}
//在指定位置插入
void SLInsert(SL* ps, int pos, SLDataType x)//注意pos是下标
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);
	SLCheckCapacity(ps);
	for (int i = ps->size; i > pos; i--)
	{
		ps->arr[i] = ps->arr[i - 1];//arr[pos+1]=arr[pos];
	}
	ps->arr[pos] = x;
	ps->size++;
}
//在指定位置删除
void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	for (int i = pos; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];//arr[size-2]=arr[size-1]
	}
	ps->size--;
}
//查找
int SLFind(SL* ps, SLDataType x)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == x)
		{
			return i;
		}
	}
	return -1;
}

完