• 首页 首页 icon
  • 工具库 工具库 icon
    • IP查询 IP查询 icon
  • 内容库 内容库 icon
    • 快讯库 快讯库 icon
    • 精品库 精品库 icon
    • 问答库 问答库 icon
  • 更多 更多 icon
    • 服务条款 服务条款 icon

数据结构 | 顺序表

武飞扬头像
北 海
帮助1

🌳🌲🌱本文已收录至:数据结构 | C语言
更多知识尽在此专栏中!

学新通
学新通


🌳前言

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


🌳正文

🌲结构

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

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

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

🌲初始化

初始化的目的很简单

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

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

🌲销毁

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

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

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

🌲打印

打印的话,可以根据 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");	//全部输出结束后,可以换行

🌲尾插与尾删

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

🌱尾插

🪴容量检查

尾插的话,直接在 顺序表 尾部,也就是 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;
	}
🪴执行尾插

检查容量结束后,就可以直接执行尾插程序了。
学新通

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

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

🌱尾删

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

可以看下面的动图
学新通

下面是代码实现

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

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

🌲头插与头删

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

🌱头插

头插的容量检查和尾插一样,对 sizecapacity 进行比较,相等就扩容。
头插的步骤:

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

其中第一点需要特别注意,起点是 ps->size ,而终点是 0处(不能为0) ,否则会发生越界行为;另一种组合方式为 ps->size-10处(可以为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  ;

🌱头删

顺序表 的头删基本逻辑与头插差不多,但头删是 将元素整体往前移动(覆盖) ,整体覆盖结束后,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,就可以实现头删

注意: 凡是涉及删除的操作,都要 断言,防止 顺序表 为空的情况,同样的 前置后置 在这里的效果都一样
头删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  ;

注意: 对于传入的下标参数 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--;

注意: 删除前要判断参数 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;	//没有找到目标元素

🌱修改

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

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

🌱复用

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

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

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

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

🌱断言

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

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

🌲源码区

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

🌱功能声明头文件部分

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>

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);	//查找元素
学新通

🌱功能实现源文件部分

#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;	//没有找到目标元素
}
学新通

🌱主函数调用源文件部分

#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;
}
学新通

🌲OJ试题推荐

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

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

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

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


🌳总结

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

如果本文有不足或错误的地方,随时欢迎指出,我会在第一时间改正
学新通

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

这篇好文章是转载于:学新通技术网

  • 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
  • 本站站名: 学新通技术网
  • 本文地址: /boutique/detail/tanhggfkbk
系列文章
更多 icon
同类精品
更多 icon
继续加载