实现顺序表（增、删、查、改）

引言：顺序表是数据结构中的一种形式，就是存储数据的一种结构。

这里会用到动态内存开辟，指针和结构体的知识

1.什么是数据结构

数据结构就是组织和存储数据的结构。

数据结构的特性：

物理结构：在内存中存储的数据是否连续

逻辑结构:   逻辑上是否连续

2.什么是顺序表

为了更好的实现顺序表，首先的了解其的特性。

顺序表的特性：

物理结构：连续的

逻辑结构：连续的

顺序表也是线性结构的一种

线性结构的特性：

物理结构：不一定连续

逻辑结构：连续的

顺序表的底层是数组。顺序表在数组的基础上能通过调用函数实现数据的增删查改。

数组在内存中开辟的空间是连续的，所以其存储的数据在内存中也是连续的。

3.静态顺序表与动态顺序表哪个更好呢？ 

顺序表又分为静态顺序表，和动态顺序表

那么哪种更好呢？ 

静态顺序表和动态顺序表的结构

//静态顺序表的结构
struct SeqList
{
	int arr[100];//开辟的空间大小已经确定
	int size;//记录当前元素的个数
};
//动态顺序表的结构
struct SeqList
{
	int* arr;
	int size;//记录当前元素的个数
	int capacity;//记录当前能存放元素的个数，如果size=capacity时，扩容
};

动态顺序表的结构图解：

 

比较：

静态顺序表开辟的存放数据的空间：如果开辟过大，则浪费空间；若开辟过小，若想存的数据过多，则有的数据存不进去。

而动态顺序表则更灵活，不够了再开辟就可以了。

所以动态顺序表更好，这里也只会将动态顺序表的实现。

4.动态顺序表的实现

4.1通过多文件的形式实现

文件管理：

test.c进行各个接口的测试
SeqList.c实现增删查改函数的实现
SeqLst.h引用需要使用的头文件，动态顺序表结构体的定义，实现增删查改函数函数的声明，#define 定义的符号

需要实现的函数： 

初始化、销毁创建完动态顺序表的结构后应对其成员进行初始化，释放开辟的空间，并将结构体的成员初始化
增

有头插，尾插

任意插

删

头删，尾删

任意删

查查找顺序表中是否有查找的元素

这里直接给出完整的SeqList.h 中的全部代码：

#pragma once//防止头文件多次包含

//用到的库函数
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

//如果以后想存储的数据不再是int 只需要改这一出的int改为别的数据类型
#define SLDataType int

//顺序表的结构定义
typedef struct SeqList
{
	SLDataType* arr;
	int size;
	int capacity;
}SL;


//以下为需要实现的函数的声明
//初始化
void SLInit(SL* ps);
void SLDestory(SL* ps);
//打印
void SLPrint(SL ps);
//尾插，尾删
void SLPushBack(SL* ps, SLDataType x);
void SLPushFront(SL* ps, SLDataType x);
//尾删，头删
void SLPopFront(SL* ps);
void SLPopBack(SL* ps);
//任意插，任意删
void SLInsert(SL* ps, int pos, SLDataType x);
void SLErase(SL* ps, int pos);
//查找
int SLFind(SL* ps,SLDataType find);

4.2初始化和销毁注意事项

//初始化
void SLInit(SL* ps)
{
	ps->arr = NULL;
	ps->size = 0;
	ps->capacity = 0;
}

 一定要传定义的结构体的地址，这样才能改变所定义的结构体的值。

//销毁
void SLDestory(SL* ps)
{
	assert(ps);
	free(ps->arr);
	ps->arr = NULL;
	ps->size = 0;
	ps->capacity = 0;
}

4.3尾插，头插中的一些注意事项

尾插实现函数：

void SLPushBack(SL* ps, SLData x)
{
    //ps不能为NULL
	assert(ps != NULL);
	//增容：1.capacity和size都为0   2.空间不够用
	if (ps->capacity == ps->size)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SLData* tmp = (SLData*)realloc(ps->arr, newcapacity * sizeof(SLData));
		if (tmp == NULL)
		{
			perror("realloc");
			exit(-1);
		}
		//开辟成功
		ps->arr = tmp;
		ps->capacity = newcapacity;
	}
    //将值写入顺序表
	ps->arr[ps->size] = x;
    //插入完顺序表中元素的个数+1
	ps->size++;
}

增容问题：

如果结构体中的size 和capacity 都为0，或size等于capacity（所开辟的空间都被使用完）时，就要增容。

