当前位置： 首页 > article >正文

数据结构：详解【顺序表】的实现

article 2024/12/22 14:03:42

1. 顺序表的定义

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。动态顺序表与数组的本质区别是——根据需要动态的开辟空间大小。

2. 顺序表的功能

动态顺序表的功能一般有如下几个：

  • 初始化顺序表
  • 打印顺序表中的数据
  • 检查顺序表的容量
  • 顺序表头部插入数据
  • 顺序表尾部插入数据
  • 顺序表头部删除数据
  • 顺序表尾部删除数据
  • 顺序表任意位置插入数据
  • 顺序表任意位置删除数据
  • 顺序表中查找数据
  • 顺序表中修改指定位置数据
  • 顺序表的销毁

3.顺序表各功能的实现

3.1 创建顺序表

typedef int SQDateType;//对int进行重命名，可增加代码的普适性。

typedef struct SeqList
{
	SQDateType* a;
	size_t size; //有效数据
	size_t capacity;//容量的空间大小
}SL;//对这个结构体重命名为SL，书写方便

在这里插入图片描述

3.2 初始化顺序表
由于建立顺序表后并没有原始空间，所以我们自行动态开辟空间，又因为后续要进行扩容，所以我们必须初始化容量大小。

void SeqListInit(SL*ps)
{
	ps->a = (SQDateType*)malloc(sizeof(SQDateType) * 4);//初始化开辟4个int类型的空间
	//检查是否开辟成功
	if (ps->a == NULL)
	{
		printf("malloc fail!\n");
		return;
	}
	ps->capacity = 4;//初始化容量大小为4
	ps->size = 0;
}

3.3 打印顺序表中的数据
对顺序表进行增删查改等操作后，我们要把数据打印在控制台以便观察。

void SeqListPrint(SL* ps)
{
	//判断顺序表中是否有数据
	assert(ps->size > 0);
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->a[i]);
	}
	printf("\n");
}

3.4 检查顺序表的容量
对顺序表进行插入（增加）数据的操作时，我们必须先对顺序表进行容量的检查，若容量不够，则扩容。
并且扩容的幅度一般是原来容量的2倍。

void CheckSeqListCapacity(SL*ps)
{
	assert(ps);//断言
	//检查容量是否已满
	if (ps->capacity == ps->size)
	{
		//扩容
		SQDateType* tmp = (SQDateType*)realloc(ps->a, ps->capacity * 2 * sizeof(SQDateType*));
		if (tmp == NULL)
		{
			printf("realloc fail!\n");
			return;
		}
		else
		{
			ps->a = tmp;
			ps->capacity *= 2;//容量增大为原来的两倍
		}
	}
}

