Gausst松鼠会

这个屌丝很懒，什么也没留下！

热门标签

C语言【数据结构】顺序表（动态开辟）实现_c语言列表结构体开辟空间

作者：Gausst松鼠会 | 2024-04-30 14:45:48

踩

c语言列表结构体开辟空间

四.用Insert和Erase代替尾插尾删头插头删

顺序表OJ题练习：C语言【数据结构】顺序表【OJ题（C++）练习】_糖果雨滴a的博客-CSDN博客

前言：这是数据结构的开始，顺序表。现在已经开始学数据结构了，学数据结构最重要的3点是

①善于画图，多画图思考

②一定要细心

③勤加练习

好了，现在开始顺序表的学习了：

1.创建结构体

首先呢，要想创建一个顺序表，首先我们可以创建3个文件分别为SeqList.h, SeqList.c, Test.c

接下来我们就首先要创建一个结构体：


typedef int SLDataType
 
typedef struct SeqList
{
	SLDataType* a;//指向动态开辟的数组
	int size;//存储数据个数
	int capacity;//存储空间大小
}SeqList;

而在创建结构体的时候，我们会发现如果我们定义动态开辟的空间为int类型，那么我们只能存放int类型的数据，而想要修改，就必须把之后的int都修改一遍，很麻烦。因此我们可以用typedef用SLDataType作为数据类型。

2.初始化

创建顺序表首先要初始化。这里为什么用SeqList* psl，在3里详细说明。


void SeqListInit(SeqList* psl)
{
	assert(psl);
 
	psl->a = NULL;
	psl->size = 0;
	psl->capacity = 0;
}

3.尾插（需判断是否要扩容）

我们想要创建一个顺序表，那么就应该有增删查改。我们先来完成尾插。首先在Test.c创建一个main函数，然后可以用多个TestSeqList去测试写的对错。

然后呢，我们创建一个TestSeqList1，然后在里面定义结构体类型变量，SeqList s。接下来就创建尾插函数，并传参。然后再创建一个函数来打印顺序表，验证对错。

当我们实参为s的时候，我们会发现无论插入什么数，顺序表都为空，这是因为实参为s，而传过去的形参是临时创建的，出函数即销毁。因此我们应该传地址，即&s，这样实参和形参的地址一样，改形参的时候，实参也会被改，因此就可以输入数据了。

实现尾插很简单，只要通过当前size的值就可以，同时每插入一个，size++。但是我们应该注意扩容的问题，如果数据过多，需要扩容，而该扩容应该多次使用，因此我们可以创建SeqListCheckCapacity函数来判断是否需要扩容。


void SeqListCheckCapacity(SeqList* psl)
{
    assert(psl);
 
	if (psl->size == psl->capacity)
	{
		size_t newCapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
		SLDataType* tmp = realloc(psl->a, sizeof(SLDataType) * newCapacity);
 		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		else
		{
			psl->a = tmp;
			psl->capacity = newCapacity;
		}
	}
}


void SeqListsPushBack(SeqList* psl, SLDataType x)
{
	assert(psl);
 
	SeqListCheckCapacity(psl);
 
	psl->a[psl->size] = x;
	++psl->size;
}

assert(psl)是为了防止传过来空指针导致出错，而我们不知道在哪出错，有了assert传空指针时会告诉我们在哪出错，因此我们都应该加上assert断言。

4.尾删

尾删也很简单。每次让size--就行。要注意size > 0，否则会导致后面的插入出错。


void SeqListPopBack(SeqList* psl)
{
	assert(psl);
 
	if (psl->size > 0)
	{
		--psl->size;
	}
 
}

5.头插

头插和头删相对于尾插和尾删要复杂一些，并且尾插和尾删的时间复杂度为O(1)，而头插和头删的时间复杂度为O(N)。

我们想要头插一个数，可以先把原来其中的数向后依次挪动，然后再插入该数。


void SeqListPushFront(SeqList* psl, SLDataType x)
{
	assert(psl);
 
	SeqListCheckCapacity(psl);
 
	int end = psl->size - 1;
	while (end >= 0)
	{
		psl->a[end + 1] = psl->a[end];
		--end;
	}
	psl->a[0] = x;
	++psl->size;
}

6.头删

头删正好与头插相反，头删应该把数依次向前挪动，覆盖第一个数据。


void SeqListPopFront(SeqList* psl)
{
	assert(psl);
 
	int begin = 1;
	if(psl->size > 0)
	{ 
		while (begin < psl->size)
		{
			psl->a[begin - 1] = psl->a[begin];
			++begin;
		}
		--psl->size;
	}
}

7.插入

插入与头插类似，但是因为pos的存在，我们需要判断pos的值是否越界。

同时因为size_t的原因，我们要注意，不要让end变成负数，否则因为size的原因，会导致负数变成一个非常大的正数，导致出错。