用realloc，malloc还是用calloc开辟空间呢？

考虑到增容的问题所以用realloc开辟空间。

那么增多大呢？

这里不好解释，建议增大当前所开辟空间的2或3倍。如果开辟小了的话，很快就会被用完，就会频繁地开辟，如果是下图中realloc开辟空间中的情况2，拷贝数据很影响程序性能；若开辟过大，则浪费空间。

因为插入会考虑到增容问题所以可以写一个实现增容的函数。

void CheckSLCapacity(SL* ps)
{
    //如果size等于capacity说明开辟的空间已经使用完，得增容
	if (ps->capacity == ps->size)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SLData* tmp = (SLData*)realloc(ps->arr, newcapacity * sizeof(SLData));
		if (tmp == NULL)
		{
			perror("realloc");
			exit(-1);
		}
		//开辟成功
		ps->arr = tmp;
		ps->capacity = newcapacity;
	}
}

头插和尾插实现的代码：

//头插
void SLPushFront(SL* ps, SLData x)
{
	assert(ps != NULL);
	CheckSLCapacity(ps);//增容函数，上面的尾插的代码中的实现增容的代码也可以替换为这个函数
	for (int i = ps->size; i>0; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[0] = x;
	ps->size++;
}

//头插
void SLPushBack(SL* ps, SLDataType x)
{
	assert(ps != NULL);
	CheckSLCapacity(ps);
	ps->arr[ps->size] = x;
	ps->size++;
}

 4.4 头删和尾删

实现代码：

//尾删
void SLPopBack(SL* ps)
{
	assert(ps != NULL);
	assert(ps->size > 0);
	ps->size--;
}

//头删
void SLPopFront(SL* ps)
{
	assert(ps != NULL);
	assert(ps->size > 0);
	for (int i = 0; i <ps->size-1 ; i++)
		ps->arr[i] = ps->arr[i + 1];
	ps->size--;
}

注意：如果顺序表中没有数据那么就不能继续删除了， assert(ps->size > 0)防止没有数据了继续删。

尾删：只需要将size--就可以，不需要将最后的数据修改（修改也是可以的），但别忘了最后size--

头删：将除头部的其他数据整体向前挪动一位。

头删图解：

4.5 任意删和任意插

实现代码：

//任意插
//pos为想要插入的位置的下标
void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
    //若pos小于0，不能插入；若想要插入的位置大于size也不能插入
	assert(pos >= 0 && pos <= ps->size);
    //考虑扩容问题
	CheckSLCapacity(ps);
    //注意赋值的顺序和 i 的范围
	for (int i = ps->size; i>pos ; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[pos] = x;
	ps->size++;
}


//任意删
void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	for (int i = pos; i < ps->size-1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;

}

注意事项：

任意插入：

对插入位置下标（pos）的限制： pos >= 0 && pos <= ps->size

图解：

通过上图可以用任意插函数实现头插和尾插

 

任意插入后挪动数据的方式：

从pos位置开始集体往后挪

 任意删除后的数据挪动方式：

从size-1 开始往前挪直到pos+1 的位置。

用任意插入和任意删除的函数实现 头插，尾插和头删，尾删

//头插、尾插
void SLPushBack1(SL* ps, SLDataType x)
{
	SLInsert(ps, ps->size, x);
}
void SLPushFront1(SL* ps, SLDataType x)
{
	SLInsert(ps, 0, x);
}
//尾删，头删
void SLPopFront1(SL* ps)
{
	SLErase(ps, 0);
}
void SLPopBack1(SL* ps) 
{
	SLErase(ps, ps->size-1);

}

4.6查找 

实现函数：

int SLFind(SL* ps,SLDataType find)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
        //如果找到返回下标
		if (ps->arr[i] == find)
			return i;
	}
    //没找到返回小于0 的数
	return -1;
}

查找函数的使用：

	int find = SLFind(&s, 6);
	if (find < 0)
		printf("找不到\n");
	else
		printf("%d\n", find);

为什么没找到返回小于0的数？

因为存储的数据的下标都大于等于0。

 

 5.完整代码来喽！

test.c：（这就是我自己写代码使用的一些测试用例，大家可以自己写测试用例，自己测试，则一块不是很重要）