3.5 顺序表头部插入数据
头插，意思是在顺序表的最前面插入一个数据。我们需要把顺序表里的原数据（如果原来有数据的话）从后往前向后挪一个空间，再把要插入的数据放到第一个位置即可。
![在这里插入图片描述](https://img-blog.csdnimg.cn/direct/1b879d6df276406d8a11e8655d9e8cb0.png
代码实现如下：

void SeqListPushFront(SL* ps, SQDateType x)
{
     assert(ps);
	//检查是否要扩容
	CheckSeqListCapacity(ps);

	int end = ps->size;
	for (end = ps->size ; end >0; end--)
	{
		ps->a[end] = ps->a[end - 1];
	}
	ps->a[end] = x;
	ps->size++;//有效数据+1
}

3.6 顺序表尾部插入数据
尾插，意思是在顺序表的最后面插入一个数据。只需要找到该位置的下标（ps->size处)直接插入即可。
![在这里插入图片描述](https://img-blog.csdnimg.cn/direct/11372c84deae44a7b1dc038142252cc9.png

代码实现如下：

void SeqListPushBack(SL* ps, SQDateType x)
{
     assert(ps);
     //检查是否要扩容
	CheckSeqListCapacity(ps);

	ps->a[ps->size] = x;
	ps->size++;//有效数据+1
}

3.7 顺序表头部删除数据
头删，意思是删除一个顺序表最前面的数据。只需把原数据从前往后开始向前覆盖一个空间即可。
![在这里插入图片描述](https://img-blog.csdnimg.cn/direct/589b3cd1ddcc4189be625c3189619a32.png

代码实现如下：

void SeqListPopFront(SL* ps)
{
	assert(ps->size > 0);//断言，当顺序表内有数据时才删除
	
	for (int start = 0; start < ps->size; start++)
	{
		ps->a[start] = ps->a[start + 1];
	}
	ps->size--;//有效数据-1
}

3.8 顺序表尾部删除数据
尾删，直接删除顺序表中最后一个数据即可。

void SeqListPopBack(SL* ps)
{
	assert(ps->size > 0);
	ps->size--;//有效数据-1
}

3.9 顺序表任意位置插入数据
在顺序表的pos位置处插入一个数据，先要把pos处及其后面的原数据向后挪一个空间，再把数据放入pos处。
在这里插入图片描述
代码实现如下：

void SeqListInsert(SL* ps, int pos, SQDateType x)
{
	assert(ps && pos < ps->size);//pos<size时才满足
	CheckSeqListCapacity(ps);

	int end = ps->size ;
	for (end = ps->size ; end > pos; end--)
	{
		ps->a[end] = ps->a[end-1];
	}
	ps->a[pos] = x;//在pos的位置放入数据
	ps->size++;//有效数据+1
}

3.10 顺序表任意位置删除数据
在顺序表的pos位置处删除一个数据，只要把pos处后面的数据向前覆盖一个空间。
在这里插入图片描述
代码实现如下：

void SeqListEarse(SL* ps, int pos)
{
	assert(ps && pos < ps->size);//pos<size时才满足
	int start = pos;
	for (start = pos; start < ps->size; start++)
	{
		ps->a[start] = ps->a[start + 1];
	}
	ps->size--;//有效数据-1
}

3.11 顺序表中查找数据
把顺序表中的数据循环遍历，判断每个数据与查找数据是否相等，若相等，返回1，否则返回-1。

int  SeqListFind(SL* ps, SQDateType x)
{
	assert(ps && ps->size > 0);//表中有数据时才能查找
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->a[i] == x)
		{
			return 1;
			break;
		}
	}
	return -1;
}

3.12 顺序表中修改指定位置数据
只要在顺序表中找到指定位置，把修改的值赋给它即可。

void SeqListModify(SL* ps, int pos, SQDateType x)
{
	assert(ps && pos < ps->size);//要修改的位置要小于数据个数
	ps->a[pos] = x;
}

3.13 顺序表的销毁
顺序表的空间的动态开辟的，最后需要free释放空间，避免造成空间泄漏。

void SeqListDestory(SL* ps)
{
	free(ps->a);
	ps->a = NULL;
	ps->capacity = 0;
	ps->size = 0;
}

4. 完整代码

SeqList.h

#pragma once

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int SQDateType;

typedef struct SeqList
{
	SQDateType* a;
	size_t size; //有效数据
	size_t capacity;//容量的空间大小
}SL;

//初始化顺序表
void SeqListInit(SL* ps);

//头部插入数据
void SeqListPushFront(SL* ps, SQDateType x);

//尾部插入数据
void SeqListPushBack(SL* ps, SQDateType x);

//头部删除数据
void SeqListPopFront(SL* ps);

//尾部删除数据
void SeqListPopBack(SL* ps);

//任意位置插入数据
void SeqListInsert(SL* ps, int pos,SQDateType x);

//任意位置删除数据
void SeqListEarse(SL* ps, int pos);

//打印数据函数
void SeqListPrint(SL* ps);

//查找数据
int SeqListFind(SL* ps, SQDateType x);

//修改指定位置数据
void SeqListModify(SL* ps, int pos, SQDateType x);

//销毁顺序表
void SeqListDestory(SL* ps);

SeqList.c

#define _CRT_SECURE_NO_WARNINGS 

#include "SeqList.h"

void SeqListInit(SL*ps)
{
	ps->a = (SQDateType*)malloc(sizeof(SQDateType) * 4);//初始化开辟4个int类型的空间
	if (ps->a == NULL)
	{
		printf("malloc fail!\n");
		return;
	}
	ps->capacity = 4;
	ps->size = 0;
}

