动态顺序表的增删改查（数据结构）

news/2024/9/29 6:09:40 标签: 数据结构, c语言, 开发语言, 算法

目录

一、顺序表

二、静态顺序表

三、动态顺序表

3.1、动态顺序表的实现

3.2、动态顺序表的实现

3.3.1、结构体创建

3.3.2、初始化

3.3.3、销毁数据

3.3.4、增容空间

3.3.5、尾插数据

3.3.6、头插数据

3.3.7、删除尾数据

3.3.8、打印数据

3.3.9、删除头数据

3.3.10、在指定位置之前插入数据

3.3.11、删除指定位置的数据

3.3.12、查找数据是否存在

四、全部代码

顺序表是数据结构的基础知识，通过学习次内容，可以让我们了解顺序表中数据中是如何进行存储，删除，插入数据的。

一、顺序表

顺序表在逻辑上与物理上是连续存放的，比如我们之前学习的数组，数组中包含许多数，每个数据在内存中存储都是连续的，在我们逻辑思维上存储也是连续的，当然，据我自己所了解，所以数据都需要是具有逻辑存储的，如果不是逻辑存储，那么根本就无法找到此数据。

以下是数组存储的数据：

顺序表与数组的区别：

顺序表的底层结构是数组，对于数组进行封装，实现了增删查改的接口。

使用数组很单一，无法进行修改，而使用顺序表进行存储数据，我们可以任意进行数据的修改。

二、静态顺序表

使用静态顺序表存储数据：

静态顺序表的大小被限制死了，无法进行扩容。

空间给少了不够用，空间给多了浪费。

三、动态顺序表

SLDataType* a;

为什么在这动态顺序表中，数据需要加上“*”,这是因为创建的是一个动态的顺序表，我们可以使用malloc，realloc进行开辟新空间来存储a，如果使用静态数据“a”的话，数据的存储位置就无法变动，当我们在增加数据时候，数据不够了，我们使用realloc开辟新空间，并且空间的其实位置进行改变，那么a就地址就会更改。

3.1、动态顺序表的实现

我们需要创建三个文件，node.h , node.c , test.c

node.h存储头文件与函数的参数

node.c实现函数

test.c为我们的主函数

代码小提示：

在编写代码的时候，我们需要勤测试，在完成一个函数体时，就需要测试，避免写完一大堆函数以后再测试，这样会无从下手。

3.2、动态顺序表的实现

在这部分，我只进行函数的讲解，想要查看全部源码的同学，可以拉到博客的最后进行查看

3.3.1、结构体创建

typedef int SLDatatype;
// 动态顺序表 -- 按需申请
typedef struct SeqList
{
	SLDatatype* arr;
	int size;     // 有效数据个数
	int capacity; // 空间容量
}SL;

我们把int类型的名字改变成了SLDatatype，这样可以方便进行数据类型大小的修改。

3.3.2、初始化

test.c

SL s;  //新建结构体
SLInit(&s);  //取地址传给函数进行初始化
//初始化
void SLInit(SL* ps) //进行传址调用，否则堆栈在运行完如何销毁的时候，内容也会消失
{
	ps->arr = NULL;                 //把数据给置空
	ps->size = ps->capacity = 0;   //把数据大小与空间也置零
}

因为是顺序表，无需修改首元素的地址，所以我们不需要进行SL* lisk=NULL；把新创建的内容给置为空。我们只要在一个空间进行增删改查。

初始化时我们需要把结构体中的arr置为空，数据大小与空间大小置为0

3.3.3、销毁数据

//销毁
void SLDestroy(SL* ps)
{
	if (ps->arr)    //相当于ps->arr != NULL
	{
		free(ps->arr);
	}
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}

当需要销毁数据时，需要把有数据的空间给释放掉，把释放掉空间的地址给置为NULL，避免这个地址变为野指针，影响其他软件的运行，然后我们把size数据大小与capacity 空间大小都置为0。

3.3.4、增容空间

//增容空间
void SLCheckCapacity(SL* ps)
{
	//判断空间是否充足
	if (ps->size == ps->capacity)
	{
		//增容//0*2 = 0
		//若capacity为0，给个默认值，否则×2倍
		int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		SLDatatype* tmp = (SLDatatype*)realloc(ps->arr, newCapacity * sizeof(SLDatatype));
		if (tmp == NULL)
		{
			perror("realloc fail!");
			exit(1);
		}
		ps->arr = tmp;
		ps->capacity = newCapacity;
	}
}

