人工智能uu

这个屌丝很懒，什么也没留下！

热门标签

初阶数据结构——顺序表（详解）_初始化顺序表

作者：人工智能uu | 2024-08-04 05:52:36

踩

初始化顺序表

扩容顺序表 SLCheckCapacity

什么是数据结构？

数据结构，就是数据和结构

我们平常看到的各种页面，每个人的身份信息等等，这些都是数据

而结构，就是我们用不同的方式管理数据，看个例子：

我们看到百度热搜部分，数据以 1、2、3、4、5 的方式被管理了起来，这是一种结构

再比如我们去饭店吃饭，我们有时可能需要拿号等位置，因为饭店需要以这种方式管理顾客，才能防止场面过于混乱，这也是一种结构

而我们的数据在我们的电脑里也需要被管理起来，所以才有了数据结构

线性表

线性表里面包含了顺序表、链表、栈、队列等等，我们可以这么理解：

狗是一种动物，狗里面包含了哈士奇、藏獒、柴犬、阿拉斯加等等

线性表有一个很重要的特点：

线性表在逻辑结构上是连续的，是一条直线，在物理结构上不一定是连续的

怎么理解这句话呢？

比如数组，数组在内存上连续开辟了一块空间，地址是连续的，所以数组在逻辑和物理上都是连续的

再比如我们后面会学到的链表，如下图：

我们如上的每个数据都是结构体，每个结构体内部都存放着指向下一个元素的指针，通过这个指针我们就可以将数据像链条一样连接起来

这就是链表，在逻辑结构上像一条链子一样，是连续的。但是每个成员之间的地址不一定相邻，所以其在物理结构上就不是连续的

静态顺序表

静态顺序表与数组十分相似，只不过我们将其包装在一个结构体里面而已，如下：


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

我们静态顺序表里面封装了一个数组，一个 size 统计有效的数据个数

同时，我们用 #define 定义的数据 N 使静态顺序表变得更加灵活

但这样有一个小问题

如果我们后期要将顺序表中的 int 型数据全部转化成 char 型的话，我们该怎么改？一个一个改吗？效率太低了

这时我们可以考虑如下做法：


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

我们用 typedef 将 int 换成了 SLDataType，当我们后期需要转换顺序表中的类型的时候，我们只需将 typedef 内的 int 改成 char 就行了

这里对 size 简单说明一下：size 代表的是有效的个数，如果我想要将最尾端的数据删除的话，那么我只需要让 size 减 1 ，后续要遍历静态顺序表时，for 循环只需要执行 size 次就行了，而数据放在那里，后续有数据可以直接覆盖，对顺序表本身毫无影响

这里和动态顺序表相似，后续动态顺序表要执行尾删操作的时候，和如上是同一个原理

但是

静态顺序表有一个非常不好的点在于，你输入了一个值之后，顺序表的大小就固定了，如果发现大小不够也只能停止程序之后，人工修改，因为这个缺点，我们就有了动态顺序表

动态顺序表

动态顺序表结构


typedef int SLDataType;
 
typedef struct SeqList
{
	SLDataType* arr; //动态管理
	int capacity;    //顺序表总容量
	int size;        //有效数据个数
}SL;

如上，我们动态顺序表的数组并不是数组，而是一个指针

这时因为我们动态顺序表的空间是在堆区上开辟的，也就是 malloc、calloc、realloc 等，对动态内存管理相关知识不太熟悉或是想深入了解的，可以点击下方博客链接：

C语言——动态内存管理

我们用 malloc 申请了一块空间之后，当顺序表不够大时，我们可以用 realloc 再进行扩容操作

同时，我们还定义了 capacity（容量）来代表顺序表的总大小，以及 size 来表示有效的数据个数

考虑到每次写该结构体都要写 struct SeqList，太麻烦了，所以我们就使用 typedef 将 struct SeqList 改成 SL


//写法一
typedef struct SeqList
{
	SLDataType* arr;
	int capacity;
	int size;
}SL;
 
//写法二
typedef struct SeqList SL;

如上两种写法起到的是相同的效果，在这里更推荐方法一，因为更为方便

初始化、销毁、打印顺序表

初始化顺序表 SLInit

我们需在 SeqList.h 文件中先定义函数


//SeqList.h
void SLInit(SL* ps);//初始化

然后在 SeqList.c 文件中实现具体操作

注：指针 ps 指向的是顺序表的头部


void SLInit(SL* ps) 
{
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}

销毁顺序表 SLDestroy

SeqList.h

void SLDestroy(SL* ps);//销毁

SeqList.c


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

如上，我们首先将传过来的指针 assert 断言了一下，确保顺序表存在

然后我们将 ps 指向的动态空间直接 free 掉，这里判断了一下，确保顺序表不为空

最后将指向顺序表的指针置为 NULL，并将 size 与 capacity 同时置为 0

如此，我们就完成了顺序表的销毁

打印顺序表 SLPrint

