顺序表——功能实现

 702e764bf4974ad29bf6997b3256d93c.jpeg

✨✨欢迎👍👍点赞☕️☕️收藏✍✍评论

个人主页：秋邱'博客

所属栏目：C语言

（感谢您的光临，您的光临蓬荜生辉）

目录

1.0 前言

2.0 线性表

2.1 顺序表

2.2 顺序表的分类

2.3 顺序表功能的实现

2.3.1 准备前奏

2.3.2 初始化

2.3.3 打印

2.3.4 销毁空间

2.3.5 申请空间

2.3.6 头部插入

 2.3.7 删除头部数据

2.3.8 尾部插入

2.3.9 删除尾部数据

2.3.10 指定位置之前插入

 2.3.11 指定位置之前删除

2.3.12 寻找指定数字

3.0 完整代码

3.1 SeqList.h

3.2 SeqList.c

3.3 test.c

 

 

1.0 前言


学习顺序表之前，我们需要具备三方面的知识点。指针，结构体，动态内存的开辟。

2.0 线性表

线性表是数据结构中的一种基本形式，是 n 个数据元素的有限序列。线性表中的数据元素之间有序且连续，可以用一组地址连续的存储单元存储。

线性表可以表示一维数组，也可以表示一串具有相同类型的元素。线性表中的元素可以是数字、字符、对象等。线性表有两种基本形式：顺序表和链表。

本章主要讲的是顺序表。

2.1 顺序表

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

2.2 顺序表的分类

开辟数组我们有两个方法：

1.静态内存开辟,开辟一个固定的空间。如：int arr[10]={0};

2.动态内存开辟，确定大小之后再去申请空间。如：int *arr

同理，顺序表分类也有两种：

1.静态顺序表定义

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

2.动态顺序表定义

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

这两种哪一个好呢？

举个例子：
某app原定只能储存100万的用户信息，但随着app的爆火，越来越多的人注册使用这app，但这个后台只能储存100万，剩下的数据全部丢失，这将是一次重大的事故。

若动态数组，那么我们就能够在空间不够的情况下，再一次进行开辟空间，代码更加灵活。

2.3 顺序表功能的实现

开始之前我们需要创建三个文件，分别是

test.c             顺序表结构声明，顺序表的方法。

SeqList.h      实现顺序表的方法。

SeqList.c      对实现的顺序表进行测试

在之前我们就讲过了多文件的好处，这里就不在重复了。

2.3.1 准备前奏

顺序表的实现需要创建一个动态顺序表。其中包括了有效数据的大小size，已经整个动态空间的大小。

SeqList.h

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
typedef int SLDataType;//将int重命名，方便后续其他类型的修改
//动态顺序表
typedef struct SeqList 
{SLDataType* arr;//指向动态开辟的数组int size;       //有效数据个数int capacity;   //空间大小
}SL;//typedef struct SeqList Sl;

text.c

#define _CRT_SECURE_NO_WARNINGS
#include"SeqList.h"
int main()
{SL s1;//创建变量s1return 0;
}

 SeqList.c

#include"SeqList.h"

 接下来就能进入我们函数的实现了。

2.3.2 初始化

//初始化
//错误示范
void SLInit(SL ps)
{ps.arr = NULL;ps.capacity = ps.size = 0;
}//正确代码
void SLInit(SL * ps)
{ps->arr = NULL;ps->capacity = ps->size = 0;
}

 刚刚开始的时候，数组空间还没开辟所以是0；arr也还没有数据所以是空。

坑：错误的代码中采用了传值，而传值实际是是实参，拷贝一份给形参。还没进行初始化没有值。

所以这里要用传地址，用指针来接收。

2.3.3 打印

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

完成的函数，要验证它它能不能符合要求，就要打印出来，方便观察。

2.3.4 销毁空间

动态内存用完之后，我们要进行销毁。且将ps置为空，将size和capacity赋为0。

有借有还，再借不难。  

void SLDestroy(SL * ps)
{if (ps->arr)//等价于if(ps->arr != NULL){free(ps->arr);}ps->arr = NULL;ps->size = ps->capacity = 0;
}

 

2.3.5 申请空间

//申请空间的判断
void SLCheckCapacity(SL* ps)
{if (ps->capacity == ps->size){int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));if (tmp == NULL){perror("realloc error");exit(1);}//空间申请成功ps->capacity = newCapacity;ps->arr = tmp;}
}