void SeqListInsert(SeqList* psl, size_t pos, SLDataType x)
{
	assert(psl);
 
	if (pos > psl->size)
	{
		printf("pos 越界: %d\n", pos);
		return;
	}
 
	SeqListCheckCapacity(psl);
 
	size_t end = psl->size;
	while (end > pos)
	{
		psl->a[end] = psl->a[end - 1];
		end--;
	}
	psl->a[pos] = x;
	++psl->size;
}

8.删除

删除与头删类似。


void SeqListErase(SeqList* psl, size_t pos)
{
	assert(psl);
    assert(pos < psl->size);    
 
	size_t begin = pos + 1;
	while (begin < psl->size)
	{
		psl->a[begin - 1] = psl->a[begin];
		++begin;
	}
 
	--psl->size;
}

9.查找

这个很简单。


int SeqListFind(SeqList* psl, SLDataType x)
{
    assert(psl);
 
	for (int i = 0; i < psl->size; ++i)
	{
		if (psl->a[i] == x)
		{
			return i;
		}
	}
	return -1;
}

10.修改

也很简单。也要注意pos的值。


void SeqListModify(SeqList* psl, size_t pos, SLDataType x)
{
	assert(psl);
	assert(pos < psl->size);
 
	psl->a[pos] = x;
}

11.销毁

销毁顺序表，变为初始状态


void SeqListDestory(SeqList* psl)
{
	assert(psl);
 
	free(psl->a);
	psl->a = NULL;
	psl->size = 0;
	psl->capacity = 0;
}

12.打印

遍历打印即可


void SeqListPrint(SeqList* psl)
{
    assert(psl);
 
	for (int i = 0; i < psl->size; ++i)
	{
		printf("%d ", psl->a[i]);
	}
	printf("\n");
}

一.SeqList.h


#pragma once
 
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
 
typedef int SLDataType;
 
typedef struct SeqList
{
	SLDataType* a;
	int size;
	int capacity;
}SeqList;
 
void SeqListInit(SeqList* psl);
void SeqListDestory(SeqList* psl);
 
void SeqListPrint(SeqList* psl);
 
void SeqListCheckCapacity(SeqList* psl);
 
void SeqListsPushBack(SeqList* psl, SLDataType x);
void SeqListPopBack(SeqList* psl);
 
void SeqListPushFront(SeqList* psl, SLDataType x);
void SeqListPopFront(SeqList* psl);
 
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x);
 
void SeqListErase(SeqList* psl, size_t x);
 
int SeqListFind(SeqList* psl, SLDataType x);
 
void SeqListModify(SeqList* psl, size_t pos, SLDataType x);

二.SeqList.c


#include "SeqList.h"
 
void SeqListInit(SeqList* psl)
{
	assert(psl);
 
	psl->a = NULL;
	psl->size = 0;
	psl->capacity = 0;
}
 
void SeqListDestory(SeqList* psl)
{
	assert(psl);
 
	free(psl->a);
	psl->a = NULL;
	psl->size = 0;
	psl->capacity = 0;
}
 
void SeqListPrint(SeqList* psl)
{
    assert(psl);
 
	for (int i = 0; i < psl->size; ++i)
	{
		printf("%d ", psl->a[i]);
	}
	printf("\n");
}
 
void SeqListCheckCapacity(SeqList* psl)
{
    assert(psl);
 
	if (psl->size == psl->capacity)
	{
		size_t newCapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
		SLDataType* tmp = realloc(psl->a, sizeof(SLDataType) * newCapacity);
 		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		else
		{
			psl->a = tmp;
			psl->capacity = newCapacity;
		}
	}
}
 
void SeqListsPushBack(SeqList* psl, SLDataType x)
{
	assert(psl);
 
	SeqListCheckCapacity(psl);
 
	psl->a[psl->size] = x;
	++psl->size;
}
 
void SeqListPopBack(SeqList* psl)
{
	assert(psl);
 
	if (psl->size > 0)
	{
		--psl->size;
	}
}
 
void SeqListPushFront(SeqList* psl, SLDataType x)
{
	assert(psl);
 
	SeqListCheckCapacity(psl);
 
	int end = psl->size - 1;
	while (end >= 0)
	{
		psl->a[end + 1] = psl->a[end];
		--end;
	}
	psl->a[0] = x;
	++psl->size;
}
 
void SeqListPopFront(SeqList* psl)
{
	assert(psl);
 
	int begin = 1;
	if(psl->size > 0)
	{ 
		while (begin < psl->size)
		{
			psl->a[begin - 1] = psl->a[begin];
			++begin;
		}
		--psl->size;
	}
}
 
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x)
{
	assert(psl);
 
	if (pos > psl->size)
	{
		printf("pos 越界: %d\n", pos);
		return;
	}
 
	SeqListCheckCapacity(psl);
 
	size_t end = psl->size;
	while (end > pos)
	{
		psl->a[end] = psl->a[end - 1];
		end--;
	}
	psl->a[pos] = x;
	++psl->size;
}
 
