亲宝软件园·资讯

展开

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

乔乔家的龙龙 人气:0

初始化

在初步认识顺序表这一结构后,我们就可以继续深入探究
这是我之前在.h文件中创建的结构体

typedef int type;
typedef struct list
{
	type* a;
	int size;
	int capacity;
}st;

在处理顺序表结构时我们会用到的一些接口,处理其中的关系,其实本质上就是函数,这里我用复杂英文对应出来方便形成记忆。

void init(st *s);  //插入
void pushback( st* p, type x);//尾插
void popback(st* p); //尾删
void pushfront( st* p, type x); //头插
void popfront(st* p);   //头删
void insert(st* p, int n, type x);  //中间位置插入
void erase(st* p, int n);  //中间位置删处

我用 init 函数实现简单的初始化,首先会先把结构体成员传过来,注意再次强调区别形参和实参,传值调用肯定会报错滴,乖乖的换成指针,其实不论是不是传址调用,我们都可以搞成指针传过去,为了保险起见。
我们第一步肯定是开辟空间,先用 malloc 函数参上,当然,null 还玩个屁屁,为了先避免掉这种情况,我们就 if 意思一下,然后给初始有效位设为 0,初始容量设为 5。

void init(st *s)
{
	s->a = (type*)malloc(sizeof(type) * 4);
	if (s->a == NULL)
	{
		printf("申请内存失败!\n");
		exit(-1);
	}
	s->size = 0;
	s-> capacity = 1;
}

尾插

然后就开始pushback 尾插操作:

void pushback(st* s, type x)
{
	assert(s);//空指针判断
	s->a[s->size] = x;
	s->size++;
}

还是老规矩,assert 断言是否为空指针,再放行。往下就简单的,把x的值放入数组的size 位置上,让 size ++即可。

但是 malloc 这种的指针是指向独立不连续的空间,我们监视窗口观察也只能看到一个个不连续的值,所以还是要老老实实搞一个打印函数,和数组一样,直接遍历一下我们++过的size即可:

void print(st* s)
{
	assert(s);
	int i = 0;
	for(i = 0; i < s->size; i++)
	{
		printf("%d ", s->a[i]);
	}
}

结果如下:

在这里插入图片描述

格局打开

但是奇不奇怪,我 capacity 初始设定为 1,而我却尾插了两个数还没有报错,为什么捏?其实报错了一定是你越界了,但没有报错不代表你就没有越界,往往有些越界是检查不出来的,因为还没走到检查的点上;就好比咱卷了不一定成功但不卷就一定不会成功。
所以我们的逻辑就要进行更替:

	if (s->size >= s->capacity)
		s->capacity++; 

在assert 后加上 if 判断句,让容量随有效位及时更新,但是又有一个问题,当我数据量非常大时,我们使用一位开辟一位的方法让 capacity++ 非常频繁,但一下子开辟一大片空间有会浪费资源,到后面已有数据越多开辟越大浪费的越多怎么办呢?我们比较普遍的做法就是开辟 2 倍:

	if (s->size == s->capacity)
	{
		s->capacity *= 2;
		s->a = (type*)realloc(s->a, sizeof(type) * s->capacity);
	}

这里敏感的朋友应该张口就来realloc,realloc函数会对已有空间直接扩容,但不一定是原地扩容,后面有足够的空间就会原地扩容,但是不够就会找一块新的空间将数据拷贝过去再释放掉原来空间。上面代码将原来的空间给realloc,再增容到我要的空间,就能很好的满足我们的要求。

尾删

尾删没什么技术含量,和我们数组的思路一样

void popback(st* s)
{
	assert(s);
	s->size--;
}

结果如下:

在这里插入图片描述

以此类推,头插头删是一个道理,不做赘述,更多关于C语言数据结构顺序表增删改的资料请关注其它相关文章!

加载全部内容

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