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

数据结构之顺序表

news 2024/11/16 6:04:56

目录

前言

一、线性表

二、顺序表

三、动态顺序表的实现

总结

前言

        本文概述了什么是线性表，并实现了线性表之一的顺序表。

❤️感谢支持，点赞关注不迷路❤️

     

     

     

一、线性表

什么是线性表？

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

线性表的逻辑结构和物理结构：

  • 逻辑结构：线性表在逻辑上是线性结构，也就说是连续的一条直线。
  • 物理结构：线性表在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

二、顺序表

概念：顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。其在物理和逻辑上都是连续的，属于线性表的一种。

顺序表和数组的区别？

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

顺序表的分类：

  • 静态顺序表：使用定长数组存储元素。
  • 动态顺序表：实现按需申请空间。

静态顺序表和动态顺序表哪一个更好呢？

答：很明显动态顺序表更好，静态顺序表最大的缺点就是空间大小是固定的，空间小了可能不够用，空间大了可能浪费，但是动态顺序表就没有这种问题。所以本文主要实现动态顺序表。

顺序表的取名：SeqList，取单词 Sequential（顺序） 和 List（列表）组合而成

顺序表的文件安排：

三、动态顺序表的实现

1.SeqList.h声明

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>//定义动态顺序表结构
typedef int SLDatatype;//方便后续数据类型修改typedef struct SeqList
{SLDatatype* arr;int capacity;//空间大小int size;//有效数据个数
}SL;//重命名方便使用//初始化
void SLInit(SL* ps);
//注意因为是要改变顺序表，所以要传地址，后面的同理//销毁
void SLDestroy(SL* ps);//打印
void SLPrint(SL* ps);//插入数据
//1.尾插
void SLPushBack(SL* ps, SLDatatype x);//2.头插
void SLPushFront(SL* ps, SLDatatype x);//删除数据
//1.尾删
void SLPopBack(SL* ps);//2.头删
void SLPopFront(SL* ps);//在指定位置之前插入数据
void SLInsert(SL* ps, SLDatatype x, int pos);//删除指定位置的数据
void SLErase(SL* ps, int pos);//数据查找
int SLFind(SL* ps, SLDatatype x);

顺序表结构：

//定义动态顺序表结构
typedef int SLDatatype;//方便后续数据类型修改

typedef struct SeqList
{
    SLDatatype* arr;
    int capacity;//空间大小
    int size;//有效数据个数
}SL;//重命名方便使用

解析：顺序表结构就是由一个指针变量arr，一个表示顺序表容量capacity，一个表示当前有效数据个数 size 这三个变量组成，对 int 重命名是为了方便变换数据类型，比如我需要一个 char 类型的数据表，我们只需将 typedef int SLDatatype; 该为 typedef char SLDatatype; 即可。

2.SeqList.c的实现

1.SLInit 函数

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

解析：该函数用于对顺序表的初始化，因为初始化需要对顺序表本身进行修改，因此参数需要传顺序表的地址。

2.SLDestroy 函数

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

解析：此函数用于对顺序表的销毁，因为顺序表中 arr 指向的空间是动态开辟的，因此需要手动释放，避免内存泄漏，free后也需要将 arr 置空，避免野指针。

3.SLPrint 函数

//打印
void SLPrint(SL* ps)
{assert(ps);for (int i = 0; i < ps->size; i++){printf("%d ", ps->arr[i]);}printf("\n");
}

解析：用于打印顺序表中 arr 中的数据，这个可用于我们写顺序表时检测各功能函数的正确性

4.SLCheckCapacity 函数

//检查空间
void SLCheckCapacity(SL* ps)
{//判断空间是否充足if (ps->capacity == ps->size){//扩容//三目操作符，若capacity为0，则给初始值4，反之x2倍int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;SLDatatype* tmp = (SLDatatype*)realloc(ps->arr, newCapacity * sizeof(SLDatatype));if (tmp == NULL){perror("realloc fail!");exit(1);}ps->arr = tmp;ps->capacity = newCapacity;}
}

