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

顺序表（数据结构与算法）

news 2025/8/8 16:04:55

请添加图片描述
✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅
✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨
🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿
🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟
🌟🌟 无人扶我青云志 🌟🌟
🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀
🌟🌟 我自踏雪之山巅🌟🌟
🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟
🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿
✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨
✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅

🍋顺序表

  • 🍌顺序表的定义
  • 🍌顺序表的结构
    • 🍍静态顺序表
    • 🍍动态顺序表
  • 🍌顺序表接口的实现（增删查改）
    • 🍍其它接口
    • 🍍顺序表初始化
    • 🍍检查空间是否增容（空间满了就增容）
    • 🍍顺序表尾插
    • 🍍顺序表尾删
    • 🍍顺序表头插
    • 🍍顺序表头删
    • 🍍顺序表查找
    • 🍍顺序表在pos位置插入x
    • 🍍顺序表删除pos位置的值
    • 🍍顺序表修改pos位置的值
    • 🍍顺序表销毁
    • 🍍顺序表打印
  • 🍌顺序表整体代码的实现

🍌顺序表的定义

顺序表是在计算机内存中以数组的形式保存的线性表,线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素、使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系，采用顺序存储结构的线性表通常称为顺序表。顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。

在这里插入图片描述

线性表：线性表是最基本、最简单、也是最常用的一种数据结构。大部分线性表除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。而又一些小部分,比如，循环链表逻辑层次上也是一种线性表（存储层次上属于链式存储，但是把最后一个数据元素的尾指针指向了首位结点

🍌顺序表的结构

🍍静态顺序表

静态顺序表就是以一定长度的数组来存储元素

//静态存储
#define  N  5
typedef int SLDetatype ;
typedef struct SeqList
{SLDetatype a[N] ;//有限空间的数组int size ;//有效的数据个数
}SeqList;

在这里插入图片描述

🍍动态顺序表

动态顺序表使用动态开辟的数组来存储元素

//动态存储
typedef  int SLDetatype ;
typedef struct SeqList
{SLDetatype *a ;   //指向动态开辟的数组int size ;       //有效的数据个数int capicity ;   //空间的容量
}SeqList;

在这里插入图片描述

🍌顺序表接口的实现（增删查改）

🍍其它接口

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>typedef int SLDatatype;
typedef struct SeqList
{SLDatatype* a;int capacity;int size;
}SeqList;

🍍顺序表初始化

void SeqListInit(SeqList* ps)
{ps->a = NULL;            //在初始情况我们可以直接置空//当然也可以创建空间，看自己习惯ps->capacity = ps->size = 0;
}

🍍检查空间是否增容（空间满了就增容）

void CheckCapacity(SeqList* ps)
{assert(ps);//在两个相等时，空间可能会满，还可能空间为0，这是因为我们在初始化没有创建空间导致if (ps->capacity == ps->size){if (ps->capacity == 0)ps->capacity = 2;elseps->capacity *= 2;int newcapacity = ps->capacity;//在扩容时，我们都是利用realloc,创建空间利用mallocSLDatatype* cur = (SLDatatype*)realloc(ps->a, sizeof(SLDatatype) * newcapacity);if (cur == NULL){perror("realloc   faild");exit(-1);}ps->a = cur;ps->capacity = newcapacity;}
}

大家如果对于malloc和realloc以及空间的创建的用法有些遗忘，可以看我这篇博客：动态内存管理（这是一个链接，有需要的朋友可以直接点进去）

🍍顺序表尾插

void SeqListPushBack(SeqList* ps, SLDatatype x)
{assert(ps);CheckCapacity(ps);  //需要检查空间是否满或者空ps->a[ps->size] = x;(ps->size)++;
}

在这里插入图片描述

🍍顺序表尾删

//顺序表尾删
void SeqListPopBack(SeqList* ps)
{assert(ps);assert(ps->size > 0);  //检查数据个数是否为0，如果为0就不执行，反之亦然(ps->size)--;
}

在这里插入图片描述

🍍顺序表头插

// 顺序表头插
void SeqListPushFront(SeqList* ps, SLDatatype x)
{assert(ps);CheckCapacity(ps);//判断空间是否满还是空//注意头插要分两种情况//第一种是数组里没有元素，此时头插就是相当于尾插//第二种是数组里有元素，这时就先把整体元素往后移动一位if (ps->size - 1 == 0){ps->a[ps->size -1] = x;(ps->size)++;}else{int end = ps->size - 1;while (end >= 0){ps->a[end + 1] = ps->a[end];end--;}ps->a[0] = x;(ps->size)++;}
}

