数据结构之顺序表

前言

顺序表采用模块化编程思路，顺序表的实现使用3个模块，test.c—测试模块 Seqlist.c—接口函数的实现模块  seqlist.h—接口函数声明

顺序表的基本概念

顺序表是在计算机内存中通常以数组形式存储的线性表，线性表是n个具有相同特性的数据元素的有限序列，线性表的顺序存储是用一组地址连续的存储单元依次存储线性表中的各个元素；采用顺序存储结构的线性表通常称为顺序表，顺序表是将表中的节点依次存放在计算机内存中一组地址连续的存储单元之中；

顺序表的结构

静态顺序表

静态顺序表：使用定长数组存储元素;

//静态顺序表
# define N 100
typedef int SeqlistDatatye;
typedef struct Seqlist
{SeqlistDatatye nums[N];int size;//记录有效数据的个数
}Seqlist;

静态顺序表的缺点：当定义容量的N太小，空间不够使用，当N过大，浪费多余的空间；

为解决这种缺点，创建了动态顺序表，可以根据需要分配空间的大小；

动态顺序表

动态顺序表：使用动态开辟的数组存储；

//动态顺序表
typedef int SLDataType;
typedef struct Seqlist
{SLDataType* nums;//nums指向动态开辟的数组int size;//记录有效数据的个数int capacity;//存储有效数据的容量大小,单位为每个结构体的大小
}Seqlist;

如图所示：

动态顺序表的优点：动态顺序表的容量由动态内存函数所开辟，当容量不够使用时可以增加容量capacity, 扩容方法是利用realloc()函数动态开辟一块新的空间（新空间的大小一般为原空间的两倍），若为本地扩容，直接返回原先空间的起始地址，若为异地扩容，首先将旧空间的数据拷贝到新的空间，其次释放旧的空间,最后返回新空间的起始地址；

顺序表的接口实现

1.顺序表的初始化

//test.c文件void Test()
{Seqlist SL;//创建顺序表InitSeqlist(&SL);//初始化顺序表
}
int main()
{Test();return 0;
}
//Seqlist.c文件
//初始化顺序表
void InitSeqlist(Seqlist* ps)
{assert(ps != NULL);//开辟一定容量的空间 (*ps).nums成员类型为SLDataType*，malloc返回值类型为void*,所以发生强转ps->nums = (SLDataType*)malloc(4 * sizeof(SLDataType*));//判断空间开辟是否成功if (ps->nums == NULL){perror("malloc");exit(-1);//exit()函数 exit(0)表示正常退出，exit(x),x不为0表示异常退出，终止正在执行的进程;}//空间开辟成功ps->size = 0;ps->capacity = 4;//单位大小为sizeof(SLDataType*)
}

 调试窗口：

2.顺序表的销毁

//Seqlist.c文件//顺序表的销毁
void DestroySeqlist(Seqlist* ps)
{assert(ps != NULL);free(ps->nums);ps->nums = NULL;ps->size = 0;ps->capacity = 0;
}

3.顺序表显示

//Seqlist.c文件void printSeqlist(Seqlist* ps)
{assert(ps != NULL);int i = 0;for (i = 0; i < ps->size; i++){printf("%d ", ps->nums[i]);}printf("\n");
}

4.顺序表尾插元素