void CheckSeqListCapacity(SL*ps)
{
	assert(ps);
	//检查容量是否已满
	if (ps->capacity == ps->size)
	{
		//扩容
		SQDateType* tmp = (SQDateType*)realloc(ps->a, ps->capacity * 2 * sizeof(SQDateType*));
		if (tmp == NULL)
		{
			printf("realloc fail!\n");
			return;
		}
		else
		{
			ps->a = tmp;
			ps->capacity *= 2;
		}
	}
}


void SeqListPushFront(SL* ps, SQDateType x)
{
	assert(ps);
	CheckSeqListCapacity(ps);

	int end = ps->size;
	for (end = ps->size ; end >0; end--)
	{
		ps->a[end] = ps->a[end - 1];
	}
	ps->a[end] = x;
	ps->size++;
}

void SeqListPrint(SL* ps)
{
	//判断顺序表中是否有数据
	assert(ps->size > 0);
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->a[i]);
	}
	printf("\n");
}

void SeqListPushBack(SL* ps, SQDateType x)
{
	CheckSeqListCapacity(ps);

	ps->a[ps->size] = x;
	ps->size++;
}

void SeqListPopFront(SL* ps)
{
	assert(ps->size > 0);
	for (int start = 0; start < ps->size; start++)
	{
		ps->a[start] = ps->a[start + 1];
	}
	ps->size--;
}

void SeqListPopBack(SL* ps)
{
	assert(ps->size > 0);
	ps->size--;
}

void SeqListInsert(SL* ps, int pos, SQDateType x)
{
	assert(ps && pos < ps->size);
	CheckSeqListCapacity(ps);

	int end = ps->size ;
	for (end = ps->size ; end > pos; end--)
	{
		ps->a[end] = ps->a[end-1];
	}
	ps->a[pos] = x;
	ps->size++;
}

void SeqListEarse(SL* ps, int pos)
{
	assert(ps && pos < ps->size);
	int start = pos;
	for (start = pos; start < ps->size; start++)
	{
		ps->a[start] = ps->a[start + 1];
	}
	ps->size--;
}

int  SeqListFind(SL* ps, SQDateType x)
{
	assert(ps && ps->size > 0);
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->a[i] == x)
		{
			return 1;
			break;
		}
	}
	return -1;
}

void SeqListModify(SL* ps, int pos, SQDateType x)
{
	assert(ps && pos < ps->size);
	ps->a[pos] = x;
}

void SeqListDestory(SL* ps)
{
	free(ps->a);
	ps->a = NULL;
	ps->capacity = 0;
	ps->size = 0;
}

test.c

#define _CRT_SECURE_NO_WARNINGS 

#include "SeqList.h"

void SeqListTest()
{
	SL sl;
	
	//在这里调用各数据接口（函数）进行测试
}

int main()
{

	SeqListTest();

	return 0;
}

http://www.kler.cn/a/274423.html

相关文章：

  • 【C++11】可变模板参数
  • 中化信息与枫清科技深化合作：共探“AI+”产业新生态
  • CH340系列芯片驱动电路·CH340系列芯片驱动！！！
  • 时间序列预测论文阅读和相关代码库
  • 模型 结构化思维
  • PHY6239：具有高精确度AFE的无线MCU芯片，常用在智能穿戴上
  • PlantUML Integration 编写短信服务类图
  • 深入挖掘C语言之——枚举
  • Redis数据结构对象中的对象共享、对象的空转时长
  • 【Godot4.2】2D导航01 - AStar2D及其使用方法
  • python企业编码管理的程序（附源码）
  • 微信小程序接口请求出错:request:fail url not in domain list:xxxxx
  • 代码随想录算法训练营第53天 | 1143.最长公共子序列 ，1035.不相交的线 ，53. 最大子序和
  • 5.1.4、【AI技术新纪元：Spring AI解码】Amazon Bedrock
  • ASP .Net Core ILogger日志服务
  • MongoDB聚合运算符：$getField
  • 点云配准9：Colored-ICP的Open3D实现
  • Echarts折线图x轴不显示全部数据的解决办法，亲测有效
  • 电脑数据安全新利器：自动备份文件的重要性与实用方案
  • JupytetNotebook常用的快捷键
  • 【Vue3】Vue3中的编程式路由导航 重点！！！
  • test测试类-变量学习
  • 简单算法题收录
  • 【Python操作基础】——变量操作
  • HarmonyOS（鸿蒙）快速入门
  • Avalon总线学习