数据结构--顺序表

目录

1.顺序表

1.1顺序表的概念及结构

线性表

 2、顺序表分类

2.1顺序表和数组的区别

静态顺序表

动态顺序表

3.顺序表的实现

 3.1初始化

随后便可对顺序表初始化

3.2插入数据

尾插

头插

 在指定位置插入数据

顺序表的查找

头删、尾删及指定位置删除

实现代码：

1.顺序表

1.1顺序表的概念及结构

线性表

线性表（ linear list ）是n个具有相同特性的数据元素的有限序列。 线性表是⼀种在实际中⼴泛使⽤的数据结构，常⻅的线性表：顺序表、链表、栈、队列、字符串...
线性表在逻辑上是线性结构，也就说是连续的⼀条直线。但是在物理结构上并不⼀定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。
案例：蔬菜分为绿叶类、⽠类、菌菇类。

 2、顺序表分类

2.1顺序表和数组的区别

顺序表的底层结构是数组，对数组的封装，实现了常⽤的增删改查等接⼝

  • 静态顺序表

struct SeqList
{int arr[100];//定长数组int size;//顺序表当前的数据个数
};

概念：使用定长数组存放元素

缺陷：空间给少了不够⽤，给多了造成空间浪费

  • 动态顺序表

struct SeqList
{int *arr;int size;//有效的数据个数int capacity;//空间大小
};

因为数组并不是定长的，可根据实际数据大小进行动态申请空间，随着数据的增加，也可进行动态增容。

3.顺序表的实现

分成三个文件实现：

SeqList.h

SeqList.c

test.c

 3.1初始化

首先在SeqList.h创建好顺序表的结构

typedef int SLDataType;//顺序表存放的类型可能是int 也可能是char，
所有重新起个名字，方便以后更改
//动态顺序表
typedef struct SeqList
{SLDataType* arr;int size;//有效数据个数int capacity;//空间大小
}SL;

随后便可对顺序表初始化

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

3.2插入数据

在插入数据之前首先要判断空间是否为0，空间是否足够，

若不够，一次应增容多少？

通常来说增容是成倍的增长，一般是2倍或3倍

因此，创建一个函数SLCheckCapacity专门实现增容，每次插入数据之前需调用一次函数

void SLCheckCapacity(SL* ps)
{//插入数据之前先看空间够不够if (ps->capacity == ps->size){//申请空间-->增容reallocint newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;//三目表达式 判断capacity是否为0 是：赋值为4 否：赋值为2 * ps->capacity//增容通常来说是成倍数的增加，一般是2或3倍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)
{//防止ps可能为NULLassert(ps);//等价于assert(ps!=NULL);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--)//数组下标不会为-1{ps->arr[i] = ps->arr[i - 1];}ps->arr[0] = x;//头插ps->size++;
}

 在指定位置插入数据

创建一个变量pos存放指定位置，然后把pos之后的数据整体往后移动一位，在pos位置插入所需要的数据即可。

//在指定位置之前插入数据
void SLlnsert(SL* ps, int pos, SLDataType x)//pos：指定的位置 x：插入的数据
{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];//arr[pos+1]=arr[pos] 最后下标为pos位置为空}ps->arr[pos] = x;//在pos位置插入数据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;
}

头删、尾删及指定位置删除

与插入数据原理一样，只需在所需的位置删除数据即可

实现代码：

SeqList.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
//定义顺序表的结构//#define N 100静态顺序表
//struct SeqList
//{
//	int arr[N];
//	int size;//有效数据个数
//};typedef int SLDataType;//顺序表存放的类型可能是int 也可能是char，所有重新起个名字，方便以后更改
//动态顺序表
typedef struct SeqList
{SLDataType* arr;int size;//有效数据个数int capacity;//空间大小
}SL;//顺序表初始化
void SLlnit(SL* ps);
//顺序表的销毁
void SLDestroy(SL* ps);
//顺序表的打印
void SLprint(SL s);//头部插入删除/尾部插入删除
void SLPushBack(SL* ps, SLDataType x);
void SLPushFront(SL* ps, SLDataType x);void SLPopBack(SL* ps);
void SLPopFront(SL* ps);//指定位置之前插入/删除数据
void SLlnsert(SL* ps,int pos,SLDataType x );
void SLErase(SL* ps, int pos);//查找
int SLFind(SL* ps, SLDataType x);

