数据结构——顺序表

2024-03-24 13:50:01
开发
17

【本节内容】

1、顺序表的概念及结构

1.1 线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。线性表是⼀种在实际中广泛使

用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串...

线性表在逻辑上是线性结构，也就说是连续的⼀条直线。但是在物理结构上并不⼀定是连续的，

线性表在物理上存储时，通常以数组和链式结构的形式存储。

案例：蔬菜分为绿叶类、瓜类、菌菇类。线性表指的是具有部分相同特性的一类数据结构的集合

2、顺序表分类

• 顺序表和数组的区别

◦ 顺序表的底层结构是数组，对数组的封装，实现了常用的增删改查等接口

• 顺序表分类

◦ 静态顺序表

概念：使用定长数组存储元素

静态顺序表缺陷：空间给少了不够用，给多了造成空间浪费

◦ 动态顺序表

3、动态顺序表的实现

在完成一个顺序表的代码撰写前，我们需要创建三个文件。

SeqList.h：存放所有函数声明

SeqList.c：存放所有函数

test.c：测试顺序表

3.1首先先创建我们的顺序表结构体：

//SeqList.h
typedef int SLDataType;//方便修改我们的数据类型
// 顺序表的动态存储
typedef struct SeqList
{
	SLDataType* arr; // 指向动态开辟的数组
	int size; // 有效数据个数
	int capicity; // 容量空间的大小
}SL;
// 基本增删查改接口

3.2然后在声明我们顺序表初始化的函数：

//SeqList.h
// 顺序表初始化
void SeqListInit(SL* psl);

编写顺序表初始化函数：

//SeqList.c
void SeqListInit(SL* psl, int capacity)
{
	assert(psl);//断言我们的结构体指针是否为空
	psl->arr = (SLDataType*)malloc(sizeof(SLDataType) * 4);//为数组开辟空间
	if (psl->arr == NULL)//判断我们是否成功为结构体的数组成功开辟空间
	{
		perror("malloc fail");
		return;
	}

	psl->capacity = 4;//先开辟4个容量大小空间
	psl->size = 0;//初始化有效数据个数一般为0
}

完成上述的代码编写后，我们可以做一个测试，看看是否初始化成功。

在调试窗口中，我们可以看见我们的顺序表初始化都已成功。

3.3检查是否需要扩容

数据的量是不定的，我们有可能会变多或者变少，那么我们对应的就需要对顺序表的空间进行检查，如果空间满了，那么我们就要进行扩容。

//SeqList.h
void CheckCapacity(SL* psl);

//SeqList.c
void CheckCapacity(SL* psl)
{
	assert(psl);//断言检查

	if (psl->size == psl->capacity)
	{
		SLDataType* temp = (SLDataType*)realloc(psl->arr, sizeof(SLDataType) * psl->capacity * 2);
		if (temp == NULL)//判断我们是否成功为结构体的数组成功开辟空间
		{
			perror("realloc fail");
			return;
		}

		psl->arr = temp;//将扩容后的空间给到结构体的数组里
		psl->capacity *= 2;//扩容两倍
	}
}

3.4顺序表的销毁

为了合理规划内存使用，在我们使用完顺序表后，需要销毁空间，从而达到合理利用内存的效果。

//SeqList.h
void SeqListDestory(SL* psl);

//SeqList.c
void SeqListDestory(SL* psl)
{
	assert(psl);//断言
	free(psl->arr);//释放结构体中数组的空间
	psl->arr = NULL;//将数组置为空
	psl->size = 0;//有效数据个数清零
	psl->capacity = 0;//容量空间的大小清零
}

3.5顺序表的数据打印

为了能更直观的展现顺序表中的数据，我们可以定义一个打印函数，打印顺序表中的数据。

//SeqList.h
void SeqListPrint(SL* psl);

//SeqList.c
void SeqListPrint(SL* psl)
{
	assert(psl);//断言
	for (int i = 0; i < psl->size; i++)
	{
		printf("%d ", psl->arr[i]);//逐个打印
	}
	printf("\n");
}

3.6顺序表的增删查改

3.6.1顺序表尾插

在顺序表的尾部插入数据。

//SeqList.h
void SeqListPushBack(SL* psl, SLDataType x);