SeqList.h

void SLPrint(SL* ps);

SeqList.c


void SLPrint(SL* ps)
{
    assert(ps);
 
    //遍历顺序表
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->arr[i]);
	}
    //打印完之后换行，确保下次打印时
    //数据出现在下一行
	printf("\n");
}

如上，先断言确保顺序表存在

要打印顺序表我们使用一个 for 循环就可以了，这里需要注意的一个点是，因为我们传的是指针，使用这里用到的是箭头操作符（->）而非点操作符（.）来找arr对应的数据

扩容顺序表 SLCheckCapacity

SeqList.h

void SLCheckCapacity(SL* ps);

SeqList.c


typedef int SLDataType;
 
void SLCheckCapacity(SL* ps) 
{
    //当顺序表满了时
	if (ps->size == ps->capacity) 
	{
		int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));
		if (tmp == NULL) 
		{
			perror("realloc fail!");
			return 1;
		}
		//扩容成功
		ps->arr = tmp;
		ps->capacity = newCapacity;
	}
}

如上，我们这个函数的作用是检测顺序表是否满了

我们检测的条件就是：当 size（有效数据个数）等于 capacity（顺序表总容量）时，我们就进入 if 内部，即，能进入 if 内部就代表着顺序表已经满了，这时我们就需要扩容

接着，我们可以使用 realloc 进行扩容，但是，我们不清楚，size 与 capacity 是因为同等与 0 还是同等与开辟的空间，这时我们就可以定义一个 newCapacity 作为 realloc 要开辟的个数

同时我们可以使用三目操作符，如果 size 与 capacity 同等于 0，我们就返回 4，让 realloc 开辟 4 个字节的空间，至少保证了顺序表不为空

如果 size 与 capacity 不同等于 0，那么我们就让 newCapacity 等于原来 capacity 的两倍，因为每次开辟两倍于原空间能实现效率最大化

或许我们这样子看这句话会更容易理解一点：

int newCapacity = ( (ps->capacity == 0) ? 4 : (2 * ps->capacity) );

接着，既然顺序表满了，那么我们自然需要 realloc 扩容一下，扩容的字节数就是 newCapacity 个 int 的大小，扩容完之后，我们就判断一下防止开辟失败导致返回的是一个空指针（NULL）


SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));
if (tmp == NULL) 
{
	perror("realloc fail!");
	exit(1);
}

最后，将 capacity 改为 newCapacity，并让我们定义的顺序表里的 arr 指针指向新扩容出来的空间

头部插入删除/尾部插入删除

顺序表的头插 SLPushFront

SeqList.h

void SLPushFront(SL* ps, SLDataType x);

SeqList.c


void SLPushFront(SL* ps, SLDataType x) 
{
	assert(ps);
 
	//判断是否扩容
	SLCheckCapacity(ps);
 
	//旧数据往后挪动一位
	//从后开始挪
	for (int i = ps->size; i > 0; i--) 
	{
		//后移一位
		ps->arr[i] = ps->arr[i - 1]; 
	}
	//头部放上要插入的数据
	ps->arr[0] = x;
	//有效数据需要增加
	ps->size++;
}

首先，我们先用 assert 断言一下，避免顺序表不存在的情况，同时用我们上面写的 SLCheckCapacity 函数检测一下顺序表是否已经满了，如果满了的话我们就没法再往顺序表里插入数据了

重点来了，由于我们需要的是头插，也就是在顺序表最前面插入数据，但是最前面已经有数据了，所以我们需要将所有数据向后移一位，然后再在头部的位置插入我们传到函数的数据

但是，我们应该从头往后挪还是从后往前挪呢？

如果我们从前往后挪的话，那么就是如下代码：


for (int i = 0; i > ps->size; i++) 
{
	//后移一位
	ps->arr[i] = ps->arr[i - 1]; 
}

那么就会出现这样的情况：（第一个后移一位）

第二个后移一位（此时第二个已经变成了 1 ）：

......

最后会变成现在这个样子，第一个位置还有数据，是因为我们用第一个的数据覆盖了第二个数据，从而实现了向后移一位的效果

既然从前往后不行，那我们就从后往前


for (int i = ps->size; i > 0; i--) 
{
	//后移一位
	ps->arr[i] = ps->arr[i - 1]; 
}

效果如下：

......

我们会发现，从后往前是可以的，对于第一个位置的数据，我们只需要将传过来的参数 X 覆盖在上面就行了

ps->arr[0] = x;

最后让 size++ 一下，我们的头插操作就完成了

顺序表的尾插 SLPushBack

SeqList.h

void SLPushBack(SL * ps, SLDataType x);

SeqList.c


void SLPushBack(SL* ps, SLDataType x) 
{
	assert(ps);
 
	//空间不够，扩容
	SLCheckCapacity(ps);
 
	//空间足够，直接插入
	ps->arr[ps->size++] = x;
 
}

尾插比起头插就会简单得多

