【数据结构】手撕顺序表

一，概念及结构

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储；

在数组上完成数据的增删查改。

 1， 静态顺序表：使用定长数组存储元素。

2.，动态顺序表：使用动态开辟的数组存储。

 

二，接口实现

静态顺序表只适用于确定知道需要存多少数据的场景；

静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用；

所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实现动态顺序表；

        1，顺序表的创建（动态）

//动态顺序表
typedef int SLDataType;

typedef struct SqList
{
	SLDataType* a;
	int size;		//存储有效数据个数
	int capacity;	//容量空间大小
}SL;

这里我们将数据类型暂时定为int类型，typedef为SLDataType，便于我们后续对顺序表数据类型的修改；

定义属性表为SL*的指针a，有效数据个数size，现有容量capacity;

        2，接口函数

// 顺序表初始化
void SLInit(SL* ps);
// 顺序表销毁
void SLDestroy(SL* ps);
// 检查空间，如果满了，进行增容
void SLChenkCapacity(SL* ps);
//顺序表尾插
void SLPushBack(SL* ps,SLDataType x);
//顺序表尾删
void SLPopBack(SL* ps);
//顺序表头插
void SLPushFront(SL* ps, SLDataType x);
//顺序表头删
void SLPopFront(SL* ps);
//顺序表打印
void SLPrint(SL* ps);
// 顺序表查找
int SeqListFind(SL* ps, SLDataType x);
// 顺序表在pos位置插入x
void SLInsert(SL*ps, int pos, SLDataType x);
// 顺序表在pos位置删除x
void SLErase(SL*ps, int pos);

        3，初始化 

	//定义
	SL s1;
	//初始化
	SLInit(&s1);
// 顺序表初始化
void SLInit(SL* ps)
{
	assert(ps);
	ps->a = (SLDataType*)malloc(sizeof(SLDataType) * 4);
	if (ps->a== NULL)
	{
		perror("malloc");
		exit(-1);
	}
	ps->size = 0;
	ps->capacity = 4;
}

首先要进行断言ps不能为空，如果ps为空则下面对ps解引用就会报错；

刚开始先给 a 申请4个SLDataType大小的空间，这个自己可以任意修改，然后对size和capacity进行赋值；

        4，销毁

// 顺序表销毁
void SLDestroy(SL*ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->size = ps->capacity = 0;
}

然后就是销毁顺序表，直接用 free 释放掉 a 即可，再置为空指针，再重置 size 和 capacity ；

        5，判断是否增容

// 检查空间，如果满了，进行增容
void SLChenkCapacity(SL* ps)
{
	assert(ps);
	if (ps->size == ps->capacity)
	{
		ps->a = (SLDataType*)realloc(ps->a, ps->capacity * 2 * (sizeof(SLDataType)));
		if (ps->a == NULL)
		{
			perror("realloc");
			exit(-1);
		}
		ps->capacity = ps->capacity * 2;
	}
}

像后面如果进行尾插，头插的话就需要检查空间是否需要增容了，也很好判断，当size等于capacity时就需要增容了，我们这里是选择直接扩容一倍；

然后再更新一下capacity的值就行了；

        6，尾插

//顺序表尾插
void SLPushBack(SL* ps, SLDataType x)
{
	assert(ps);
	//检查空间
	SLChenkCapacity(ps);
	ps->a[ps->size] = x;
	ps->size++;
}

首先判断是否需要增容，此时size的值就是末尾的数的下标加一；

直接对其下标进行赋值，再让size加一；

        7，尾删

//顺序表尾删
void SLPopBack(SL* ps)
{
	assert(ps);
	//温柔的检查
	//if (ps->size == 0)
	//	return;

	//暴力检查
	assert(ps->size > 0);
	ps->size--;
}

这里有两种检查方式，推荐暴力检查法，要删除值，size的值必须大于0；

然后直接令size减一即可，访问不到即为删除；

          8，头插

//顺序表头插
void SLPushFront(SL* ps, SLDataType x)
{
	assert(ps);
	SLChenkCapacity(ps);
	int end = ps->size-1;
	while (end >= 0)
	{
		ps->a[end + 1] = ps->a[end];
		end--; 
	}
	ps->a[0] = x;
	ps->size++;
}

还是先判断是否需要增容，然后先将整体的值往后推一位；

给头赋值，令size加一；

           9，头删

//顺序表头删
void SLPopFront(SL* ps)
{
	assert(ps);
	assert(ps->size > 0);
	int i = 0;
	while (i < ps->size - 1)
	{
		ps->a[i] = ps->a[i + 1];
		i++;
	}
	ps->size--;
}

要删除数据首先数据不能为空，要进行断言一下；

