数据结构 顺序表1

1. 何为顺序表:

        顺序表是一种线性数据结构,是由一组地址连续的存储单元依次存储数据元素的结构,通常采用数组来实现。顺序表的特点是可以随机存取其中的任何一个元素,并且支持在任意位置上进行插入和删除操作。在顺序表中,每个元素的下标都是唯一的,而且在顺序表中,相邻的元素在内存中也是相邻的。

        顺序表通常包含两个重要的属性:容量和长度。容量指该顺序表所能容纳的最大元素数量,而长度指当前已经存储的元素数量。当长度等于容量时,顺序表就已经满了,不能再插入元素。

2. 静态顺序表和动态顺序表的区别:

        由于顺序表底层是用数组完成的,所以这个数组决定了我们这个顺序表的大小,同时也区分出了静态顺序表与动态顺序表,下面我们来一一了解:

        静态顺序表:有着静态两字顾名思义则这个顺序表写好以后大小就固定死了,是不可以改变的(为了方便我们后期更改顺序表的类型,此处我们define定义一个变量,专门存放顺序表类型

typedef int SLDataTYpe;

typedef struct SeqList
{
	SLDataTYpe p[50];	//数组大小为50,代表这个顺序表可以存储50个元素
	int size;   //顺序表有效数据个数
	int capacity;	//顺序表空间大小
}SL;   //将顺序表struct SeqList取别名为SL

        动态顺序表:相较于静态,动态顺序表则在定义顺序表是写死数据的大小,而是定义了一个指针,等到后边需要用到顺序表的时候,再动态分配内存空间(C语言动态内存空间分配-CSDN博客)

typedef int SLDataTYpe;

typedef struct SeqList
{
	SLDataTYpe* p;
	int size;   //顺序表有效数据个数
	int capacity;	//顺序表空间大小
}SL;   //将顺序表struct SeqList取别名为SL

3. 顺序表的实现:

        在本次项目当中我们以动态顺序表为例,来对顺序表各类功能的实现,项目文件分为SeqList.h(顺序表中各类函数的声明),SeqList.c(顺序表各类功能的实现),SeqList_test(对应顺序表各类功能的测试),实现环境为VS2022

3.1. 顺序表的初始化:

        在SeqList.h声明一个函数用于实现顺序表的初始化,同时传入一个顺序表变量,SeqList.c实现顺序表的初始化,顺序表没被调用前,顺序表为NULL(注:要想调用SeqList.h中声明好的方法,则得包含该方法所在的头文件

SeqList.h:

#pragma once
#include <stdio.h>
typedef int SLDataTYpe;

//动态顺序表
typedef struct SeqList
{
	SLDataTYpe* p;
	int size;   //顺序表有效数据个数
	int capacity;	//顺序表空间大小
}SL;    //将顺序表struct SeqList取别名为SL

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

SeqList.c:

#define _CRT_SECURE_NO_WARNINGS 1
#include "SeqList.h"    //头文件包含

//顺序表初始化的实现
void SLInit(SL* ps)
{
	ps->p = NULL;   
	ps->size = 0;    //有效数据个数为0
	ps->capacity = 0;    //空间大小为0
}

  SeqList_test(在SeqList_test中调用SLInit函数,打开监视查看是否赋值成功):

void SLTest01()
{
	SL s1;
	SLInit(&s1);
	
}

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

测试结果:

(如上图所示,则初始化成功)

3.2. 顺序表的销毁:

        顺序表的销毁分为两种情况,一是顺序表已写入数据,二是没有写入数据

SeqList.h:

#pragma once
#include <stdio.h>
typedef int SLDataTYpe;

//动态顺序表
typedef struct SeqList
{
	SLDataTYpe* p;
	int size;   //顺序表有效数据个数
	int capacity;	//顺序表空间大小
}SL;    //将顺序表struct SeqList取别名为SL

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

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

SeqList.c:

#define _CRT_SECURE_NO_WARNINGS 1
#include "SeqList.h"

//顺序表初始化的实现
void SLInit(SL* ps)
{
	ps->p = NULL;
	ps->size = 0;
	ps->capacity = 0;
}

//顺序表的销毁
void SLDesttroy(SL* ps)
{
	if (ps->p)    //判断是否为NULL
	{
		free(ps->p);
	}
	ps->p = NULL;
	ps->size = 0;
	ps->capacity = 0;
}

(由于代码量的缘故,后边只展示对应文件中要添加的代码)

3.3. 顺序表插入数据:

        为了方便展示,关于SeqList.h文件当中的代码,统一展示在此处

//顺序表头部插入删除 / 尾部插入删除
void SLPushBack(SL* ps, SLDataTYpe x);
void SLPushFront(SL* ps, SLDataTYpe x);

void SLPopBack(SL* ps);
void SLPopFront(SL* ps);

//在指定位置之前插入数据
void SLInsert(SL* ps, int pos, SLDataTYpe x);

//删除指定位置数据
void SLErase(SL* ps, int pos);

3.3.1. 头插:

头插可以分为以下几点:

1. 函数传参:

void SLPushFront(SL* ps, SLDataTYpe x);   //x为要插入的元素

2. 判断顺序表是否为空:

#include <assert.h>    //头文件包含
assert(ps);    //ps为要断言的变量

3. 判断顺序表空间是否够用:

由于后续我们要多次判断是否要增容,此处我们重新用一个函数完成顺序表的增容:

(注:realloc函数如果申请内存空间失败,则返回NULL,所以此处不可将realloc申请的空间直接赋给p->p这样会导致原来p->p中的数据全部清空,应先判断增容是否成功,再进行赋值)

void SLcheckCapacity(SL* p)
{
	//插入数据前判断空间是否足够 如果数组大小与内存总大小相等,则申请空间
	if (p->size == p->capacity)
	{
		//判断capacity的值是否为0,不为0则2倍增容
		int newcapacity = p->capacity == 0 ? 4 : 2 * p->capacity;
		//增容空间
		SLDataTYpe* tmp = (SLDataTYpe*)realloc(p->p, 2 * newcapacity * sizeof(SLDataTYpe));
		//判断增容是否成功
		if (tmp == NULL)
		{
			perror("relloc fail");
			exit(1);
		}
		//申请成功以后
		p->p = tmp;
		p->capacity = newcapacity;
	}
}

4. 头部插入数据:

        假设一个数组中已有数据a,b,c,d,现在要在头部添加一个元素f,我们应该如何添加?

思路分析:

代码实现(SeqList.c):

void SLPushFront(SL* ps, SLDataTYpe x)
{
	//判断ps是否为NULL
	assert(ps);
	//判断内存空间是否足够,是否需要增容
	SLcheckCapacity(ps);
	//将顺序表中原有的数据整体往后挪一位
	for (int i = ps->size; i > 0; i--)
	{
		ps->p[i] = ps->p[i - 1];
	}
    //添加元素
	ps->p[0] = x;
    //size向后挪动一位
	ps->size++;
}

3.3.2. 尾插:

         假设一个数组中已有数据a,b,c,d,现在要在最后添加一个元素f,我们应该如何添加?

思路分析:

代码实现(SeqList.c):

void SLPushBack(SL* ps, SLDataTYpe x)
{
	//判断ps是否为NULL
	assert(ps);
    //判断内存空间是否足够,是否需要增容
	SLcheckCapacity(ps);
	ps->p[ps->size++] = x;
	
}

3.3.3 头删:

        将除首地址的元素外其余所以元素往前挪动一位,同时size也需往前挪动一位(size--),覆盖首元素即可(注:如果数组中没有元素,即size=0,此时是没有元素可以删的,所以此处应还需断言size是否为0)

思路分析:

代码实现(SeqList.c):

void SLPopFront(SL* ps)
{
    //判断ps是否为NULL
	assert(ps);
    //判断数组是否为空
	assert(ps->size);
	for (int i = 0; i < ps->size - 1; i++)
	{
		ps->p[i] = ps->p[i + 1];
	}
	ps->size--;
}

3.3.4 尾删:

        当数组不为空时,size往前挪一位(注size代表的是数组的大小,即下标+1,也就是说size前边为整个数组,因此删除末尾元素时,我们只需要将size--即可)

思路分析:

代码实现(SeqList.c):

void SLPopBack(SL* ps)
{
	//断言
	assert(ps);
	//判断顺序表是否为NULL,为空删除等于-1,越界
	assert(ps->size);
	//删除数据
	ps->size--;
}

3.3.5 指定位置添加数据:

        与头插相类似,此处只需要将指定位置的数据整体往后挪一位size++,由于和头插相类似,就不在此处重复直接看代码:

void SLInsert(SL* ps, int pos, SLDataTYpe x)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);	//判断pos的有效范围
	//插入数据:空间够不够
	SLcheckCapacity(ps);
	//让pos下标对应的数据,全部往后挪一位
	for (int i = ps->size; i > pos; i--)
	{
		ps->p[i] = ps->p[i - 1];
	}
	ps->p[pos] = x;
	ps->size++;

}