注意：
注意头插要分两种情况
（1）第一种是数组里没有元素，此时头插就是相当于尾插
（2）第二种是数组里有元素，这时就先把整体元素往后移动一位

在这里插入图片描述

🍍顺序表头删

// 顺序表头删
void SeqListPopFront(SeqList* ps)
{assert(ps);assert(ps->size > 0);//注意头删要分两种情况//第一种是数组里没有元素，此时头删就是相当于尾删//第二种是数组里有元素，这时就需要把除了第一个元素外的所有元素往前移动一位，把原来的第一位元素覆盖if (ps->size - 1 == 0){(ps->size)--;}else{int end = 0;while (end < ps->size - 1){ps->a[end] = ps->a[end + 1];end++;}(ps->size)--;}
}

注意:
注意头删要分两种情况
（1）第一种是数组里没有元素，此时头删就是相当于尾删
（2）第二种是数组里有元素，这时就需要把除了第一个元素外的所有元素往前移动一位，把原来的第一位元素覆盖

在这里插入图片描述

🍍顺序表查找

// 顺序表查找
int SeqListFind(SeqList* ps, SLDatatype x)
{assert(ps);int i = 0;for (int i = 0; i < ps->size; i++){if (ps->a[i] == x)return 1;}return -1;
}

🍍顺序表在pos位置插入x

// 顺序表在pos位置插入x
void SeqListInsert(SeqList* ps, int pos, SLDatatype x)
{assert(ps);assert(pos >= 0 && pos <= ps->size);CheckCapacity(ps);int i = 0;for (i = pos - 1; i < ps->size - 1; i++){ps->a[i + 1] = ps->a[i];}ps->a[pos-1] = x;(ps->size)++;
}

注意:pos必须在0到ps->size之间

在这里插入图片描述

🍍顺序表删除pos位置的值

// 顺序表删除pos位置的值
void SeqListErase(SeqList* ps, int pos)
{assert(ps);assert(pos >= 0 && pos <= ps->size);int i = 0;for (i = pos - 1; i < ps->size - 1; i++){ps->a[i] = ps->a[i + 1];}(ps->size)--;
}

注意：pos必须在0到ps->size之间

🍍顺序表修改pos位置的值

//顺序表修改pos位置的值
void SeqModify(SeqList* ps, int pos, SLDatatype x)
{assert(ps);assert(pos >= 0 && pos < ps->size);ps->a[pos - 1] = x;
}

🍍顺序表销毁

// 顺序表销毁
void SeqListDestory(SeqList* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->size = ps->capacity = 0;
}

🍍顺序表打印

// 顺序表打印
void SeqListPrint(SeqList* ps)
{assert(ps);int i = 0;for (i = 0; i < ps->size; i++){printf("%d ", ps->a[i]);}printf("\n");
}