我们还是先 assert 断言，随后检查顺序表容量是否足够

如果后面有空余的位置的话，我们就直接在尾部插入数据就行了，并不涉及到数据的迁移

最后再加 size++ 一下

但是这里我们可以做一点小小的改装，在插入数据时就将 size 后置 ++，当数据插入成功时，size 的大小也起到了 ++ 的效果


//方法一
ps->arr[ps->size] = x;
ps->size++;
 
//方法二
ps->arr[ps->size++] = x;

顺序表的头删 SLPopFront

SeqList.h

void SLPopFront(SL* ps);

SeqList.c


void SLPopFront(SL* ps) 
{
	assert(ps && ps->size);
 
	//挪动
	for (int i = 0; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}

在执行头删操作之前，我们需要 assert 断言一下

但是我们这次断言的不止是传过来的指针，我们还需要断言一下顺序表的有效数据的个数，如果没有数据我们怎么头删？

因为是头删，所以接下来的就是挪动数据了，我们只需要将所有的数据往前挪一位，把前面的数据覆盖住，而对于最后一位数据，我们只需要让 size-- 就能实现把尾部数据删除的效果

这也是尾删的核心思想

因为那个数据放着就放着，后期我们遍历顺序表也只会遍历 szie 次，而有数据要插入的话我们可以直接将该数据覆盖，所以该数据的存在与否对顺序表并不影响

对于挪动数据

从头到尾地挪是不对的，这样子会把前面的数据覆盖住，而下一个要往前挪动的数据已经被覆盖了，所以会出错，具体的可以看看上方顺序表的头插 SLPushFront 相关实现

所以我们这里选择从前往后挪动数据


for (int i = 0; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}

顺序表的尾删 SLPopBack

SeqList.h

void SLPopBack(SL* ps);

SeqList.c


void SLPopBack(SL* ps) 
{
	assert(ps);
	assert(ps->size);
 
	//顺序表不为空
	ps->size--;
}

尾删部分的原理在头删处讲得足够清楚了，这里就不再过多赘述

指定位置之前插入数据 SLInsert

SeqList.h

void SLInsert(SL* ps, int pos, SLDataType x);

SeqList.c


void SLInsert(SL* ps, int pos, SLDataType x) 
{
	assert(ps && pos >= 0 && pos <= ps->size);
 
	SLCheckCapacity(ps);
 
	//pos及之后的数据往后挪动一位
	for (int i = ps->size; i > pos; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[pos] = x;
	ps->size++;
}

我们先 assert 断言，要保证的是指针 ps（确保顺序表存在）以及要插入的位置在 size 的有效范围之内，接着就判断一下顺序表是否满了，毕竟我们是要插入数据

指定位置之前插入数据的核心思想与头插极为相似

如果要头插，就需要从头开始挪动数据（从后往前挪），每个向后挪一位，将第一个的位置空出来，随后用要插入的数据将第一个位置的数据覆盖，进而实现头插

而指定位置之前插入数据的核心思想就是，将指定位置及之后的数据往后挪一位，将指定位置给空出来，然后将要插入的数据放如指定位置


for (int i = ps->size; i > pos; i--)
{
	ps->arr[i] = ps->arr[i - 1];
}

如下，假如我们现在要在 4 之前插入一个 9 ：

......

移动完并插入数据之后，我们还需要让 size++ 一下

ps->size++;

删除指定位置数据 SLErase

SeqList.h

void SLErase(SL* ps, int pos);

SeqList.c


void SLErase(SL* ps, int pos) 
{
	assert(ps && pos >= 0 && pos < ps->size);
 
	//pos以后的数据往前挪动一位
	for (int i = pos; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}

和指定位置之前插入数据一样，先 assert 断言指针 ps 以及要插入的位置在 size 的有效范围之内

删除指定位置数据的核心思想和头删也是极为相似

头删是将除第一个数据以外的所有数据往前挪动一位，最后 size-- 相当于尾删

而我们的删除指定位置数据，就是将指定位置之后的数据（不包括指定位置的数据）往前挪一位，将指定位置数据覆盖住，以达到删除的效果

如下，假设我们要将数据 4 给删除：

在顺序表中查找X SLFind

SeqList.h

int SLFind(SL* ps, SLDataType x);

SeqList.c


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;
}

我们要在顺序表中查找数据 X，首先先 assert 断言指针 ps 以确保顺序表存在

然后我们遍历顺序表就行了，如果有相同的，就返回下标

如果能走出 for 循环，那就证明并没有数据 X，那我们返回 -1 就行了

顺序表总代码

今天顺序表的全部代码都会放在下面链接中，有需要的可以点开来看看

顺序表代码 gitee

结语

至此，我们初阶数据结构里，顺序表的相关知识就讲完啦

接下来会给大家带来顺序表的应用——通讯录的相关讲解

如果能给你带来帮助的话，希望能多多支持！！！

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/人工智能uu/article/detail/926419