拿捏 顺序表(1)

news/2024/5/27 13:16:36/ 标签: 学习方法, c语言, visualstudio, 数据结构

目录

  • 1. 顺序表的分类
  • 2. 顺序表实现
  • 3. 顺序表实现完整代码
  • 4. 总结

前言:
一天xxx想存储一组数据, 并且能够轻松的实现删除和增加, 此时数组大胆站出, 但是每次都需要遍历一遍数组, 来确定已经存储的元素个数, 太麻烦了, 于是迎来了顺序表不屑的调侃: 数组你不行啊…

顺序表是一种常见的数据结构,它是由一组连续的存储单元组成的线性表。顺序表的优点是可以随机存取,即可以通过下标直接访问元素,查找和更新操作的时间复杂度为O(1)。同时,顺序表还可以通过动态扩容来实现自动调整大小,使得其具有灵活性。本文将介绍顺序表的定义、操作以及一些应用场景,帮助读者更好地理解和应用顺序表。

博客主页: 酷酷学!!! 感谢关注❤


正文开始

1. 顺序表的分类

顺序表的底层结构就是数组,对数组的封装,实现了常用的增删改查等接,
也就是顺序表是站在数组的肩膀上飞黄腾达.

顺序表又分为静态和动态

静态顺序表:
概念:使用定长数组存储元素

在这里插入图片描述
这里有个缺陷: 空间给少了不够用, 给多了造成浪费, 于是直接pass

动态顺序表 :
在这里插入图片描述
弥补了缺陷: 就你了,下面进行实现

2. 顺序表实现

第一步:
首先完成顺序表我们分成三个源文件来完成, 这样看起来代码更舒服

在这里插入图片描述

//我们这里创建三个源文件
//Seqlist.h 用来放文件的声明已经类型的定义
//Seqlist.c 用来放顺序表实现的方法
//test.c 用来进行代码测试

第二步:
我们直接在头文件声明结构体, 并且进行一些函数的声明

//直接在.h包含头文件, 以方便我们直接使用
#pragma once//以下声明只会包含一次, 提高代码效率
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int SeqDataType;//自定义类型名,方便后期修改存储数据类型typedef struct SeqList
{SeqDataType* arr;int size;int capacity;
}SL;//声明结构体类型,自定义类型名为SLvoid SLInit(SL* ps);//初始化函数声明
void SLDestory(SL* ps);//销毁函数声明void SLCheckCapacity(SL* ps);//判断空间容量函数声明
void SLPushBack(SL* ps, SeqDataType x);//尾插汉书声明
void SLPushFront(SL* ps, SeqDataType x);//头插函数声明void SLprint(SL ps);//打印内容函数void SLPopBack(SL* ps);//尾删函数
void SLpopFront(SL* ps);//头删函数

第三步:
来到.Seqlist.c 封装各类函数

初始化:

void SLInit(SL* ps)
{assert(ps);//不可以给我传个NULL哦,之后每次参数为指针最好都断言一下ps->arr = NULL;ps->size = ps->capacity = 0;
}

销毁操作:

void SLDestory(SL* ps)
{assert(ps);if (ps->arr)//如果arr里面有内容,那么就释放这块内存, 我们之后会动态开辟内存{free(ps->arr);}ps->arr = NULL;//避免成为野指针ps->capacity = ps->size = 0;
}

第四步:
前期准备工作已完成, 下面进行代码高速

首先完成怎么插入, 但是有一个问题: 如果这个顺序表大小为0, 或者大小满了的情况下我们怎么插入呢? 所以我们要进行先判断空间容量, 但是后期我们可能还要进行头插操作是不是也要判断一次, 好麻烦欸, 干脆直接封装成函数, 这样更简洁

于是乎:

void SLCheckCapacity(SL* ps)
{assert(ps);if (ps->size == ps->capacity)//没空间或者满了,这不就是需要扩容吗{int Newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//如果第一次没空间让它开辟个四块内存,不够再成倍给SeqDataType* tmp = (SeqDataType*)realloc(ps->arr, Newcapacity * sizeof(SeqDataType));//不要忘记realloc申请失败可是会返回NULL,直接赋值会造成内存泄露,不如交给临时变量if (tmp == NULL){perror("realloc fail");exit(1);}ps->arr = tmp;//没问题再给ps->arrtmp = NULL;//不需要的指针变量可以拴起来ps->capacity = Newcapacity;//修改空间容量大小}
}

第五步:实现头插尾插

先看尾插(因为比较简单)