#include "SeqList.h"
void SLTest()
{
	SL s;
	SLInit(&s);
	//SLPrint(s);
	//SLPushBack(&s, 1);
	//SLPrint(s);
	//SLPushBack(&s, 2);
	//SLPrint(s);	
	//SLPushBack(&s, 3);
	//SLPrint(s);
	//SLPushBack(&s, 4);
	//SLPrint(s);
	SLPushBack(&s, 5);
	SLPrint(s);
	/*SLPushBack(NULL, 5);*/
	SLPushFront(&s, 6);
	SLPrint(s);
	SLPushFront(&s, 7);
	SLPrint(s);
	/*SLPushFront(NULL, 7);*/
	SLPopFront(&s);
	SLPrint(s);
	SLPopBack(&s);
	SLPrint(s);
	//SLPopFront(&s);
	//SLPrint(s);
	SLPopFront(&s);
	SLPrint(s);
	SLDestory(&s);
}
void SLTest1()
{
	SL s;
	SLInit(&s);
	SLPushFront(&s, 1);
	SLPushBack(&s, 2);
	SLPushBack(&s, 3);
	SLPrint(s);
	SLInsert(&s, 0, 4);
	SLPrint(s);
	SLInsert(&s,4,5);
	SLInsert(&s,3,6);
	SLPrint(s);
	SLErase(&s, 4);
	SLPrint(s);
	SLErase(&s, 0);
	SLPrint(s);
	int find = SLFind(&s, 6);
	if (find < 0)
		printf("找不到\n");
	else
		printf("%d\n", find);
	SLDestory(&s);
}
int main()
{
	/*SLTest();*/
	SLTest1();
	return 0;
}

SeqList.h

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

#define SLDataType int
typedef struct SeqList
{
	SLDataType* arr;
	int size;
	int capacity;
}SL;

//初始化
void SLInit(SL* ps);
void SLDestory(SL* ps);
//打印
void SLPrint(SL ps);
//尾插，尾删
void SLPushBack(SL* ps, SLDataType x);
void SLPushFront(SL* ps, SLDataType x);
//尾删，头删
void SLPopFront(SL* ps);
void SLPopBack(SL* ps);
//任意插，任意删
void SLInsert(SL* ps, int pos, SLDataType x);
void SLErase(SL* ps, int pos);
//查找
int SLFind(SL* ps,SLDataType find);

 

SeqList.c：

#include "SeqList.h"

void CheckSLCapacity(SL* ps)
{
	if (ps->capacity == ps->size)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SLDataType* tmp = (SLDataType*)realloc(ps->arr, newcapacity * sizeof(SLDataType));
		if (tmp == NULL)
		{
			perror("realloc");
			exit(-1);
		}
		//开辟成功
		ps->arr = tmp;
		ps->capacity = newcapacity;
	}
}

void SLInit(SL* ps)
{
	ps->arr = NULL;
	ps->size = 0;
	ps->capacity = 0;
}

void SLDestory(SL* ps)
{
	assert(ps);
	free(ps->arr);
	ps->arr = NULL;
	ps->size = 0;
	ps->capacity = 0;
}

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


void SLPushBack(SL* ps, SLDataType x)
{
	assert(ps != NULL);

	CheckSLCapacity(ps);
	ps->arr[ps->size] = x;
	ps->size++;
}

void SLPushFront(SL* ps, SLDataType x)
{
	assert(ps != NULL);
	CheckSLCapacity(ps);
	for (int i = ps->size; i>0; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[0] = x;
	ps->size++;
}


void SLPopBack(SL* ps)
{
	assert(ps != NULL);
	assert(ps->size > 0);
	ps->size--;
}

void SLPopFront(SL* ps)
{
	assert(ps != NULL);
	assert(ps->size > 0);
	for (int i = 0; i <ps->size-1 ; i++)
		ps->arr[i] = ps->arr[i + 1];
	ps->size--;
}

void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);
	CheckSLCapacity(ps);
	for (int i = ps->size; i>pos ; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[pos] = x;
	ps->size++;
}

void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	for (int i = pos; i < ps->size-1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;

}

int SLFind(SL* ps,SLDataType find)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == find)
			return i;
	}
	return -1;
}

结语：

头次写数据结构，放平心态 ，一定要写完一个接口调试一个接口，不要都写完了再去调试，若有一堆问题容易心态爆炸（boom）。

 拜拜，下一期。目标项目：通讯录。

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

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

相关文章

k8s calico由IPIP模式切换为BGP模式

k8s calico由IPIP模式切换为BGP模式