3.3.6 指定位置删除数据:

        与添加相反,删除指定对应数据以后,指定位置后的元素整体往前挪一位,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->p[i] = ps->p[i + 1];
	}
	ps->size--;
}

3.4 顺序表的打印:

        遍历数组

代码实现(SeqList.h  / SeqList.c):

//顺序表的打印
void SLPrintf(SL s);
void SLPrintf(SL s)
{
	//打印
	for (int i = 0; i < s.size; i++)
	{
		printf("%d ", s.p[i]);
	}
	printf("\n");
}

3.5 顺序表的查找:

        遍历数组,查找对应的元素,存在返回元素的下标,不存在返回无效下标-1

代码实现(SeqList.h  / SeqList.c):

//查找
int SLFind(SL* ps, SLDataTYpe x);  //数据有,返回值的下标,否则返回-1
查找
int SLFind(SL* ps, SLDataTYpe x)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->p[i] == x)
		{
			//找到了
			return i;
		}
	}
	//没找到
	return -1;
}

4.实现代码:

SeqList.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLDataTYpe;
//动态顺序表
typedef struct SeqList
{
	SLDataTYpe* p;
	int size;   //顺序表有效数据个数
	int capacity;	//顺序表空间大小
}SL;

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

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

//顺序表头部插入删除 / 尾部插入删除
void SLPushBack(SL* ps, SLDataTYpe x);
void SLPushFront(SL* ps, SLDataTYpe x);

