C语言 数据结构【动态顺序表】详解

引言

        详细介绍了顺序表中各个接口的实现，一定要亲自动手敲一遍，要能想象出具体的图像

第一次敲可能不能完全靠自己敲出来（很正常），过一段时间可以根据顺序表的原理敲第二遍

孰能生巧

一、线性表

在介绍顺序表之前先认识一下线性表，顺序表是线性表的一种

        线性表（linearlist）是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串...

线性表在逻辑上是线性结构，也就说是连续的⼀条直线。

但是在物理结构上并不⼀定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

二、顺序表 

概念：顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，⼀般情况下采用数组存储。（在逻辑结构上肯定是连续的）

顺序表和数组的区别？

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

三、实现动态顺序表 

💡代码小提示

        编写代码过程中要勤测试，避免写出大量代码后再测试而导致出现问题，问题定位无从下手。 

        定义三个文件：

text.c       //测试代码是否正确
SeqList.c //Sequece List(顺序表)所有代码
SeqList.h //顺序表里所有的头文件 和 声明函数

text.c    //测试代码是否正确
SeqList.c //Sequece List(顺序表)所有代码
SeqList.h //顺序表里所有的头文件 和 声明函数

1.定义顺序表类型，引用需要的头文件 

 在SeqList.h文件中：

#pragma once   //确保头文件在一个编译单元中只被包含一次
#include<stdio.h>   //输入输出需要，perror函数需要
#include<stdlib.h>  //开辟动态内存需要
#include<assert.h>  //assert函数需要//定义动态顺序表的结构
typedef int SLDataType;
typedef struct SeqList
{SLDataType* arr;int size;        //有效数据个数//size位置是空的，待放入值int capacity;    //空间容量
}SL;   // 顺序表

2.初始化顺序表 

在SeqList.c文件中的代码：

#include"SeqList.h"  //引用头文件
void SLInit(SL* ps) //初始化
{ps->arr = NULL;    ps->size = ps->capacity = 0;
}

3.销毁顺序表 

在SeqList.c中的代码：


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

4.对顺序表扩容 

在SeqList.c文件中的代码：

void SLCheckCapacity(SL* ps) //增容
{if (ps->size == ps->capacity){int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;//如果capacity 是 0，就先扩容4个空间//如果capacity 不是0，就扩容2倍空间SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));//先将扩容后的空间存在tmp中if (tmp == NULL){perror("realloc"); //输出错误信息exit(1); //退出程序并返回1；}ps->arr = tmp; //tmp不是空，传给arrps->capacity = newCapacity; //更新空间}
}

这里采用的是2倍扩容，有效利用空间。

注意：realloc函数第二个参数就是扩容后空间的大小，而不是扩容第二个参数那么大。

5. 实现尾插和打印

在SeqList.c文件中的代码：

#include"SeqList.h"
void SLpushBack(SL* ps, SLDataType x)//尾插
{assert(ps);SLCheckCapacity(ps);  //空间不够的话就扩容ps->arr[ps->size++] = x;
}void SLprint(SL* ps)  //打印顺序表
{assert(ps);for (int i = 0; i < ps->size; i++){printf("%d ", ps->arr[i]);}printf("\n");
}

6.实现头插 

在SeqList.c文件中的代码：

#include"SeqList.h"
void SLpushFront(SL* ps, SLDataType x) //头插
{assert(ps);SLCheckCapacity(ps);for (int i = ps->size;i > 0; i--) //将顺序表中所有数据向后挪动一位{ps->arr[i] = ps->arr[i - 1];}ps->arr[0] = x;++ps->size;
}

7.实现在指定位置插入数据 

在SeqList.c文件中的代码：

#include"SeqList.h"
void SLInsert(SL* ps, int pos, SLDataType 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];}ps->arr[pos] = x;++ps->size;
}

8.测试头插，尾插，任意位置插入元素 

在text.c文件中的代码：

#include"SeqList.h"void text01() //测试尾插
{SL s1;SLInit(&s1);SLpushBack(&s1,1);SLpushBack(&s1,2);SLpushBack(&s1,3);SLprint(&s1);SLDestroy(&s1);
}
void text02() //测试头插
{SL s2;SLInit(&s2);SLpushFront(&s2, 1);SLpushFront(&s2, 2);SLpushFront(&s2, 3);SLprint(&s2);SLDestroy(&s2);
}void text03() //测试在指定位置插入元素
{SL s3;SLInit(&s3);SLpushFront(&s3, 1);SLpushFront(&s3, 2);SLpushFront(&s3, 3);SLInsert(&s3, 2, 10);SLprint(&s3);SLDestroy(&s3);
}
int main()
{//text01(); //测试尾插//text02(); //测试头插text03(); //测试在指定位置插入元素return 0;
}