按照官网calico.yaml部署后&#xff0c;默认是IPIP模式 查看route -n &#xff0c; 看到是tunl0口进行转发 怎么切换到BGP模式呢&#xff1f; kubectl edit ippool 将ipipMode由Always修改为Never &#xff0c;修改后保存文件即可。无需做任何操作&#xff0c;自动就切换为BG…
阅读更多...
picgo启动失败解决

picgo启动失败解决

文章目录 报错信息原因分析解决方案 报错信息 打开Picgo&#xff0c;显示报错 A JavaScript error occurred in the main process Uncaught Exception: Error:ENOENT:no such file or directory,open ‘C:\Users\koko\AppData\Roaming\picgo\data.json\picgo.log’ 原因分析…
阅读更多...
绝不忽视！List.add方法揭秘：你绝对需要了解的覆盖现象

绝不忽视！List.add方法揭秘：你绝对需要了解的覆盖现象

文章目录 引言一、背景介绍1.1 事件背景1.2 List.add()方法简介示例影响 二、覆盖现象解决方案1. 每次循环创建新对象2. 使用工厂方法或建造者模式3. 深拷贝4. 不可变对象 三、解决方案1. 使用深拷贝2. 创建新对象3. 避免直接修改原对象 四、 结论 引言 在 Java 编程中&#x…
阅读更多...
MyBatis的基本应用

MyBatis的基本应用

源码地址 01.MyBatis环境搭建 添加MyBatis的坐标 <!--mybatis坐标--><dependency><groupId>org.mybatis</groupId><artifactId>mybatis</artifactId><version>3.5.9</version></dependency><!--mysql驱动坐…
阅读更多...
VSCode调试C++

VSCode调试C++

1、环境准备 1.1、g的安装与使用 1.1.1、安装 方式一&#xff1a;Xcode安装 苹果的开发集成工具是Xcode.app&#xff0c;其中包含一堆命令行工具。 在 App store 可以看到其大小有好几个G&#xff0c;有点大。 方式二&#xff1a;Command Line Tools 安装 Command Line Too…
阅读更多...
OpenHarmony实战：小型系统器件驱动移植

OpenHarmony实战：小型系统器件驱动移植

本章节讲解如何移植各类器件驱动。 LCD驱动移植 移植LCD驱动的主要工作是编写一个驱动&#xff0c;在驱动中生成模型的实例&#xff0c;并完成注册。 这些LCD的驱动被放置在源码目录//drivers/hdf_core/framework/model/display/driver/panel中。 创建Panel驱动 创建HDF驱动…
阅读更多...
高级数据结构与算法习题（6）

高级数据结构与算法习题（6）

一、单选题 1、In the Tic-tac-toe game, a "goodness" function of a position is defined as f(P)=Wcomputer​−Whuman​ where W is the number of potential wins at position P. In the following figure, O represents the computer and X the human. What i…
阅读更多...
农业保险利用卫星遥感监测、理赔、农作物风险评估

农业保险利用卫星遥感监测、理赔、农作物风险评估

​农业保险一直是农民和农业生产者面临的重要课题&#xff0c;而卫星遥感技术的不断发展正为农业保险带来全新的解决方案。通过高分辨率的卫星遥感监测&#xff0c;农业保险得以更精准、及时地评估农田状况&#xff0c;为农业经营者提供可靠的风险管理手段。 **1. 灾害监测与风…
阅读更多...
2024年第三期丨全国高校大数据与人工智能师资研修班邀请函

2024年第三期丨全国高校大数据与人工智能师资研修班邀请函

2024年第三期 杭州线下班 数据采集与机器学习实战&#xff08;Python&#xff09; 线上班 八大专题 大模型技术与应用实战 数据采集与处理实战&#xff08;Python&八爪鱼&#xff09; 大数据分析与机器学习实战&#xff08;Python&#xff09; 商务数据分析实战&…
阅读更多...
29.使线程以固定顺序输出结果

29.使线程以固定顺序输出结果

借助wait和notify方法控制线程以固定的顺序执行&#xff1a; /*** 控制输出字符的顺序&#xff0c;必须是固定顺序2,1* 采用wait-notify实现* param args*/public static void main(String[] args) {new Thread(() -> {synchronized (lock) {while (!isPrint2) {try {lock.…
阅读更多...
【c++】STl-list使用list模拟实现

【c++】STl-list使用list模拟实现