🍌顺序表整体代码的实现

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>typedef int SLDatatype;
typedef struct SeqList
{SLDatatype* a;int capacity;int size;
}SeqList;//顺序表初始化
void SeqListInit(SeqList* ps)
{ps->a = NULL;ps->capacity = ps->size = 0;
}//检查空间，如果满了就增容
void CheckCapacity(SeqList* ps)
{assert(ps);if (ps->capacity == ps->size){if (ps->capacity == 0)ps->capacity = 2;elseps->capacity *= 2;int newcapacity = ps->capacity;SLDatatype* cur = (SLDatatype*)realloc(ps->a, sizeof(SLDatatype) * newcapacity);if (cur == NULL){perror("realloc   faild");exit(-1);}ps->a = cur;ps->capacity = newcapacity;}
}//顺序表尾插
void SeqListPushBack(SeqList* ps, SLDatatype x)
{assert(ps);CheckCapacity(ps);ps->a[ps->size] = x;(ps->size)++;
}//顺序表尾删
void SeqListPopBack(SeqList* ps)
{assert(ps);assert(ps->size > 0);(ps->size)--;
}// 顺序表头插
void SeqListPushFront(SeqList* ps, SLDatatype x)
{assert(ps);CheckCapacity(ps);if (ps->size == 0){ps->a[ps->size] = x;(ps->size)++;}else{int end = ps->size - 1;while (end >= 0){ps->a[end + 1] = ps->a[end];end--;}ps->a[0] = x;(ps->size)++;}
}// 顺序表头删
void SeqListPopFront(SeqList* ps)
{assert(ps);assert(ps->size > 0);if (ps->size - 1 == 0){(ps->size)--;}else{int end = 0;while (end < ps->size - 1){ps->a[end] = ps->a[end + 1];end++;}(ps->size)--;}
}// 顺序表查找
int SeqListFind(SeqList* ps, SLDatatype x)
{assert(ps);int i = 0;for (int i = 0; i < ps->size; i++){if (ps->a[i] == x)return 1;}return -1;
}// 顺序表在pos位置插入x
void SeqListInsert(SeqList* ps, int pos, SLDatatype x)
{assert(ps);assert(pos >= 0 && pos <= ps->size);CheckCapacity(ps);int i = 0;for (i = pos - 1; i < ps->size - 1; i++){ps->a[i + 1] = ps->a[i];}ps->a[pos-1] = x;(ps->size)++;
}// 顺序表删除pos位置的值
void SeqListErase(SeqList* ps, int pos)
{assert(ps);assert(pos >= 0 && pos <= ps->size);int i = 0;for (i = pos - 1; i < ps->size - 1; i++){ps->a[i] = ps->a[i + 1];}(ps->size)--;
}// 顺序表销毁
void SeqListDestory(SeqList* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->size = ps->capacity = 0;
}// 顺序表打印
void SeqListPrint(SeqList* ps)
{assert(ps);int i = 0;for (i = 0; i < ps->size; i++){printf("%d ", ps->a[i]);}printf("\n");
}//顺序表修改pos位置的值
void SeqModify(SeqList* ps, int pos, SLDatatype x)
{assert(ps);assert(pos >= 0 && pos < ps->size);ps->a[pos - 1] = x;
}void test1()
{SeqList cur;SeqListInit(&cur);SeqListPushBack(&cur, 500);//尾插SeqListPushBack(&cur, 400);//尾插SeqListPushBack(&cur, 300);//尾插SeqListPrint(&cur);SeqListPopBack(&cur);//尾删SeqListPrint(&cur);SeqListPushFront(&cur, 100);//头插SeqListPushFront(&cur, 200);//头插SeqListPushFront(&cur, 600);//头插SeqListPrint(&cur);SeqListPopFront(&cur); //头删SeqListPrint(&cur);if (SeqListFind(&cur,200) == 1)//元素查找printf("找到了\n");else{printf("没有找到\n");}SeqListInsert(&cur, 3, 999);//在pos位置插入xSeqListPrint(&cur);SeqListErase(&cur, 3);//删除pos位置的值SeqListPrint(&cur);SeqModify(&cur, 3, 666); //修改pos位置的值SeqListPrint(&cur);
}int main()
{test1();return 0;
}

请添加图片描述

http://www.lryc.cn/news/234289.html

相关文章：

  • 【大连民族大学C语言CG题库练习题】——判断一个矩阵是另一个矩阵的子矩阵
  • C#WPF控制模板实例
  • MATLAB Simulink和S7-1200PLC MOBUSTCP通信
  • 五、函数的介绍
  • 【广州华锐互动VRAR】VR元宇宙技术在气象卫星知识科普中的应用
  • F. Alex‘s whims Codeforces Round 909 (Div. 3) 1899F
  • 面试题-5
  • 车载以太网-ARP
  • Kafka学习笔记（三）
  • JVM-HotSpot虚拟机对象探秘
  • 大模型技术的发展：开源和闭源，究竟谁强谁弱又该何去何从？
  • Python学习笔记--自定义元类
  • 软件测试 —— 常见的自动化测试架构！
  • Python 的 @lru_cache() 装饰器
  • Swift制作打包framework
  • 无线WiFi安全渗透与攻防（N.2）WPA渗透-使用airolib-ng创建彩虹表加速
  • 整形数据和浮点型数据在内存中的存储差别
  • 【Python基础篇】运算符
  • 开启数据库审计 db,extended级别或os级别)并将审计文件存放到/opt/oracle/audit/下
  • 02.webpack中多文件打包
  • IEEE Standard for SystemVerilog Chapter 22. Compiler directives
  • 机器学习中的独立和同分布 （IID）：假设和影响
  • PTP软硬件时间戳
  • 使用ADS进行serdes仿真时，Tx_Diff中EQ的设置对发送端波形的影响。
  • 数据库迁移(DBeaver版本)
  • 【c++STL常见排序算法sort，merge，random_shuffle，reverse】
  • STM32/N32G455国民科技芯片驱动DS1302时钟---笔记
  • 基于PLC的污水厌氧处理控制系统(论文+源码)
  • Unity之NetCode多人网络游戏联机对战教程(9)--NetworkAnimator组件
  • iceoryx之Roudi