注意：一定不用忘记对顺序表的初始化 

text03运行的结果：

9.实现尾删，头删

在SeqList.c中的代码：

void SLPopBack(SL* ps) //尾删,直接让size减1即可
{//ps：限制参数不能直接给NULL//ps->size：顺序表为空assert(ps && ps->size);--ps->size;
}void SLPopFront(SL* ps) //头删，从第二位到最后一位整体向前挪动一位即可，最后size--
{assert(ps && ps->size);for (int i = 0; i < ps->size - 1; i++){ps->arr[i] = ps->arr[i + 1];}--ps->size;
}

10. 实现任意位置删除元素

在SeqList.c中的代码：

void SLErase(SL* ps, int pos) //删除pos位置的元素
{assert(ps);assert(pos >= 0 && pos <=ps->size);for (int i = pos; i < ps->size - 1; i++) //pos及其位置之后的元素整体向前挪动一位{ps->arr[i] = ps->arr[i + 1];}--ps->size;
}

11.测试头删，尾删，删除任意位置的元素

 在text.c中的代码：

#include"SeqList.h"
void text04()
{SL s4;SLInit(&s4);SLpushFront(&s4, 1);SLpushFront(&s4, 2);SLpushFront(&s4, 3);SLInsert(&s4, 2, 10);SLPopBack(&s4);SLPopFront(&s4);SLprint(&s4);SLDestroy(&s4);
}void text05() //测试删除任意位置的元素
{SL s5;SLInit(&s5);SLpushFront(&s5, 1);SLpushFront(&s5, 2);SLpushFront(&s5, 3);SLInsert(&s5, 2, 10);SLErase(&s5, 2);SLprint(&s5);SLDestroy(&s5);
}int main()
{//text01(); //测试尾插//text02(); //测试头插text03(); //测试在指定位置插入元素//text04();//测试尾删和头删text05(); //测试删除任意位置的元素return 0;
}

text03和text05运行的结果： 

12.查找元素所在的位置，找不到返回-1 

 在SeqList.c中的代码：

#include"SeqList.h"
int SLFind(SL* ps, int x) //查找元素x的位置
{assert(ps);for (int i = 0; i <= ps->size - 1; i++){if (ps->arr[i] == x)return i;}return -1;
}

 13.测试查找元素所在的位置

在text.c中的代码：

#include"SeqList.h"
int text06()
{SL s6;SLInit(&s6);SLpushFront(&s6, 1);SLpushFront(&s6, 2);SLpushFront(&s6, 3);SLInsert(&s6, 2, 10);int r1 = SLFind(&s6, 2);int r2 = SLFind(&s6, 9);SLprint(&s6);printf("2元素的位置：%d\n", r1);printf("9元素的位置：%d\n", r2);SLDestroy(&s6);
}int main()
{//text01(); //测试尾插//text02(); //测试头插text03(); //测试在指定位置插入元素//text04();//测试尾删和头删//text05(); //测试删除任意位置的元素text06(); //测试查找元素的位置return 0;
}

运行结果：（下标是从0开始的）

四、顺序表所有代码

在SeqList.h中的代码（核心）：

#pragma once   //确保头文件在一个编译单元中只被包含一次
#include<stdio.h>   //输入输出需要，perror函数需要
#include<stdlib.h>  //开辟动态内存需要
#include<assert.h>  //assert函数需要//定义动态顺序表的结构
typedef int SLDataType;
typedef struct SeqList
{SLDataType* arr;int size;        //有效数据个数int capacity;    //空间容量
}SL;              // 顺序表void SLprint(SL* ps);  //打印顺序表void SLInit(SL* ps);//初始化void SLDestroy(SL* ps);//销毁顺序表void SLCheckCapacity(SL* ps); //增容void SLpushBack(SL* ps, SLDataType x);//尾插void SLpushFront(SL* ps, SLDataType x); //头插void SLInsert(SL* ps, int pos, SLDataType x);//在指定位置插入数据void SLPopBack(SL* ps); //尾删void SLPopFront(SL* ps); //头删void SLErase(SL* ps, int x); //删除pos位置的数据int SLFind(SL* ps, int x); //查找元素x的位置

在SeqList.c中的文件（核心）： 

