• 数据结构 | 顺序表

    …

    🌳🌲🌱本文已收录至：数据结构 | C语言
    更多知识尽在此专栏中!
    道阻且长，行则将至
    欢迎标头

    文章目录

    🌳前言

    顺序表 本质上就是数组，这也表明 顺序表 的基本要求是存储空间要连续，并且元素必须是连续存储。除了数组外，我们还可以使用堆区上开辟的空间，这也是可以实现 顺序表 的，下面一起来看看怎么实现吧！
    这是9月15日的日落

    🌳正文

    🌲结构

    首先认识一下 顺序表 的基本结构

    typedef int SLDatatype;	//顺序表类型
typedef struct SeqListInfo	//基本结构
{
	SLDatatype* data;	//数据
	size_t size;	//实际有效数据数
	size_t capacity;	//容量
}SL;

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    可以看到 顺序表 数据类型使用了 typedef 重命名，这样做的好处是方便后续切换 顺序表 数据元素类型，比如现在存储的是 整型 ，后续想存 字符型 ，直接把 int 换成 float 就行了
    本文的 顺序表 是动态的 ，因此不需要预设大小，需要多少空间就申请多少就行了，顺序表 本质上是数组，因此 下标 size 是少不了的，size 代表有效元素数 ；为了方便扩容，还需要一个 容量值 capacity辅助 判断是否需要进行扩容。

    🌲初始化

    初始化的目的很简单

    1. 把顺序表指针 data 置空
    2. 将下标 size 归零
    3. 将容量 capacity 归零
        //注意：这里是ps就是指向顺序表s的指针
    //这里的代码位于初始化函数内部，当然后面的ps，都是这个意思
	ps->data = NULL;	//指针置空
	ps->size = ps->capacity = 0;	//数据、容量归零

    • 1
    • 2
    • 3
    • 4

    原因：刚开始都是 随机值 ，需要 规范 一下

    🌲销毁

    动态申请的空间位于堆区 ，本着 有借有还，再借不难 的原则，我们在使用完堆区空间后，要记得释放空间 ，养成一个良好习惯，避免出现 内存泄漏 的问题，关于动态内存管理的介绍可以点这里。

    	free(ps->data);	//直接释放顺序表数据域
	SeqListInit(ps);	//代码复用

    • 1
    • 2

    释放完空间后，原指针要置空，下标和容量要归零 ，这里直接调用前面的初始化函数就行(偷个懒)

    🌲打印

    打印的话，可以根据 size 写一个 for 循环，因为 size 代表有效存储元素个数，比如 size=3，那么依靠下标 0、1、2 就能打印所有元素。

    	size_t i = 0;	//定义一个同样类型的变量i
	//配合size进行打印
	for (i = 0; i < ps->size; i++)
		printf("%d ", ps->data[i]);	
		//ps->data[i]相当于我们熟悉的arr[i]
	printf("\n");	//全部输出结束后，可以换行

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    🌲尾插与尾删

    尾插尾删比较简单，这也是 顺序表 的优势之一。

    🌱尾插

    🪴容量检查

    尾插的话，直接在 顺序表 尾部，也就是 ps->data[ps->size] 处插入目标元素就行了，当然插入成功后 size+1 。值得一提的是，我们在 插入前要进行容量检查 ，判断已有的空间是否足够使用，如果不够，就向堆区申请扩容，至于扩多大，可以自己把握 ，当然我们第一次是肯定要扩的。

    可以看动图(第一次制作，不足还请多包涵)
    顺序表第一次扩容

    	if (ps->size == ps->capacity)
	{
		size_t newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;	//两倍扩容
		SLDatatype* tmp = (SLDatatype*)realloc(ps->data, sizeof(SLDatatype) * newcapacity);
		assert(tmp);	//断言，可能存在扩容失败的情况
		ps->data = tmp;
		ps->capacity = newcapacity;
	}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    🪴执行尾插

    检查容量结束后，就可以直接执行尾插程序了。
    顺序表尾插

    	decideCapacity(ps);	//判断是否需要扩容

	ps->data[ps->size++] = x;	//尾插成功

    • 1
    • 2
    • 3

    🌱尾删

    先说明一个概念：删除不是真删除，想办法让你碰不到待删除元素就行了 ，比如我们可以将 size-1 ，这样有效存储元素数量就会-1，在进行后续操作时，就找不到最后一个元素了。

    可以看下面的动图
    顺序表尾删

    下面是代码实现

    	assert(ps->size > 0);	//需要断言一下，如果顺序表本来一个元素都没有，是肯定删不了的
	ps->size--;	//有效数据-1，就是尾删

    • 1
    • 2

    注意： 一定要断言或进行特殊处理 ，不然会出错，size - 1 时，前置后置都一样

    🌲头插与头删

    头部操作会比尾部操作复杂一些，比如 头插需要把所有元素整体往后移动，头删需要把元素整体往前移动 ，当然头插前需要检查容量。

    🌱头插

    头插的容量检查和尾插一样，对 size 和 capacity 进行比较，相等就扩容。
    头插的步骤：

    1. 确定起点与终点
    2. 通过 while 循环使元素整体往后移动
    3. 在顺序表首位， ps->data[0] 处插入元素值

    其中第一点需要特别注意，起点是 ps->size ，而终点是 0处(不能为0) ，否则会发生越界行为；另一种组合方式为 ps->size-1 与 0处(可以为0) ，两种方法的移动实现不同，这里演示第一种方式。

    注意： 实际使用时创建一个 end 变量存储起点信息，避免原起点被改变

    顺序表头插

    	decideCapacity(ps);	//判断扩容

	//先把数据整体往后挪动，再头插
	size_t end = ps->size;
	while (end > 0)
	{
		ps->data[end] = ps->data[end - 1];
		end--;
	}
	ps->data[end] = x;
	ps->size++;

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    🌱头删

    顺序表 的头删基本逻辑与头插差不多，但头删是 将元素整体往前移动(覆盖) ，整体覆盖结束后，size-- 就行了，通俗来说跟尾删一样，真移动，假删除。

    注意： 这里也需要一个变量 begin 来记录起点位置，终点就是 ps->size-1
    顺序表头删

    
	//同头插原理一样，需要把数据整体往前挪动
	size_t begin = 0;
	while (begin < ps->size - 1)
	{
		ps->data[begin] = ps->data[begin + 1];
		begin++;
	}

	ps->size--;	//有效元素-1，就可以实现头删

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    注意： 凡是涉及删除的操作，都要 断言，防止 顺序表 为空的情况，同样的 前置后置++在这里的效果都一样
    头删gif动图中的终止条件有误，应该为 begin < ps->size-1，不会造成很大影响，提前说声抱歉，因为动图不太好改

    🌲任意位置插入与删除

    任意位置插入与删除就像是头插与头删的升级版，不过是多了一个参数 pos

    🌱插入

    头插是整体从后往前移动，任意位置插也是如此，不过任意位置插的结束条件不再是 0 ，而是 pos(不能等于 pos)，当 end 变量等于 pos 时，就可以停止移动了，此时将 ps->data[pos] 处赋为目标值，ps->size++ ，就完成了任意插，当然，插入前要先检查容量。
    顺序表任意插

    	assert(pos >= 0);
	assert((size_t)pos <= ps->size);
	decideCapacity(ps);	//判断容量

	//原理有点类似头插，不过终止条件依赖于pos
	size_t end = ps->size;
	while (end > (size_t)pos)
	{
		ps->data[end] = ps->data[end - 1];
		end--;
	}

	ps->data[pos] = x;
	ps->size++;

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

    注意： 对于传入的下标参数 pos，需要做断言检查 ，如果 pos 是非法的，就无法继续完成插入程序

    🌱删除

    任意位置删除与头删类似，都是将元素整体往前移动，不过起始变量 begin 变成了参数 pos，终止变量依旧可以使用 ps->size-1 ，任意位置删除就像是 “可控的头删” 。
    顺序表任意删

    	assert(pos >= 0);
	assert((size_t)pos < ps->size);

	//类似于头删
	size_t begin = (size_t)pos;
	while (begin < ps->size - 1)
	{
		ps->data[begin] = ps->data[begin + 1];
		begin++;
	}

	ps->size--;

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    注意： 删除前要判断参数 pos 是否合法，此时不需要判断 顺序表 为空的情况，因为 pos < ps->size 就已经可以排除这种情况了
    任意位置删除gif动图中的终止条件有误，应该为 begin == ps->size-1，不会造成很大影响，提前说声抱歉，因为动图不太好改

    🌲关于其他需要补充的点

    🌱查找

    查找功能就是 遍历+比较 ，类似于打印函数,不过加了一个比较而已，这个函数可以设置返回值，返回下标，如果没找到返回-1(没有-1这个下标)，这个比较简单，就不做动图展示了

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

	return -1;	//没有找到目标元素

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    🌱修改

    修改就是在调用查找的基础上进行操作，如果找到了目标元素，返回 对应下标 ，根据此下标直接修改值就可以了，这个也比较简单，可以自己试着实现一下吧！

    可以看出，在查找元素方面是 顺序表 的强项，提供下标，那么对应元素可以秒出结果

    🌱复用

    其实不难发现，任意位置插删与头尾插删有很多相似之处 ，并且 任意插删 包含 头尾插删 因此我们可以通过调用函数来节省代码量，在调用时，调好起始(终止)条件就行了

    比如，在头插中，调用任意插入函数，可以写成:

    SeqListInsert(ps, 0, x);	//可以使用任意位置插入，替代插入

    • 1

    其他函数调用可以自己去试试

    🌱断言

    为了确保发生某些隐藏事我们能知晓，可以常用 assert 断言函数。对于上面的所有功能函数，我们都可以在函数内部先写上一条断言语句，防止空指针的传入导致的程序崩溃。

    assert(ps);	//断言，防止空指针

    • 1

    🌲源码区

    是整个 顺序表 工程的源码，可以随意 review

    🌱功能声明头文件部分

    #define _CRT_SECURE_NO_WARNINGS 1
