【数据结构】知识点一:线性表之顺序表

内容导航

  • 一、什么是线性表?
  • 二、什么是顺序表?
    • 1、顺序表的概念
    • 2、顺序表的结构
      • a. 静态顺序表:使用定长数组存储元素。
      • b. 动态顺序表:使用动态开辟的数组存储。
  • 三、顺序表的接口实现精讲
    • 1.接口一:打印数据
    • 2.接口二:表初始化
    • 3.接口三:数据销毁
    • 4.接口四:尾插数据
    • 5.接口五:尾删数据
    • 6.接口六:头插数据
    • 7.接口七:头删数据
    • 8.接口八:容量检查
    • 9.接口九:任意位置的插入
    • 9.接口九:任意位置的删除
    • 10.接口十:任意数据的查找
  • 四、源代码分享
    • 1.SeqList.h
    • 2.SeqList.c
    • 3.test.c

一、什么是线性表?

线性表(linear list)是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构,常见的线性表:顺序表、链表、栈、队列、字符串…
线性表在逻辑上是线性结构,也就说是连续的一条直线。但是在物理结构上并不一定是连续的,线性表在物理上存储时,通常以数组和链式结构的形式存储。
在这里插入图片描述

二、什么是顺序表?

1、顺序表的概念

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用数组存储,在数组上完成数据的增删查改。

2、顺序表的结构

a. 静态顺序表:使用定长数组存储元素。

b. 动态顺序表:使用动态开辟的数组存储。

三、顺序表的接口实现精讲

静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了,空间开多了浪费,开少了不够用,所以现实中基本都是使用动态顺序表,根据需要动态的分配空间大小,所以下面我们实现动态顺序表。

1.接口一:打印数据

<font color=black size=4 font face=黑体" >代码之函数的定义:

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

2.接口二:表初始化

<font color=black size=4 font face=黑体" >代码之函数的定义:

void SLInit(SL* ps1)							//初始化顺序表,全部为0
{assert(ps1);ps1->a = NULL;ps1->size = 0;ps1->capacity = 0;
}

3.接口三:数据销毁

<font color=black size=4 font face=黑体" >代码之函数的定义:

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

4.接口四:尾插数据

<font color=black size=4 font face=黑体" >代码之函数的定义:

void SLPushBack(SL* ps1, SLDataType x)			//尾插入
{assert(ps1);SLCheckCapacity(ps1);						//检查容量ps1->a[ps1->size] = x;ps1->size++;
}

5.接口五:尾删数据

<font color=black size=4 font face=黑体" >代码之函数的定义:

void SLPopBack(SL* ps1)							//尾删除
{assert(ps1);assert(ps1->size > 0);						//有效数据为0则不需要删ps1->size--;
}

6.接口六:头插数据

<font color=black size=4 font face=黑体" >代码之函数的定义:

void SLPushFront(SL* ps1, SLDataType x)		//头插入
{assert(ps1);SLCheckCapacity(ps1);						//检查容量//往后挪动数据int end = ps1->size - 1;while (end >= 0){ps1->a[end + 1] = ps1->a[end];end--;}ps1->a[0] = x;ps1->size++;
}

7.接口七:头删数据

<font color=black size=4 font face=黑体" >代码之函数的定义:

void SLPopFront(SL* ps1)						//头删除
{assert(ps1);assert(ps1->size > 0);						//有效数据为0则不需要删//往前挪动数据int begin = 1;while (begin < ps1->size){ps1->a[begin - 1] = ps1->a[begin];begin++;}ps1->size--;
}

8.接口八:容量检查

<font color=black size=4 font face=黑体" >代码之函数的定义:

void SLCheckCapacity(SL* ps1)					//检查空间是否充足,若否,使空间充足,头插尾插都要用到
{assert(ps1);if (ps1->size == ps1->capacity){int NewCapacity = ps1->capacity == 0 ? 4 : ps1->capacity * 2;SLDataType* tmp = (SLDataType*)realloc(ps1->a, sizeof(SLDataType) * NewCapacity);if (tmp == NULL){perror("realloc fail");return;}ps1->a = tmp;ps1->capacity = NewCapacity;}
}

9.接口九:任意位置的插入

<font color=black size=4 font face=黑体" >代码之函数的定义:

void SLInsert(SL* ps1, int pos, SLDataType x)	//任意位置的插入
{assert(ps1);assert(pos >= 0 && pos <= ps1->size);		//确保pos大小的有效性SLCheckCapacity(ps1);						//检查容量//往后挪动数据int end = ps1->size - 1;while (end > pos){ps1->a[end + 1] = ps1->a[end];end--;}ps1->a[pos] = x;ps1->size++;
}

9.接口九:任意位置的删除

<font color=black size=4 font face=黑体" >代码之函数的定义:

void SLErase(SL* ps1, int pos)					//任意位置的删除
{assert(ps1);assert(pos >= 0 && pos <= ps1->size);		//确保pos大小的有效性//往前挪动数据int begin = pos+1;while (begin < ps1->size){ps1->a[begin - 1] = ps1->a[begin];begin++;}ps1->size--;
}

10.接口十:任意数据的查找

<font color=black size=4 font face=黑体" >代码之函数的定义:

int SLFind(SL* ps1, SLDataType x)				//查找某个数据,找到返回下标,未找到返回-1
{assert(ps1);for (int i = 0; i < ps1->size; i++)			//直接遍历查找{if (ps1->a[i] == x){return i;}}return -1;
}

四、源代码分享

1.SeqList.h

#define  _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<assert.h>
typedef int SLDataType;typedef struct SeqList
{SLDataType* a;							//开辟的数组地址int size;								//有效数据个数int capacity;							//容量空间的大小
}SL;void SLPrint(SL* ps1);						//打印数据
void SLInit(SL* ps1);						//初始化顺序表,全部为0
void SLDestroy(SL* ps1);					//销毁顺序表void SLPushBack(SL* ps1, SLDataType x);		//尾插入
void SLPushFront(SL* ps1, SLDataType x);	//头插入
void SLPopBack(SL* ps1);					//尾删除
void SLPopFront(SL* ps1);					//头删除void SLInsert(SL* ps1, int pos, SLDataType x);	//任意位置的插入
void SLErase(SL* ps1, int pos);					//任意位置的删除int SLFind(SL* psl, SLDataType x);				//查找某个数据,找到返回下标,未找到返回-1

2.SeqList.c

#include"SeqList.h"void SLPrint(SL* ps1)								//打印数据
{assert(ps1);for (int i = 0; i < ps1->size; i++){printf("%d ", ps1->a[i]);}printf("\n");
}void SLInit(SL* ps1)							//初始化顺序表,全部为0
{assert(ps1);ps1->a = NULL;ps1->size = 0;ps1->capacity = 0;
}void SLDestroy(SL* ps1)							//销毁顺序表
{assert(ps1);if (ps1->a != NULL)							{free(ps1->a);ps1->a = NULL;ps1->size = 0;ps1->capacity = 0;}
}void SLCheckCapacity(SL* ps1)					//检查空间是否充足,若否,使空间充足,头插尾插都要用到
{assert(ps1);if (ps1->size == ps1->capacity){int NewCapacity = ps1->capacity == 0 ? 4 : ps1->capacity * 2;SLDataType* tmp = (SLDataType*)realloc(ps1->a, sizeof(SLDataType) * NewCapacity);if (tmp == NULL){perror("realloc fail");return;}ps1->a = tmp;ps1->capacity = NewCapacity;}
}
void SLPushBack(SL* ps1, SLDataType x)			//尾插入
{assert(ps1);SLCheckCapacity(ps1);						//检查容量ps1->a[ps1->size] = x;ps1->size++;
}void SLPushFront(SL* ps1, SLDataType x)		//头插入
{assert(ps1);SLCheckCapacity(ps1);						//检查容量//往后挪动数据int end = ps1->size - 1;while (end >= 0){ps1->a[end + 1] = ps1->a[end];end--;}ps1->a[0] = x;ps1->size++;
}void SLPopBack(SL* ps1)							//尾删除
{assert(ps1);assert(ps1->size > 0);						//有效数据为0则不需要删ps1->size--;
}void SLPopFront(SL* ps1)						//头删除
{assert(ps1);assert(ps1->size > 0);						//有效数据为0则不需要删//往前挪动数据int begin = 1;while (begin < ps1->size){ps1->a[begin - 1] = ps1->a[begin];begin++;}ps1->size--;
}void SLInsert(SL* ps1, int pos, SLDataType x)	//任意位置的插入
{assert(ps1);assert(pos >= 0 && pos <= ps1->size);		//确保pos大小的有效性SLCheckCapacity(ps1);						//检查容量//往后挪动数据int end = ps1->size - 1;while (end > pos){ps1->a[end + 1] = ps1->a[end];end--;}ps1->a[pos] = x;ps1->size++;
}void SLErase(SL* ps1, int pos)					//任意位置的删除
{assert(ps1);assert(pos >= 0 && pos <= ps1->size);		//确保pos大小的有效性//往前挪动数据int begin = pos+1;while (begin < ps1->size){ps1->a[begin - 1] = ps1->a[begin];begin++;}ps1->size--;
}int SLFind(SL* ps1, SLDataType x)				//查找某个数据,找到返回下标,未找到返回-1
{assert(ps1);for (int i = 0; i < ps1->size; i++)			//直接遍历查找{if (ps1->a[i] == x){return i;}}return -1;
}