void SeqListErase(SeqList* psl, size_t pos)
{
	assert(psl);
	assert(pos < psl->size);
 
	size_t begin = pos + 1;
	while (begin < psl->size)
	{
		psl->a[begin - 1] = psl->a[begin];
		++begin;
	}
 
	--psl->size;
}
 
int SeqListFind(SeqList* psl, SLDataType x)
{
    assert(psl);
    
	for (int i = 0; i < psl->size; ++i)
	{
		if (psl->a[i] == x)
		{
			return i;
		}
	}
	return -1;
}
 
void SeqListModify(SeqList* psl, size_t pos, SLDataType x)
{
	assert(psl);
	assert(pos < psl->size);
 
	psl->a[pos] = x;
}

三.Test.c


#include "SeqList.h"
 
TestSeqList1()
{
	SeqList s;
	SeqListInit(&s);
 
	SeqListsPushBack(&s, 1);
	SeqListsPushBack(&s, 2);
	SeqListsPushBack(&s, 3);
	SeqListsPushBack(&s, 4);
	SeqListsPushBack(&s, 5);
	SeqListsPushBack(&s, 0);
	SeqListPrint(&s);
 
	SeqListPopBack(&s);
	SeqListPopBack(&s);
	SeqListPopBack(&s);
	SeqListPopBack(&s);
	SeqListPopBack(&s);
	SeqListPopBack(&s);
	SeqListPopBack(&s);
	SeqListPrint(&s);
 
	SeqListsPushBack(&s, 10);
	SeqListsPushBack(&s, 20);
	SeqListPrint(&s);
 
	SeqListDestory(&s);
}
 
TestSeqList2()
{
	SeqList s;
	SeqListInit(&s);
 
	SeqListsPushBack(&s, 1);
	SeqListsPushBack(&s, 2);
	SeqListsPushBack(&s, 3);
	SeqListsPushBack(&s, 4);
	SeqListPrint(&s);
 
	SeqListPushFront(&s, 0);
	SeqListPushFront(&s, -1);
	SeqListPrint(&s);
 
	SeqListPopFront(&s);
	SeqListPopFront(&s);
	SeqListPopFront(&s);
	SeqListPopFront(&s);
	SeqListPopFront(&s);
	SeqListPopFront(&s);
	SeqListPopFront(&s);
	SeqListPopFront(&s);
	SeqListPushFront(&s, 10);
	SeqListPushFront(&s, 20);
	SeqListPrint(&s);
 
}
 
TestSeqList3()
{
	SeqList s;
	SeqListInit(&s);
 
	SeqListsPushBack(&s, 1);
	SeqListsPushBack(&s, 2);
	SeqListsPushBack(&s, 3);
	SeqListsPushBack(&s, 4);
	SeqListPrint(&s);
 
	SeqListInsert(&s, 4, 10);
	SeqListInsert(&s, 2, 20);
	SeqListInsert(&s, 0, 30);
	SeqListPrint(&s);
 
	SeqListErase(&s, 6);
	SeqListErase(&s, 0);
	SeqListErase(&s, 2);
	SeqListPrint(&s);
 
 
}
 
TestSeqList4()
{
	SeqList s;
	SeqListInit(&s);
 
	SeqListsPushBack(&s, 1);
	SeqListsPushBack(&s, 2);
	SeqListsPushBack(&s, 3);
	SeqListsPushBack(&s, 4);
	SeqListPrint(&s);
 
	int ret = SeqListFind(&s, 4);
	printf("%d", ret);
}
 
int main()
{
 
	TestSeqList1();
	TestSeqList2();
	TestSeqList3();
	TestSeqList4();
	return 0;
}

测试结果：

四.用Insert和Erase代替尾插尾删头插头删

最后，因为学了插入和删除，我们可以用它们代替尾插尾删头插头删。如下：


void SeqListsPushBack(SeqList* psl, SLDataType x)
{
	assert(psl);
 
	SeqListInsert(psl, psl->size, x);
}


void SeqListPopBack(SeqList* psl)
{
	assert(psl);
 
	SeqListErase(psl, psl->size - 1);
}


void SeqListPushFront(SeqList* psl, SLDataType x)
{
	assert(psl);
 
	SeqListInsert(psl, 0, x);
}


void SeqListPopFront(SeqList* psl)
{
	assert(psl);
 
	SeqListErase(psl, 0);
}

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Gausst松鼠会/article/detail/513855

C语言【数据结构】顺序表（动态开辟）实现_c语言 列表结构体 开辟空间

1.创建结构体

2.初始化

3.尾插（需判断是否要扩容）

4.尾删

5.头插

6.头删

7.插入

8.删除

9.查找

10.修改

11.销毁

12.打印

一.SeqList.h

二.SeqList.c

三.Test.c

四.用Insert和Erase代替尾插尾删头插头删

C语言【数据结构】顺序表（动态开辟）实现_c语言列表结构体开辟空间