然后将整体往前推一位，再令size减一；

        10，打印

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

size是数据个数，其减一就是末尾数据的下标，然后进行遍历打印即可；

        11，查找

// 顺序表查找
int SeqListFind(SL* ps, SLDataType x)
{
	assert(ps);
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		if (ps->a[i] == x)
			return i;
	}
	return -1;
}

直接遍历数组进行查找然后返回下标，没有则返回-1；

         12，指定位置进行插入

// 顺序表在pos位置插入x
void SLInsert(SL*ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos>=0 && pos <= ps->size);
	SLChenkCapacity(ps);
	int end = ps->size - 1;
	while (end >=pos)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	ps->a[pos] = x;
	ps->size++;
}

首先判断pos要大于等于0且小于等于size，是否需要增容；

然后从pos数组的值往后推一位，再对其位置重新赋值，再令size++；

         13，指定位置进行删除

// 顺序表在pos位置删除x
void SLErase(SL*ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	int i = pos;
	while (i < ps->size - 1)
	{
		ps->a[i] = ps->a[i + 1];
		i++;
	}
	ps->size--;
}

首先还是要判断pos的值，大于等于0小于size，因为数组下标为size是没有值的，所以pos不能等于size；

然后在pos处往前推一位，令size--；

三，源码

        1，头文件

SqList.h

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

//动态顺序表
typedef int SLDataType;

typedef struct SqList
{
	SLDataType* a;
	int size;		//存储有效数据个数
	int capacity;	//容量空间大小
}SL;

// 顺序表初始化
void SLInit(SL* ps);
// 顺序表销毁
void SLDestroy(SL* ps);
// 检查空间，如果满了，进行增容
void SLChenkCapacity(SL* ps);
//顺序表尾插
void SLPushBack(SL* ps,SLDataType x);
//顺序表尾删
void SLPopBack(SL* ps);
//顺序表头插
void SLPushFront(SL* ps, SLDataType x);
//顺序表头删
void SLPopFront(SL* ps);
//顺序表打印
void SLPrint(SL* ps);
// 顺序表查找
int SeqListFind(SL* ps, SLDataType x);
// 顺序表在pos位置插入x
void SLInsert(SL*ps, int pos, SLDataType x);
// 顺序表在pos位置删除x
void SLErase(SL*ps, int pos);

         2，执行文件

SqList.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"SqList.h"

// 顺序表初始化
void SLInit(SL* ps)
{
	assert(ps);
	ps->a = (SLDataType*)malloc(sizeof(SLDataType) * 4);
	if (ps->a== NULL)
	{
		perror("malloc");
		exit(-1);
	}
	ps->size = 0;
	ps->capacity = 4;
}

// 顺序表销毁
void SLDestroy(SL*ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->size = ps->capacity = 0;
}

// 检查空间，如果满了，进行增容
void SLChenkCapacity(SL* ps)
{
	assert(ps);
	if (ps->size == ps->capacity)
	{
		ps->a = (SLDataType*)realloc(ps->a, ps->capacity * 2 * (sizeof(SLDataType)));
		if (ps->a == NULL)
		{
			perror("realloc");
			exit(-1);
		}
		ps->capacity = ps->capacity * 2;
	}
}

//顺序表尾插
void SLPushBack(SL* ps, SLDataType x)
{
	assert(ps);
	//检查空间
	SLChenkCapacity(ps);
	ps->a[ps->size] = x;
	ps->size++;
}

//顺序表尾删
void SLPopBack(SL* ps)
{
	assert(ps);
	//温柔的检查
	//if (ps->size == 0)
	//	return;

	//暴力检查
	assert(ps->size > 0);
	ps->size--;
}

//顺序表头插
void SLPushFront(SL* ps, SLDataType x)
{
	assert(ps);
	SLChenkCapacity(ps);
	int end = ps->size-1;
	while (end >= 0)
	{
		ps->a[end + 1] = ps->a[end];
		end--; 
	}
	ps->a[0] = x;
	ps->size++;
}

//顺序表头删
void SLPopFront(SL* ps)
{
	assert(ps);
	assert(ps->size > 0);
	int i = 0;
	while (i < ps->size - 1)
	{
		ps->a[i] = ps->a[i + 1];
		i++;
	}
	ps->size--;
}

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


// 顺序表查找
int SeqListFind(SL* ps, SLDataType x)
{
	assert(ps);
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		if (ps->a[i] == x)
			return i;
	}
	return -1;
}


// 顺序表在pos位置插入x
void SLInsert(SL*ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos>=0 && pos <= ps->size);
	SLChenkCapacity(ps);
	int end = ps->size - 1;
	while (end >=pos)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	ps->a[pos] = x;
	ps->size++;
}