//Seqlist.c文件void Seqlistpushback(Seqlist* ps, SLDataType x)
{assert(ps != NULL);//首先应该判断顺序表是否已满,若空间已满，进行扩容;//当ps->size=ps->capacity说明空间已满if (ps->capacity == ps->size){//用realloc()函数进行扩容，出现两种情况 1.同地扩容 2.异地扩容//必须新建变量接收扩容后的地址变量;SLDataType* tmp = (SLDataType*)realloc(ps->nums, (ps->capacity) * 2 * sizeof(SLDataType));if (tmp == NULL){perror("realloc failed");exit(-1);}ps->capacity = (ps->capacity) * 2;ps->nums = tmp;}//扩容成功，尾插元素//总共有ps->size个有效数据,数组下标范围为0到(ps->size)-1;ps->nums[ps->size] = x;ps->size++;}

顺序表尾插元素测试

void Test1()
{Seqlist SL;InitSeqlist(&SL);Seqlistpushback(&SL, 1);Seqlistpushback(&SL, 2);Seqlistpushback(&SL, 3);Seqlistpushback(&SL, 4);Seqlistpushback(&SL, 5);printSeqlist(&SL);DestroySeqlist(&SL);
}int main()
{Test1();return 0;
}

运行结果：

5.顺序表尾删元素

void Seqlistpopback(Seqlist* ps)
{assert(ps != NULL);//首先检查顺序表中是否可以有元素删除,若不做检查，可能导致指针越界访问;//检查方式一/*if (ps->size == 0){return;}*///检查方式二assert(ps->size > 0);//尾删元素ps->size--;}

顺序表尾删元素测试

//尾删元素测试
void Test2()
{Seqlist SL;InitSeqlist(&SL);Seqlistpushback(&SL, 1);Seqlistpushback(&SL, 2);Seqlistpushback(&SL, 3);Seqlistpushback(&SL, 4);Seqlistpushback(&SL, 5);printSeqlist(&SL);Seqlistpopback(&SL);printSeqlist(&SL);DestroySeqlist(&SL);
}int main()
{Test2();return 0;
}

运行结果：

6.顺序表头插元素

当顺序表头插和尾插元素时，需要检查空间是否足够使用，若空间不够，需要进行扩容，为使代码不要冗余，单独封装为Checkcapacity()函数,方便使用；

扩容函数的封装

void CheckCapacity(Seqlist* ps)
{assert(ps != NULL);//首先应该判断顺序表是否已满,若空间已满，进行扩容;//当ps->size=ps->capacity说明空间已满if (ps->capacity == ps->size){//用realloc()函数进行扩容，出现两种情况 1.本地扩容 2.异地扩容//必须新建变量接收扩容后的地址变量;SLDataType* tmp = (SLDataType*)realloc(ps->nums, (ps->capacity) * 2 * sizeof(SLDataType));if (tmp == NULL){perror("realloc failed");exit(-1);}ps->capacity = (ps->capacity) * 2;ps->nums = tmp;}
}

顺序表头插元素的实现

void Seqlistpushfront(Seqlist* ps, SLDataType x)
{assert(ps != NULL);CheckCapacity(ps);//从后向前依次拷贝数据，直至首元素int end = ps->size - 1;while (end >= 0){ps->nums[end + 1] = ps->nums[end];--end;}//插入元素ps->nums[0] = x;ps->size++;
}

顺序表头插元素测试

//头插元素测试
void Test3()
{Seqlist SL;InitSeqlist(&SL);Seqlistpushfront(&SL, 1);Seqlistpushfront(&SL, 2);Seqlistpushfront(&SL, 3);Seqlistpushfront(&SL, 4);Seqlistpushfront(&SL, 5);printSeqlist(&SL);DestroySeqlist(&SL);}
int main ()
{Test3();return 0;
}

运行结果如下：

7.顺序表头删元素

//顺序表头删元素
void Seqlistpopfront(Seqlist* ps)
{assert(ps != NULL);assert(ps->size > 0);int begin = 1;while (begin < ps->size){ps->nums[begin - 1] = ps->nums[begin];++begin;}ps->size--;}

顺序表头删元素测试

void Test4()
{Seqlist SL;InitSeqlist(&SL);Seqlistpushback(&SL, 1);Seqlistpushback(&SL, 2);Seqlistpushback(&SL, 3);Seqlistpushback(&SL, 4);Seqlistpushback(&SL, 5);printSeqlist(&SL);Seqlistpopfront(&SL);printSeqlist(&SL);Seqlistpopfront(&SL);printSeqlist(&SL);DestroySeqlist(&SL);
}
int main()
{ Test4();return 0;
}

运行结果：

8.顺序表在pos位置插入元素x

void SeqlistInsert(Seqlist* ps, int pos, SLDataType x)
{assert(ps != NULL);assert(pos >= 0 && pos <= ps->size);CheckCapacity(ps);//从顺序表最后一个元素向前拷贝，向后移动，直到pos位置为止int end = ps->size - 1;while (end >= pos){ps->nums[end + 1] = ps->nums[end];end--;}ps->nums[pos] = x;ps->size++;
}

顺序表在pos位置插入元素x测试

void Test5()
{Seqlist SL;InitSeqlist(&SL);Seqlistpushback(&SL, 1);Seqlistpushback(&SL, 2);Seqlistpushback(&SL, 3);Seqlistpushback(&SL, 4);Seqlistpushback(&SL, 5);printSeqlist(&SL);SeqlistInsert(&SL, 3, 20);printSeqlist(&SL);DestroySeqlist(&SL);
}
int main()
{Test5();return 0;
}

运行结果：

9.顺序表查找某元素

//顺序表查找某个元素(查找到该元素返回下标，查找不到返回-1)
int SeqlistFind(Seqlist* ps, SLDataType x)
{assert(ps != NULL);int j = 0;for (j = 0; j < ps->size; j++){if (ps->nums[j] == x){return j;break;}}//查找不到该元素return -1;
}

顺序表查找某元素测试

void Test6()
{Seqlist SL;InitSeqlist(&SL);Seqlistpushback(&SL, 1);Seqlistpushback(&SL, 2);Seqlistpushback(&SL, 3);Seqlistpushback(&SL, 4);Seqlistpushback(&SL, 5);int x;printf("请输入要查找的元素\n");scanf("%d", &x);int pos = SeqlistFind(&SL, x);if (pos != -1){SeqlistInsert(&SL, pos, x * 10);printSeqlist(&SL);}else{printf("查找的元素不存在\n");}DestroySeqlist(&SL);
}
int main()
{Test6();return 0;
}

运行结果：

10.顺序表删除指定位置pos处的值

void SeqlistErase(Seqlist* ps, int pos)
{assert(ps != NULL);//首先判断pos位置下标是否合法，避免数组越界访问assert(pos >= 0 && pos < ps->size);//坐标合法,从pos下一个位置从前向后拷贝int begin = pos + 1;while (begin<ps->size){ps->nums[begin - 1] = ps->nums[begin];begin++;}ps->size--;}

顺序表删除指定位置pos处的值测试

void Test7()
{Seqlist SL;InitSeqlist(&SL);Seqlistpushback(&SL, 1);Seqlistpushback(&SL, 2);Seqlistpushback(&SL, 3);Seqlistpushback(&SL, 4);Seqlistpushback(&SL, 5);printSeqlist(&SL);int x;printf("请输入要删除的元素\n");scanf("%d", &x);int pos = SeqlistFind(&SL, x);if (pos != -1){SeqlistErase(&SL, pos);printSeqlist(&SL);}else{printf("删除的元素不存在\n");}DestroySeqlist(&SL);
}
int main()
{Test7();return 0;
}

运行结果：

 11.头插函数改造版本SeqlistPushfront()函数

利用SeqlistInsert()函数改造头插 ，尾插函数；

//头插函数改造版
void SeqlistPushfront(Seqlist* ps, SLDataType x)
{SeqlistInsert(ps, 0, x);
}

SeqlistPushfront()函数测试

void Test8()
{Seqlist SL;InitSeqlist(&SL);SeqlistPushfront(&SL, 10);SeqlistPushfront(&SL, 20);SeqlistPushfront(&SL, 30);SeqlistPushfront(&SL, 40);SeqlistPushfront(&SL, 50);printSeqlist(&SL);DestroySeqlist(&SL);
}
int main()
{Test8();return 0;
}

运行结果：

12.尾插函数改造版本SeqlistPushback()函数

void SeqlistPushback(Seqlist* ps, SLDataType x)
{SeqlistInsert(ps, ps->size, x);
}

SeqlistPushback()函数测试

void Test9()
{Seqlist SL;InitSeqlist(&SL);SeqlistPushback(&SL, 11);SeqlistPushback(&SL, 12);SeqlistPushback(&SL, 13);SeqlistPushback(&SL, 14);SeqlistPushback(&SL, 15);printSeqlist(&SL);DestroySeqlist(&SL);
}int main()
{Test9();return 0;
}

运行结果：

13.头删函数改造版本SeqlistPopfront()函数

利用SeqlistErase()函数改造头删 尾删函数；

void SeqlistPopfront(Seqlist* ps)
{SeqlistErase(ps, 0);
}

 SeqlistPopfront()函数测试

void Test10()
{Seqlist SL;InitSeqlist(&SL);Seqlistpushback(&SL, 1);Seqlistpushback(&SL, 2);Seqlistpushback(&SL, 3);Seqlistpushback(&SL, 4);Seqlistpushback(&SL, 5);printSeqlist(&SL);SeqlistPopfront(&SL);printSeqlist(&SL);DestroySeqlist(&SL);
}
int main()
{Test10();return 0;
}

运行结果：

14.尾删函数改造版本SeqlistPopback()函数

void Test11()
{Seqlist SL;InitSeqlist(&SL);Seqlistpushback(&SL, 1);Seqlistpushback(&SL, 2);Seqlistpushback(&SL, 3);Seqlistpushback(&SL, 4);Seqlistpushback(&SL, 5);printSeqlist(&SL);SeqlistPopback(&SL);printSeqlist(&SL);SeqlistPopback(&SL);printSeqlist(&SL);DestroySeqlist(&SL);
}
int main()
{Test11();return 0;
}

SeqlistPopback()函数测试

15.顺序表修改pos位置的值

void SeqlistModify(Seqlist* ps, int pos, SLDataType x)
{assert(ps != NULL);//检查要修改某个元素的下标是否合法assert(pos >= 0 && pos < ps->size - 1);ps->nums[pos] = x;}

顺序表修改pos位置的值测试 

void Test12()
{Seqlist SL;InitSeqlist(&SL);Seqlistpushback(&SL, 1);Seqlistpushback(&SL, 2);Seqlistpushback(&SL, 3);Seqlistpushback(&SL, 4);Seqlistpushback(&SL, 5);printSeqlist(&SL);SeqlistModify(&SL, 2, 100);printSeqlist(&SL);SeqlistModify(&SL, 2, 200);printSeqlist(&SL);DestroySeqlist(&SL);}int main()
{Test12();return 0;
}

运行结果：

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

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

相关文章

R语言绘制PCA双标图、碎石图、变量载荷图和变量贡献图

R语言绘制PCA双标图、碎石图、变量载荷图和变量贡献图

1、原论文数据双标图 代码&#xff1a; setwd("D:/Desktop/0000/R") #更改路径#导入数据 df <- read.table("Input data.csv", header T, sep ",")# ----------------------------------- #所需的包: packages <- c("ggplot2&quo…
阅读更多...
电视访问群晖共享文件失败的设置方式，降低协议版本

电视访问群晖共享文件失败的设置方式，降低协议版本

控制面板-文件服务-SMB-高级设置&#xff0c;常规及其他里面配置即可。
阅读更多...
【红外图像增强】基于引力和侧向抑制网络的红外图像增强模型（Matlab代码实现）

【红外图像增强】基于引力和侧向抑制网络的红外图像增强模型（Matlab代码实现）

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…
阅读更多...
计算机视觉: 三维物体生成

计算机视觉: 三维物体生成

三维物体生成与编辑 论文地址: Controllable Mesh Generation Through Sparse Latent Point Diffusion Models 背景 数据是目前数字化和AI领域最宝贵的财富之一&#xff0c;但是对于目前的开发者来说&#xff0c;收集数据都意味着极大的成本。所以建立一个高效的生成模型能极…
阅读更多...
Linux学习之Redis使用

Linux学习之Redis使用

搭建Redis服务器 在主机redis64运行redis服务 #安装redis服务 [rootredis64 ~]# yum install -y redis # 启动redis服务并开机启动 [rootredis64 ~]# systemctl enable redis --now # 查看redis端口 [rootredis64 ~]# ss -tnlp | grep redis-server LISTEN 0 128 …
阅读更多...
PythonWeb服务器（HTTP协议）

PythonWeb服务器（HTTP协议）

一、HTTP协议与实现原理 HTTP&#xff08;Hypertext Transfer Protocol&#xff0c;超文本传输协议&#xff09;是一种用于在网络上传输超文本数据的协议。它是Web应用程序通信的基础&#xff0c;通过客户端和服务器之间的请求和响应来传输数据。在HTTP协议中连接客户与服务器的…
阅读更多...
网工基础知识——以太网

网工基础知识——以太网

1972年Bob Metcalfe“以太网之父”被Xerox雇佣为网络专家&#xff0c;Bob Metcalfe 来到Xerox公司的Palo Alto研究中心&#xff08;PARC&#xff09;的第一个任务是把Palo Alto的计算机连接到ARPANET&#xff08;Internet的前身&#xff09;上。1972年底Bob Metcalfe以ALOHA系统…
阅读更多...
Day 02 python学习笔记

Day 02 python学习笔记

python运算符 算术运算符 混合运算的优先级&#xff1a; () 高于 ** * / // % 高于 - 赋值运算符 - * / ** a 1 > a 3 > a a 3 其余同理 注意&#xff1a; python没有自增自减 &#xff08;a a a-- --a&#xff09;…
阅读更多...
力扣刷题-链表-设计链表

力扣刷题-链表-设计链表

题意&#xff1a; 在链表类中实现这些功能&#xff1a; get(index)&#xff1a;获取链表中第 index 个节点的值。如果索引无效&#xff0c;则返回-1。 addAtHead(val)&#xff1a;在链表的第一个元素之前添加一个值为 val 的节点。插入后&#xff0c;新节点将成为链表的第一个节…
阅读更多...
华为OD机考算法题：分积木

华为OD机考算法题：分积木

目录 题目部分 解读与分析 代码实现 题目部分 题目分积木难度难题目说明Solo和koko是两兄弟&#xff0c;妈妈给了他们一大堆积木&#xff0c;每块积木上都有自己的重量。现在他们想要将这些积木分成两堆。哥哥Solo负责分配&#xff0c;弟弟koko要求两个人获得的积木总重量“…
阅读更多...
ImportError: Java package ‘edu‘ not found, requested by alias ‘edu‘

ImportError: Java package ‘edu‘ not found, requested by alias ‘edu‘

参考issue&#xff1a; https://github.com/ncbi-nlp/NegBio/issues/44 我目前的解决办法 pip uninstall jpype1 -y可以成功运行。
阅读更多...
Ubuntu修改静态IP、网关和DNS的方法总结

Ubuntu修改静态IP、网关和DNS的方法总结

Ubuntu修改静态IP、网关和DNS的方法总结 ubuntu系统&#xff08;其他debian的衍生版本好像也可以&#xff09;修改静态IP有以下几种方法。&#xff08;搜索总结&#xff0c;可能也不太对&#xff09; /etc/netplan (use) Ubuntu 18.04开始可以使用netplan配置网络&#xff0…
阅读更多...
二十五、MySQL事务的四大特性和常见的并发事务问题

二十五、MySQL事务的四大特性和常见的并发事务问题

1、事务的四大特性 2、常见的并发事务问题 &#xff08;1&#xff09;并发事务问题分类&#xff1a; &#xff08;2&#xff09;脏读&#xff1a; 一个事务正在对一条记录做修改&#xff0c;在这个事务完成并提交前&#xff0c;这条记录的数据就处于不一致的状态&#xff1b;…
阅读更多...
HTTP代理反爬虫技术详解

HTTP代理反爬虫技术详解

HTTP代理是一种网络技术&#xff0c;它可以将客户端的请求转发到目标服务器&#xff0c;并将服务器的响应返回给客户端。在网络安全领域中&#xff0c;HTTP代理经常被用来反爬虫&#xff0c;以保护网站的正常运营。 HTTP代理反爬虫的原理是通过限制访问者的IP地址、访问频率、U…
阅读更多...
【Spark】win10配置IDEA、saprk、hadoop和scala

【Spark】win10配置IDEA、saprk、hadoop和scala

终于&#xff0c;要对并行计算下手了哈哈哈。 一直讲大数据大数据&#xff0c;我单次数据处理量大概在1t上下&#xff0c;是过亿级的轨迹数据。 用python调用multiprogress编写的代码&#xff0c;用多线程也要一个多月跑完。 我对这个效率不太满意&#xff0c;希望能快一点再快…
阅读更多...
python实验2

python实验2

1、实验题目&#xff1a;个人用户信息注册 模拟用户个人信息注册&#xff0c;需要输入用户个人信息 姓名、性别、年龄、血型、身高、电话 信息&#xff0c;并输出显示。 源代码&#xff1a; print(用户个人信息注册) name input("请输入您的姓名&#xff1a;") sex…
阅读更多...
基于微信小程序四六级助手系统设计与实现(源码+lw+部署文档+讲解等)

基于微信小程序四六级助手系统设计与实现(源码+lw+部署文档+讲解等)

文章目录 前言用户微信小程序端的主要功能有&#xff1a;管理员的主要功能有&#xff1a;具体实现截图为什么选择我自己的网站自己的小程序&#xff08;小蔡coding&#xff09;有保障的售后福利 代码参考论文参考源码获取 前言 &#x1f497;博主介绍&#xff1a;✌全网粉丝10W…
阅读更多...
论文阅读_大语言模型_Llama2

论文阅读_大语言模型_Llama2

英文名称: Llama 2: Open Foundation and Fine-Tuned Chat Models 中文名称: Llama 2&#xff1a;开源的基础模型和微调的聊天模型 文章: http://arxiv.org/abs/2307.09288 代码: https://github.com/facebookresearch/llama 作者: Hugo Touvron 日期: 2023-07-19 引用次数: 11…
阅读更多...
Linux下的系统编程——线程同步（十三）

Linux下的系统编程——线程同步（十三）

前言&#xff1a; 在多线程编程中&#xff0c;如果多个线程同时访问和修改共享资源&#xff0c;可能会产生竞争条件和数据不一致的问题。同步机制用于协调线程之间的访问和操作&#xff0c;确保数据的正确性和一致性。为了避免多个线程同时访问和操作共享资源导致的问题&#…
阅读更多...
云上亚运：所使用的高新技术，你知道吗？

云上亚运：所使用的高新技术，你知道吗？

作者简介&#xff1a;一名云计算网络运维人员、每天分享网络与运维的技术与干货。 公众号&#xff1a;网络豆云计算学堂 座右铭&#xff1a;低头赶路&#xff0c;敬事如仪 个人主页&#xff1a; 网络豆的主页​​​​​ 目录 前言 一.什么是云上亚运会 二.为什么要使用云…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023

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