//SeqList.c
void SeqListPushBack(SL* psl, SLDataType x)
{
	assert(psl);//断言
	CheckCapacity(psl);//先检查空间是否足够插入
	psl->arr[psl->size] = x;//插入到尾部
	psl->size++;//下一次插入点向后移一位
}

测试结果：

3.6.2 顺序表尾删

将顺序表尾部的数据删除。

//SeqList.h
void SeqListPopBack(SL* psl);

//SeqList.c
void SeqListPopBack(SL* psl)
{
	assert(psl);//断言
	assert(psl->size > 0);//断言
	psl->arr[psl->size - 1] = 0;//将尾部的数据删除
	psl->size--;//插入点向前移一位
}

测试结果：

3.6.3顺序表头插

在顺序的头部插入数据。

//SeqList.h
void SeqListPushFront(SL* psl, SLDataType x);

//SeqList.c
void SeqListPushFront(SL* psl, SLDataType x)
{
	assert(psl);
	CheckCapacity(psl);
	// 挪动数据
	int end = psl->size - 1;
	while (end >= 0)
	{
		psl->arr[end + 1] = psl->arr[end];
		end--;
	}
	psl->arr[0] = x;
	psl->size++;
}

测试结果：

3.6.4顺序表头删

在顺序表头部删除数据。

//SeqList.h
void SeqListPopFront(SL* psl);

//SeqList.c
void SeqListPopFront(SL* psl)
{
	assert(psl);//断言
	assert(psl->size > 0);//断言
	int start = 0;
	//挪动数据
	while (start < psl->size-1)
	{
		psl->arr[start] = psl->arr[start + 1];
		start++;
	}
	psl->size--;
}

测试结果：

3.6.5顺序表数据的插入

顺序表在pos位置插入x。

//SeqList.h
void SeqListInsert(SL* psl, int pos, SLDataType x);

//SeqList.c
void SeqListInsert(SL* psl, int pos, SLDataType x)
{
	assert(psl);//断言
	assert(0 <= pos && pos <= psl->size);//断言
	CheckCapacity(psl);//检查空间大小是否足够
	//挪动数据
	int end = psl->size - 1;
	while (end >= pos)
	{
		psl->arr[end + 1] = psl->arr[end];
		end--;
	}
	psl->arr[pos] = x;
	psl->size++;
}

代码测试：

3.6.6顺序表数据的删除

顺序表删除pos位置的值。

//SeqList.h
void SeqListErase(SL* psl, int pos);

//SeqList.c
void SeqListErase(SL* psl, int pos)
{
	assert(psl);//断言
	assert(0 <= pos && pos < psl->size);//断言
	int start = pos + 1;
	//挪动数据
	while (start < psl->size)
	{
		psl->arr[start - 1] = psl->arr[start];
		start++;
	}
	psl->size--;
}

代码测试：

3.6.7顺序表数据的查找

查找顺序表中的数据。

//SeqList.h
int SeqListFind(SL* psl, SLDataType x);

//SeqList.c
int SLFind(SL* psl, SLDataType x)
{
	assert(psl);//断言
	//搜索数据
	for (int i = 0; i < psl->size; i++)
	{
		if (psl->arr[i] == x)
		{
			return i;
		}
	}
	return -1;//找不到就返回-1
}

代码测试：

3.6.8顺序表数据的修改

修改顺序表中修改pos位置的数据。

//SeqList.h
void SeqListModify(SL* psl, int pos, SLDataType);

//SeqList.c
void SeqListModify(SL* psl, int pos, SLDataType x)
{
	assert(psl);//断言
	assert(0 <= pos && pos < psl->size);//断言
	psl->arr[pos] = x;//修改数据
}

代码测试：

PS：看到这里了，码字不易，给个一键三连鼓励一下吧！有不足或者错误之处欢迎在评论区指出！

原文地址:https://blog.csdn.net/CptGhost/article/details/136952300 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：https://www.suanlizi.com/kf/1771776461657739264.html 如若内容造成侵权/违法违规/事实不符，请联系《酸梨子》网邮箱：1419361763@qq.com进行投诉反馈，一经查实，立即删除！

阅读全部