数据结构之——(手撕)顺序表

这篇具有很好参考价值的文章主要介绍了数据结构之——(手撕)顺序表。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

本章会介绍的知识点如下图:

数据结构之——(手撕)顺序表,数据结构,c语言

 

 1: 顺序表的概念:顺序表是用一段物理地址连续的存储单元依次存储数据的线性结构,通常我们使用数组来表示,对数组进行增删查改。

                 顺序表的结构:逻辑结构与物理结构都是内存中一块连续开辟的空间,都是11对应的线性结构。

2: 顺序表的两种定义方式:静态的顺序表与动态的顺序表,一般情况下我们很少会用静态的顺序表,因为静态的顺序表会将空间固定,导致如果我们使用顺序表的时候可能会浪费很多的空间,也可能在我们增容的时候会出现空间不够的情况,这种情况下如果我们还是在继续使用的话那么数组将会越界这种情况是error的。

两种定义顺序表的方式代码如下

        静态的顺序表        

typedef int SqListDataType;//这里是给我们的顺序表元素的类型起个名字
//							 假设元素是其他类型我们就可以修改这里
//静态的
struct SqList1
{
	SqListDataType arr1[1000];//开辟了一个整形的数组
	int size;//用来记录顺序表当前使用了多少的空间
};

动态的顺序表:

        

struct SqList2
{
	SqListDataType* arr2;
	int size;
	int Capacity;//用来记录当前数组开辟了多少个空间
};

在这两种结构中通常我们是会选择动态的顺序表来管理数据的。

3:顺序表的接口实现:

我们最终选择这个定义的顺序表 

数据结构之——(手撕)顺序表,数据结构,c语言

        1:这个接口的定义是应为当我们在增加元素的时候我们所存储的元素会变多,总有一种情况下我们空间会慢,所以这时候我们就需要扩容,使用了realloc这个函数扩容有两种情况,一种是原地扩,一种是换个空间扩。不管怎么样我们都定义一个空间,用来存储新开辟的地址,让后在给ps

//检查容量的代码
void check_capacity(SqList* ps)
{
	assert(ps);
	//空间不够,扩容,一次扩两倍
	if (ps->Capacity == ps->size)
	{

		SqListDataType* tmp=(SqListDataType*)realloc(ps->arr, (ps->Capacity)* 2*sizeof(SqListDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		else
		{
			printf("扩容成功\n");
			ps->arr = tmp;
			ps->Capacity *= 2;
		}
	}
	
}

2:头插思路:先检查空间是否足够,在从后往前移动元素,将第一个位置出来,最后在添加元素即可。

void PushFrontSqList(SqList* ps, SqListDataType x)
{
	//先检查空间够不够,空间不够扩容
	check_capacity(ps);//先判断空间是否满了
	//先移动元素
	int end = ps->size - 1;
	while (end >= 0)
	{
		ps->arr[end + 1] = ps->arr[end];
		end--;
	}
	ps->arr[0] = x;
	ps->size++;
}

上述代码的意思如下图:

        数据结构之——(手撕)顺序表,数据结构,c语言

 3:尾插思路:这个挺简单的,我们只要在size位置插入即可,size在++即可,这里要注意的就是我们插入要以数组的下标。

代码:

void PushBackSqList(SqList* ps, SqListDataType x)
{
	assert(ps);
	check_capacity(ps);
	ps->arr[ps->size] = x;
	ps->size++;
	//SqListInsert(ps, ps->size, x);
}

 4:头删思路:我们首先得判断顺序表是否有元素,如果有的话才能进行删除,我们只需要遍历数组从前往后将后一个元素移动到前一个就行,这里需要注意的就是我们移动时位置的不同可能导致代码的不一样,而我的代码是从第一个开始所以我最后的位置因该是size-2处,然后size--就可以了。

代码:

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

5:尾删思路:这个挺简单的,首先还是得判断顺序表是否存在元素,如果有将size--就行了。

代码:

void PopBackSqList(SqList* ps)
{
	assert(ps);
	assert(ps->size > 0);
	ps->size--;
}

6:顺序表得查找思路:遍历数组就行了,如果存在则返回下标,如果不存在我们返回-1.

代码:

int FindSqList(SqList* ps, SqListDataType x)
{
    assert(ps);//防止ps没有意义
	//思路:遍历顺序表找
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == x)
		{
			return i;
		}
	}
	//未找到
	printf("未找到\n");
	return -1;
}

7:顺序表插入思路:在pos位置处插入一个元素,pos为下标,首先先我们得判断pos是否存在,如果存在我们先从前往后将元素向后移动,然后在pos位置处插入即可。

代码:

void SqListInsert(SqList* ps, int pos, SqListDataType x)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);
	check_capacity(ps);
	int end = ps->size - 1;
	while (end >= pos)
	{
		ps->arr[end + 1] = ps->arr[end];
		end--;
	}
	ps->arr[pos] = x;
	ps->size++;
}

图:数据结构之——(手撕)顺序表,数据结构,c语言

 8:顺序表的删除思路:先判断,pos是否在顺序表中,我们只要从前完后移动pos后面的元素即可,然后我们在把size--;

代码:

void SqListErase(SqList* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	int i = pos;
	for (i = pos; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}

9:顺序表的修改思路:先判断,pos是否在顺序表中,然后在根据数组随机访问的特点修改即可。

代码:

void ModifySqlist(SqList* ps, int pos, SqListDataType x)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	ps->arr[pos] = x;

}

10:打印:遍历数组即可

代码:

void SqListPrint(SqList* ps)
{
	assert(ps);
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->arr[i]);
	}
	printf("\n");
}

11:销毁顺序表这一步也不能省略,防止内存泄漏。

代码:

//销毁
void DestorySqList(SqList* ps)
{
	assert(ps);
	free(ps->arr);
	ps->arr = NULL;
	ps->Capacity = ps->size = 0;
}

以上就是顺序表的大致结构了。

通过上面我们可以发现:顺序表适合尾插,尾删,修改,这是因为顺序表随机访问的特点造成的。

        本章完,感谢大家的观看。

        数据结构之——(手撕)顺序表,数据结构,c语言文章来源地址https://www.toymoban.com/news/detail-665510.html

到了这里,关于数据结构之——(手撕)顺序表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构:手撕顺序表---顺序表增删查改寻找功能的实现

    顺序表作为数据结构的入门知识,整体知识较为简单,主要对动态内存开辟 结构体 指针有要求,其余难度较低 顺序表主要需要实现的有顺序表的增删查改和定向搜索销毁等,具体实现函数如下 要实现顺序表,就需要对顺序表进行定义,在c语言中通常使用结构体进行写入,

    2024年02月15日
    浏览(40)
  • 数据结构之手撕顺序表(讲解➕源代码)

            在本章之后,就要求大家对于指针、结构体、动态开辟等相关的知识要熟练的掌握,如果有小伙伴对上面相关的知识还不是很清晰,要先弄明白再过来接着学习哦!         那进入正题,在讲解顺序表之前,我们先来介绍线性表这个数据结构。         线

    2024年02月08日
    浏览(37)
  • 数据结构之队列详解(C语言手撕)

    🎉个人名片: 🐼作者简介:一名乐于分享在学习道路上收获的大二在校生 🙈个人主页🎉:GOTXX 🐼个人WeChat:ILXOXVJE 🐼本文由GOTXX原创,首发CSDN🎉🎉🎉 🐵系列专栏:零基础学习C语言----- 数据结构的学习之路----C++的学习之路 🐓每日一句:如果没有特别幸运,那就请特

    2024年03月10日
    浏览(66)
  • 数据结构之单链表详解(C语言手撕)

    ​ 🎉文章简介: 概念:链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的 从图片中可以看出,链表的每个节点都是一个结构体,该结构体中有一个存储数据的变量和一个指向下一节点的结构体指针; 在逻辑上

    2024年03月10日
    浏览(45)
  • 数据结构之栈详解(C语言手撕)

    🎉个人名片: 🐼作者简介:一名乐于分享在学习道路上收获的大二在校生 🙈个人主页🎉:GOTXX 🐼个人WeChat:ILXOXVJE 🐼本文由GOTXX原创,首发CSDN🎉🎉🎉 🐵系列专栏:零基础学习C语言----- 数据结构的学习之路----C++的学习之路 🐓每日一句:如果没有特别幸运,那就请特

    2024年03月19日
    浏览(48)
  • 追梦之旅【数据结构篇】——C语言手撕八大经典排序

        😎博客昵称:博客小梦 😊最喜欢的座右铭:全神贯注的上吧!!! 😊作者简介:一名热爱C/C++,算法等技术、喜爱运动、热爱K歌、敢于追梦的小博主! 😘博主小留言:哈喽! 😄各位CSDN的uu们,我是你的博客好友小梦,希望我的文章可以给您带来一定的帮助,话不

    2024年02月17日
    浏览(48)
  • 数据结构入门(C语言版)一篇文章教会你手撕八大排序

    排序 :所谓排序,就是使一串记录,按照其中的某个或某些的大小,递增或递减的排列起来的操作。 稳定性 :假定在待排序的记录序列中,存在多个具有相同的的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,r[i]=r[j],且r[i]在r[j]之前,而

    2024年02月01日
    浏览(65)
  • [数据结构 - C语言] 顺序表

    目录 1、线性表 2、顺序表 2.1 顺序表的概念 2.2 接口 3、接口实现 3.1 初始化 3.2 销毁 3.3 容量检测 3.4 打印数据 3.5 顺序表的头插 3.6 顺序表的尾插 3.7 顺序表的头删、尾删 3.8 顺序表查找 3.9 指定位置插入数据 线性表(linear list)是n个具有相同特性的数据元素的有限序列。 线性

    2023年04月21日
    浏览(36)
  • 数据结构——顺序表(C语言)

    1.线性表 (1).线性表是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构,常见的线性表:顺序表,链表,栈,队列,字符串... (2).线性表在逻辑上是线性结构,也就是说连续的一条直线。但是在物理结构上并不是一定是连续的,线性表

    2024年02月13日
    浏览(49)
  • 【数据结构<顺序表>】C语言

    线性表(linear list)是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构,常见的线性表:顺序表、链表、栈、队列、字符串… 线性表在逻辑上是线性结构,也就说是连续的一条直线。但是在物理结构上并不一定是连续的,线性表在物理上

    2024年02月05日
    浏览(41)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包