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

动态顺序表

news 2026/3/27 0:51:12

一.概念

顺序表是线性表的一种(其中常见的线性表：顺序表，链表，栈，队列，字符串......），顺序表的底层是数组，但顺序表能够实现数据的增删查改等操作，而数组不行。因此学习线性表能够让我们更好的管理数据。

二.分类

顺序表主要分为静态顺序表和动态顺序表，动态顺序表应用广泛，下面讲解的是动态顺序表

补充：静态顺序表主要框架

//静态顺序表 #define N 100 struct SeqList { int arr[N]; int size;//有效个数 };

三.代码实现

1.顺序表框架--结构体

typedef int SLDataType;//对类型重命名 typedef struct SeqList { SLDataType* arr; int size;//有效数据个数 int capacity;//空间大小 }SL;//对结构体类型重命名

2.顺序表初始化

void SLInit(SL* ps); void SLInit(SL* ps) { ps->arr = NULL;//空指针 ps -> size = ps -> capacity = 0; }

3.顺序表的销毁

void SLDestroy(SL* ps); void SLDestroy(SL* ps) { if (ps->arr)//判断是否为空指针 {//不为空指针，销毁 free(ps->arr); } ps->arr = NULL;//销毁后置为空指针 ps->size = ps->capacity = 0; }

4.顺序表的尾插

void SLPushBack(SL* ps, SLDataType x);//传结构体指针+插入数据类型变量 void SLCheckCapacity(SL* ps) { if (ps->size == ps->capacity)//判断size和capacity是否相等 { //判断空间大小是否为0，创建新变量 int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity; //申请/增容空间realloc： //一般增容增2/3倍 SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));//注意乘数据类型大小+强制类型转化+临时指针变量 if (tmp == NULL) { perror("realloc"); return 1; } ps->arr = tmp; ps->capacity = newCapacity;//别漏 } } void SLPushBack(SL* ps, SLDataType x) { assert(ps);//注意判断是否为空指针 //或： //if(ps==NULL) //{ // return; //} SLCheckCapacity(ps); ps->arr[ps->size++] = x; //或：ps->arr[ps->size] = x; //++ps->size; }

5.顺序表的头插

void SLPushFront(SL* ps, SLDataType x);//传结构体指针+插入数据类型变量 void SLCheckCapacity(SL* ps) { if (ps->size == ps->capacity)//判断size和capacity是否相等 { //判断空间大小是否为0，创建新变量 int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity; //申请/增容空间realloc： //一般增容增2/3倍 SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));//注意乘数据类型大小+强制类型转化+临时指针变量 if (tmp == NULL) { perror("realloc"); return 1; } ps->arr = tmp; ps->capacity = newCapacity;//别漏 } } 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]; } //memmove： ps->arr[0] = x; ps->size++;//别漏！！！只要插入数据，size要++ }

6.顺序表的尾删

void SLPopBack(SL* ps); void SLPopBack(SL* ps) { assert(ps); assert(ps->size);//顺序表不为空 //ps->arr[ps->size-1]=-1; --ps->size; }

7.顺序表的头删

void SLPopFront(SL* ps); void SLPopFront(SL* ps) { assert(ps); assert(ps->size); for (int i = 0; i < ps->size-1; i++) { ps->arr[i] = ps->arr[i + 1];//最后一次：ps->arr[i-2]=ps->arr[i-1] } ps->size--; }

8.在指定位置插入数据

void SLInsert(SL* ps, int pos, SLDataType x); 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+1]=ps->arr[pos]; } ps->arr[pos] = x; ps->size++; }

9.删除指定位置的数据

void SLErase(SL* ps, int pos); 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->arr[ps->size-2]=ps->arr[ps->size-1] } ps->size--; }

10.顺序表的查找

int SLFind(SL* ps, SLDataType x); 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;//没找到，返回-1 }

整体代码

test.c

#define _CRT_SECURE_NO_WARNINGS 1 #include "SeqList.h"//注意头文件 /* struct SeqList { int* arr; int size；//有效数据个数 int capacity;//空间大小 }; */ #include<stdio.h> SL sl;//sl无初始化，因此传址调用 void SLTest01() { //顺序表的初始化 SLInit(&sl); //顺序表的增删查改等操作 //尾插： SLPushBack(&sl, 1); SLPushBack(&sl, 2); SLPushBack(&sl, 3); SLPushBack(&sl, 4); SLPushBack(&sl, 5); SLPrint(sl);//打印1 2 3 4 5 //头插： SLPushFront(&sl, 0); SLPrint(sl);//打印0 1 2 3 4 5 //尾删： SLPopBack(&sl); SLPrint(sl);//打印1 2 3 4 //头删： SLPopFront(&sl); SLPopFront(&sl); SLPopFront(&sl); SLPopFront(&sl); SLPopFront(&sl); SLPrint(sl);//打印2 3 4 //顺序表的销毁 SLDestroy(&sl); } SLTest02() { //顺序表的初始化 SLInit(&sl); SLPushBack(&sl, 1); SLPushBack(&sl, 2); SLPushBack(&sl, 3); SLPushBack(&sl, 4); SLPushBack(&sl, 5); SLPrint(sl);//打印1 2 3 4 5 SLInsert(&sl, 1, 100); SLPrint(sl);//打印1 100 2 3 4 5 SLInsert(&sl, sl.size, 200); SLPrint(sl);//打印1 100 2 3 4 5 200 SLInsert(&sl, 0, 0); SLPrint(sl);//打印0 1 100 2 3 4 5 200 SLErase(&sl, 1); SLPrint(sl);//打印0 100 2 3 4 5 200 printf("%d\n",SLFind(&sl, 100)); } int main() { //SLTest01(); SLTest02(); return 0; }

SeqList.c

#define _CRT_SECURE_NO_WARNINGS 1 #include"SeqList.h"//注意头文件 void SLCheckCapacity(SL* ps) { if (ps->size == ps->capacity)//判断size和capacity是否相等 { //判断空间大小是否为0，创建新变量 int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity; //申请/增容空间realloc： //一般增容增2/3倍 SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));//注意乘数据类型大小+强制类型转化+临时指针变量 if (tmp == NULL) { perror("realloc"); return 1; } ps->arr = tmp; ps->capacity = newCapacity;//别漏 } } void SLInit(SL* ps) { ps->arr = NULL;//空指针 ps -> size = ps -> capacity = 0; } void SLDestroy(SL* ps) { if (ps->arr)//判断是否为空指针 {//不为空指针，销毁 free(ps->arr); } ps->arr = NULL;//销毁后置为空指针 ps->size = ps->capacity = 0; } void SLPushBack(SL* ps, SLDataType x) { assert(ps);//注意判断是否为空指针 //或： //if(ps==NULL) //{ // return; //} SLCheckCapacity(ps); ps->arr[ps->size++] = x; //或：ps->arr[ps->size] = x; //++ps->size; } 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]; } //memmove： ps->arr[0] = x; ps->size++;//别漏！！！只要插入数据，size要++ } void SLPrint(SL s) { for (int i = 0; i < s.size; i++) { printf("%d ", s.arr[i]); } printf("\n"); } void SLPopBack(SL* ps) { assert(ps); assert(ps->size);//顺序表不为空 //ps->arr[ps->size-1]=-1; --ps->size; } void SLPopFront(SL* ps) { assert(ps); assert(ps->size); for (int i = 0; i < ps->size-1; i++) { ps->arr[i] = ps->arr[i + 1];//最后一次：ps->arr[i-2]=ps->arr[i-1] } 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+1]=ps->arr[pos]; } 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->arr[ps->size-2]=ps->arr[ps->size-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;//没找到，返回-1 } //注意不要漏assert // realloc常见易错点 // ps->arr,ps->capacity注意要赋值 //插入或删除数据后size要变化

SeqList.h

#pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> //定义顺序表的结构 //静态顺序表 //#define N 100 //struct SeqList //{ // int arr[N]; // int size;//有效个数 //}; //动态顺序表 typedef int SLDataType;//对类型重命名 typedef struct SeqList { SLDataType* arr; int size;//有效数据个数 int capacity;//空间大小 }SL;//对结构体类型重命名 //顺序表初始化 void SLInit(SL* ps); //顺序表的销毁 void SLDestroy(SL* ps); //尾部插入 void SLPushBack(SL* ps, SLDataType x);//传结构体指针+插入数据类型变量 //头部插入 void SLPushFront(SL* ps, SLDataType x);//传结构体指针+插入数据类型变量 //尾部删除 void SLPopBack(SL* ps); //头部删除 void SLPopFront(SL* ps); //顺序表的打印 void SLPrint(SL s);//打印不传指针 //在指定位置插入数据 void SLInsert(SL* ps, int pos, SLDataType x); //删除指定位置的数据 void SLErase(SL* ps, int pos); //顺序表的查找 int SLFind(SL* ps, SLDataType x);

文章到这里就结束了，创造不易，如果喜欢的话点个关注，点个赞，谢谢大家！

http://www.jsqmd.com/news/229376/

相关文章：

  • Qwen大模型新手指南：没环境别怕，3步体验
  • AI助力自动化测试：用ALLURE下载生成精美测试报告
  • Qwen vs ChatGLM实测对比：云端GPU 2小时搞定选型
  • 中文情感分析模型应用：StructBERT在客服系统实战案例
  • SpringBoot开发效率提升：传统vsAI辅助对比
  • 对比评测：传统PC维护 vs Microsoft PC Manager服务
  • AI恶意流量识别避坑指南：云端GPU 1小时1块，新手友好
  • 无需安装！5分钟快速验证JDK1.8环境的云方案
  • Process Explorer入门指南：小白也能看懂的系统监控教程
  • WSL2中Ubuntu发行版的完全卸载干净指南
  • LangChain中文手册VS传统开发：效率提升对比
  • 5个为什么选择YashanDB提升数据库效率
  • 轻量级中文情感分析解决方案：StructBERT部署与优化全攻略
  • StructBERT轻量级情感分析：企业级教程
  • 智能工单分类实战：从Excel到AI的云端升级之路
  • nodejs基于Vue的电子数码手机商城交易平台秒杀_b6thv
  • AI智能体舆情监测方案：10分钟部署，比人工快24小时发现危机
  • AutoGLM-Phone-9B实战：构建智能客服移动应用
  • 5个小技巧帮你掌握YashanDB数据库的高级功能
  • 没GPU如何做AI项目？智能侦测云端方案，成本直降80%
  • nodejs基于Vue的钢材商城销售订单管理系统_17585
  • 5个小技巧帮助你提升YashanDB数据库的安全性
  • StructBERT轻量级部署：情感分析API调优
  • AI如何帮你快速构建贝叶斯网络模型
  • 网络异常检测从零开始：云端GPU手把手教学，2小时掌握
  • 5个小贴士帮助你更好地管理YashanDB数据库
  • 如何用AI快速生成EASYDATASET处理代码
  • Linux小白必看：3分钟学会修改系统时间
  • AI如何解决微信小程序WXSS选择器限制问题
  • 5个行业最佳实践：使用YashanDB达成目标