void SLPopBack(SL* ps);
void SLPopFront(SL* ps);

//在指定位置之前插入数据
void SLInsert(SL* ps, int pos, SLDataTYpe x);

//删除指定位置数据
void SLErase(SL* ps, int pos);

//顺序表的打印
void SLPrintf(SL s);

//查找
int SLFind(SL* ps, SLDataTYpe x);  //数据有,返回值的下标,否则返回-1

SeqList.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "SeqList.h"

//顺序表初始化的实现
void SLInit(SL* ps)
{
	ps->p = NULL;
	ps->size = 0;
	ps->capacity = 0;
}

//顺序表的销毁
void SLDesttroy(SL* ps)
{
	if (ps->p)
	{
		free(ps->p);
	}
	ps->p = NULL;
	ps->size = 0;
	ps->capacity = 0;
}

//增容
void SLcheckCapacity(SL* p)
{
	//插入数据前判断空间是否足够 如果数组大小与内存总大小相等,则申请空间
	if (p->size == p->capacity)
	{
		//判断capacity的值是否为0
		int newcapacity = p->capacity == 0 ? 4 : 2 * p->capacity;
		//增容空间
		SLDataTYpe* tmp = (SLDataTYpe*)realloc(p->p, 2 * newcapacity * sizeof(SLDataTYpe));
		//判断增容是否成功
		if (tmp == NULL)
		{
			perror("relloc fail");
			exit(1);
		}
		//申请成功以后
		p->p = tmp;
		p->capacity = newcapacity;
	}
}