SeqList.c

#include"SeqList.h"
void SLlnit(SL* ps)//顺序表初始化
{ps->arr = NULL;ps->size = ps->capacity=0;
}
//顺序表的销毁
void SLDestroy(SL* ps)
{if (ps->arr)//等价于 if(ps->!=NULL){free(ps-> arr);//释放空间}ps->arr = NULL;ps->size = ps->capacity = 0;
}void SLCheckCapacity(SL* ps)
{//插入数据之前先看空间够不够if (ps->capacity == ps->size){//申请空间-->增容reallocint newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;//三目表达式 判断capacity是否为0 是：赋值为4 否：赋值为2 * ps->capacity//增容通常来说是成倍数的增加，一般是2或3倍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)
{//防止ps可能为NULLassert(ps);//等价于assert(ps!=NULL);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--)//数组下标不会为-1{ps->arr[i] = ps->arr[i - 1];}ps->arr[0] = x;//头插ps->size++;
}
//打印顺序表
void SLprint(SL s)
{for (int i = 0; i < s.size; i++){printf("%d ", s.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];}ps->size--;//删除
}
//在指定位置之前插入数据
void SLlnsert(SL* ps, int pos, SLDataType x)//pos：指定的位置 x：插入的数据
{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];//arr[pos+1]=arr[pos] 最后下标为pos位置为空}ps->arr[pos] = x;//在pos位置插入数据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];//pos位置后的数据全部往前挪动一位}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

#include<SeqList.h>
void SLTest01()//测试
{SL sl;//初始化SLlnit(&sl);//尾插SLPushBack(&sl, 1);//打印顺序表SLprint(sl);//头插SLPushFront(&sl,1);SLPushFront(&sl, 2);SLPushFront(&sl, 3);SLPushFront(&sl, 4);SLprint(sl);SLPopBack(&sl);SLprint(sl);//测试指定位置之前插入数据SLlnsert(&sl, 3, 90);SLprint(sl);//删除指定位置的数据SLErase(&sl, 4);SLprint(sl);int a=SLFind(&sl, 40);if (a >= 0){printf("找到了，下标是：%d\n", a);}else{printf("没找到\n");}SLDestroy(&sl);}
int main()
{SLTest01();return 0;
}

感谢观看，再见

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

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

汽车R155法规中，汽车获取到的VTA证书，E后面的数字表示什么意思？

汽车R155法规中，汽车获取到的VTA证书，E后面的数字表示什么意思？

标签&#xff1a; 汽车R155法规中&#xff0c;汽车获取到的VTA证书&#xff0c;E后面的数字表示什么意思&#xff1f;&#xff1b; 汽车&#xff1b;VTA认证; 有些厂商汽车拿到的VTA证书上面写着E9&#xff0c; 有些厂商汽车拿到的VTA证书上面写着E5&#xff0c;E9与E5有什么差…
阅读更多...
primeflex样式库笔记 Display相关的案例

primeflex样式库笔记 Display相关的案例

回顾 宽度设置的基本总结 w-full&#xff1a;表示widtdh&#xff1a;100%&#xff1b;占满父容器的宽度。 w-screen&#xff1a;表示占满整个屏幕的宽度。 w-1到w-12&#xff0c;是按百分比划分宽度&#xff0c;数字越大&#xff0c;占据的比例就越大。 w-1rem到w-30rem&…
阅读更多...
Vitis HLS 学习笔记--控制驱动任务示例

Vitis HLS 学习笔记--控制驱动任务示例

目录 1. 简介 2. 代码解析 2.1 kernel 代码回顾 2.2 功能分析 2.3 查看综合报告 2.4 查看 Schedule Viewer 2.5 查看 Dataflow Viewer 3. Vitis IDE的关键设置 3.1 加载数据文件 3.2 设置 Flow Target 3.3 配置 fifo 深度 4. 总结 1. 简介 本文对《Vitis HLS 学习…
阅读更多...
零拷贝(Zero-Copy)

零拷贝(Zero-Copy)

1.背景 现在有这样一个场景&#xff0c;我们需要在本地选择一个文件后&#xff0c;然后上传到网络上。 我们再看看文件的内容数据的具体搬运过程&#xff1a; 你会发现&#xff0c;在整个文件搬运的过程中&#xff0c;发生了多次的数据拷贝和上下文转换。 4次数据拷贝&#…
阅读更多...
Git总结超全版

Git总结超全版

最近想系统的回顾一下Git的使用&#xff0c;如果只想快速的集成git到idea&#xff0c;可以参考另一篇我的博客中的git部分 目录 版本管理工具简介Git安装与配置Git远程仓库配置 Git常用命令为常用命令配置别名(可选)Git忽略文件.gitignore一些概念*本地仓库操作删除仓库内容 *远…
阅读更多...
Wireshark 4.2.5：发现 QUIC 和 VXLAN 协议的新功能

Wireshark 4.2.5：发现 QUIC 和 VXLAN 协议的新功能

Wireshark 是一种先进且广泛使用的网络协议分析仪&#xff0c;最近发布了新版本 4.2.5&#xff0c;它提供了许多新功能和改进。 Wireshark 4.2.5 发行说明 什么是 Wireshark&#xff1f; Wireshark 是世界上最流行的网络协议分析器。它用于故障排除、分析、开发和教育。 Wiresh…
阅读更多...
Elasticsearch 分析器的高级用法一（同义词，高亮搜索）

Elasticsearch 分析器的高级用法一（同义词，高亮搜索）

Elasticsearch 分析器的高级用法一&#xff08;同义词&#xff0c;高亮搜索&#xff09; 同义词简介分析使用同义词案例 高亮搜索高亮搜索策略unifiedplainvh 同义词 简介 在搜索场景中&#xff0c;同义词用来处理不同的查询词&#xff0c;有可能是想表达相同的搜索目标。 例…
阅读更多...
系统架构师考试（九）

系统架构师考试（九）

TCP/IP协议族 SMTP是简单邮件传输协议 DNS 域名解析协议 URL - IP&#xff0c;通过URL解析ip是哪一台电脑 DHCP 动态IP地址分配的协议 SNMP 简单网络管理协议 TFTP 简单文件管理协议 ICMP 是网络中差错校验&#xff0c;差错报错的协议 IGMP G是组&#xff0c;组…
阅读更多...
Hadoop3：客户端向HDFS写数据流的流程讲解（较枯燥）

Hadoop3：客户端向HDFS写数据流的流程讲解（较枯燥）

一、场景描述 我们登陆HDFS的web端&#xff0c;上传一个大文件。 二、流程图 三、讲解 流程1&#xff08;Client与NameNode交互&#xff09; 1、HDFS client创建DistributedFileSystem&#xff0c;通过dfs与NameNode进行2次&#xff08;一来一回4次&#xff09;对话&#x…
阅读更多...
了解K8s集群kubectl命令进行陈述式资源管理

了解K8s集群kubectl命令进行陈述式资源管理

前言 在 Kubernetes 集群中&#xff0c;通过陈述式和声明式资源管理是确保应用程序高效运行的关键。认识这两种管理方法&#xff0c;能够更好地掌握 Kubernetes 集群的运维和管理。 目录 一、K8s 资源管理操作分类 1. 陈述式 2. 声明式 3. K8s 集群管理常用命令概览 二…
阅读更多...
Docker Desktop安装和如何在WSL2中使用Docker

Docker Desktop安装和如何在WSL2中使用Docker

最近在使用WSL的过程中&#xff0c;想使用docker遇到了一些问题&#xff0c;在WSL中安装Linux版本的docker&#xff0c;启动镜像之后不能从Windows机器的端口映射出来&#xff0c;查了一圈之后&#xff0c;发现应该使用Docker Desktop软件&#xff0c;下面是安装和使用的方式 …
阅读更多...
2、xss-labs之level2

2、xss-labs之level2

1、打开页面 2、传入xss代码 payload&#xff1a;<script>alert(xss)</script>&#xff0c;发现返回<script>alert(xss)</script> 3、分析原因 打开f12&#xff0c;没什么发现 看后端源码&#xff0c;在这form表单通过get获取keyword的值赋给$str&am…
阅读更多...
基于Keras的手写数字识别(附源码)

基于Keras的手写数字识别(附源码)

目录 引言 为什么要创建虚拟环境&#xff0c;好处在哪里&#xff1f; 源码 我修改的部分 调用本地数据 修改第二层卷积层 引言 本文是博主为了记录一个好的开源代码而写&#xff0c;下面是代码出处&#xff01;强烈建议收藏&#xff01;【深度学习实战—1】&#xff1a…
阅读更多...
Spring Web MVC(2)

Spring Web MVC(2)

响应 Http响应的结果可以是数据也可以是静态页面可以针对响应设置状态码 Header信息 返回静态页面注解RestController和Controller 我们创建一个前端页面 package com.example.demo.demos.web.controller;import org.springframework.web.bind.annotation.RequestMapping; i…
阅读更多...
Rolla‘s homework：Image Processing with Python Final Project

Rolla‘s homework：Image Processing with Python Final Project

对比学习Yolo 和 faster rcnn 两种目标检测 要求 Image Processing with Python Final Project Derek TanLoad several useful packages that are used in this notebook:Image Processing with Python Final Project Project Goals: • Gain an understanding of the object …
阅读更多...
海康威视硬盘录像机NVR连接公网视频监控平台，注册失败，抓包发现有403 forbidden的问题解决

海康威视硬盘录像机NVR连接公网视频监控平台，注册失败，抓包发现有403 forbidden的问题解决

目录 一、问题描述 二、问题定位 1、查看DVR的配置 2、查看需要使用的端口是否开放 3、查看日志 4、抓包 &#xff08;1&#xff09;找出错误 &#xff08;2&#xff09;查看数据包内容 三、问题分析 1、国标28181中的域的概念 2、域应该如何定义 &#xff08;1&am…
阅读更多...
蓝桥杯备赛——DP【python】

蓝桥杯备赛——DP【python】

一、小明的背包1 试题链接&#xff1a;https://www.lanqiao.cn/problems/1174/learning/ 问题描述 输入实例 5 20 1 6 2 5 3 8 5 15 3 3 输出示例 37 问题分析 这里我们要创建一个DP表&#xff0c;DP&#xff08;i&#xff0c;j&#xff09;表示处理到第i个物品时消耗j体…
阅读更多...
STM32学习和实践笔记（30）：窗口看门狗（WWDG）实验

STM32学习和实践笔记（30）：窗口看门狗（WWDG）实验

1.WWDG介绍 1.1 WWDG简介 上一章我们已经介绍了IWDG&#xff0c;知道它的工作原理就是一个12位递减计数器不断递减计数&#xff0c;当减到0之前还未进行喂狗的话&#xff0c;产生一个MCU复位。 窗口看门狗WWDG其实和独立看门狗类似&#xff0c;它是一个7位递减计数器不断的往…
阅读更多...
C语言之指针进阶（3），函数指针

C语言之指针进阶（3），函数指针

目录 前言&#xff1a; 一、函数指针变量的概念 二、函数指针变量的创建 三、函数指针变量的使用 四、两段特殊代码的理解 五、typedef 六、函数指针数组 总结&#xff1a; 前言&#xff1a; 本文主要讲述C语言指针中的函数指针&#xff0c;包括函数指针变量的概念、创建…
阅读更多...
aws msk加密方式和问控制连接方式

aws msk加密方式和问控制连接方式

msk加密方式 msk提供了两种加密方式 静态加密传输中加密 创建集群时可以指定加密方式&#xff0c;参数如下 aws kafka create-cluster --cluster-name "ExampleClusterName" --broker-node-group-info file://brokernodegroupinfo.json --encryption-info file:/…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023