亲宝软件园·资讯

展开

C语言数据结构顺序表增删改

乔乔家的龙龙 人气:0

头插操作

继上一章内容(C语言数据结构顺序表中的增删改教程示例详解),继续讲讲顺序表的基础操作。

和尾插不一样,尾插出手阔绰直接的开空间,咱头插能开吗?好像没听说过哪个接口可以在数据前面开一片空间吧,那我们思路就只有一个了——挪数据。那应该从第一位开始挪吗?注意,这和 memcpy 函数机制是一样的,并不意味着后面数据一起挪动,也不会彼此独立,而是相互影响,挪动的数据会对后面数据进行覆盖。

在这里插入图片描述

那我们的逻辑就应该是从后往前挪,那我们就直接定一个下标,指向这段空间的最后一个位置即可,再利用香香 while 循环一手:

void pushfront(st* s, type x)
{
	assert(s);
	int end = s->size - 1;
	while (end >= 0)
	{
		s->a[end + 1] = s->a[end];//将从后往前的数据都向后挪一位
		end--;
	}
	s->a[0] = x;
	s->size++;
}

我们的 end 下标不是指向 size ,而是size后面一位也就是我们初始的capacity,end = 0时处理的是第一位之后的数据,那么我们while循环时就应该循环到 end<0为止。挪完了就可以sei数据,最后不要忘了让size++。
结果如下:

在这里插入图片描述


我们如果对之前写尾插时的细节记得的话,我们是需要有扩容操作的,这么写过去写过来很难受啊,我们就直接做成接口直接调用岂不美哉?

void enough(st* s)
{
	if (s->size == s->capacity)
	{
		s->capacity *= 2;
		s->a = (type*)realloc(s->a, sizeof(type) * s->capacity);
		if (s->a == NULL)
		{
			printf("扩容失败\n");
			exit(0);
		}
	}
}

头删操作

一样的,在头删操作时不仅要像尾删一样置0,还得把数据挪回去,注意是从前往后挪,不然数据又会被覆盖,最后size–一下就搞定:

void popfront(st* s)
{
	assert(s);
	enough(s);
	int head = 0;
	while (head < s->size - 1)
	{
		s->a[head] = s->a[head + 1]; //从前往后的数据依次向前挪一位
		head++;
	}
	s->size--;
}

结果如下:

在这里插入图片描述

小结

综上所述,顺序表其实就是在数组的基础上保留了一个特性——数据是连续的,但又摆脱了数组固定大小的限制,他适应性超强,随插随删随改。

但是顺序表不是十全十美,我们数据量足够庞大,比如已有一万条数据的空间,我要插入一万零一条,增容就会增到两万,空间浪费率极高。另外,尾插尾删操作是很快的,直接放入拿走数据,这是顺序表最常见的操作,这是他的特长。

但是话说回来,头插头删也很快吗?显然不是,头插头删的时间复杂度是O(n), 代价全在数据挪动上,所以如果要想不挪动的话,就要涉及到链表的引入。但链表在二分查找,排序等方面都有致命缺陷,他不能随机访问,所以链表和顺序表是相辅相成的。

今天就先到这里吧,摸了家人们,更多关于C语言数据结构顺序表增删改的资料请关注其它相关文章!

加载全部内容

相关教程
猜你喜欢
用户评论