初级数据结构（一）——顺序表

文中代码源文件已上传：数据结构源码

1、顺序表的特点

1.1、数组

        现实中数据记录一般都记录在表格中，如进货单、菜单等，它们的最大特点就是有序。表述中可以用第一项、第二项、第 n 项来描述表格中某个数据或者某串数据。在 C 语言中，数组的特点恰好匹配此功能。

        由于数组在内存中的储存方式就如同列表依序排布，对数组可以用 arr[n] 或者 *(arr+n) 来迅速获得第 n-1 项数据。再加上而且数组是 C 语言的原生类型，创建数组极其便利，作为有序数据的载体着实是不二之选。

1.2、结构

        顺序表为了方便使用，除了用数组作为数据载体外，一般还包含记录数组空间大小和开辟空间大小的两个变量。常以结构体将这三个变量作为成员变量进行囊括。主要有两种创建方式：

        柔性数组顺序表（ Sequence table with flexible array ）：

#include <stdlib.h>//重定义数据类型
typedef int DATA;//创建并重定义结构体类型
typedef struct SeqTab
{int size;           //数据长度int capacity;       //数据空间大小DATA arr[];         //数据载体柔性数组
}SeqTab;int main()
{//开辟结构体空间SeqTab* sqList = (SeqTab*)malloc(sizeof(SeqTab) + sizeof(DATA)*4);//初始化数据长度及空间大小sqList->size = 0;sqList->capacity = 4;return 0;
}

        数组指针顺序表（ Sequence table with array pointer ）：

#include <stdlib.h>//重定义数据类型
typedef int DATA;//创建并重定义结构体类型
typedef struct SeqTab
{int size;           //数据长度int capacity;       //数据空间大小DATA* arr;          //数据载体数组指针
}SeqTab;int main()
{//创建结构体变量SeqTab sqList;//开辟数据载体数组空间sqList.arr = (DATA*)malloc(sizeof(DATA)*4);//初始化数据长度及空间大小sqList.size = 0;sqList.capacity = 4;return 0;
}

2、顺序表创建

        接下来以数组指针顺序表为例进行演示。

2.1、文件结构

        seqTab.h ：用于创建结构体类型及声明函数；

        sqFunction.c ：用于创建顺序表初始化及增删改查的函数；

        main.c ：仅创建 main 函数，用作测试。

2.2、前期工作

        在 seqTab.h 中先写入以下内容：

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>//用于初始化顺序表时开辟空间
#define INIT_SIZE 4//顺序表数据类型，方便顺序表储存数据类型修改
typedef int DATATYPE;//创建顺序表结构体类型
typedef struct SeqTab
{DATATYPE* data;int size;int capacity;
}SeqTab;//---------------------函数声明---------------------
//初始化顺序表
extern void DataInit(SeqTab*);//销毁顺序表
extern void DataDestory(SeqTab*);//打印顺序表
extern void DataPrint(const SeqTab*);

         在 sqFunction.c 中包含 seqTab.h 并分别创建一个初始化顺序表和销毁顺序表的函数：

#include "seqTab.h"//初始化顺序表
void DataInit(SeqTab* sq)
{//断言确保结构体指针不为空assert(sq);//为顺序表开辟空间sq->data = (DATATYPE*)malloc(INIT_SIZE * sizeof(DATATYPE));//加入判断防止空间开辟失败if (sq->data == NULL){perror("Malloc Fail");return;}//初始化记录数据长度及开辟空间长度的变量sq->size = 0;sq->capacity = INIT_SIZE;
}//销毁顺序表
void DataDestory(SeqTab* sq)
{//断言确保结构体指针不为空assert(sq);//释放顺序表数据空间free(sq->data);//数组指针置空sq->data = NULL;//数组长度及空间尺寸全部置0sq->size = 0;sq->capacity = 0;
}//打印顺序表
void DataPrint(const SeqTab* sq)
{//断言确保结构体指针不为空assert(sq);//遍历顺序表并逐个数据打印for (int i = 0; i < sq->size; i++){printf("%d ", sq->data[i]);}printf("\n");
}

        最后在 main.c 中包含 seqTab.h，并创建一个顺序表及初始化：

#include "seqTab.h"int main()
{//创建顺序表SeqTab sqList;//初始化顺序表DataInit(&sqList);return 0;
}

        至此，前期工作准备完毕，之后便是对顺序表的数据进行增删改查。