对于动态顺序表来说，每次增容的大小我们统一规定为：新空间大小 = 2 * 原空间大小。

当原空间大小为0时，我们可以增加一行进行判断，如果原空间等于0那么我们就随机给个默认值，我们这里默认值给的是4个整型。

在扩容完以后，我们将原空间的数据与空间大小都指向为新的地址。

3.3.5、尾插数据

//插入数据
void SLPushBack(SL* ps, SLDatatype x)
{
	//粗暴的解决方法---断言
	assert(ps);//等价于assert(ps != NULL)

	温柔的解决方式
	//if (ps == NULL)
	//{
	//	return;
	//}
	SLCheckCapacity(ps);
	ps->arr[ps->size++] = x;  //每插入一个数据，有效数据大小size就会+1
}

assert（ps）断言是为了判断ps是一个空指针。

当ps->arr[0]=1;进行完这个操作，我们如果想继续插入2，那么我们就要让arr的大小增加1位，此时就变成了ps->arr[1]=2。因此得出代码：ps->arr[ps->size++] = x;

3.3.6、头插数据

void SLPushFront(SL* ps, SLDatatype x)
{
	assert(ps);
	//判断空间是否足够
	SLCheckCapacity(ps);

	//数据整体后移一位
	for (int i = ps->size; i > 0; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	//下标为0的位置空出来
	ps->arr[0] = x;

	ps->size++;
}

这段代码里的注释应该是很清楚的表示了

我们需要把表中数据集体往后移动一位，让新数据放到首元素。

3.3.7、删除尾数据

//删除
void SLPopBack(SL* ps)
{
	assert(ps);       //判断ps不为空，如果为空，代码没必要运行
	assert(ps->size); //判断有效数据大小不为空，如果为空，代码没必要运行

	//ps->arr[ps->size - 1] = -1;  //多余了
	ps->size--;    //直接将有效数据个数-1就达到我们尾删的效果
}

我们可以直接将有效数据个数-1就达到我们尾删的效果

3.3.8、打印数据

void SLPrint(SL* ps)
{
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->arr[i]);
	}
	printf("\n");
}

这个很好理解，不过多阐述了。

3.3.9、删除头数据

void SLPopFront(SL* ps)
{
	assert(ps);
	assert(ps->size);

	//数据整体向前挪动一位
	for (int i = 0; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];   //i = size-2
	}
	ps->size--;
}

将数据集体往前移动一位。

移动前：

移动后：

3.3.10、在指定位置之前插入数据

//在指定位置之前插入数据(空间足够才能直接插入数据）
void SLInsert(SL* ps, SLDatatype x, int pos)
{
	assert(ps);   //判断ps是否为空
	assert(pos >= 0 && pos <= ps->size);    //判断指定位置的数据是否在顺序表中有效

	SLCheckCapacity(ps);

	//pos及之后的数据整体向后移动一位
	for (int i = ps->size; i > pos; i--)
	{
		ps->arr[i] = ps->arr[i - 1]; //pos+1   ->   pos
	}

	ps->arr[pos] = x;
	ps->size++;
}

插入前：

插入后：

3.3.11、删除指定位置的数据

//删除指定位置的数据
void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	//还有更多的限制：如顺序表不能为空....

	//pos之后的数据整体向前挪动一位
	for (int i = pos; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];// size-2 <- size-1
	}
	ps->size--;
}

删除前：

删除后：

3.3.12、查找数据是否存在

//查找数据
int SLFind(SL* ps, SLDatatype x)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == x)  //如果arr指向的数据等于x那么就return i
		{
			return i;
		}
	}
	//没有找到：返回一个无效的下标
	return -1;
}
test.c

int find = SLFind(&s, 222);
if (find < 0)
{
	printf("没找到\n");
}
else
{
	printf("找到了\n");
}

如果return返回的数字小于零，打印没找到，否则就打印找到了

四、全部代码

node.h

typedef int SLDatatype;
// 动态顺序表 -- 按需申请
typedef struct SeqList
{
	SLDatatype* arr;
	int size; // 有效数据个数
	int capacity; // 空间容量
}SL;

//初始化
void SLInit(SL* ps);
//销毁数据
void SLDestroy(SL* ps);
//打印数据
void SLPrint(SL* ps);
//扩容
void SLCheckCapacity(SL* ps);
//尾插
void SLPushBack(SL* ps, SLDatatype x);
//头插
void SLPushFront(SL* ps, SLDatatype x);
//尾删
void SLPopBack(SL* ps);
//头删
void SLPopFront(SL* ps);
//查找指定数据
int SLFind(SL* ps, SLDatatype x);
//指定位置之前插⼊
void SLInsert(SL* ps, int pos, SLDatatype x);
//指定位置之前删除数据
void SLErase(SL* ps, int pos);
node.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "node.h"