//尾插
void SLPushBack(SL* ps, SeqDataType x)
{assert(ps);SLCheckCapacity(ps);ps->arr[ps->size++] = x;
}//寥寥三行,这不比数组简单?

头插:

void SLPushFront(SL* ps, SeqDataType x)
{assert(ps);SLCheckCapacity(ps);for (int i = ps->size; i>0; i--){ps->arr[i] = ps->arr[i-1];//最后一次ps->arr[1] = ps->arr[0]}//参考下图ps->arr[0] = x;ps->size++;
}

在这里插入图片描述

我们是不是需要由左图变成右图呀, 给第一个位置空出来

第六步:
当然了, 我们也可以实验一下前面的代码正不正确,于是乎我们可以让控制台打印, 不妨写如下函数:

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

我举个栗子:
我们不妨在test.c里面写上如下代码,看看成功与否

#include "Seqlist.h"int main()
{SL s;SLInit(&s);SLPushBack(&s, 4);SLPushBack(&s, 3);SLPushBack(&s, 2);SLPushBack(&s, 1);SLprint(s);SLPushFront(&s, 3);SLPushFront(&s, 4);SLprint(s);

我只能说轻松拿捏:
在这里插入图片描述

最后一步:

实现删除操作:

先来尾删(因为简单)

void SLPopBack(SL* ps)
{assert(ps);assert(ps->size);ps->size--;
}//想一想为什么这么简单,就是这么简单,因为最后那个位置直接可以被其它值覆盖

接着头删:

void SLpopFront(SL* ps)
{assert(ps);assert(ps->size);for (int i = 0; i <=ps->size-2 ; i++){ps->arr[i] = ps->arr[i + 1];//最后一次arr[size-2] = arr[size-1]}//看下图:ps->size--;
}

这里我们依旧需要由左边变成右边想想看是不是
在这里插入图片描述

okok,到此我们顺序表已经全部结束, 欲知后事如何,请见下回讲解,点个关注不迷路

下面直接开始今天的代码测试

#include "Seqlist.h"int main()
{SL s;SLInit(&s);SLPushBack(&s, 4);SLPushBack(&s, 3);SLPushBack(&s, 2);SLPushBack(&s, 1);SLprint(s);SLPushFront(&s, 3);SLPushFront(&s, 4);SLprint(s);SLPopBack(&s);SLprint(s);SLpopFront(&s);SLprint(s);SLDestory(&s);return 0;
}

没有一点容错, 学废了吗
在这里插入图片描述

3. 顺序表实现完整代码

Seqlist.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int SeqDataType;typedef struct SeqList
{SeqDataType* arr;int size;int capacity;
}SL;void SLInit(SL* ps);
void SLDestory(SL* ps);void SLCheckCapacity(SL* ps);
void SLPushBack(SL* ps, SeqDataType x);
void SLPushFront(SL* ps, SeqDataType x);void SLprint(SL ps);void SLPopBack(SL* ps);
void SLpopFront(SL* ps);

Seqlist.c

#include"Seqlist.h"void SLInit(SL* ps)
{assert(ps);ps->arr = NULL;ps->size = ps->capacity = 0;
}void SLDestory(SL* ps)
{assert(ps);if (ps->arr){free(ps->arr);}ps->arr = NULL;ps->capacity = ps->size = 0;
}void SLCheckCapacity(SL* ps)
{assert(ps);if (ps->size == ps->capacity){int Newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;SeqDataType* tmp = (SeqDataType*)realloc(ps->arr, Newcapacity * sizeof(SeqDataType));if (tmp == NULL){perror("realloc fail");exit(1);}ps->arr = tmp;ps->capacity = Newcapacity;}
}//尾插
void SLPushBack(SL* ps, SeqDataType x)
{assert(ps);SLCheckCapacity(ps);ps->arr[ps->size++] = x;
}void SLPushFront(SL* ps, SeqDataType x)
{assert(ps);SLCheckCapacity(ps);for (int i = ps->size; i>0; i--){ps->arr[i] = ps->arr[i-1];//最后一次ps->arr[1] = ps->arr[0]}ps->arr[0] = x;ps->size++;
}void SLprint(SL ps)
{for (int i = 0; i < ps.size; i++){printf("%d ", ps.arr[i]);}printf("\n");
}void SLPopBack(SL* ps)
{assert(ps);assert(ps->size);ps->size--;
}void SLpopFront(SL* ps)
{assert(ps);assert(ps->size);for (int i = 0; i <=ps->size-2 ; i++){ps->arr[i] = ps->arr[i + 1];//arr[size-2] = arr[size-1]}ps->size--;
}

test.c

#include "Seqlist.h"int main()
{SL s;SLInit(&s);SLPushBack(&s, 4);SLPushBack(&s, 3);SLPushBack(&s, 2);SLPushBack(&s, 1);SLprint(s);SLPushFront(&s, 3);SLPushFront(&s, 4);SLprint(s);SLPopBack(&s);SLprint(s);SLpopFront(&s);SLprint(s);SLDestory(&s);return 0;
}

4. 总结

顺序表是一种线性数据结构,用于存储具有相同数据类型的数据元素。它通过一片连续的存储空间来存储数据,可以按照元素的物理顺序来访问和操作。

在顺序表中,元素的存储位置是连续的,可以通过下标来访问元素。通过下标,可以快速访问和修改顺序表中的元素,这是顺序表的一个重要特点。

顺序表的插入操作比较复杂,需要将插入位置之后的所有元素后移一位,然后将新元素插入到空出的位置。删除操作也类似,需要将删除位置之后的所有元素前移一位,然后将最后一个元素删除。

顺序表的优点是存储和访问元素的效率高,可以随机访问元素。而缺点是插入和删除操作的效率相对较低,需要进行大量的数据迁移。

顺序表适用于元素数量固定且不经常变动的场景,例如存储静态的数据集合。在元素数量会经常变动的情况下,使用链表等动态数据结构更为合适。

总之,顺序表是一种经典的线性数据结构,具有高效的存储和访问性能。但在插入和删除操作上稍显不足,适用于元素数量固定且不经常变动的场景。


看完, 记得点个关注


http://www.ppmy.cn/news/1434620.html

相关文章

mac qt android开发环境

1,安装Android Studio 下载 Android Studio 和应用工具 - Android 开发者 | Android Developers (google.cn)

求建筑高度(C语言)

一、N-S流程图&#xff1b; 二、运行结果&#xff1b; 三、源代码&#xff1b; # define _CRT_SECURE_NO_WARNINGS # include <stdio.h>int main() {//初始化变量值&#xff1b;float x, y;//提示用户&#xff1b;printf("请输入x y坐标的值&#xff1a;");//…

HarmonyOS NEXT星河版之实战商城App瀑布流(含加载更多)

文章目录 一、目标二、开撸2.1 声明商品对象2.2 mock数据2.3 主页面2.4 加载更多2.5 完整代码 三、小结 一、目标 二、开撸 2.1 声明商品对象 export interface GoodsItem {title: stringimageUrl: string }2.2 mock数据 export const mockGoodsList: GoodsItem[] [{title:…

Android判断应用是否在前台运行

Android判断应用是否在前台运行 /*** Android判断应用是否在前台运行* 0&#xff1a;异常&#xff1b;1&#xff1a;前台&#xff1b;2&#xff1a;后台&#xff1b;3&#xff1a;未运行&#xff1b;*/private int isFrontShow(Context context) {if (context null) {ret…

动力学重构/微分方程参数拟合 - 基于模型

这一篇文章&#xff0c;主要是给非线性动力学&#xff0c;对微分方程模型参数拟合感兴趣的朋友写的。笼统的来说&#xff0c;这与混沌系统的预测有关&#xff1b;传统的机器学习的模式识别虽然也会谈论预测结果&#xff0c;但他们一般不会涉及连续的预测。这里我们考虑的是&…

Linux读写文件

前言 学习了文件系统&#xff0c;就能理解为什么说Linux下一切皆文件。 语言层面的操作 在c语言的学习中我们可以使用fopen()函数对文件进行操作。 int main() {//FILE * fp fopen("./log.txt", "w");//FILE * fp fopen("./log.txt", "…

Music Tag Editor Pro for Mac:音乐标签编辑软件

Music Tag Editor Pro for Mac是一款功能强大的音乐标签编辑软件&#xff0c;专为Mac用户设计&#xff0c;旨在帮助用户轻松管理音乐库中的标签信息。 Music Tag Editor Pro for Mac v8.0.0中文激活版下载 该软件支持多种音频格式&#xff0c;包括MP3、M4A、FLAC、APE等&#x…

Midjourney如何实现人物角色的一致性?

在数字艺术和AI生成媒体的发展中&#xff0c;保持人物一致性是一个巨大的挑战。Midjourney作为一个先进的图像生成平台&#xff0c;它如何确保在连续的图像生成过程中&#xff0c;同一人物能保持一致的外观和特征呢&#xff1f;本文将深入探讨Midjourney如何通过技术手段实现这…

人工智能论文GPT-3(1):2020.5 Language Models are Few-Shot Learners;摘要;引言;scaling-law

摘要 近期的工作表明&#xff0c;在大量文本语料库上进行预训练&#xff0c;然后针对特定任务进行微调&#xff0c;可以在许多NLP任务和基准测试中取得实质性进展。虽然这种方法在架构上通常是与任务无关的&#xff0c;但仍然需要包含数千或数万示例的针对特定任务的微调数据集…

SpringMVC基础篇(二)

文章目录 1.Postman1.基本介绍Postman是什么&#xff1f; 2.Postman快速入门1.Postman下载点击安装自动安装在系统盘 2.基本操作1.修改字体大小2.ctrl “” 放大页面3.进入创建请求界面 2.需求分析3.具体操作4.保存请求到文件夹中1.点击保存2.创建新的文件夹3.保存成功 3.使用…

互联网轻量级框架整合之MyBatis动态SQL

MyBatis的动态SQL是一项强大且实用的功能&#xff0c;它允许开发者在XML映射文件中编写可灵活变化的SQL语句&#xff0c;这些语句能够根据传入参数的条件或值动态地调整其结构和内容。这样&#xff0c;程序可以在运行时生成适应特定业务场景的SQL&#xff0c;避免了手动拼接SQL…

css文字和span在一行对不齐

1.需求背景 父盒子中有两个span&#xff0c;但是span中的文字对不齐。如下图&#xff0c;明显右边的文字偏高 处理后的效果&#xff08;已经对齐&#xff0c;图中标记的是基本的div结构&#xff09;&#xff1a; 2.该问题出现的原因&#xff1a; span1设置的高度比span2内…

设计模式——2_A 访问者(Visitor)

文章目录 定义图纸一个例子&#xff1a;如何给好奇宝宝提供他想知道的内容菜单、菜品和配方Menu(菜单) & Cuisine(菜品)Material(物料、食材) 产地、有机蔬菜和卡路里Cuisine & Material 访问者VisitorCuisine & Material 碎碎念访问者和双分派访问者和代理写在最后…

VBA之正则表达式(45)-- 提取SQL语句中的函数

实例需求&#xff1a;数据工程师或者DBA日常工作中大量使用SQL语句&#xff0c;有些语句&#xff08;或者存储过程&#xff09;行数非常多&#xff0c;现在需要提取其中的所有使用了函数的相关部分&#xff0c;对于如下语句&#xff0c;需要提取Mid([编号],2,4) AS [产品]和dat…

【上海大学计算机组成原理实验报告】四、指令系统实验

一、实验目的 了解指令结构、PC寄存器的功能和指令系统的基本工作原理。 学习设计指令的方法。 二、实验原理 根据实验指导书的相关内容&#xff0c;对于部分使用频率很高&#xff0c;且只用几条微指令即可完成的简单操作&#xff0c;可以把这部分简单操作的微指令序列固定下…

扩散卷积模型 笔记

1 Title Diffusion Convolutional Neural Networks&#xff08;James Atwood and Don Towsley&#xff09;【NeurIPS 2016】 2 Conclusion This paper presents diffusion-convolutional neural networks (DCNNs), a new model for graph-structured data. Through the introd…

13个Java基础面试题

Hi&#xff0c;大家好&#xff0c;我是王二蛋。 金三银四求职季&#xff0c;特地为大家整理出13个 Java 基础面试题&#xff0c;希望能为正在准备或即将参与面试的小伙伴们提供些许帮助。 后续还会整理关于线程、IO、JUC等Java相关面试题&#xff0c;敬请各位持续关注。 这1…

python常见语法

变量赋值&#xff1a; my_var 10 基本数据类型&#xff1a; 整数&#xff08;int&#xff09;、浮点数&#xff08;float&#xff09;、字符串&#xff08;str&#xff09;、布尔值&#xff08;bool&#xff09;、列表&#xff08;list&#xff09;、元组&#xff08;tuple&…

myql 获取二维数组字符串的最后一个值

继续《mysql 存储过程和函数》的实战&#xff1a; 要分离字符串&#xff1a;[["1","1007","1007012"],["5","5005"],["6","6002","6002005"],["7","7003"],["8&quo…

零基础入门学习Python第一阶10图形用户界面和游戏开发

图形用户界面和游戏开发 基于tkinter模块的GUI GUI是图形用户界面的缩写&#xff0c;图形化的用户界面对使用过计算机的人来说应该都不陌生&#xff0c;在此也无需进行赘述。Python默认的GUI开发模块是tkinter&#xff08;在Python 3以前的版本中名为Tkinter&#xff09;&…