数据结构初阶之顺序表(C语言实现)

2023-12-28 20:28:08

在这里插入图片描述

🍏前言:

顺序表是数据结构里面很基础的一类,它是线性表的一种,其它线性表还有链表、栈和队列等,今天来和博主一起学习关于顺序表的知识吧。

🍏顺序表和数组的区别

顺序表,它分为两类:动态顺序表静态顺序表,这两个表的区别就是前者的空间不固定,是支持扩容的,后者的空间是固定的,但是两者的共同点空间都是连续的,动态顺序表的底层是动态数组,而静态顺序表的底层是数组。

  • 很明显我们经常用到的数据结构就是动态的顺序表,因为静态的顺序表空间固定,没什么实际的价值。
  • 还有一个区别就是,动态顺序表是基于动态数组的,但是它作为一个数据结构,提供了很多动态数组没有直接提供的功能,像增、删、查、改、创建和销毁、以及计算数组的大小这些基本的功能。

在这里插入图片描述

🍏动态顺序表的模拟实现

🍀动态顺序表的基本结构设计

#define DataTypeVector int
typedef struct my_vector
{
	int* a;//储存数据
	size_t size;//顺序表的数据大小
	size_t capacity;//顺序表的空间大小
}mv;

各种接口:

//初始化

mv* Init();

//头插
void push_front(mv* mv1, DataTypeVector x);

//头删
void pop_front(mv* mv1);

//尾插
void push_back(mv* mv1, DataTypeVector x);

//尾删
void pop_back(mv* mv1);

//插入--在某个位置之前
void insert(mv* mv1,size_t positon, DataTypeVector x);

//删除某个位置的元素
void erase(mv* mv1,size_t position);

//查找某个值,并返回它出现的位置,没有找到,返回-1;
int find(mv* mv1, DataTypeVector x);

//计算动态顺序表的大小
size_t Size(mv* mv1);

//销毁动态顺序表
void Destroy(mv** mv1);

//修改某个位置的值
void Modify(mv* mv1, size_t position, DataTypeVector x);

🍀动态顺序表的各种功能模拟实现

🐲 初始化(init)

返回值版本:

//初始化动态顺序表
//返回值版本
mv* Init()
{
	mv* mv1 = (mv*)malloc(sizeof(mv));
	if (mv1 == NULL)
	{
		printf("malloc Falied\n");
		exit(-1);
	}
	mv1->a = NULL;
	mv1->capacity = 0;
	mv1->size = 0;
	return mv1;
}

二级指针版本:

//二级指针版本,不带返回值
void Init(mv** mv1)
{
	assert(mv1);
	(*mv1) = (mv*)malloc(sizeof(mv));
	if ((*mv1) == NULL)
	{
		printf("malloc failed\n");
		exit(-1);
	}
	(*mv1)->a = NULL;
	(*mv1)->capacity = NULL;
	(*mv1)->size = NULL;
}

🐲 头插、头删

🚙 头插
//头插
void push_front(mv* mv1, DataTypeVector x)
{
	assert(mv1 != NULL);
	if ((mv1)->capacity == (mv1)->size)//判断是否需要扩容
	{
		(mv1)->capacity = (mv1)->capacity == 0 ? 4 : (mv1)->capacity * 2;
		DataTypeVector* tmp = NULL;
		tmp = (DataTypeVector*)realloc(mv1->a, sizeof(DataTypeVector) * mv1->capacity);
		if (tmp == NULL)
		{
			printf("realloc failed\n");
			exit(-1);
		}
		mv1->a = tmp;
	}

	//将所有值后移
	for (size_t i = mv1->size; i > 0; --i)
	{
		mv1->a[i] = mv1->a[i-1];
	}

	mv1->a[0] = x;
	++mv1->size;
}

在这里插入图片描述

🚙 头删
//头删
void pop_front(mv* mv1)
{
	assert(mv1 != NULL);
	assert(mv1->size > 0);

	//将后面的值依次覆盖前面的值
	for (size_t i = 0; i < mv1->size-1; ++i)
	{
		mv1->a[i] = mv1->a[i + 1];
	}

	--mv1->size;//别忘了数组的大小要减减
}

在这里插入图片描述

🐲 尾插、尾删