主页&#xff1a;醋溜马桶圈-CSDN博客 专栏&#xff1a;c_醋溜马桶圈的博客-CSDN博客 gitee&#xff1a;mnxcc (mnxcc) - Gitee.com 目录 1. list的介绍及使用 1.1 list的介绍 1.2 list的使用 1.2.1 list的构造 1.2.2 list iterator的使用 1.2.3 list capacity 1.2.4 …
阅读更多...
【Java】CAS详解

【Java】CAS详解

一.什么是CAS CAS(compare and swap) 比较并且交换. CAS是一个cpu指令,是原子的不可再分.因此基于CAS就可以给我们编写多线程的代码提供了新的思路---->使用CAS就不用使用加锁,就不会牵扯到阻塞,也称为无锁化编程 下面是一个CAS的伪代码: address是一个内存地址,expectVal…
阅读更多...
电脑便签软件怎么用 纯分享几款电脑便签软件

电脑便签软件怎么用 纯分享几款电脑便签软件

在当今快节奏的生活中&#xff0c;随时记录灵感、待办事项或重要信息变得越来越重要。电脑便签软件成为了我们日常生活中不可或缺的工具之一。本文将介绍几款常见的电脑便签软件&#xff0c;并分享它们的使用方法&#xff0c;帮助读者更好地管理信息和提高工作效率。 1. 敬业签…
阅读更多...
【ESP32S3 Sense接入语音识别+MiniMax模型+TTS模块语音播报】

【ESP32S3 Sense接入语音识别+MiniMax模型+TTS模块语音播报】

【ESP32S3 Sense接入语音识别MiniMax模型TTS模块语音播报】 1. 前言2. 功能模块概述2.1 语音接入2.2 大模型接入2.3 TTS模块接入 3. 先决条件3.1 环境配置3.2 所需零件3.3 硬件连接步骤 4. 核心代码4.1 源码分享4.2 代码解析 5. 上传验证5.1 对话测试5.2 报错 6. 总结 1. 前言 …
阅读更多...
NumPy的ndarray常用属性和索引你学会了吗

NumPy的ndarray常用属性和索引你学会了吗

1.ndarray的4个重要属性 ndim&#xff1a;返回数组的维度数。例如&#xff0c;一维数组的ndim为1&#xff0c;二维数组的ndim为2 shape&#xff1a;返回数组的形状&#xff0c;即各个维度的大小。例如&#xff0c;对于一个二维数组&#xff0c;shape会返回一个包含行数和列数的…
阅读更多...
Docker in Docker原理与实战探索

Docker in Docker原理与实战探索

博主猫头虎的技术世界 &#x1f31f; 欢迎来到猫头虎的博客 — 探索技术的无限可能&#xff01; 专栏链接&#xff1a; &#x1f517; 精选专栏&#xff1a; 《面试题大全》 — 面试准备的宝典&#xff01;《IDEA开发秘籍》 — 提升你的IDEA技能&#xff01;《100天精通鸿蒙》 …
阅读更多...
使用CyberRT写第一个代码

使用CyberRT写第一个代码

0. 简介 计算框架是自动驾驶系统中的重中之重&#xff0c;也是整个系统得以高效稳定运行的基础。为了实时地完成感知、决策和执行&#xff0c;系统需要一系列的模块相互紧密配合&#xff0c;高效地执行任务流。由于各种原因&#xff0c;这些模块可能位于不同进程&#xff0c;也…
阅读更多...
Android Studio 打开Logcat界面

Android Studio 打开Logcat界面

在平时调试过程中查看调试日志需要打开 Android Studio Logcat界面。 每次安装AS都会忘记&#xff0c;自己备注一下。 AS->View->Tool Windows->Logcat
阅读更多...
Windows12安装Docker

Windows12安装Docker

环境及工具&#xff08;文末提供&#xff09; Docker Desktop Installer.exe &#xff08;官网&#xff09; 一、查看windows相关配置 查看是否开启相应的功能&#xff0c;如果没有需要开启&#xff0c;然后重启电脑 打开任务管理器&#xff08;CTRLSHIFTESC&#xff09;-&g…
阅读更多...
【Linux】进程控制详解

【Linux】进程控制详解

目录 前言 进程创建 认识fork 写时拷贝 再谈fork 进程终止 进程退出码 用代码来终止进程 常见的进程终止的方式 exit _exit 进程等待 进程等待的必要性 进程等待的方式 wait waitpid 详解status参数 详解option参数 前言 本文适合有一点基础的人看的&#…
阅读更多...
最新文章

Copyright @ 2022~2023