// 顺序表在pos位置删除x
void SLErase(SL*ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	int i = pos;
	while (i < ps->size - 1)
	{
		ps->a[i] = ps->a[i + 1];
		i++;
	}
	ps->size--;
}

如有不足之处欢迎来补充交流！

完结。。。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/96755.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Java 8的重要知识点

Java 8的重要知识点

一、Lambda 表达式 Lambda 表达式的初衷是&#xff0c;进一步简化匿名类的语法&#xff08;不过实现上&#xff0c;Lambda 表达式并不是匿名类的语法糖&#xff09; 1、使用 Stream 简化集合操作&#xff1b; map 方法传入的是一个 Function&#xff0c;可以实现对象转换&…
阅读更多...
无涯教程-Android Studio函数

无涯教程-Android Studio函数

第1步-系统要求 您将很高兴知道您可以在以下两种操作系统之一上开始Android应用程序的开发- MicrosoftWindows10/8/7/Vista/2003(32或64位)MacOSX10.8.5或更高版本,最高10.9(小牛) GNOME或KDE桌面 第二点是,开发Android应用程序所需的所有工具都是开源的,可以从Web上下载。以…
阅读更多...
设计模式——装饰器模式

设计模式——装饰器模式

装饰器模式 装饰器模式&#xff08;Decorator Pattern&#xff09;允许向一个现有的对象添加新的功能&#xff0c;同时又不改变其结构。这种类型的设计模式属于结构型模式&#xff0c;它是作为现有的类的一个包装。 装饰器模式通过将对象包装在装饰器类中&#xff0c;以便动态…
阅读更多...
嵌入式Linux开发实操（十五）：nand flash接口开发

嵌入式Linux开发实操（十五）：nand flash接口开发

# 前言 flash memory，分NAND和NOR： 如果说nor flash有个特点就是能执行代码，NOR并行接口具有地址和数据总线，spi flash更是主要用于存储代码，SPI（或QSPI）NOR代码可就地执行（XiP），一般系统要求flash闪存提供相对较高的频率和数据缓存的clocking。而nand flash主要用于…
阅读更多...
【Golang】go条件编译

【Golang】go条件编译

交叉编译只是为了能在一个平台上编译出其他平台可运行的程序&#xff0c;Go 作为一个跨平台的语言&#xff0c;它提供的类库势必也是跨平台的&#xff0c;比如说程序的系统调用相关的功能&#xff0c;能根据所处环境选择对应的源码进行编译。让编译器只对满足条件的代码进行编译…
阅读更多...
【算法训练-字符串】一 最长无重复子串

【算法训练-字符串】一 最长无重复子串

废话不多说&#xff0c;喊一句号子鼓励自己&#xff1a;程序员永不失业&#xff0c;程序员走向架构&#xff01;本篇Blog的主题是最长无重复子串或最长无重复子数组&#xff0c;这类题目出现频率还是很高的。 最长无重复子串【MID】 先来看字符串数据结构的题目 题干 解题思…
阅读更多...
vue3的面试题

vue3的面试题

ref里面放对象发生的事情 ref只会对对象的属性进行响应式转换&#xff0c;而不会对对象的原型链上的属性进行转换。如果需要对对象的原型链上的属性进行响应式转换&#xff0c;可以使用reactive函数。 toRefs的适用场景&#xff1f; toRefs是Vue 3中的一个响应式API&#xf…
阅读更多...
【Java】基础入门 （十六）--- 异常

【Java】基础入门 （十六）--- 异常

1.异常 1.1 异常概述 异常是指程序在运行过程中出现的非正常的情况&#xff0c;如用户输入错误、除数为零、文件不存在、数组下标越界等。由于异常情况再程序运行过程中是难以避免的&#xff0c;一个良好的应用程序除了满足基本功能要求外&#xff0c;还应具备预见并处理可能发…
阅读更多...
实验室的服务器和本地pycharm怎么做图传

实验室的服务器和本地pycharm怎么做图传

参考 远程调试 qt.qpa.xcb: could not connect to display, echo DISPLAY为空[已解决]_功夫小象的博客-CSDN博客 先安装x11 MobaXterm x11-forwarding_C--G的博客-CSDN博客 我是在容器中搞得 1&#xff0c;安装qt5 pip install PyQt5 -i https://pypi.douban.com/simple …
阅读更多...
Spring-SpringBoot-SpringMVC-MyBatis常见面试题

Spring-SpringBoot-SpringMVC-MyBatis常见面试题

文章目录 Spring篇springbean是安全的的?什么是AOP你们工作中有用过AOP吗spring中的事务是如何实现的spring中事务失效场景Spring的生命周期spring中的循坏依赖springMVC的执行流程springboot的启动原理常用注解MyBatis执行流程Mybatis是否支持延迟加载&#xff1f;Mybatis的一…
阅读更多...
静态类方法的同步