#include
#include
#include

typedef int SLDatatype;	//顺序表类型
typedef struct SeqListInfo	//基本结构
{
	SLDatatype* data;	//数据
	size_t size;	//实际有效数据数
	size_t capacity;	//容量
}SL;

void SeqListInit(SL* ps);	//顺序表初始化
void SeqListDestroy(SL* ps);	//销毁顺序表

void SeqListPrint(SL* ps);	//打印顺序表

void SeqListPushBack(SL* ps, SLDatatype x);		//尾插
void SeqListPopBack(SL* ps);	//尾删

void SeqListPushFront(SL* ps, SLDatatype x);		//头插
void SeqListPopFront(SL* ps);	//头删

void SeqListInsert(SL* ps, int pos, SLDatatype x);	//任意插
void SeqListErase(SL* ps, int pos);	//任意位置删除

int SeqListFind(SL* ps, SLDatatype x);	//查找元素

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28

    🌱功能实现源文件部分

    #define _CRT_SECURE_NO_WARNINGS 1	
#include"SeqList.h"

void SeqListInit(SL* ps)	//顺序表初始化
{
	assert(ps);
	ps->data = NULL;	//指针置空
	ps->size = ps->capacity = 0;	//数据、容量归零
}

void SeqListDestroy(SL* ps)	//销毁顺序表
{
	assert(ps);
	free(ps->data);	//直接释放顺序表数据域
	SeqListInit(ps);	//代码复用
}