🚙 尾插
//尾插
void push_back(mv* mv1, DataTypeVector x)
{
	assert(mv1 != NULL);

	if ((mv1)->capacity == (mv1)->size)//判断是否需要扩容
	{
		(mv1)->capacity = (mv1)->capacity == 0 ? 4 : (mv1)->capacity * 2;
		DataTypeVector* tmp = NULL;
		tmp = (DataTypeVector*)realloc(mv1->a,sizeof(DataTypeVector) * mv1->capacity);
		if (tmp == NULL)
		{
			printf("realloc failed\n");
			exit(-1);
		}
		mv1->a = tmp;
	}
	mv1->a[mv1->size] = x;
	++mv1->size;
}

在这里插入图片描述

🚙 尾删
//尾删
void pop_back(mv* mv1)
{
	assert(mv1);
	assert(mv1->size > 0);
	--mv1->size;
}

在这里插入图片描述

🐲 计算动态顺序表的大小(size接口)

//计算动态线性表的大小
size_t Size(mv* mv1)
{
	assert(mv1);
	return mv1->size;
}

在这里插入图片描述

🐲 动态顺序表在特定位置插入(insert)

这里我们仿照C++STL库,只实现了在pos位置之前插入。
在这里插入图片描述

//插入--在某个位置之前
//插入--在某个位置之前
void insert(mv* mv1, size_t position,DataTypeVector x)
{
	assert(mv1 != NULL);
	assert(position < mv1->size);

	if ((mv1)->capacity == (mv1)->size)//判断是否需要扩容
	{
		(mv1)->capacity = (mv1)->capacity == 0 ? 4 : (mv1)->capacity * 2;
		DataTypeVector* tmp = NULL;
		tmp = (DataTypeVector*)realloc(mv1->a, sizeof(DataTypeVector) * mv1->capacity);
		if (tmp == NULL)
		{
			printf("calloc failed\n");
			exit(-1);
		}
		mv1->a = tmp;
	}

	//从下标size开始,把数据都往后挪动.
	
		for (size_t i = mv1->size; i > position; --i)
		{
			mv1->a[i] = mv1->a[i-1];
		}
	
	
	//最后把下标position位置赋值为x
	mv1->a[position] = x;
	//别忘了size
	++mv1->size;
}

在这里插入图片描述

🐲 动态顺序表在特定位置删除(erase)

//删除某个位置的元素
void erase(mv* mv1, size_t position)
{
	assert(mv1 != NULL);
	assert(position < mv1->size);

	for (size_t i = position; i < mv1->size-1; ++i)
	{
		mv1->a[i] = mv1->a[i + 1];
	}

	--mv1->size;
}

在这里插入图片描述

🐲 动态顺序表的查找

//查找某个值,并返回它出现的位置,没有找到,返回-1;
int find(mv* mv1,DataTypeVector x)
{
	assert(mv1 != NULL);

	for (size_t i = 0; i < mv1->size; ++i)
	{
		if (x == mv1->a[i])//找到直接返回下标i
			return i;
	}

	return -1;//没有找到返回-1
}

这里顺序表不一定是有序的,所以不能使用二分查找。

🐲 修改某个位置的值

void Modify(mv* mv1,size_t position,DataTypeVector x)
{
	assert(mv1);
	assert(position < mv1->size);

	mv1->a[position] = x;
}

🐲 动态顺序表的销毁

动态顺序表的底层就是动态数组,它是堆上开辟的,通常遵循一下原则:
1. 由谁申请就由谁释放。 这是一个约定俗成的说法,指的是谁(程序员)申请的内存,需要自己负责去释放,避免出现内存泄漏。
2.只能一次释放整个动态数组,而不能只释放一部分
只要我们遵循这两个原则,然后再对顺序表类型的成员进行置空和置零,就实现了动态线顺序表的销毁。

//销毁动态顺序表
void Destroy(mv** mv1)
{
	assert(mv1 != NULL);
	(*mv1)->capacity = (*mv1)->size = 0;
	free((*mv1)->a);//先销毁顺序表里面的成员
	(*mv1)->a = NULL;
	free(*mv1);//销毁整个顺序表
	*mv1 = NULL;
}

?? 总结

关于《数据结构初阶之顺序表(C语言实现)》这篇文章就讲解到这儿,感谢大家的支持,欢迎大家留言交流以及批评指正。接下来将为大家带来一篇《不一样的C语言之easyx库的使用》,敬请期待吧。下面是本篇博客的思维导图希望对您有所帮助。

在这里插入图片描述

文章来源:https://blog.csdn.net/wszhj_/article/details/135251595
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。