3.test.c

#define  _CRT_SECURE_NO_WARNINGS 1
#include"SeqList.h"void menu()
{printf("********************************\n");printf("****1、尾插数据  2、尾删数据****\n");printf("****3、头插数据  4、头删数据****\n");printf("****5、打印数据  0、退出    ****\n");printf("********************************\n");
}int main()
{SL s;SLInit(&s);int option = 0;do{menu();printf("请输入你的选择:>");scanf("%d", &option);if (option == 1){printf("请依次输入你的要尾插数据个数和数据:>");int n = 0;scanf("%d", &n);for (int i = 0; i < n; i++){int x = 0;scanf("%d", &x);SLPushBack(&s, x);}}else if (option == 2){printf("请依次输入你的要尾删数据的个数:>");int n = 0;scanf("%d", &n);for (int i = 0; i < n; i++){SLPopBack(&s);}}else if (option == 3){printf("请依次输入你的要头插数据个数和数据:>");int n = 0;scanf("%d", &n);for (int i = 0; i < n; i++){int x = 0;scanf("%d", &x);SLPushFront(&s, x);}}else if (option == 4){printf("请依次输入你的要头删数据的个数:>");int n = 0;scanf("%d", &n);for (int i = 0; i < n; i++){SLPopFront(&s);}}else if (option == 5){SLPrint(&s);}else if (option == 0){break;}else{printf("无此选项,请重新输入\n");}} while (option != 0);SLDestroy(&s);return 0;
}

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

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

相关文章

持安科技亮相张江高科895创业营,总评分第三名荣获「最具创新性企业」!

近日&#xff0c;张江高科895创业营&#xff08;第十三季&#xff09;信息安全专场Demo day&结营仪式在上海集成电路设计产业园圆满落幕。本季创业营通过多种渠道在海内外甄选优秀创业项目&#xff0c;一共择优录取了29家入营&#xff0c;最终甄选出9家代表参加Demo day路演…

Django后端开发——中间件

文章目录 参考资料中间件注册中间件settings.pymiddleware/mymiddleware.pymysite3/views.pymysite3/urls.py 练习 参考资料 B站网课&#xff1a;点击蓝色字体跳转 或复制链接至浏览器&#xff1a;https://www.bilibili.com/video/BV1vK4y1o7jH?p39&vd_source597e21cf34f…

数据可视化原理-腾讯-热力图

在做数据分析类的产品功能设计时&#xff0c;经常用到可视化方式&#xff0c;挖掘数据价值&#xff0c;表达数据的内在规律与特征展示给客户。 可是作为一个产品经理&#xff0c;&#xff08;1&#xff09;如果不能够掌握各类可视化图形的含义&#xff0c;就不知道哪类数据该用…

Mybatis plus扩展功能-Db静态工具

目录 1 前言 2 使用方法 2.1 Db静态工具拥有的部分方法 2.2 举例 1 前言 在我们的服务层中&#xff0c;有时为了实现一个方法需要引入其它的Mapper层方法&#xff0c;但是&#xff0c;这样可能出现循环依赖。虽然Spring已经给我们解决了简单的循环依赖问题&#xff0c;但是…

深入剖析k8s-Pod篇

为什么需要Pod&#xff1f; 进程是以进程组的方式组织在一起。受限制容器的“单进程模型”&#xff0c; 成组调用没有被妥善处理&#xff08;资源调用有限&#xff09;&#xff0c;使用资源囤积则导致复杂度上升。 在k8s项目中&#xff0c;Pod的实现需要使用一个中间容器——…

web组态(BY组态)接入流程

技术文档 官网网站&#xff1a;www.hcy-soft.com 体验地址&#xff1a; www.byzt.net:60/sm 一、数据流向图及嵌入原理 数据流向 嵌入原理 二、编辑器调用业务流程图 三、集成前需要了解的 1、后台Websocket端往前台监控画面端传输数据规则 后台websocket向客户端监控画面…

基于CNN-LSTM-Attention的时间序列回归预测matlab仿真

目录 1.算法运行效果图预览 2.算法运行软件版本 3.部分核心程序 4.算法理论概述 4.1卷积神经网络&#xff08;CNN&#xff09;在时间序列中的应用 4.2 长短时记忆网络&#xff08;LSTM&#xff09;处理序列依赖关系 4.3 注意力机制&#xff08;Attention&#xff09; 5…

python自动化之项目架构搭建与思路讲解(第二天)

1.自动化测试的概念 自动化测试是指使用自动化工具和脚本来执行测试任务&#xff0c;以验证软件或系统的正确性和稳定性。它可以提高测试的效率和准确性&#xff0c;并节约时间和成本。 2.自动化脚本编写的思路 xmind文档如有需要&#xff0c;可在资源里自行下载 3.项目代码…

