数据结构-顺序表学习

最新推荐文章于 2025-01-07 20:24:34 发布

zyjyyds113

最新推荐文章于 2025-01-07 20:24:34 发布

阅读量101 数据结构学习文章标签：数据结构 c语言

本文链接：https://blog.csdn.net/m0_69550216/article/details/131078831

数据结构学习专栏收录该内容

2 篇文章 0 订阅

二、接口定义：

静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致 N定大了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实现动态顺序表。

接口定义：

void SepListInit(SL* ps);					 //初始化
void SepListCheckCapacity(SL* ps);			 //检查空间是否充足，不够进行扩容
void SepListprint(SL* ps);				     //顺序表遍历打印
void SepListDestory(SL* ps);				 //顺序表销毁，释放内存
void SepListPushBack(SL* ps, SLDataType x);  //尾插
void SepListPopBack(SL* ps);				 //尾删
void SepListPushFront(SL* ps, SLDataType x); //头插
void SepListPopFront(SL* ps);				 //头删

// 找到了 返回下标X 没有找到返回-1
int SepListFind(SL* ps, SLDataType x);
//指定pos下标位置插入
void SepListInsert(SL* ps, int pos, SLDataType x);
//指定pos下标位置删除
void SepListErase(SL* ps, int pos);

三、接口实现：

初始和遍历打印接口实现：

void SepListprint(SL* ps)
{
	//for遍历打印
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->a[i]);
	}
	printf("\n");
}

void SepListInit(SL* ps)
{
	//初始化空间
	ps->capacity = 0;
	ps->a = NULL;
	ps->size = 0;
}

空间大小检查和扩容接口实现：

void SepListCheckCapacity(SL* ps)//检查空间是否充足，不够进行扩容
{
	//如果没有空间或者空间不足，那就扩容
	if (ps->size == ps->capacity)
	{
		int newcapcity = ps->capacity == 0 ? 4 : ps->capacity * 2;  //不够每次扩容两倍
		SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapcity * sizeof(SLDataType));
		if (NULL == tmp)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newcapcity;
	}
}

顺序表销毁接口实现：

void SepListDestory(SL* ps)
{
	free(ps->a);//free函数用来释放动态开辟的内存
	ps->a = NULL;//
	ps->capacity = ps->size = 0;
}

free函数使用细节：

free函数释放先前通过调用callloc、malloc或realloc分配的内存块(memblock)。释放的字节数等于分配块时请求的字节数(或在realloc的情况下重新分配)。如果memblock为NULL，指针被忽略，free立即返回。试图释放无效指针(指向未由calloc、malloc或realloc分配的内存块的指针)可能会影响后续的分配请求并导致错误。

头插、头删、尾插、尾删接口实现：

//头部插入
void SepListPushFront(SL* ps, SLDataType x)
{
	//步骤一：检查空间大小，动态开辟空间
	SepListCheckCapacity(ps);
	int end = ps->size - 1;
	//步骤二：现有数据向后移动一位
	while (end >= 0) {
		ps->a[end + 1] = ps->a[end];
		--end;
	}
	//步骤三：用新的数据覆盖头部第一位数据
	ps->a[0] = x;
	//步骤四：顺序表存储数据大小加一
	ps->size++;
}
//头部删除
void SepListPopFront(SL* ps)
{
	//步骤一：检查空间大小是否有数据
	assert(ps -> size>0);
	//步骤二：现有数据向前移动一位，头部第一位被覆盖掉
	int end = 0;
	while (end!=ps->size-1) {
		ps->a[end] = ps->a[end + 1];
		end++;
	}
	//步骤三：顺序表存储数据大小减一
	ps->size--;
}
//尾部插入数据
void SepListPushBack(SL* ps, SLDataType x)
{
	//步骤一：检查空间大小，动态开辟空间
	SepListCheckCapacity(ps);
	//步骤二：新的数据插入最后一位
	ps->a[ps->size] = x;
	//步骤三：顺序表存储数据大小加一
	ps->size++;
}
//尾部删除数据
void SepListPopBack(SL* ps)
{
	//步骤一：检查空间是否有数据
	//ps->a[ps->size - 1] = 0;
	if (ps->size != 0)
	{
		//步骤二：顺序表存储数据大小减一
		ps->size--;
	}

}

数据查询接口实现：

//找到x返回数据对应下标
int SepListFind(SL* ps, SLDataType x)
{
	//步骤一：遍历数据找到x
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->a[i] == x) {
			//步骤二：返回数据对应下标
			return i;
		}
	}
	//没有找到返回 - 1
	return -1;
}

找到指定pos下标位置插入接口实现：

//找到指定pos下标位置插入
void SepListInsert(SL* ps, int pos, SLDataType x)
{
	//步骤一：检查空间大小，动态开辟空间
	SepListCheckCapacity(ps);
	//步骤二：从尾部遍历数据，向后移动数据，找到指定pos下标
	int end = ps->size - 1;
	while (end!=pos)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	ps->a[end + 1] = ps->a[end];
	//步骤三：将x值覆盖指定pos下标上
	ps->a[pos] = x;
	//步骤四：顺序表存储数据大小加一
	ps->size++;
}

指定pos下标位置删除接口实现：

//指定pos下标位置删除
void SepListErase(SL* ps, int pos)
{
	//步骤一：检查空间大小是否有数据
	assert(ps->size > 0);
	int end = ps->size - 1;
	//步骤二：从指定pos下标开始，遍历数据，向前移动一位，覆盖pos下标数据
	while (end != pos)
	{
		ps->a[pos] = ps->a[pos+1];
		pos++;
	}
	//步骤三：顺序表存储数据大小减一
	ps->size--;
}