由于空间的申请不止一个函数需要用到，在这就单独给它封装函数，方便后续的使用。

首先，要判断arr数组空间内存的大小。

如果数组的空间容量Capacity不等于有效数据size，则跳出函数。

相反，相等的情况下，开始开辟空间，创建一个变量newCapacity来储存新的空间容量大小，再创建tmp来存放首元素的地址(防止realloc开辟失败，将原来的arr置为NULL)。并且判断tmp是否开辟成功。

最后将newCapacity赋给capacity，将tmp赋值给arr。

2.3.6 头部插入

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

 头部插入之前要满足两个条件：

  • 传入指针不能为空。
  • 判断是否需要申请空间。

 因为这里是头部插入，所以需要讲数组内的数据往后移一位。然后将新的数据插入数组下标为0的地址。最后对size进行+1即可。

cf1656275fd443af8c6281d3aa8afa8a.png

 2.3.7 删除头部数据

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

删除头部数据之前，首先要assert断言传入的指针是不是空指针。删除头部数据只需要将后一位往前移，循环往复，最后size进行-1。

2.3.8 尾部插入

void SLPushBack(SL*ps, SLDataType x)
{assert(ps);SLCheckCapacity(ps);ps->arr[ps->size++] = x;}

尾插相比于头插会简单点，但同样也是需要断言，看传入的指针是否为空。在末尾插入数据需要在size处插入新的数据，然后对size进行+1即可。

2.3.9 删除尾部数据

void SLPopBack(SL* ps)
{assert(ps);--ps->size;
}

 同样尾删也是需要断言，看传入的指针是否为空。然后厎size-1就行了，有效数据减一，不会影响其他功能。

2.3.10 指定位置之前插入


void SLInsert(SL* ps, int pos, SLDataType x)
{assert(ps);assert(pos >= 0 && pos <= ps->size);SLCheckCapacity(ps);for (int i = ps->size; i >  pos ; i--){ps->arr[i] = ps->arr[i - 1];}ps->arr[pos] = x;ps->size++;
}
//pos 表示数组的下标值。

 掌握了头插和尾插，那么在指定位置之前插入数据就不难，这其实就是头插和尾插的结合。

在插入之前，要用assert断言传入指针是否为空。pos只能在0~size之间插入数据，当传入的数据不是这个范围，程序就会出错，所以这里也需要用assert来断言assert(pos >= 0 && pos <= ps->size)。

2bc037074be746a19b33953c99c054d1.png

 假设在下标为2的位置插入新的数据，就需要讲下标为2的数据移到后面，从后往前移（防止数据被覆盖），然后对size进行+1。

中间的值会了，插入两边就是头插和尾插，前面已经讲过了，这里就都是一样的。

 2.3.11 指定位置之前删除

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--;
}

在删除数据之前，要用assert断言传入指针是否为空。pos只能在0~size之间删除数据，但size指向的地址是没有数据的，当传入的数据不是这个范围，程序就会出错，所以这里也需要用assert来断言assert(pos >= 0 && pos < ps->size)。

834c6c9d4811420cba6161914155beef.png

接下来就是删除数据的部分，假设删除数组下标为2内容，只需要将后面的的数组往前放，循环往复，最后对size进行-1。

2.3.12 寻找指定数字

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;}
}

寻找指定数据，对传入的地址进行断言，然后用一个for循环来寻找数组的值，再用if-else来判断，若ps->arr[i] == x则返回的值。相反则返回-1。

3.0 完整代码

3.1 SeqList.h

#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
typedef int SLDataType;
//动态顺序表
typedef struct SeqList 
{SLDataType* arr;int size; //有效数据个数int capacity; //空间大小
}SL;//typedef struct SeqList Sl;
//开辟空间
void SLCheckCapacity(SL* ps);//初始化
void  SLInit(SL* ps);//打印
void SLPrint(SL s);//头插
void SLPushFront(SL* ps, SLDataType x);//尾插
void SLPushBack(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 x);//销毁
void SLDestroy(SL* ps);

3.2 SeqList.c