#define _CRT_SECURE_NO_WARNINGS
#include"SeqList.h"
void SLInit(SL* ps) //初始化
{ps->arr = NULL;ps->size = ps->capacity = 0;
}void SLDestroy(SL* ps)//销毁顺序表
{assert(ps);if (ps->arr)free(ps->arr);ps->arr = NULL;ps->arr = ps->capacity = 0;
}void SLprint(SL* ps)  //打印顺序表
{assert(ps);for (int i = 0; i < ps->size; i++){printf("%d ", ps->arr[i]);}printf("\n");
}void SLCheckCapacity(SL* ps) //增容
{if (ps->size == ps->capacity){int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));if (tmp == NULL){perror("realloc");exit(1); //退出程序并返回1；}ps->arr = tmp;ps->capacity = newCapacity;}
}void SLpushBack(SL* ps, SLDataType x)//尾插
{assert(ps);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--) //将顺序表中所有数据向后挪动一位{ps->arr[i] = ps->arr[i - 1];}ps->arr[0] = x;++ps->size;
}void SLInsert(SL* ps, int pos, SLDataType 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];}ps->arr[pos] = x;++ps->size;
}void SLPopBack(SL* ps) //尾删,直接让size减1即可
{//ps：限制参数不能直接给NULL//ps->size：顺序表为空assert(ps && ps->size);--ps->size;
}void SLPopFront(SL* ps) //头删，从第二位到最后一位整体向前挪动一位即可，最后size--
{assert(ps && ps->size);for (int i = 0; i < ps->size - 1; i++){ps->arr[i] = ps->arr[i + 1];}--ps->size;
}void SLErase(SL* ps, int pos) //删除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, int x) //查找元素x的位置
{assert(ps);for (int i = 0; i <= ps->size - 1; i++){if (ps->arr[i] == x)return i;}return -1;
}

在text.c中的代码（测试写的函数是否能实现功能）：


#include"SeqList.h"void text01()
{SL s1;SLInit(&s1);SLpushBack(&s1,1);SLpushBack(&s1,2);SLpushBack(&s1,3);SLprint(&s1);SLDestroy(&s1);
}
void text02()
{SL s2;SLInit(&s2);SLpushFront(&s2, 1);SLpushFront(&s2, 2);SLpushFront(&s2, 3);SLprint(&s2);SLDestroy(&s2);
}void text03()
{SL s3;SLInit(&s3);SLpushFront(&s3, 1);SLpushFront(&s3, 2);SLpushFront(&s3, 3);SLInsert(&s3, 2, 10);SLprint(&s3);SLDestroy(&s3);
}void text04()
{SL s4;SLInit(&s4);SLpushFront(&s4, 1);SLpushFront(&s4, 2);SLpushFront(&s4, 3);SLInsert(&s4, 2, 10);SLPopBack(&s4);SLPopFront(&s4);SLprint(&s4);SLDestroy(&s4);
}void text05() //测试删除任意位置的元素
{SL s5;SLInit(&s5);SLpushFront(&s5, 1);SLpushFront(&s5, 2);SLpushFront(&s5, 3);SLInsert(&s5, 2, 10);SLErase(&s5, 2);SLprint(&s5);SLDestroy(&s5);
}int text06()
{SL s6;SLInit(&s6);SLpushFront(&s6, 1);SLpushFront(&s6, 2);SLpushFront(&s6, 3);SLInsert(&s6, 2, 10);int r1 = SLFind(&s6, 2);int r2 = SLFind(&s6, 9);SLprint(&s6);printf("2元素的位置：%d\n", r1);printf("9元素的位置：%d\n", r2);SLDestroy(&s6);
}int main()
{//text01(); //测试尾插//text02(); //测试头插text03(); //测试在指定位置插入元素//text04();//测试尾删和头删//text05(); //测试删除任意位置的元素text06(); //测试查找元素的位置return 0;
}

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

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

相关文章

人脸表情识别系统分享（基于深度学习+OpenCV+PyQt5）

人脸表情识别系统分享（基于深度学习+OpenCV+PyQt5）

最近终于把毕业大论文忙完了&#xff0c;众所周知硕士大论文需要有三个工作点&#xff0c;表情识别领域的第三个工作点一般是做一个表情识别系统出来&#xff0c;如下图所示。 这里分享一下这个表情识别系统&#xff1a; 采用 深度学习OpenCVPyQt5 构建&#xff0c;主要功能包…
阅读更多...
集成学习（下）：Stacking集成方法

集成学习（下）：Stacking集成方法

一、Stacking的元学习革命 1.1 概念 Stacking&#xff08;堆叠法&#xff09; 是一种集成学习技术&#xff0c;通过组合多个基学习器&#xff08;base learner&#xff09;的预测结果&#xff0c;并利用一个元模型&#xff08;meta-model&#xff09;进行二次训练&#xff0c…
阅读更多...
tcping 命令的使用，ping IP 和端口