3、顺序表操作

3.1、增

        插入数据一般为头部插入数据、尾部插入数据及指定位置插入数据。插入数据时除了写入数据到数组中，还需时刻判断开辟的空间尺寸是否足以容纳已有数据。

        先将以下三个函数声明添加到 seqTab.h 中：

//指定位置插入数据
extern void DataInsert(SeqTab*, int, DATATYPE);
//头部插入数据
extern void DataPushHead(SeqTab*, DATATYPE);
//尾部插入数据
extern void DataPushTail(SeqTab*, DATATYPE);

        然后便是 DataInsert 函数。如图：

        据此可以轻松写出其代码。以下写入 sqFunction.c 中： 

void DataInsert(SeqTab* sq, int pos, DATATYPE data)
{//数据有效性判断assert(sq);if (pos < 0 || pos > sq->size){printf("Illegal Position : %d\n", pos);return;}//空间不足则创建空间if (sq->size + 1 >= sq->capacity){//申请新空间DATATYPE* ptr_newSqData = (DATATYPE*)realloc(sq->data, sizeof(DATATYPE) * (sq->capacity * 2));//空间申请结果判断if (ptr_newSqData == NULL){perror("Realloc Fail");return;}//赋予新空间地址sq->data = ptr_newSqData;//空间大小记录翻倍sq->capacity *= 2;}//数据后移直至腾出 pos 位置的空间for (int i = sq->size; i > pos; i--){sq->data[i] = sq->data[i - 1];}//写入数据*(sq->data + pos) = data;//数据长度+1sq->size++;
}

        至于头插尾插数据，只不过是上述函数 pos 位置的区别。因此：

//pos = 0 便是头插
void DataPushHead(SeqTab* sq, DATATYPE data)
{DataInsert(sq, 0, data);
}
//pos = 数据尺寸便是尾插
void DataPushTail(SeqTab* sq, DATATYPE data)
{DataInsert(sq, sq->size, data);
}

        在 main 函数里写入下列代码验证一下：

	DataInsert(&sqList, 10, 32);   //报错DataPushTail(&sqList, 10);DataPrint(&sqList);            //打印 10DataPushHead(&sqList, 20);DataPrint(&sqList);            //打印 20 10DataPushHead(&sqList, 3);DataPushTail(&sqList, 6);DataPushHead(&sqList, 8);DataPushHead(&sqList, 7);DataPushHead(&sqList, 2);DataPushTail(&sqList, 100);DataPushTail(&sqList, 432);DataPrint(&sqList);            //打印 2 7 8 3 20 10 6 10 432

        结果与预期无误。至此插入功能便已完成。

3.2、删

        正如插入数据分为头插、尾插及指定插，删除也分头删及任意位删。与插入相反，删除数据需要在数据删除结束后关注数据长度与开辟的数据空间，当空间分配过大时，对多余空间进行回收。

        同样先将以下三个函数声明添加到 seqTab.h 中：

//指定位置删除数据
extern void DataRemove(SeqTab*, int);
//删除头部数据
extern void DataPopHead(SeqTab*);
//删除尾部数据
extern void DataPopTail(SeqTab*);

         DataRemove 函数流程图如下：

        根据图中逻辑在 sqFunction.c 中写入以下：

void DataRemove(SeqTab* sq, int pos)
{//数据有效性判断assert(sq);if (pos < 0 || pos > sq->size - 1){printf("Illegal Position : %d\n", pos);return;}//列表不为空则执行if (sq->size - 1 >= 0){//由 pos 位开始，之后所有数据前移 1 位for (int i = pos; i < sq->size - 1; i++){sq->data[i] = sq->data[i + 1];}//数据长度-1sq->size--;}//开辟空间过大则执行if (sq->size < sq->capacity / 2){//申请新空间DATATYPE* ptr_newSqData = (DATATYPE*)realloc(sq->data, sizeof(DATATYPE) * (sq->capacity / 2));//空间申请结果判断if (ptr_newSqData == NULL){perror("Realloc Fail");return;}//赋予新空间地址sq->data = ptr_newSqData;//空间大小记录减半sq->capacity /= 2;}
}

         至于头删尾删数据，也同样是上述函数 pos 位置的区别：