void SeqListPrint(SL* ps)	//打印顺序表
{
	assert(ps);
	size_t i = 0;	//定义一个同样类型的变量i
	//配合size进行打印
	for (i = 0; i < ps->size; i++)
		printf("%d ", ps->data[i]);	//ps->data[i]相当于我们熟悉的arr[i]
	printf("\n");	//全部输出结束后，可以换行
}

void decideCapacity(SL* ps)	//判断容量
{
	assert(ps);
	if (ps->size == ps->capacity)
	{
		size_t newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;	//两倍扩容
		SLDatatype* tmp = (SLDatatype*)realloc(ps->data, sizeof(SLDatatype) * newcapacity);
		assert(tmp);	//断言，可能存在扩容失败的情况
		ps->data = tmp;
		ps->capacity = newcapacity;
	}
}
void SeqListPushBack(SL* ps, SLDatatype x)		//尾插
{
	assert(ps);
	decideCapacity(ps);	//判断是否需要扩容

	ps->data[ps->size++] = x;	//尾插成功
	//SeqListInsert(ps, ps->size, x);	//可以使用任意位置插入，替代插入
}

void SeqListPopBack(SL* ps)	//尾删
{
	assert(ps);
	assert(ps->size > 0);	//需要断言一下，如果顺序表本来一个元素都没有，是肯定删不了的
	ps->size--;	//有效数据-1，就是尾删
	//SeqListErase(ps, ps->size - 1);	//可以使用任意位置删除，替代删除
}

void SeqListPushFront(SL* ps, SLDatatype x)		//头插
{
	assert(ps);
	decideCapacity(ps);	//判断扩容

	//先把数据整体往后挪动，再头插
	size_t end = ps->size;
	while (end > 0)
	{
		ps->data[end] = ps->data[end - 1];
		end--;
	}
	ps->data[end] = x;
	ps->size++;
	//SeqListInsert(ps, 0, x);	//可以使用任意位置插入，替代插入
}

void SeqListPopFront(SL* ps)	//头删
{
	assert(ps);
	assert(ps->size > 0);

	//同头插原理一样，需要把数据整体往前挪动
	size_t begin = 0;
	while (begin < ps->size - 1)
	{
		ps->data[begin] = ps->data[begin + 1];
		begin++;
	}

	ps->size--;	//有效元素-1，就可以实现头删
	//SeqListErase(ps, 0);	//可以使用任意位置删除，替代删除
}