tcping 命令的使用，ping IP 和端口

1. ‌Windows系统安装‌ ‌下载tcping工具‌&#xff1a;根据系统位数&#xff08;32位或64位&#xff09;下载对应的tcping.exe文件。‌安装步骤‌&#xff1a; 将下载的tcping.exe文件复制到C:\Windows\System32目录下。如果下载的是64位版本&#xff0c;需将文件名改为tcpi…
阅读更多...
浅谈跨平台框架的演变（H5混合开发-＞RN-＞Flutter）

浅谈跨平台框架的演变（H5混合开发-＞RN-＞Flutter）

引言 这里分为四个阶段&#xff1a; 第一阶段 &#xff1a; 原生开发 第二阶段 &#xff1a; H5混合开发 第三阶段&#xff1a; 跨平台RN 第四阶段&#xff1a; 跨平台Flutter 正文 第一阶段&#xff1a; 原生开发 开发成本比较大 &#xff1a; 需要Android 和ios 开发两…
阅读更多...
《TCP/IP网络编程》学习笔记 | Chapter 20：Windows 中的线程同步

《TCP/IP网络编程》学习笔记 | Chapter 20：Windows 中的线程同步

《TCP/IP网络编程》学习笔记 | Chapter 20&#xff1a;Windows 中的线程同步 《TCP/IP网络编程》学习笔记 | Chapter 20&#xff1a;Windows 中的线程同步用户模式和内核模式用户模式同步内核模式同步 基于 CRITICAL_SECTION 的同步内核模式的同步方法基于互斥量对象的同步基于…
阅读更多...
力扣45.跳跃游戏

力扣45.跳跃游戏

45. 跳跃游戏 II - 力扣&#xff08;LeetCode&#xff09; 代码区&#xff1a; #include<vector> class Solution {public:int jump(vector<int>& nums) {int ans[10005] ;memset(ans,1e4,sizeof(ans));ans[0]0;for(int i0;i<nums.size();i){for(int j1;j…
阅读更多...
深入理解 Collections.emptyList()：优雅处理空列表的利器！！！

深入理解 Collections.emptyList()：优雅处理空列表的利器！！！

&#x1f680; 深入理解 Collections.emptyList()&#xff1a;优雅处理空列表的利器&#xff01;&#x1f527; 大家好&#xff01;&#x1f44b; 今天我们来聊聊 Java 中一个非常实用但容易被忽视的小工具——Collections.emptyList()。&#x1f389; 如果你经常需要返回一个…
阅读更多...
SpringBoot教程（十四） SpringBoot之集成Redis

SpringBoot教程（十四） SpringBoot之集成Redis

SpringBoot教程&#xff08;十四&#xff09; | SpringBoot之集成Redis 一、Redis集成简介二、集成步骤 2.1 添加依赖2.2 添加配置2.3 项目中使用之简单使用 &#xff08;举例讲解&#xff09;2.4 项目中使用之工具类封装 &#xff08;正式用这个&#xff09;2.5 序列化 &…
阅读更多...
VC6.0图文安装教程

VC6.0图文安装教程

VC6.0图文安装教程 ​ 1、首先&#xff0c;右击安装包&#xff0c;以管理员身份运行 2、点击下一步 ​​​​ 3、点击下一步 4、选择安装路径&#xff0c;点击下一步 5、点击下一步 6、点击安装 7、安装ing 8、点击完成 至此&#xff0c;安装完成&#xff01;
阅读更多...
用户说 | 零基础用通义灵码 AI 程序员开发个人笔记网站

用户说 | 零基础用通义灵码 AI 程序员开发个人笔记网站

作者&#xff1a;宋镇江&#xff0c;安阳幼儿师范高等专科学校数字媒体技术专业教师 通义灵码是一款基于通义大模型的智能编码辅助工具&#xff0c;支持自然语言生成代码、单元测试生成、代码注释生成等功能&#xff0c;兼容多种主流IDE和编程语言。对于零基础用户&#xff0c…
阅读更多...
试验一 mybatis 入门操作

试验一 mybatis 入门操作

试验一 mybatis 入门操作 一 实验目的 1.掌握mybatis基础操作&#xff0c;包括如何在maven工程中引入依赖&#xff0c;创建mapper文件&#xff0c;核心配置文件&#xff0c;映射文件&#xff0c;并测试对数据库表基本的的CRUD操作&#xff1b; 2.掌握核心配置文件中几个重要标…
阅读更多...
使用Gitee Go流水线部署个人项目到服务器指南