//头删 pos = 0
void DataPopHead(SeqTab* sq)
{DataRemove(sq, 0);
}
//尾删 pos = 数据长度-1
void DataPopTail(SeqTab* sq)
{DataRemove(sq, sq->size - 1);
}

        之后同样是验证，将以下代码写到之前测试代码之后：

	DataRemove(&sqList, 100);    //报错DataRemove(&sqList, 3);DataPrint(&sqList);          //打印 2 7 8 20 10 6 100 432DataPopHead(&sqList);DataPrint(&sqList);          //打印 7 8 20 10 6 100 432DataPopTail(&sqList);DataPrint(&sqList);          //打印 7 8 20 10 6 100DataPopTail(&sqList);DataPopTail(&sqList);DataPopTail(&sqList);DataPopTail(&sqList);DataPopTail(&sqList);DataPrint(&sqList);          //打印 7DataPopTail(&sqList);DataPopTail(&sqList);DataPrint(&sqList);          //因为 size = 0 ，pos = -1 ， 报错

         删除数据功能完毕。

3.3、改

        改数据的功能实现起来，逻辑上毫无难度可言。以下函数声明添加到 seqTab.h 中：

//修改指定位置数据
extern void DataModify(SeqTab*, int, DATATYPE);

         在 sqFunction.c 中写入：

void DataModify(SeqTab* sq, int pos, DATATYPE data)
{//数据有效性判断assert(sq);if (pos < 0 || pos > sq->size - 1){printf("Illegal Position : %d\n", pos);return;}//修改数据sq->data[pos] = data;
}

        在 main 函数中追加以下代码验证：

	for (int i = 0; i < 10; i++){DataPushTail(&sqList, i);}DataPrint(&sqList);            //打印 0 1 2 3 4 5 6 7 8 9DataModify(&sqList, 100, 30);  //报错DataModify(&sqList, 3, 30);DataPrint(&sqList);            //打印 0 1 2 30 4 5 6 7 8 9

         完毕。

3.4、查

        查到数据返回该数据的位置，查不到返回 -1 。同样很简单。 seqTab.h 中写入声明：

//在表中查找数据
extern int DataSearch(SeqTab*, DATATYPE);

        然后是 sqFunction.c 中写入：

int DataSearch(SeqTab* sq, DATATYPE data)
{//数据有效性判断assert(sq);//遍历数组for (int i = 0; i < sq->size; i++){//如果找到数据则返回下标if (sq->data[i] == data){return i;}}//遍历完毕仍找不到数据返回 -1return -1;
}

        main 函数中验证：

	int num = 1200;int pos = DataSearch(&sqList, num);if (pos == -1){printf("The number \"%d\" is not exist!\n", num);}else{printf("The position of number \"%d\" is %d\n", num, pos);}//打印不存在num = 9;pos = DataSearch(&sqList, num);if (pos == -1){printf("The number \"%d\" is not exist!\n", num);}else{printf("The position of number \"%d\" is %d\n", num, pos);}//打印 9DataModify(&sqList, DataSearch(&sqList, 8), 11001);DataPrint(&sqList);    //打印 0 1 2 30 4 5 6 7 11001 9

        至此增删改查功能实现均已完毕。除此之外，还有排序、截断等其他一系列可以自定的操作。总之，操作顺序表就是操作数组，实现起来难度几乎为 0 。

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

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

相关文章

uni-app 微信小程序之swiper轮播图

uni-app 微信小程序之swiper轮播图

1. 实现效果 2. 完成代码 <template><view class"components-home"><view style"margin-top:-50rpx;height: 486rpx; position: relative;margin-bottom: 80rpx;"><image srchttps://xxx.com/img/wccQQP.png modewidthFix classpng …
阅读更多...
基于STM32驱动的压力传感器实时监测系统

基于STM32驱动的压力传感器实时监测系统

本文介绍了如何使用STM32驱动压力传感器进行实时监测。首先&#xff0c;我们会介绍压力传感器的工作原理和常见类型。然后&#xff0c;我们将介绍如何选择合适的STM32单片机和压力传感器组合。接下来&#xff0c;我们会详细讲解如何使用STM32驱动压力传感器进行数据采集和实时监…
阅读更多...
【C++】POCO学习总结（九）：网络

【C++】POCO学习总结（九）：网络