#define _CRT_SECURE_NO_WARNINGS#include"SeqList.h"
//申请空间的判断
void SLCheckCapacity(SL* ps)
{if (ps->capacity == ps->size){int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));if (tmp == NULL){perror("realloc error");exit(1);}//空间申请成功ps->capacity = newCapacity;ps->arr = tmp;}
}
//初始化
void SLInit(SL* ps)
{ps->arr = NULL;ps->capacity = ps->size = 0;
}//打印
void SLPrint(SL s)
{for (int i = 0; i < s.size; i++){printf("%d ", s.arr[i]);}printf("\n");
}//销毁
void SLDestroy(SL * ps)
{if (ps->arr)//等价于if(ps->arr != NULL){free(ps->arr);}ps->arr = NULL;ps->size = ps->capacity = 0;
}//头插
void SLPushFront(SL* ps, SLDataType x)
{assert(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);SLCheckCapacity(ps);ps->arr[ps->size++] = x;}//头删
void SLPopFront(SL* ps)
{assert(ps);ps->arr[0] = -1;for (int i = 0; i > ps->size-1; i++){ps->arr[i] = ps->arr[i + 1];}ps->size--;
}//尾删
void SLPopBack(SL* ps)
{assert(ps);--ps->size;
}//指定位置之前插入
void SLInsert(SL* ps, int pos, SLDataType x)
{assert(ps);assert(pos >= 0 && pos <= ps->size);SLCheckCapacity(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 x)
{assert(ps);for (int i = 0; i < ps->size; i++){if (ps->arr[i] == x){//找到啦return i;}//没有找到return -1;}
}

3.3 test.c

void SLTest01()
{SL sl;SLInit(&sl);//增删查改操作//测试尾插SLPushBack(&sl, 1);SLPushBack(&sl, 2);SLPushBack(&sl, 3);SLPushBack(&sl, 4);SLPrint(sl);//1 2 3 4//SLPushFront(&sl, 5);//SLPushFront(&sl, 6);//测试尾删SLPopBack(&sl);SLPrint(sl);//1 2 3 SLPopBack(&sl);SLPrint(sl);SLPopBack(&sl);SLPrint(sl);SLPopBack(&sl);SLPrint(sl);SLPopFront(&sl);SLPrint(sl);//...........SLDestroy(&sl);
}void SLTest02()
{SL sl;SLInit(&sl);SLPushBack(&sl, 1);SLPushBack(&sl, 2);SLPushBack(&sl, 3);SLPushBack(&sl, 4);SLPrint(sl);//1 2 3 4//测试指定位置之前插入数据//SLInsert(&sl, 1, 99);//SLInsert(&sl, sl.size, 88);//测试删除指定位置的数据//SLErase(&sl, 1);//SLPrint(sl);//1 3  4//测试顺序表的查找int find = SLFind(&sl, 40);if (find < 0){printf("没有找到！\n");}else {printf("找到了！下标为%d\n",find);}SLDestroy(&sl);
}int main()
{//SLTest01();//SLTest02();ContactTest01();return 0;
}

 

 

 

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

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

相关文章

基于SSM的宠物管理系统

基于SSM的宠物管理系统

点击以下链接获取源码： https://download.csdn.net/download/qq_64505944/89076676?spm=1001.2014.3001.5503 技术：SSM(Spring+SpringMVC+MyBatis)+LayUI+Echarts技术栈，分页采用pagehelper插件，EasyExcel进行Excel文件的导入导出。 宠物管理系统 1 CHINER-宠物管理系…
阅读更多...
ESP32S3网络编程学习笔记（1）—— Wi-Fi扫描实验

ESP32S3网络编程学习笔记（1）—— Wi-Fi扫描实验

前言 &#xff08;1&#xff09;如果有嵌入式企业需要招聘湖南区域日常实习生&#xff0c;任何区域的暑假Linux驱动/单片机/RTOS的实习岗位&#xff0c;可C站直接私聊&#xff0c;或者邮件&#xff1a;zhangyixu02gmail.com&#xff0c;此消息至2025年1月1日前均有效 &#xff…
阅读更多...
数据结构进阶篇 之 【交换排序】（冒泡排序，快速排序递归、非递归实现）详细讲解

数据结构进阶篇 之 【交换排序】（冒泡排序，快速排序递归、非递归实现）详细讲解

当你觉的自己不行时&#xff0c;你就走到斑马线上&#xff0c;这样你就会成为一个行人 一、交换排序 1.冒泡排序 BubbleSort 1.1 基本思想 1.2 实现原理 1.3 代码实现 1.4 冒泡排序的特性总结 2.快速排序 QuickSort 2.1 基本思想 2.2 递归实现 2.2.1 hoare版 2.2.2 …
阅读更多...
vitepress系列-04-规整sideBar左侧菜单导航

vitepress系列-04-规整sideBar左侧菜单导航

规整左侧菜单导航 新建navConfig.ts 文件用来管理左侧导航菜单&#xff1a; 将于其他的配置分开&#xff0c;避免config.mts太大 在config目录下&#xff0c;新建 sidebarModules文件目录用来左侧导航菜单 按模块进行分类&#xff1a; 在config下新建sidebarConfig.ts文件&…
阅读更多...
【引子】C++从介绍到HelloWorld

【引子】C++从介绍到HelloWorld

C从介绍到HelloWorld 一、C的介绍1. 简介2. 应用场景3. C的标准![在这里插入图片描述](https://img-blog.csdnimg.cn/direct/e3efb0f207f647729b92c0b5bcd4b330.png)4. C的运行过程 二、Visual Studio的安装1. 什么是Visual Studio2. Visual Studio的安装 三、完成HelloWorld1.…
阅读更多...
白色磨砂质感html5页源码

白色磨砂质感html5页源码

白色磨砂质感html5页源码&#xff0c;简约的基础上加上了团队成员&#xff0c;自动打字特效音乐播放器存活时间 源码下载 https://www.qqmu.com/2980.html
阅读更多...
书籍《笔记的方法》读后感

书籍《笔记的方法》读后感

读完《笔记的方法》有几周的时间&#xff0c;书里有些记录的内容&#xff0c;觉得非常有价值的&#xff0c;自己的观点&#xff0c;当下读书&#xff0c;其实并没有那么高大尚&#xff0c;就是存粹陶冶下情操&#xff0c;读书还是有一定作用的&#xff0c;毕竟看书只能慢慢来&a…
阅读更多...
软件设计师：11-结构化开发与UML

软件设计师：11-结构化开发与UML

结构化开发&#xff08;3-4分&#xff09; 一、模块化 二、耦合&#xff08;背&#xff09; 三、内聚&#xff08;背&#xff09; 四、设计原则&#xff08;背&#xff09; 五、系统文档 六、数据流图 数据流的起点或终点必须有一个是加工 判断依据&#xff1a; 1、…
阅读更多...
Python | NCL风格 | EOF | 相关 | 回归

Python | NCL风格 | EOF | 相关 | 回归

这里在linux系统上使用geocat实现NCL风格的图片绘制 Linux上安装 geocat conda update conda conda create -n geocat -c conda-forge geocat-viz conda activate geocat conda update geocat-vizDataset - NOAA Optimum Interpolation (OI) SST V2 # 海温月平均数据 - lsmas…
阅读更多...
内容创作策略：打造影响力强大的技术博客

内容创作策略：打造影响力强大的技术博客

CSDN的朋友你们好&#xff0c;我是未来&#xff0c;今天给大家带来专栏【程序员博主教程&#xff08;完全指南&#xff09;】的第6篇文章——“博客内容创作策略”。本文为技术博主提供了一个精简的内容创作策略指南&#xff0c;涵盖了设定目标、分析竞争、关键词研究、内容规划…
阅读更多...
24 个Intellij IDEA好用插件

24 个Intellij IDEA好用插件

24 个Intellij IDEA好用插件 一. 安装插件 Codota 代码智能提示插件 只要打出首字母就能联想出一整条语句&#xff0c;这也太智能了&#xff0c;还显示了每条语句使用频率。 原因是它学习了我的项目代码&#xff0c;总结出了我的代码偏好。 Key Promoter X 快捷键提示插件 …
阅读更多...
vscode 安装vim插件配置ctrl + c/v功能

vscode 安装vim插件配置ctrl + c/v功能

搜索Vim插件 插件介绍部分有提示操作 首先安装该插件&#xff0c;然后按照下述步骤设置ctrl相关的快捷键&#xff0c;以便于脱离im快捷键而愉快的敲代码。 1.在“设置”搜索框内搜索vim.handleKeys&#xff0c;选择 Edit in settings.json 2. 设置ctrl-c,ctrl-v等快捷键置为fa…
阅读更多...
室友打团太吵？一条命令让它卡死

室友打团太吵？一条命令让它卡死

「作者主页」&#xff1a;士别三日wyx 「作者简介」&#xff1a;CSDN top100、阿里云博客专家、华为云享专家、网络安全领域优质创作者 「推荐专栏」&#xff1a;更多干货&#xff0c;请关注专栏《网络安全自学教程》 SYN Flood 1、hping3实现SYN Flood1.1、主机探测1.2、扫描端…
阅读更多...
Unity类银河恶魔城学习记录12-7-1 p129 Craft UI - part 1源代码

Unity类银河恶魔城学习记录12-7-1 p129 Craft UI - part 1源代码

Alex教程每一P的教程原代码加上我自己的理解初步理解写的注释&#xff0c;可供学习Alex教程的人参考 此代码仅为较上一P有所改变的代码 【Unity教程】从0编程制作类银河恶魔城游戏_哔哩哔哩_bilibili UI_CraftList.cs using System.Collections; using System.Collections.Gen…
阅读更多...
zdpdjango_argonadmin使用Django开发一个美观的后台管理系统

zdpdjango_argonadmin使用Django开发一个美观的后台管理系统

初始代码 安装依赖 pip install -r requirements.txt生成管理员账户 迁移模型&#xff1a; python manage.py makemigrations python manage.py migrate创建超级用户&#xff1a; python manage.py createsuperuser启动服务 python manage.py runserver浏览器访问&#xf…
阅读更多...
2024新版PHP在线客服系统多商户AI智能在线客服系统源码机器人自动回复即时通讯聊天系统源码PC+H5

2024新版PHP在线客服系统多商户AI智能在线客服系统源码机器人自动回复即时通讯聊天系统源码PC+H5

搭建环境&#xff1a; 服务器 CPU 2核心 ↑ 运存 2G ↑ 宽带 5M ↑ 服务器操作系统 Linux Centos7.6-7.9 ↑ 运行环境&#xff1a; 宝塔面板 Nginx1.18- 1.22 PHP 7.1-7.3 MYSQL 5.6 -5.7 朵米客服系统是一款全功能的客户服务解决方案&#xff0c;提供多渠道支持…
阅读更多...
计算机组成原理（超详解！！） 第四节 存储系统和结构

计算机组成原理（超详解！！） 第四节 存储系统和结构

1.存储器概述 1.存储器分类 存储器&#xff1a;用来存储程序和数据的记忆设备。 存储介质&#xff1a;具有两种明显区别且稳定的物理状态&#xff0c;在外界的作用下&#xff0c;能够相互转化&#xff1b;一种稳定状态表示“0”&#xff0c;则另一种状态表示“1”。目前主要…
阅读更多...
es6新增set、map两种数据结构（超级详细-附加代码）

es6新增set、map两种数据结构（超级详细-附加代码）

文章目录 一、Set增删改查add()delete()has()clear()遍历 二、Map增删改查sizeset()get()has()delete()clear()遍历 三、WeakSet 和 WeakMapWeakSetWeakMap 参考文献 如果要用一句来描述&#xff0c;我们可以说 Set是一种叫做集合的数据结构&#xff0c;Map是一种叫做字典的数…
阅读更多...
数据结构——链表

数据结构——链表

目录 一、链表 1、单向链表 单向链表的遍历方式&#xff1a; 2、循环链表 3、双向链表 二、自行车停放&#xff08;双向链表&#xff09; 一、链表 链表是由许多相同数据类型的数据项按特定顺序排列而成的线性表特性&#xff1a;存放的位置是不连续且随机的&#xff0c;动…
阅读更多...
全坚固笔记本丨工业笔记本丨三防笔记本相较于普通笔记本有哪些优势？

全坚固笔记本丨工业笔记本丨三防笔记本相较于普通笔记本有哪些优势？

三防笔记本和普通笔记本在设计和性能方面存在显著差异&#xff0c;三防笔记本相较于普通笔记本具备以下优势&#xff1a; 三防笔记本通常采用耐磨、耐摔的材料&#xff0c;并具有坚固的外壳设计&#xff0c;能够承受恶劣环境和意外碰撞&#xff0c;有效保护内部组件不受损坏。相…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发