静态类方法的同步

由于在调用静态方法时&#xff0c;对象实例不一定被创建。因此&#xff0c;就不能使用this来同步静态方法&#xff0c;而必须使用Class对象来同步静态方法。代码如下&#xff1a; 通过synchronized块同步静态方法 public class StaticSyncBlock { public static void…
阅读更多...
ETC reset

ETC reset

ETC重新激活 换前挡风玻璃膜会把ETC设备拿下来&#xff0c;需要到【ETC服务中心】重新【粘上去】&#xff0c;另外需要工作人员用手持终端【重新激活】 ETC 背面有个 【白色】开关小柱子&#xff0c;一旦拆下来就失效&#xff0c;因为这个开关弹出来了 截面图看就是这样的&…
阅读更多...
动态不确定性的动态S过程（Matlab代码实现）

动态不确定性的动态S过程（Matlab代码实现）

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…
阅读更多...
2023年高教社杯 国赛数学建模思路 - 案例：感知机原理剖析及实现

2023年高教社杯 国赛数学建模思路 - 案例：感知机原理剖析及实现

文章目录 1 感知机的直观理解2 感知机的数学角度3 代码实现 4 建模资料 # 0 赛题思路 &#xff08;赛题出来以后第一时间在CSDN分享&#xff09; https://blog.csdn.net/dc_sinor?typeblog 1 感知机的直观理解 感知机应该属于机器学习算法中最简单的一种算法&#xff0c;其…
阅读更多...
【项目 计网7】4.20 多进程实现并发服务器 4.22 多线程实现并发服务器

【项目 计网7】4.20 多进程实现并发服务器 4.22 多线程实现并发服务器

文章目录 4.20 多进程实现并发服务器server_process.cclient.c4.22 多线程实现并发服务器客户端代码&#xff1a;服务端代码&#xff1a; 4.20 多进程实现并发服务器 要实现TCP通信服务器处理并发的任务&#xff0c;使用多线程或者多进程来解决。 思路&#xff1a; 1、一个父进…
阅读更多...
打开软件报错mfc100u.dll缺失是什么意思?简单式修复mfc100u.dll问题

打开软件报错mfc100u.dll缺失是什么意思?简单式修复mfc100u.dll问题

首先&#xff0c;我们需要了解什么是MFC100U.dll文件以及它的作用。MFC100U.dll是一个Microsoft Foundation Class (MFC)库文件&#xff0c;它是Visual C应用程序开发的一部分。MFC库提供了许多通用的功能&#xff0c;如窗口管理、消息处理等&#xff0c;可以帮助开发者更快速地…
阅读更多...
成集云 | 抖店客户静默下单催付数据同步钉钉 | 解决方案

成集云 | 抖店客户静默下单催付数据同步钉钉 | 解决方案

源系统成集云目标系统 方案介绍 随着各品牌全渠道铺货&#xff0c;主播在平台上直播时客户下了订单后不能及时付款&#xff0c;第一时间客户收不到提醒&#xff0c;不仅造成了客户付款率下降&#xff0c;更大量消耗了企业的人力成本和经济。而成集云与钉钉深度合作&#xff0…
阅读更多...
【力扣】55、跳跃游戏

【力扣】55、跳跃游戏

var canJump function(nums){let cover 0;for(let i0;i<nums.length;i){if(i<cover){cover Math.max(nums[i]i,cover);if(cover >nums.length-1){return true;}}}}
阅读更多...
【状压+概率DP】CF678 E

【状压+概率DP】CF678 E

Problem - E - Codeforces 题意&#xff1a; 思路&#xff1a; 首先&#xff0c;n < 18&#xff0c;应当想到状压 很明显&#xff0c;这里可以使用状压DP 设 dp[s][i] 表示&#xff0c;现在选的方案为 s &#xff0c;且我是 i 的最终胜利的概率是多少 重要的是转移 这是…
阅读更多...
SpringBoot+MyBatisPlus+MySql+vue2+elementUi的案例、java访问数据库服务、java提供接口服务

SpringBoot+MyBatisPlus+MySql+vue2+elementUi的案例、java访问数据库服务、java提供接口服务

文章目录 前言后端关键代码前端关键代码完整代码 前言 1、项目不使用前后端分离。 2、在创建SpringBoot的时候要注意各个插件间的版本问题。 3、后端技术SpringBootMyBatisPlusMySql。 4、前端技术vue2elementUi。 后端关键代码 简单介绍 1、数据库名称ssm_db 2、表名称tbl_bo…
阅读更多...
最新文章

Copyright @ 2022~2023