MySQL NDB Cluster 分布式架构搭建 自定义启动与重启Shell脚本

此次NDB Cluster使用三台虚拟机进行搭建&#xff0c;一台作为管理节点&#xff1b;而对于另外两台服务器&#xff0c;每一台都充当着数据节点和SQL节点的角色。注意不是MGR主从复制架构&#xff0c;而是分布式MySQL架构。 创建 /var/lib/mysql-cluster/config.ini Cluster全局…

(面试题)数据结构:链表相交

问题&#xff1a;有两个链表&#xff0c;如何判断是否相交&#xff0c;若相交&#xff0c;找出相交的起始节点 一、介绍 链表相交&#xff1a; 若两个链表相交&#xff0c;则两个链表有共同的节点&#xff0c;那从这个节点之后&#xff0c;后面的节点都会重叠&#xff0c;知道…

灯塔:CSS笔记

CSS&#xff1a;层叠样式表 所谓层叠 即叠加的意思&#xff0c;表示样式可以一层一层的层叠覆盖 css写在style标签中&#xff0c;style标签一般写在head标签里面&#xff0c;title标签下面 <!DOCTYPE html> <html lang"en"> <head><meta cha…

Vue开发实例(一)Vue环境搭建第一个项目

Vue环境搭建&第一个项目 一、环境搭建二、安装Vue脚手架三、创建Vue项目 一、环境搭建 下载方式从官网下载&#xff1a;http://nodejs.cn/download/ 建议下载v12.16.0版本以上的&#xff0c;因为版本低无法创建Vue的脚手架 检验是否安装成功 配置环境变量 新增NODE_HOME&…

chrome选项页面options page配置

options 页面用以定制Chrome浏览器扩展程序的运行参数。 通过Chrome 浏览器的“工具 ->更多工具->扩展程序”&#xff0c;打开chrome://extensions页面&#xff0c;可以看到有的Google Chrome扩展程序有“选项Options”链接&#xff0c;如下图所示。单击“选项Options”…

车载测试_UDS诊断:功能寻址、物理寻址

车载项目讲解 简历修改优化 模拟面试 面试录音辅导 预约面试技巧 面试一对一在线协助 车载入职技术支持三个月 诊断三要素&#xff1a;请求/肯定响应/否定响应&#xff08;诊断服务失败或者无法完成&#xff09;。 服务可以诊断通信管理请求、数据请求、故障代码请求、输入/输出…

SpringBoot约定大于配置

什么是约定大于配置 "约定大于配置"&#xff08;Convention Over Configuration&#xff09;是一种理念&#xff0c;旨在通过默认约定和规则来减少开发人员需要做的配置工作。在Spring Boot框架中&#xff0c;这一原则得到了充分应用&#xff0c;帮助开发者更快地构…

使用Spark探索数据

需求分析 使用Spark来探索数据是一种高效处理大规模数据的方法&#xff0c;需要对数据进行加载、清洗和转换&#xff0c;选择合适的Spark组件进行数据处理和分析。需求分析包括确定数据分析的目的和问题、选择合适的Spark应用程序和算法、优化数据处理流程和性能、可视化和解释…

(三)softmax分类--九五小庞

softmax分类 对数几率回归解决的是二分类的问题&#xff0c;对于多个选项的问题&#xff0c;我们可以使用softmax函数&#xff0c;它是对数几率回归在N个可能不同的值上的推广 softmax各样本分量之和为1&#xff0c;当只有两个类别时&#xff0c;与对数几率回归完全相同 损失…

vmware虚拟机centos中/dev/cl_server8/root 空间不够

在使用vmware时发现自己的虚拟机的/dev/cl_server8/root空间不够了&#xff0c;没办法安装新的服务。所以查了一下改空间的办法。 1.在虚拟机关闭的状态下&#xff0c;选中需要扩容的虚拟机->设置->硬件-> 硬盘->扩展->填写扩大到的值。 2.打开虚拟机&#xff…

CSS 盒子模型(box model)

概念 所有HTML元素可以看作盒子&#xff0c;在CSS中&#xff0c;"box model"这一术语是用来设计和布局时使用CSS盒模型本质上是一个盒子&#xff0c;封装周围的HTML元素&#xff0c;它包括&#xff1a;外边距(margin)&#xff0c;边框(border)&#xff0c;内边距(pad…

ELK+kafka+filebeat企业内部日志分析系统

目录 ELKkafkafilebeat企业内部日志分析系统 1、组件介绍 1、Elasticsearch&#xff1a; 2、Logstash: 3、Kibana: 4、Kafka&#xff1a; 5、Filebeat: 2、环境介绍 3、版本说明 4、搭建架构 5、实施部署 1、 Elasticsearch集群部署 1、安装配置jdk 2、安装配置ES…