当前位置： 首页 > news >正文

顺序表——功能实现

news 2025/8/22 2:22:45

 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.lryc.cn/news/334018.html

相关文章：

  • 达梦导出工具dexp
  • Ubuntu 22.04安装新硬盘并启动时自动挂载
  • Mybatis中sqlSession.getMapper背后的原理
  • [环境配置]conda 64位安装32位python
  • 某虚假交友APP(信息窃取)逆向分析
  • 基于FPGA的按键消抖
  • 1.网络编程-网络协议
  • 代码+视频，手动绘制logistic回归预测模型校准曲线（Calibration curve）（2）
  • 金融数据_Scikit-Learn决策树(DecisionTreeClassifier)实例
  • bash的login shell与non-login shell，以及各自的初始化过程
  • 为什么苹果 Mac 电脑需要使用清理软件？
  • 33. UE5 RPG使用增强输入激活GameplayAbility（三）
  • speech to text 库FastASR交叉编译arm target的配置
  • WPS快速将插入Excle数据插入Word
  • Springboot 集成Rabbitmq之延时队列
  • 【云开发笔记NO.22】运用云原生产品打造技术中台
  • C++进阶(五) 哈希
  • 【算法基础】基于异或的排序、基于异或的经典面试题
  • HTML2:列表和表格
  • 用于无人机小型化设计的高精度温补晶振
  • 轨迹规划 | 图解最优控制LQR算法(附ROS C++/Python/Matlab仿真)
  • 工业视觉检测
  • wheeltec轮趣ROS教育机器人的网络连接
  • 【Linux ARM 裸机】开发环境搭建
  • 怎么保证缓存与数据库的最终一致性？
  • 免费SSL通配符证书/SSL泛域名证书获取教程
  • mysql结构与sql执行流程
  • vue快速入门（十二）v-key索引标志
  • 智能网联汽车自动驾驶数据记录系统DSSAD数据配置
  • linux知识点