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

数据结构 02（线性：顺序表）

java 2025/8/30 5:37:31

目录

线性表

顺序表

概念与结构

动态顺序表的实现

头文件的创建

顺序表初始化

顺序表的扩容

尾插功能

头插功能

尾删功能

头删功能

查找功能

任意位置前插入

任意位置前删除

销毁

动态顺序表整体呈现

SeqList.h

SeqList.c

线性表

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

线性表的逻辑结构一定是线性的，但物理结构不一定是线性的。

顺序表

概念与结构

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

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

分类：分为静态顺序表和动态顺序表（常用）。

动态顺序表的实现

头文件的创建

我们要在头文件中完成顺序表的创建和头文件与函数的声明。

typedef int SLDataType;
typedef struct SeqList
{SLDataType* arr;int size;int capacity;
}SL;

这是头文件的包含和顺序表的创建。

这是对函数的声明，以上函数我们都会讲到。

顺序表初始化

首先我们要在源文件中包含刚刚我们创建的头文件。

然后对顺序表进行初始化。

void SLInit(SL* ps)//初始化
{ps->arr = NULL;ps->size = ps->capacity = 0;
}

顺序表的扩容

现在我们的顺序表里面什么都没有，我们要扩大我们的空间。或者当我们的顺序表空间满了的时候，我们也要扩大我们的空间。

所以我们要先写好函数对顺序表进行扩容。

扩容函数中我们需要使用realloc函数额外申请空间。

注意：进行扩容操作时请用临时变量，防止发生问题造成不可逆的伤害。

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 fail!");exit(1);}ps->arr = tmp;ps->capacity = newcapacity;}
}

尾插功能

实现尾插功能很简单，size刚好是数组最后一个元素的后一个下标，确定指针的安全后直接令arr[size]等于x就完成了。

void SLPushBack(SL* ps,SLDataType x)//尾插
{assert(ps);SLCheckCapacity(ps);ps->arr[ps->size++] = x;
}

头插功能

头插功能比尾插复杂一点点，需要让数组中的元素整体后移一个位置，让arr[0]空缺起来实现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;
}

尾删功能

尾删很简单，直接让size减一就好了。

void SLPopBack(SL* ps)//尾删
{assert(ps && ps->size);--ps->size;
}

头删功能

头删也很简单，就让后面的元素把前面的元素一一覆盖就好了。

void SLPopFront(SL* ps)//头删
{assert(ps && ps->size);for (int i = 0; i < ps->size - 1; i++){ps->arr[i] = ps->arr[i + 1];}--ps->size;
}

查找功能

遍历数组查找元素，找到返回下标，没找到返回-1。

int SLFind(SL* ps, SLDataType x)//查找
{for (int i = 0; i < ps->size; i++){if (ps->arr[i] == x)return i;}return -1;
}

任意位置前插入

这是建立在头插的基础上的，让pos后的元素一一往后移一个位置把pos空出来实现插入。

void SLInsert(SL* ps, int pos, SLDataType x)//任意位置前插入
{assert(ps);assert(pos >= 0 && pos <= ps->size);for (int i = ps->size; i > pos; i--){ps->arr[i] = ps->arr[i - 1];}ps->arr[pos] = x;++ps->size;
}

任意位置前删除

和头删很相似，让pos后的元素一一往前移一个位置覆盖pos。

void SLErase(SL* ps, int pos)//任意位置前删除
{assert(ps && ps->size);assert(pos >= 0 && pos < ps->size);for (int i = pos; i < ps->size - 1; i++){ps->arr[i] = ps->arr[i + 1];}--ps->size;
}

销毁

结束后一定要进行函数的销毁操作。

void SLDesTroy(SL* ps)//销毁
{if (ps->arr)free(ps->arr);ps->arr = NULL;ps->size = ps->capacity = 0;
}

动态顺序表整体呈现

SeqList.h

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>typedef int SLDataType;
typedef struct SeqList
{SLDataType* arr;int size;int capacity;
}SL;void SLInit(SL* ps);
void SLDesTroy(SL* ps);
void SListPrint(SL s);
void SLCheckCapacity(SL* ps);
void SLPushBack(SL* ps,SLDataType x);
void SLPushFront(SL* ps, SLDataType x);
void SLPopBack(SL* ps);
void SLPopFront(SL* ps);
void SLInsert(SL* ps, int pos, SLDataType x);
void SLErase(SL* ps, int pos);
int SLFind(SL* ps, SLDataType);

SeqList.c

#define _CRT_SECURE_NO_WARNINGS
#include "SeqList.h"void SLInit(SL* ps)//初始化
{ps->arr = NULL;ps->size = ps->capacity = 0;
}void SListPrint(SL s)//打印
{for (int i = 0; i < s.size; i++){printf("%d ", s.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 fail!");exit(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 SLPopBack(SL* ps)//尾删
{assert(ps && ps->size);--ps->size;
}void SLPopFront(SL* ps)//头删
{assert(ps && ps->size);for (int i = 0; i < ps->size - 1; i++){ps->arr[i] = ps->arr[i + 1];}--ps->size;
}int SLFind(SL* ps, SLDataType x)//查找
{for (int i = 0; i < ps->size; i++){if (ps->arr[i] == x)return i;}return -1;
}void SLInsert(SL* ps, int pos, SLDataType x)//任意位置前插入
{assert(ps);assert(pos >= 0 && pos <= ps->size);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 && ps->size);assert(pos >= 0 && pos < ps->size);for (int i = pos; i < ps->size - 1; i++){ps->arr[i] = ps->arr[i + 1];}--ps->size;
}void SLDesTroy(SL* ps)//销毁
{if (ps->arr)free(ps->arr);ps->arr = NULL;ps->size = ps->capacity = 0;
}
http://www.xdnf.cn/news/19069.html

相关文章：

  • aggregating英文单词学习
  • 数字人 + 矩阵聚合系统源码搭建与定制化开发
  • Python 轻量级 HTML 解析器 - lxml入门教程
  • 通过Kubernetes安装mysql5服务
  • 深入解析Qt节点编辑器框架：数据流转与扩展机制（三）
  • 4. LangChain4j 模型参数配置超详细说明
  • 机器学习回顾——线性回归
  • Redis红锁（RedLock）解密:分布式锁的高可用终极方案
  • DBeaver中禁用PostgreSQL SSL的配置指南
  • 【性能优化】Unity 渲染优化全解析：Draw Call、Batch、SetPass 与批处理技术
  • 【Django】首次创建Django项目初始化
  • “帕萨特B5钳盘式制动器结构设计三维PROE模型7张CAD图纸PDF图“
  • 人工智能基础概念
  • 秋招笔记-8.28
  • 总结:在工作场景中的应用。（Excel）
  • Dify学习
  • 响应式编程框架Reactor【1】
  • Python 多版本环境治理理念驱动的系统架构设计——三维治理、四级隔离、五项自治 原则（路径治理升级修订 V 2.0 版）
  • 【深度学习新浪潮】显著性检测最新研究进展（2022-2025）
  • 上线问题——Mac系统下如何获取鸿蒙APP证书公钥和MD5指纹
  • 高并发内存池（14）- PageCache回收内存
  • Node.js的特性
  • 损失函数，及其优化方法
  • JS中的String总结
  • 2002-2020年全国投入产出表数据
  • Python 中的反射机制与动态灵活性
  • 实测阿里图像编辑模型Qwen-Image-Edit：汉字也能无痕修改（附实测案例）
  • react+vite+ts 组件模板
  • DAY-16-数组的常见操作和形状-2025.8.28
  • FISCO-BCOS-Python 模板