//顺序表的尾插
void SLPushBack(SL* ps, SLDataTYpe x)
{
	//判断ps是否为NULL
	assert(ps);
	SLcheckCapacity(ps);
	ps->p[ps->size++] = x;
	
}

//头插
void SLPushFront(SL* ps, SLDataTYpe x)
{
	//判断ps是否为NULL
	assert(ps);
	//增容
	SLcheckCapacity(ps);
	//将顺序表中原有的数据整体往后挪一位
	for (int i = ps->size; i > 0; i--)
	{
		ps->p[i] = ps->p[i - 1];
	}
	ps->p[0] = x;
	ps->size++;
}

//顺序表的打印
void SLPrintf(SL s)
{
	//打印
	for (int i = 0; i < s.size; i++)
	{
		printf("%d ", s.p[i]);
	}
	printf("\n");
}

//尾删
void SLPopBack(SL* ps)
{
	//断言
	assert(ps);
	//判断顺序表是否为NULL,为空删除等于-1,越界
	assert(ps->size);
	//删除数据
	ps->size--;
}

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

//在指定位置之前插入数据
void SLInsert(SL* ps, int pos, SLDataTYpe x)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);	//判断pos的有效范围
	//插入数据:空间够不够
	SLcheckCapacity(ps);
	//让pos下标对应的数据,全部往后挪一位
	for (int i = ps->size; i > pos; i--)
	{
		ps->p[i] = ps->p[i - 1];
	}
	ps->p[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->p[i] = ps->p[i + 1];
	}
	ps->size--;
}

//查找
int SLFind(SL* ps, SLDataTYpe x)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->p[i] == x)
		{
			//找到了
			return i;
		}
	}
	//没找到
	return -1;
}

SeqList_test.c(测试代码)

#define _CRT_SECURE_NO_WARNINGS 1
#include "SeqList.h"

void SLTest01()
{
	SL s1;
	SLInit(&s1);
	
}

int main()
{
	SLTest01();
	return 0;
}
尾插
//SLPushBack(&s1, 1);
//SLPushBack(&s1, 2);
//SLPushBack(&s1, 3);
//SLPushBack(&s1, 4);
//SLPrintf(s1);
//SLPushBack(&s1, 5);
//SLPrintf(s1);
//SLPushFront(&s1, 5);
//SLPushFront(&s1, 6);
//SLPrintf(s1);
//
//
销毁
//SLDesttroy(&s1);

(有需要的小伙伴自取喔,最后还请点赞三联支持一下博主,Thanks♪(・ω・)ノ!!!)

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

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

相关文章

【DDR 终端稳压器】Sink and Source DDR Termination Regulator [C] S0 S1 S2 S3 S4 S5 6状态

TPS51200A-Q1 器件通过 EN 功能提供 S3 支持。EN引脚可以连接到终端应用中的SLP_S3信号。当EN 高电平&#xff08;S0 状态&#xff09;时&#xff0c;REFOUT 和 VO 引脚均导通。当EN 低电平&#xff08;S3状态&#xff09;时&#xff0c;VO引脚关断并通过内部放电MOSFET放电时…