//初始化
void SLInit(SL* ps)
{
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}
//销毁
void SLDestroy(SL* ps)
{
	if (ps->arr)//相当于ps->arr != NULL
	{
		free(ps->arr);
	}
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}
void SLCheckCapacity(SL* ps)
{
	//判断空间是否充足
	if (ps->size == ps->capacity)
	{
		//增容//0*2 = 0
		//若capacity为0，给个默认值，否则×2倍
		int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		SLDatatype* tmp = (SLDatatype*)realloc(ps->arr, newCapacity * sizeof(SLDatatype));
		if (tmp == NULL)
		{
			perror("realloc fail!");
			exit(1);
		}
		ps->arr = tmp;
		ps->capacity = newCapacity;
	}
}
//插入数据
void SLPushBack(SL* ps, SLDatatype x)
{
	//粗暴的解决方法---断言
	assert(ps);//等价于assert(ps != NULL)

	温柔的解决方式
	//if (ps == NULL)
	//{
	//	return;
	//}
	SLCheckCapacity(ps);
	ps->arr[ps->size++] = x;
}
void SLPushFront(SL* ps, SLDatatype x)
{
	assert(ps);
	//判断空间是否足够
	SLCheckCapacity(ps);

	//数据整体后移一位
	for (int i = ps->size; i > 0; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	//下标为0的位置空出来
	ps->arr[0] = x;

	ps->size++;
}


void SLPrint(SL* ps)
{
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->arr[i]);
	}
	printf("\n");
}

//删除
void SLPopBack(SL* ps)
{
	assert(ps);
	assert(ps->size);

	//ps->arr[ps->size - 1] = -1;//多余了
	ps->size--;
}
void SLPopFront(SL* ps)
{
	assert(ps);
	assert(ps->size);

	//数据整体向前挪动一位
	for (int i = 0; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];//i = size-2
	}
	ps->size--;
}
//在指定位置之前插入数据(空间足够才能直接插入数据）
void SLInsert(SL* ps, SLDatatype x, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);

	SLCheckCapacity(ps);

	//pos及之后的数据整体向后移动一位
	for (int i = ps->size; i > pos; i--)
	{
		ps->arr[i] = ps->arr[i - 1]; //pos+1   ->   pos
	}

	ps->arr[pos] = x;
	ps->size++;
}
//删除指定位置的数据
void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	//还有更多的限制：如顺序表不能为空....

	//pos之后的数据整体向前挪动一位
	for (int i = pos; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];// size-2 <- size-1
	}
	ps->size--;

}

int SLFind(SL* ps, SLDatatype x)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == x)
		{
			return i;
		}
	}
	//没有找到：返回一个无效的下标
	return -1;
}
test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "node.h"

void SLtest01()
{
	SL s;
	SLInit(&s);

	SLPushBack(&s, 1);
	SLPushBack(&s, 2);
	SLPushBack(&s, 3);
	SLPushBack(&s, 4);
	//SLPushBack(&s, 5);
	//SLPushBack(&s, 6);
	//SLPushBack(NULL , 6);
	//
	//SLPushFront(&s, 1);
	//SLPushFront(&s, 2);
	//SLPushFront(&s, 3);
	//SLPushFront(&s, 4);
	SLPrint(&s); //1 2 3 4

	//SLPopBack(&s);
	//SLPrint(&s);
	//SLPopBack(&s);
	//SLPrint(&s);
	//SLPopBack(&s);
	//SLPrint(&s);
	//SLPopBack(&s);
	//SLPrint(&s);
	//SLPopBack(&s);
	//SLPrint(&s);
	//
	//SLPopFront(&s);
	//SLPrint(&s);
	//SLPopFront(&s);
	//SLPrint(&s);
	//SLPopFront(&s);
	//SLPrint(&s);
	//SLPopFront(&s);
	//SLPrint(&s);
	//SLPopFront(&s);
	//SLPrint(&s);

	//SLInsert(&s, 11, 0);
	//SLPrint(&s);
	//SLInsert(&s, 22, s.size);
	//SLPrint(&s);
	//SLInsert(&s, 33, 1);
	//SLPrint(&s);

	//SLErase(&s, 1);
	//SLPrint(&s); //1 3 4
	//SLErase(&s,s.size-1);
	//SLPrint(&s);//2 3

	int find = SLFind(&s, 222);
	if (find < 0)
	{
		printf("没找到\n");
	}
	else
	{
		printf("找到了\n");
	}

	SLDestroy(&s);
	//SLDestroy(&s);//ctrl+d
}