解析：

  1. 这个主要用于我们对顺序表插入数据时，用来检查顺序表中 arr 值向的空间是否充足，如果不充足，我们需要进行扩容操作。
  2. 扩容操作中由于我们对顺序表初始化时并没有分配 arr 空间，所以我们选择创建一个变量 newCapacity，使用三目操作符，如果顺序表容量为0，说明并没有分配空间，因此返回一个默认大小4，如果本身有空间需要扩容，那么我们将原容量x2倍返回。
  3. 为什么按2倍扩容呢，这里涉及一些数学知识，总之就是按2倍可以避免扩大了浪费过多空间，也避免扩小了，申请空间次数过多导致运行效率降低。
  4. 使用 realloc 扩容空间，检查是否扩容成功，然后将扩容后的地址赋值给 arr ，再跟新顺序表容量大小。
  5. 注意：该函数注意为其他功能函数服务，因此可只写在 SeqList.c 文件中即可，不需要在 SeqList.h 文件中声明。

5.SLPushBack 函数

//1.尾插
void SLPushBack(SL* ps, SLDatatype x)
{//断言一下，避免出现空指针assert(ps);//检查空间是否充足SLCheckCapacity(ps);//完成尾插，size+1ps->arr[ps->size++] = x;
}

解析：

  1. 用于对顺序表插入数据的一种，尾插，就是在顺序表尾部插入数据，比较简单，只需判断顺序表是否为空，不为空则继续判断顺序表空间是否充足，调用 SLCheckCapacity 函数即可，第一次肯定会进行扩容。
  2. 扩容后就将数据插入 arr 中 size 处即可，因为 size 表示当前有效数据个数，因此插入数据后需要++。

6.SLPushFront 函数

//2.头插
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];}//下标为0的位置空出来ps->arr[0] = x;ps->size++;
}

解析：

  1. 该函数为头插，意思是在顺序表的头部，也就是下标为0处插入数据
  2. 检查顺序表和空间是否充足与尾插一样，但是头插需要将数据往后整体移动一位

7.SLPopBack 函数

//1.尾删
void SLPopBack(SL* ps)
{assert(ps);//检查空指针assert(ps->size);//检查有效数据，为0不能再进行尾删//直接size--就行，因为后续数据会覆盖删除数据ps->size--;
}

解析：

  1. 尾删，删除顺序表中最后一个数据，删除前需要判断顺序表是否还有数据。
  2. 直接让 size-- 即可，因为后续数据会覆盖删掉的数据

8.SLPopFront 函数

//2.头删
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->size--;
}

解析：

  1. 头删，删除下标为0处的数据，同样需要断言一下是否还有可删除的数据
  2. 头删可以让后面数据整体往前移动一位，覆盖掉第一位数据即可，然后不要忘了size需要减1

9.SLInsert 函数

//在指定位置之前插入数据
void SLInsert(SL* ps, SLDatatype x, int pos)
{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];}//在下标为pos处插入数据，并且size+1ps->arr[pos] = x;ps->size++;
}

解析：

  1. 在指定位置之前插入数据，因此还得判断 pos 是否合法，然后也得检查空间是否充足
  2. 我们需要在 pos 的位置插入数据，注意 pos 是指数组下标，pos 及pos之后的数据要整体后移一位。

10.SLErase 函数

//删除指定位置的数据
void SLErase(SL* ps, int pos)
{assert(ps);assert(pos >= 0 && pos < ps->size);//pos的范围限定assert(ps->size);//不能无数据删除//pos后一位开始整体往前移一位for (int i = pos; i < ps->size - 1; i++){ps->arr[i] = ps->arr[i + 1];}//size要-1ps->size--;
}

解析：

  1. 删除指定位置的数据，注意这次断言中 pos 不能等于 size
  2. 删除指定位置数据就是让指定位置（不包括）后面的数据往前移一位，覆盖需要删除的数据，并 size--。

11.SLFind 函数