【C】郭老二博文之&#xff1a;C目录 1、Poco::Net::IPAddress IP地址 Poco::Net::IPAddress类存储IPv4或IPv6主机地址。 Poco::Net::IPAddress可以从字符串解析&#xff0c;也可以格式化为字符串。支持IPv4格式(d.d.d.d)和IPv6格式(x: x: x: x: x: x: x: x)。 常用函数&…
阅读更多...
搞笑视频无水印下载，高清无水印视频网站！

搞笑视频无水印下载，高清无水印视频网站！

搞笑视频无水印下载这件事情一直困扰了广大网友&#xff0c;每当看见好玩好笑的搞笑视频然而下载下来的时候&#xff0c;要么画质模糊就带有水印今天分享大家几个搞笑视频无水印下载方法。 这是一个非常良心的搞笑视频无水印下载小程序水印云&#xff0c;它支持图片去水印、视…
阅读更多...
HITOS_LAB5 进程运行轨迹的跟踪与统计

HITOS_LAB5 进程运行轨迹的跟踪与统计

5. 进程运行轨迹的跟踪与统计 5.1. 实验目的 掌握 Linux 下的多进程编程技术&#xff1b;通过对进程运行轨迹的跟踪来形象化进程的概念&#xff1b;在进程运行轨迹跟踪的基础上进行相应的数据统计&#xff0c;从而能对进程调度算法进行实际的量化评价&#xff0c; 更进一步加…
阅读更多...
高德地图加载三维模型vue（.obj转.gltf）

高德地图加载三维模型vue（.obj转.gltf）

官方glTF模型案例 obj2gltf 的开发文档 第一步&#xff1a;这里首先要将我们的.obj文件转换为.gltf文件 全局安装 npm install -g obj2gltf终端打开.obj文件所在的文件夹执行 obj2gltf -i model.obj -o model.gltf -t &#xff08;-i model.obj对应你的obj文件的名字&#x…
阅读更多...
Node包管理工具 - nvm、npm、yarn、cnpm、pnpm

Node包管理工具 - nvm、npm、yarn、cnpm、pnpm

转载说明 原文地址 简介 nvm : 可以实现一台电脑&#xff0c;拥有多个版本的Node npm : node package manager 下载Node后自带的一个包管理工具 yarn : npm 的升级版&#xff0c;更优秀 cnpm : 配置下载非官方地址的依赖&#xff08;淘宝、华为、腾讯镜像&#xff09; pnpm :…
阅读更多...
前端时间的失败总结复盘

前端时间的失败总结复盘

分享失败经验&#xff0c;前段时间的总结复盘&#xff1a; 与伙伴合作面对异常决策要及时提出质疑&#xff0c;怼&#xff0c;别太客气&#xff0c;客气起来&#xff0c;小心翼翼在意他人情绪那么这个项目就会让人难受&#xff0c;不要因为因为伙伴身上有标签/光环/权威就觉得…
阅读更多...
java后端自学错误总结

java后端自学错误总结

java后端自学错误总结 MessageSource国际化接口总结 MessageSource国际化接口 今天第一次使用MessageSource接口,比较意外遇到了一些坑 messageSource是spring中的转换消息接口&#xff0c;提供了国际化信息的能力。MessageSource用于解析 消息&#xff0c;并支持消息的参数化…
阅读更多...
题目：区间更新（蓝桥OJ 3291）

题目：区间更新（蓝桥OJ 3291）

题目描述&#xff1a; 解题思路&#xff1a; 差分模板题。 题解&#xff1a; #include<bits/stdc.h> using namespace std;const int N 1e5 10; int a[N], diff[N] ;//数组的大小不可能开到大于1e9int res(int n, int m) {for(int i 1; i < n; i)cin >&g…
阅读更多...
抖音视频如何无水印保存？抖音视频无水印保存教程

抖音视频如何无水印保存？抖音视频无水印保存教程

抖音视频如何无水印保存&#xff1f;当下短视频盛行时代&#xff0c;抖音作为当下主流短视频平台之一&#xff0c;每天都有数以亿计的用户在抖音上分享自己的创作&#xff0c;然后当我们遇到感兴趣的视频&#xff0c;下载保存后会发现带有水印&#xff0c;那么抖音视频如何无水…
阅读更多...
人、机不同在于变与多

人、机不同在于变与多