【AI Engine Series】[AI Engine Series 3 - Introduction to AI Engine kernels

AI Engine Series 3 - Introduction to AI Engine kernels 双击summary 进入analyzer AI Engine Series 6 - Analyzing AI Engine compilation results in Vitis Analyzer (2022.1 update) [connectivity] stream_connectM_AXIS_ADDER:ai_engine_0.DataIn1 stream_connecta…

C语言(指针)7

Hi~&#xff01;这里是奋斗的小羊&#xff0c;很荣幸各位能阅读我的文章&#xff0c;诚请评论指点&#xff0c;关注收藏&#xff0c;欢迎欢迎~~ &#x1f4a5;个人主页&#xff1a;小羊在奋斗 &#x1f4a5;所属专栏&#xff1a;C语言 本系列文章为个人学习笔记&#x…

网络安全ctf比赛_学习资源整理,解题工具、比赛时间、解题思路、实战靶场、学习路线,推荐收藏!...

对于想学习或者参加CTF比赛的朋友来说&#xff0c;CTF工具、练习靶场必不可少&#xff0c;今天给大家分享自己收藏的CTF资源&#xff0c;希望能对各位有所帮助。 CTF在线工具 首先给大家推荐我自己常用的3个CTF在线工具网站&#xff0c;内容齐全&#xff0c;收藏备用。 1、C…

算法练习第21天|216.组合总和|||、17.电话号码的字母组合

216.组合总和 III 216. 组合总和 III - 力扣&#xff08;LeetCode&#xff09;https://leetcode.cn/problems/combination-sum-iii/ 题目描述&#xff1a; 找出所有相加之和为 n 的 k 个数的组合&#xff0c;且满足下列条件&#xff1a; 只使用数字1到9每个数字 最多使用一…

ICode国际青少年编程竞赛- Python-5级训练场-带参数函数

ICode国际青少年编程竞赛- Python-5级训练场-带参数函数 1、 def get_item(a):Dev.step(a)Dev.step(-a) get_item(4) Spaceship.step(2) get_item(2) Spaceship.step(3) get_item(5) Spaceship.step(2) get_item(3) Spaceship.step(3) get_item(4)2、 def get_item(a): D…

超链接a的应用

主要作用&#xff1a;从当前页面进行跳转 1.跳转到页面 <!-- 跳转到其他页面 --><a href"#" target"_blank">鸡你太美</a> <!-- 跳转到本地页面 --><a href"#" target"_self">鸡你太美</a> 2.跳转…

AI大事记(持续更新)

文章目录 前言 一、人工智能AI 1.基本概念 2.相关领域 2.1基础设施 2.2大模型 2.3大模型应用 二、大事记 2024年 2024-05-14 GPT-4o发布 2024-02-15 Sora发布 2023年 2023-03-14 GPT-4.0发布 2022年 2022-11-30 ChatGPT发布 总结 前言 2022年11月30日openai的…

jdk安装多个版本,但是java -version显示最早安装的版本,换掉Path或者JAVA_HOME不生效问题

问题一&#xff1a;当你的电脑上又多个jdk版本&#xff0c;如17 或者8时&#xff0c;使用命令行 java -version显示最早安装的&#xff0c;如下图所示&#xff1a;环境变量配置的17&#xff0c;但是命令行显示的是8。 原因&#xff1a;windows电脑装jdk17后 会在你的环境变量…

C for Graphic:遮罩显示(一)

模板缓冲一般用于遮罩渲染的功能&#xff0c;其原理很以前聊过&#xff08;模板缓冲原理&#xff09;&#xff0c;就不再啰嗦了。 现在实现一个功能&#xff1a;使用一个长方体&#xff08;或任意物体&#xff09;遮罩渲染对象&#xff08;比如一个球&#xff09;。 …

Linux下COOLFluiD源码编译安装及使用

目录 软件介绍 基本依赖 其它可选依赖 一、源码下载 二、解压缩&#xff08;通过Github下载zip压缩包格式&#xff09; 三、编译安装 3.1 依赖项-BOOST 3.2 依赖项-Parmetis 3.3 依赖项-PETSc 3.4 安装COOLFluiD 四、算例运行 软件介绍 COOLFluiD&#xff08;面向对象…

Autoware内容学习与初步探索(一)

0. 简介 之前作者主要是基于ROS2&#xff0c;CyberRT还有AutoSar等中间件完成搭建的。有一说一&#xff0c;这种从头开发当然有从头开发的好处&#xff0c;但是如果说绝大多数的公司还是基于现成的Apollo以及Autoware来完成的。这些现成的框架中也有很多非常好的方法。目前作者…

深度学习之激活函数——ReLU

ReLU 整流线性单元(ReLU)&#xff0c;全称Rectified linear unit&#xff0c;是现代神经网络中最常用的激活函数&#xff0c;大多数前馈神经网络都默认使用该激活函数。 函数表达式 f ( x ) m a x { 0 , x } f(x)max\{0,x\} f(x)max{0,x} 当 x < 0 x<0 x<0时&…

5月14(信息差)

&#x1f30d;字节携港大南大升级 LLaVA-NeXT&#xff1a;借 LLaMA-3 和 Qwen-1.5 脱胎换骨&#xff0c;轻松追平 GPT-4V Demo 链接&#xff1a;https://llava-next.lmms-lab.com/ &#x1f384;阿里巴巴开源的15个顶级Java项目 ✨ 欧洲在线订餐服务Takeaway.com&#xff1a…

数据结构与算法学习笔记十二-二叉树的顺序存储表示法和实现(C语言)

目录 前言 1.数组和结构体相关的一些知识 1.数组 2.结构体数组 3.递归遍历数组 2.二叉树的顺序存储表示法和实现 1.定义 2.初始化 3.先序遍历二叉树 4.中序遍历二叉树 5.后序遍历二叉树 6.完整代码 前言 二叉树的非递归的表示和实现。 1.数组和结构体相关的一些知…

第五课,输入函数、布尔类型、比较运算和if判断

一&#xff0c;输入函数input() 与输出函数print()相对应的&#xff0c;是输入函数input()&#xff0c;前者是把程序中的数据展示给外界&#xff08;比如电脑屏幕上&#xff09;&#xff0c;而后者是把外界&#xff08;比如键盘&#xff09;的数据输入进程序中 input()函数可…

秋招算法——背包模型——423采药问题——模板:背包问题

文章目录 题目描述思路分析实现代码分析总结 题目描述 思路分析 这里明显是使用背包问题&#xff0c;所以这里参考一下背包这个模板题的内容这个是朴素版的模板&#xff0c;没有经过代码的优化 #include <iostream> #include <algorithm>using namespace std;con…

字符串函数(二):strlen(求长度),strstr(查找子串),strtok(分割),strerror(打印错误信息)

字符串函数 一.strlen&#xff08;求字符串长度&#xff09;1.函数使用2.模拟实现&#xff08;三种方法&#xff09; 二.strstr&#xff08;字符串查找子串&#xff09;1.函数使用2.模拟实现 三.strtok&#xff08;字符串分割&#xff09;四.strerror&#xff0c;perror&#x…

24点游戏679

题目描述&#xff1a; 给定一个长度为4的整数数组 cards 。你有 4 张卡片&#xff0c;每张卡片上都包含一个范围在 [1,9] 的 数字。您应该使用运算符 [, -, *, /] 和括号 ( 和 ) 将这些卡片上的数字排 列成数学表达式&#xff0c;以获得值24。你须遵守以下规则: &#xff08;1&…

AI大模型日报#0514:OpenAI GPT-4o震撼发布、我是如何赢得GPT-4提示工程大赛冠军的

导读&#xff1a;欢迎阅读《AI大模型日报》&#xff0c;内容基于Python爬虫和LLM自动生成。目前采用“文心一言”生成了今日要点以及每条资讯的摘要。《AI大模型日报》今日要点&#xff1a;OpenAI在春季新品发布会上推出全能模型GPT-4o及桌面App&#xff0c;颠覆科技界。GPT-4o…