int main()
{
	SLtest01();
	return 0;
}


http://www.niftyadmin.cn/n/5682535.html

相关文章

Python中的机器学习：从入门到实战

Python中的机器学习：从入门到实战

机器学习是人工智能领域的一个重要分支&#xff0c;它通过构建模型来使计算机从数据中学习并做出预测或决策。Python凭借其丰富的库和强大的生态系统&#xff0c;成为了机器学习的首选语言。本文将从基础到实战&#xff0c;详细介绍如何使用Python进行机器学习&#xff0c;涵盖…
阅读更多...
【深度学习】注意力机制与自注意力机制详解

【深度学习】注意力机制与自注意力机制详解

深度学习中的注意力机制/自注意力机制详解 1. 注意力机制的通俗理解2. 注意力和自注意力机制的区别3. 自注意力机制原理与计算流程3.1 引入自注意力机制的目的与思想3.2 从向量角度理解 [R1]3.3 从Self-Attention核心公式理解 [R3] 4. 多头自注意力机制&#xff08;Multi-head …
阅读更多...
MySQL：MySQL中 limit 1000000,10 为什么慢？如何优化？

MySQL：MySQL中 limit 1000000,10 为什么慢？如何优化？

一、前言 在 MySQL 中&#xff0c;使用 LIMIT X, Y 语句时&#xff0c;如果 X 的值很大&#xff0c;查询性能确实可能会受到影响。这是因为 MySQL 需要先扫描或处理前 X 条记录&#xff0c;然后才能返回从第 X1 条开始的 Y 条记录。当 X 很大时&#xff0c;这个扫描过程会消耗大…
阅读更多...
【STM32】RTT-Studio中HAL库开发教程七：IIC通信--EEPROM存储器FM24C04

【STM32】RTT-Studio中HAL库开发教程七：IIC通信--EEPROM存储器FM24C04

文章目录 一、简介二、模拟IIC时序三、读写流程四、完整代码五、测试验证 一、简介 FM24C04D&#xff0c;4K串行EEPROM&#xff1a;内部32页&#xff0c;每个16字节&#xff0c;4K需要一个11位的数据字地址进行随机字寻址。FM24C04D提供4096位串行电可擦除和可编程只读存储器&a…
阅读更多...
使用 vite 快速初始化 shadcn-vue 项目

使用 vite 快速初始化 shadcn-vue 项目

Vite 1. 创建项目 使用 vite 创建一个新的 vue 项目。 如果你正在使用 JS 模板&#xff0c;需要存在 jsconfig.json 文件才能正确运行 CLI。 # npm 6.x npm create vitelatest my-vue-app --template vue-ts# npm 7, extra double-dash is needed: npm create vitelatest m…
阅读更多...
单点登录（SSO）基础

单点登录（SSO）基础

单点登录&#xff08;SSO, Single Sign-On&#xff09; 是一种身份认证机制&#xff0c;允许用户在多个独立的应用系统中只进行一次登录操作&#xff0c;即可访问所有授权的应用或服务&#xff0c;而无需每次切换应用时都进行登录。SSO 提高了用户体验的便捷性&#xff0c;同时…
阅读更多...
Stable Diffusion绘画 | 插件-Deforum：动态视频生成

Stable Diffusion绘画 | 插件-Deforum：动态视频生成

Deforum 与 AnimateDiff 不太一样&#xff0c; AnimateDiff 是生成丝滑变化视频的&#xff0c;而 Deforum 的丝滑程度远远没有 AnimateDiff 好。 它是根据对比前面一帧的画面&#xff0c;然后不断生成新的相似图片&#xff0c;来组合成一个完整的视频。 Deforum 的优点在于可…
阅读更多...
如何评估和观测 IoTDB 所需的网络带宽？

如何评估和观测 IoTDB 所需的网络带宽？

IoTDB 推荐网络配置监控网络 I/O 一网打尽&#xff01; 网络数据传输速度太慢&#xff1f;延迟太高&#xff1f; 网络的硬件配置如何确定&#xff1f; 网络流量过大导致拥塞&#xff1f; 在现代计算机系统和应用程序中&#xff0c;网络 I/O 性能是决定整体系统表现的关键因素之…
阅读更多...
最新文章

Copyright @ 2022~2023