使用Gitee Go流水线部署个人项目到服务器指南

使用Gitee Go流水线部署个人项目到服务器指南 前言&#xff01;&#xff01;&#xff01; 本文解决的问题&#xff1a; 你有一台ECS服务器&#xff0c;你在上面部署了一个Java服务也就是一个jar&#xff0c;你觉着你每次手动本地打包&#xff0c;上传&#xff0c;在通过命令去…
阅读更多...
LCCI ESG 中英联合认证国际分析师适合的岗位

LCCI ESG 中英联合认证国际分析师适合的岗位

LCCI ESG中英联合认证国际分析师领域热门岗位大揭秘&#xff01;&#x1f30d; 大家好&#xff01;今天我们来探讨LCCI ESG中英联合认证国际分析师领域的热门岗位&#xff0c;看看是否有适合你的选择。 1️⃣ LCCI ESG中英联合认证国际分析师报告专员&#xff1a;主要负责编制…
阅读更多...
Compose 实践与探索十五 —— 自定义触摸

Compose 实践与探索十五 —— 自定义触摸

1、自定义触摸与一维滑动监测 之前我们在讲 Modifier 时讲过如下与手势检测相关的 Modifier&#xff1a; Modifier.clickable { } Modifier.combinedClickable { } Modifier.pointerInput {detectTapGestures { } }这里对以上内容就不再赘述了&#xff0c;直接去讲解更复杂的…
阅读更多...
【Linux】Makefile秘籍

【Linux】Makefile秘籍

> &#x1f343; 本系列为Linux的内容&#xff0c;如果感兴趣&#xff0c;欢迎订阅&#x1f6a9; > &#x1f38a;个人主页:【小编的个人主页】 >小编将在这里分享学习Linux的心路历程✨和知识分享&#x1f50d; >如果本篇文章有问题&#xff0c;还请多多包涵&a…
阅读更多...
LDAP从入门到实战：环境部署与配置指南（上）

LDAP从入门到实战：环境部署与配置指南（上）

#作者&#xff1a;朱雷 文章目录 一、LDAP 简介1.1. 什么是目录服务1.2. 什么是 LDAP1.3. LDAP的基本模型 二、Ldap环境部署2.1.下载软件包2.2.安装软件2.3.编辑配置文件2.4.启动服务 一、LDAP 简介 1.1. 什么是目录服务 目录是专门为搜索和浏览而设计的专用数据库&#xff…
阅读更多...
《C++智能指针：建议使用 make_shared 代替 shared_ptr》

《C++智能指针：建议使用 make_shared 代替 shared_ptr》

《C 智能指针&#xff1a;长达数十年的血泪史&#xff0c;一步步征服内存泄漏》-CSDN博客 shared_ptr<int> sp1(new int(10)); 这句代码实际存在两个内存开辟&#xff0c;一是开辟我们要托管的内存资源 &#xff0c;二是开辟引用计数的资源&#xff0c;引用技术也是new出…
阅读更多...
代码随想录刷题day50|（回溯算法篇）131.分割回文串▲

代码随想录刷题day50|（回溯算法篇）131.分割回文串▲

目录 一、回溯算法基础知识 二、分割回文串思路 2.1 如何切割 2.2 判断回文 2.3 回溯三部曲 2.4 其他问题 三、相关算法题目 四、总结 一、回溯算法基础知识 详见&#xff1a;代码随想录刷题day46|&#xff08;回溯算法篇&#xff09;77.组合-CSDN博客 二、分割回文…
阅读更多...
vivo 湖仓架构的性能提升之旅

vivo 湖仓架构的性能提升之旅

作者&#xff1a;郭小龙 vivo互联网 大数据高级研发工程师 导读&#xff1a;本文整理自 vivo互联网 大数据高级研发工程师 郭小龙 在 StarRocks 年度峰会上的分享&#xff0c;聚焦 vivo 大数据多维分析面临的挑战、StarRocks 落地方案及应用收益。 在 即席分析 场景&#xff0c…
阅读更多...
Springboot的jak安装与配置教程

Springboot的jak安装与配置教程

目录 Windows系统 macOS系统 Linux系统 Windows系统 下载JDK&#xff1a; 访问Oracle官网或其他JDK提供商网站&#xff0c;下载适合Windows系统的JDK版本。网站地址&#xff1a;Oracle 甲骨文中国 | 云应用和云平台点击进入下滑&#xff0c;点击进入下载根据自己的系统选择&…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023