void SeqListInsert(SL* ps, int pos, SLDatatype x)	//任意插
{
	assert(ps);
	assert(pos >= 0);
	assert((size_t)pos <= ps->size);
	decideCapacity(ps);	//判断容量

	//原理有点类似头插，不过终止条件依赖于pos
	size_t end = ps->size;
	while (end > (size_t)pos)
	{
		ps->data[end] = ps->data[end - 1];
		end--;
	}

	ps->data[pos] = x;
	ps->size++;
}

void SeqListErase(SL* ps, int pos)	//任意位置删除
{
	assert(ps);
	assert(pos >= 0);
	assert((size_t)pos < ps->size);

	//类似于头删
	size_t begin = (size_t)pos;
	while (begin < ps->size - 1)
	{
		ps->data[begin] = ps->data[begin + 1];
		begin++;
	}

	ps->size--;
}

int SeqListFind(SL* ps, SLDatatype x)	//查找元素
{
	assert(ps);
	size_t i = 0;
	for (i = 0; i < ps->size; i++)
	{
		if (ps->data[i] == x)
			return i;
	}

	return -1;	//没有找到目标元素
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138

    🌱主函数调用源文件部分

    #define _CRT_SECURE_NO_WARNINGS 1	
#include"SeqList.h"

void menu()
{
	printf("*******************************\n");
	printf("******  0.退出   1.打印  ******\n");
	printf("******  2.尾插   3.尾删  ******\n");
	printf("******  4.头插   5.头删  ******\n");
	printf("******  6.任意插 7.任意删******\n");
	printf("******  8.按元素值插入   ******\n");
	printf("******  9.按元素值删除   ******\n");
	printf("*******************************\n");
}

int main()
{
	int input = 1;
	SL s;
	SeqListInit(&s);	//创建一个顺序表
	while (input)
	{
		int pos = 0;
		SLDatatype x = 0;
		SLDatatype y = 0;
		menu();
		printf("请选择:>");
		scanf("%d", &input);
		switch (input)
		{
		case 0:
			printf("退出顺序表!\n");
			SeqListDestroy(&s);
			break;
		case 1:
			SeqListPrint(&s);
			break;
		case 2:
			printf("请输入一个值:>");
			scanf("%d", &x);
			SeqListPushBack(&s, x);
			break;
		case 3:
			SeqListPopBack(&s);
			break;
		case 4:
			printf("请输入一个值:>");
			scanf("%d", &x);
			SeqListPushFront(&s, x);
			break;
		case 5:
			SeqListPopFront(&s);
			break;
		case 6:
			printf("请输入下标和目标值:>");
			scanf("%d %d", &pos, &x);
			SeqListInsert(&s, pos, x);
			break;
		case 7:
			printf("请输入下标:>");
			scanf("%d", &pos);
			SeqListErase(&s, pos);
			break;
		case 8:
			printf("请输入待插入元素值和目标值:>");
			scanf("%d %d", &y, &x);
			SeqListInsert(&s, SeqListFind(&s, y), x);
			break;
		case 9:
			printf("请输入待删除元素值:>");
			scanf("%d", &y);
			SeqListErase(&s, SeqListFind(&s, y));
			break;
		default :
			printf("选择错误，请重新选择!\n");
			break;
		}
	}
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80

    🌲OJ试题推荐

    这里给大家推荐几道相关OJ题(其实都跟数组有关)

    1. 27.移除元素
    2. 26.删除有序数组中的重复项
    3. 88.合并两个有序数组

    可以先试着做一下，相关题解博客后续会发布~

    相关题解文章已发布
    移除数组(多种解法)
    删除重复项和合并数组

    🌳总结

    以上就是关于 顺序表 的所有内容了，希望你再看完后能够有所收获，掌握数据结构中最简单的存储结构，慢慢来，万丈高楼平地起!

    如果你觉得本文写的还不错的话，期待留下一个小小的赞👍，你的支持是我分享的最大动力！

    如果本文有不足或错误的地方，随时欢迎指出，我会在第一时间改正
    星辰大海

    …

    相关文章推荐
    数据结构 | 时间复杂度与空间复杂度
    C语言进阶——动态内存管理
    C语言课设——通讯录

  • 相关阅读:
    React useMemo useCallback useEffect 的区别（保姆级教程）
    springboot+宿舍管理小程序 毕业设计-附源码171008
    Unity摄像机跟随
    开机启动应用
    数据库事务的ACID属性定义
    『Java安全』利用反射调用MimeLauncher.run()触发RCE
    Docker入门尝鲜
    计算机网络那些事之 MTU 篇 pt.2
    Java Controller层异常处理示例【含面试题】
    SaaSBase：什么是小裂变SCRM？
  • 原文地址：https://blog.csdn.net/weixin_61437787/article/details/127646275