//数据查找
int SLFind(SL* ps, SLDatatype x)
{assert(ps);//循环遍历查找for (int i = 0; i < ps->size; i++){if (ps->arr[i] == x){return i;//找到返回下标}}//没有找到返回-1return -1;
}

解析：这个相对就比较简单，循环遍历进行查找

3.SeqList.c整体代码

#include "SeqList.h"//初始化
void SLInit(SL* ps)
{//全部初始化为空或0ps->arr = NULL;ps->capacity = ps->size = 0;
}//销毁
void SLDestroy(SL* ps)
{if (ps->arr)//此处判断arr是否为空{free(ps->arr);}ps->arr = NULL;//释放空间后指针要置空ps->capacity = ps->size = 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->capacity == ps->size){//扩容//三目操作符，若capacity为0，则给初始值4，反之x2倍int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;SLDatatype* tmp = (SLDatatype*)realloc(ps->arr, newCapacity * sizeof(SLDatatype));if (tmp == NULL){perror("realloc fail!");exit(1);}ps->arr = tmp;ps->capacity = newCapacity;}
}//插入数据
//1.尾插
void SLPushBack(SL* ps, SLDatatype x)
{//断言一下，避免出现空指针assert(ps);//检查空间是否充足SLCheckCapacity(ps);//完成尾插，size+1ps->arr[ps->size++] = x;
}//2.头插
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];}//下标为0的位置空出来ps->arr[0] = x;ps->size++;
}//删除数据
//1.尾删
void SLPopBack(SL* ps)
{assert(ps);//检查空指针assert(ps->size);//检查有效数据，为0不能再进行尾删//直接size--就行，因为后续数据会覆盖删除数据ps->size--;
}//2.头删
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->size--;
}//在指定位置之前插入数据
void SLInsert(SL* ps, SLDatatype x, int pos)
{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];}//在下标为pos处插入数据，并且size+1ps->arr[pos] = x;ps->size++;
}//删除指定位置的数据
void SLErase(SL* ps, int pos)
{assert(ps);assert(pos >= 0 && pos < ps->size);//pos的范围限定assert(ps->size);//不能无数据删除//pos后一位开始整体往前移一位for (int i = pos; i < ps->size - 1; i++){ps->arr[i] = ps->arr[i + 1];}//size要-1ps->size--;
}//数据查找
int SLFind(SL* ps, SLDatatype x)
{assert(ps);//循环遍历查找for (int i = 0; i < ps->size; i++){if (ps->arr[i] == x){return i;//找到返回下标}}//没有找到返回-1return -1;
}

总结

        以上就是本文的全部内容，感谢支持。


http://www.mrgr.cn/news/32953.html

相关文章：

  • 炼码LintCode--数据库题库（级别：入门；数量：144道）--刷题笔记_01
  • go语言使用总结（持续更新）
  • sql专题 之 where和join on
  • Scala中的case class
  • rust高级特征
  • 13、指向Member Function的指针
  • 【数学二】无穷小量定义、性质、比较
  • Java异常架构与异常关键字
  • MySQL基础基础篇 - SQL
  • python有main函数吗
  • C++ 单例模式
  • 如何有效检测住宅IP真伪?
  • 互斥锁和自旋锁
  • 【优选算法之双指针】No.2--- 经典双指针算法(下)
  • 简单多状态dp第二弹 leetcode -删除并获得点数 -粉刷房子
  • 【Linux课程学习】make/Makefile：Linux项目自动化构建工具
  • 【Godot4.3】胶囊形的偏移获取法
  • java实现LRU 缓存
  • [python]从零开始的PySide安装配置教程
  • 操作系统篇
  • Vue.js与Flask后端配合
  • linux网络编程5
  • Dell R720 使用 ESXI 系统直通 p40 等显存大于16g 的显卡使用 EFI 引导无法打开虚拟机。
  • C++——模板初阶
  • 智慧校园建设解决方案建设系统简介
  • C Prime Plus 第6章习题