人擅长变&#xff0c;如变模态、变尺度&#xff0c;而机器侧重多&#xff0c;如多模态、多尺度。 人类擅长变化的能力是由于我们的大脑和思维能力的灵活性所决定的。我们可以通过学习和适应&#xff0c;改变我们的态度、行为方式和观点&#xff0c;以适应不同的情境和环境。例如…
阅读更多...
51 代码审计-PHP框架MVC类上传断点调试挖掘

51 代码审计-PHP框架MVC类上传断点调试挖掘

目录 知识点1:知识点2:知识点3:演示案例:PHPStormxdebu断点调试演示Beescms无框架后台任意文件上传Finecms基于前台MVC任意文件上传CItphp基于前台TP5框架任意文件上传 涉及资源: 知识点1: #关键字搜索: (函数&#xff0c;关键字&#xff0c;全局变量等) 文件上传&#xff0c;…
阅读更多...
国标GB28181协议/RTSP视频监控汇聚平台EasyCVR（V.3.4）页面UI大更新

国标GB28181协议/RTSP视频监控汇聚平台EasyCVR（V.3.4）页面UI大更新

为提高用户体验&#xff0c;增强平台功能&#xff0c;旭帆科技的Easy系列平台也在不断优化更新中。在最新的EasyCVR&#xff08;V.3.4&#xff09;中&#xff0c;其最显著的区别即为首页UI的调整。 其亮点是在【配置中心】-【基础配置】-【展示信息】中&#xff0c;首页UI可分…
阅读更多...
短视频账号矩阵系统源码/saas独立源头技术开发

短视频账号矩阵系统源码/saas独立源头技术开发

一、批量剪辑&#xff08;采用php语言&#xff0c;数学建模&#xff09; 短视频合成批量剪辑的算法主要有以下几种&#xff1a; 1. 帧间插值算法&#xff1a;通过对多个视频的帧进行插帧处理&#xff0c;从而合成一段平滑的短视频。 2. 特征提取算法&#xff1a;提取多个视频中…
阅读更多...
Spring容器启动过程中的自定义操作插口汇总

Spring容器启动过程中的自定义操作插口汇总

目录标题 PostConstruct注解EventListener方式InitializingBean的afterPropertiesSet方法实现ApplicationRunner接口重写run方法实现AplicationContextAware接口重写setApplicationContext实现ServletContextListener接口contextInitialized方法实现ServletContextAware接口set…
阅读更多...
MacDroid Pro for Mac – 安卓设备文件传输助手，实现无缝连接与传输！

MacDroid Pro for Mac – 安卓设备文件传输助手，实现无缝连接与传输！

想要在Mac电脑上轻松管理和传输您的安卓设备文件吗&#xff1f;MacDroid Pro for Mac 是您的最佳选择&#xff01;这款强大的文件传输助手可以让您在Mac上与安卓设备之间实现快速、方便的文件传输。 MacDroid Pro for Mac 提供了简单易用的界面&#xff0c;让您能够直接在Mac上…
阅读更多...
WordPress插件大全-免费的WordPress插件汇总

WordPress插件大全-免费的WordPress插件汇总

随着互联网的不断发展&#xff0c;网站建设变得日益普及。对于大多数人而言&#xff0c;WordPress是一个熟悉且易于使用的网站建设平台。然而&#xff0c;有时候我们可能会觉得WordPress的功能还不够满足我们的需求&#xff0c;这时候&#xff0c;插件就成了解决问题的得力工具…
阅读更多...
数据库管理-第122期 配置Halo数据库（202301204）

数据库管理-第122期 配置Halo数据库（202301204）

数据库管理-第122期 配置Halo数据库&#xff08;202301204&#xff09; 在120期完成了HaloDB的安装&#xff0c;那么紧接着就需要对数据库进行具体配置。 1 数据库配置 这里首先说一下我这里数据库的给的硬件配置&#xff1a;2个CPU&#xff0c;16GB内存 1 配置数据库访问控…
阅读更多...
记录一下Mac配置SpringBoot开发环境

记录一下Mac配置SpringBoot开发环境

由于很多项目喜欢使用传统的 Java 8 进行开发&#xff0c;而且 Java 8 的稳定性也是经过长久考验的&#xff0c;我们接下来就尝试一下&#xff0c;在一台新的 Mac 中配置 Java 环境&#xff0c;并且开始创建 SpringBoot 项目。 首先&#xff0c;去 Oracle 官网下载 java8 JDK …
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023