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

瞬时存取,无限可能:顺序表的独特魅力

news 2025/6/20 22:03:32

嘿嘿,家人们,今天咱们来详细剖析数据结构中的顺序表,好啦,废话不多讲,开干!

目录

1:线性表

​2:顺序表 

2.1:概念以及结构

2.1.1:静态顺序表

2.1.2:动态顺序表

2.2:接口实现

2.2.1:Sequence_List.h

2.2.2:Sequence_List.c

2.2.2.1:初始化顺序表

2.2.2.2:检查容量

2.2.2.3:头插与尾插数据

2.2.2.4:头删与尾删数据 

2.2.2.5:任意位置的插入数据

2.2.2.6:任意位置的删除

2.2.2.7:查找元素与销毁顺序表

2.2.3:Test.c 

2.2.3.1:测试初始化与扩容

2.2.3.2:测试头插与尾插

2.2.3.3:测试头删与尾删 

2.2.3.4:测试任意位置的插入

2.2.3.5:测试任意位置的删除 

2.2.3.6:测试查找与销毁 

 3:总代码

3.1:Sequence_List.h

3.2:Sequence_List.c

3.3:Test.c

1:线性表

  • 线性表是n个具有相同特性的数据元素的有限序列,线性表是一种在实际中广泛使用的数据结构，常见的线性表:顺序表、链表、栈、队列、字符串等等.
  • 线性表在 逻辑上是线性结构 ,也就说是连续的一条直线。但是在 物理结构上并不一定是连续 的,线性表在物理上存储时，通常以数组和链式结构的形式存储

2:顺序表 

2.1:概念以及结构

顺序表是用一段 物理地址连续 的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储.在数组上完成数据的增删查改.
顺序表一般可以分为如下结构:

2.1.1:静态顺序表

静态顺序表的特点在于使用定长数组存储元素.

缺点:空间给少了不够⽤,给多了造成空间浪费.

#define N 7
//进行函数与结构体的声明
typedef int SLDataType;//定义顺序表的结构
typedef struct SeqList
{//存储数据SLDataType array[N];//记录有效数据int size;
}SeqList;

2.1.2:动态顺序表

动态顺序表的特点在于使用动态开辟的数组进行存储.

2.2:接口实现

静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致 N 定大了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，因此下面我们实现动态顺序表.

2.2.1:Sequence_List.h

我们在Sequence_List.h 这一头文件里面完成以下工作

  1. 顺序表的定义.
  2. 相关的函数接口的声明.
#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
//进行函数与结构体的声明
typedef int SLDataType;//定义顺序表的结构
typedef struct SeqList
{//存储数据int* array;//记录有效数据int size;//记录容量int capacity;
}SeqList;//顺序表初始化
void SeqInit(SeqList* ps);//检查容量
void SeqCheckcapacity(SeqList* ps);//尾插入数据
void SeqPushback(SeqList* ps, SLDataType value);//头插入数据
void SeqPushfront(SeqList* ps, SLDataType value);//任意位置下标的插入
void SeqInsertPos(SeqList* ps, int position, SLDataType value);//打印顺讯表
void SeqPrint(SeqList* ps);//尾删数据
void SeqPopback(SeqList* ps);//头删数据
void SeqPopfront(SeqList* ps);//任意位置数据的删除
void SeqErasePos(SeqList* ps, int position);//查找元素
int SeqFindelement(SeqList* ps, SLDataType value);//销毁顺序表
void SeqDestory(SeqList* ps);

2.2.2:Sequence_List.c

2.2.2.1:初始化顺序表

第一步首先是初始化顺序表.

void SeqInit(SeqList * ps)
{//防止空指针与野指针的传递assert(ps);ps->array = NULL;ps->capacity = 0;ps->size = 0;
}

2.2.2.2:检查容量

我们实现的是一个动态增长的顺序表,那么因此就需要就要检查容量,容量不够则需要进行扩容. 

void SeqCheckcapacity(SeqList * ps)
{assert(ps);//有效数据等于容量则进行扩容if(ps->size == ps->capacity){//若为0则将其初始容量为4,反之则进行二倍扩容int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//使用realloc进行扩容;如果为空指针,就等价于malloc(sizeof(SeqList) * newcapcity);防止扩容失败将原地址覆盖SLDataType* temp = (SLDataType*)realloc(ps->array, sizeof(SLDataType) * newcapacity);if(temp == NULL){perror("realloc fail\n");exit(1);}ps->array = temp;ps->capacity = newcapacity;printf("扩容成功\n");}
}

 

2.2.2.3:头插与尾插数据

那么接下来我们就要去实现数据的插入了,首先是头插数据与尾插数据.

  1. 在插入数据前,我们首先得检查其空间容量是否足够.
  2. 头插数据的话,那么我们就得将已有的数据向后挪动.
  3. 尾插数据的话,直接在尾部插入即可.
//头插入数据
void SeqPushfront(SeqList* ps, SLDataType value)
{assert(ps);//插入数据前检查容量SeqCheckcapacity(ps);for(int i = ps->size - 1; i >=0 ; i--){//进行挪动数据ps->array[i + 1] = ps->array[i];}ps->array[0] = value;ps->size++;
}void SeqPushback(SeqList* ps, SLDataType value)
{assert(ps);//插入数据前检查容量SeqCheckcapacity(ps);//数组下标从0开始ps->array[ps->size] = value;ps->size++;
}

2.2.2.4:头删与尾删数据 

那么接下来我们就要去实现数据的删除了,首先是头删数据与尾删数据.

  1. 在删除数据前,我们首先得检查里面是否有数据即有效数据不为0.
  2. 头删数据的话,那么我们就得将已有的数据向前挪动进行覆盖即可.
  3. 尾删数据的话,直接在尾部删除即可.
//头删数据
void SeqPopfront(SeqList* ps)
{assert(ps);//确保有效数据不为0assert(ps->size);for (int i = 0; i < ps->size - 1; i++){ps->array[i] = ps->array[i + 1];}ps->size--;
}//尾删数据
void SeqPopback(SeqList* ps)
{assert(ps);//确保有效数据不为0assert(ps->size);//有效数据 - 1即可达到尾删的效果ps->size--;}

2.2.2.5:任意位置的插入数据
//任意位置下标的插入
void SeqInsertPos(SeqList* ps, int position, SLDataType value)
{assert(ps);//确保插入的位置是有效的assert(position >= 1 && position <= ps->size + 1);SeqCheckcapacity(ps);for(int i = ps->size - 1; i >= position - 1; i--){//从后往前挪动覆盖ps->array[i + 1] = ps->array[i];}//插入数据ps->array[position - 1] = value;ps->size++;
}

2.2.2.6:任意位置的删除
//任意位置数据的删除
void SeqErasePos(SeqList* ps, int position)
{assert(ps);//确保插入的位置是有效的assert(position >= 1 && position <= ps->size + 1);for(int i = position - 1; i < ps->size - 1; i++){//从前向后挪动覆盖ps->array[i] = ps->array[i + 1];}ps->size--;
}
//查找元素
int SeqFindelement(SeqList* ps, SLDataType value)
{assert(ps);for(int i = 0; i < ps->size; i++){if (ps->array[i] == value)return i + 1;}return 0;
}//销毁顺序表
void SeqDestory(SeqList* ps)
{assert(ps);free(ps->array);ps->array = NULL;ps->size = 0;ps->capacity = 0;
}

 

2.2.2.7:查找元素与销毁顺序表

 

2.2.3:Test.c 

2.2.3.1:测试初始化与扩容
#define _CRT_SECURE_NO_WARNINGS
#include "List.h"void TestInitAndCheckCapcity(SeqList * ps)
{SeqInit(ps);SeqCheckcapacity(ps);
}
int main()
{SeqList s1;TestInitAndCheckCapcity(&s1);return 0;
}

2.2.3.2:测试头插与尾插
#define _CRT_SECURE_NO_WARNINGS
#include "List.h"
void TestPushFrontAndPushBack(SeqList* ps)
{SeqInit(ps);//尾插数据后SeqPushback(ps,5);SeqPushback(ps,6);SeqPushback(ps,7);SeqPrint(ps);//头插数据后SeqPushfront(ps, 4);SeqPushfront(ps, 3);SeqPushfront(ps, 2);SeqPrint(ps);
}
int main()
{SeqList s1;TestPushFrontAndPushBack(&s1);return 0;
}

2.2.3.3:测试头删与尾删 
#define _CRT_SECURE_NO_WARNINGS
#include "List.h"void TestPopFrontAndPopBack(SeqList* ps)
{SeqInit(ps);//尾插数据后SeqPushback(ps, 5);SeqPushback(ps, 6);SeqPushback(ps, 7);SeqPrint(ps);//头插数据后SeqPushfront(ps, 4);SeqPushfront(ps, 3);SeqPushfront(ps, 2);SeqPrint(ps);//头删数据后printf("头删数据后\n");SeqPopfront(ps);SeqPopfront(ps);SeqPrint(ps);//尾删数据后printf("尾删数据后\n");SeqPopback(ps);SeqPopback(ps);SeqPrint(ps);
}
int main()
{SeqList s1;TestPopFrontAndPopBack(&s1);return 0;
}

2.2.3.4:测试任意位置的插入
#define _CRT_SECURE_NO_WARNINGS
#include "List.h"void TestInsertPos(SeqList* ps)
{SeqInit(ps);//尾插数据后SeqPushback(ps, 5);SeqPushback(ps, 6);SeqPushback(ps, 7);SeqPrint(ps);//头插数据后SeqPushfront(ps, 4);SeqPushfront(ps, 3);SeqPushfront(ps, 2);SeqPrint(ps);//在第三个位置插入,即在下标为2的位置插入SeqInsertPos(ps, 3, 8);SeqInsertPos(ps, 5, 9);SeqInsertPos(ps, 9, 25);SeqPrint(ps);
}
int main()
{SeqList s1;TestInsertPos(&s1);return 0;
}

2.2.3.5:测试任意位置的删除 
#define _CRT_SECURE_NO_WARNINGS
#include "List.h"void TestErasePos(SeqList * ps)
{SeqInit(ps);//尾插数据后SeqPushback(ps, 5);SeqPushback(ps, 6);SeqPushback(ps, 7);SeqPrint(ps);//在第三个位置插入,即在下标为2的位置插入SeqInsertPos(ps, 4, 8);SeqInsertPos(ps, 5, 9);SeqInsertPos(ps, 6, 25);SeqPrint(ps);SeqErasePos(ps, 6);SeqErasePos(ps, 4);SeqErasePos(ps, 1);SeqPrint(ps);
}
int main()
{SeqList s1;TestErasePos(&s1);return 0;
}

2.2.3.6:测试查找与销毁 
#define _CRT_SECURE_NO_WARNINGS
#include "List.h"void TestDestoryAndFind(SeqList * ps)
{SeqInit(ps);//尾插数据后SeqPushback(ps, 5);SeqPushback(ps, 6);SeqPushback(ps, 7);SeqPrint(ps);//在第三个位置插入,即在下标为2的位置插入SeqInsertPos(ps, 4, 8);SeqInsertPos(ps, 5, 9);SeqInsertPos(ps, 6, 25);SeqPrint(ps);printf("找到了,在第%d个位置\n", SeqFindelement(ps,25));printf("找到了,在第%d个位置\n", SeqFindelement(ps,5));SeqDestory(ps);SeqPrint(ps);
}
int main()
{SeqList s1;TestDestoryAndFind(&s1);return 0;
}

 3:总代码

3.1:Sequence_List.h

#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
//进行函数与结构体的声明
typedef int SLDataType;//定义顺序表的结构
typedef struct SeqList
{//存储数据int* array;//记录有效数据int size;//记录容量int capacity;
}SeqList;//顺序表初始化
void SeqInit(SeqList* ps);//检查容量
void SeqCheckcapacity(SeqList* ps);//尾插入数据
void SeqPushback(SeqList* ps, SLDataType value);//头插入数据
void SeqPushfront(SeqList* ps, SLDataType value);//任意位置下标的插入
void SeqInsertPos(SeqList* ps, int position, SLDataType value);//打印顺讯表
void SeqPrint(SeqList* ps);//尾删数据
void SeqPopback(SeqList* ps);//头删数据
void SeqPopfront(SeqList* ps);//任意位置数据的删除
void SeqErasePos(SeqList* ps, int position);//查找元素
int SeqFindelement(SeqList* ps, SLDataType value);//销毁顺序表
void SeqDestory(SeqList* ps);

3.2:Sequence_List.c

#define  _CRT_SECURE_NO_WARNINGS
#include "Sequence_list.h"//初始化顺序表
void SeqInit(SeqList* ps)
{assert(ps);ps->array = NULL;ps->capcity = 0;ps->size = 0;
}//检查容量
void SeqCheckcapcity(SeqList * ps)
{assert(ps);//有效数据等于容量,进行扩容if (ps->size == ps->capcity){int newcapcity = ps->capcity == 0 ? 4 : ps->capcity * 2;//使用realloc进行扩容;如果为空指针,就等价于malloc(sizeof(SeqList) * newcapcity);防止扩容失败将原地址覆盖SLDataType * tmp = (SLDataType *)realloc(ps->array, sizeof(SLDataType) * newcapcity);if (tmp == NULL){perror("realloc");return;}ps->array = tmp;ps->capcity = newcapcity;printf("扩容成功\n");}
}//顺序表打印
void SeqPrint(SeqList * ps)
{assert(ps);for (int i = 0; i < ps->size; i++){printf("%d ", ps->array[i]);}printf("\n");
}//头插数据
void SeqPushfront(SeqList* ps, SLDataType value)
{assert(ps);//插入前检查容量SeqCheckcapcity(ps);//数据从后向前挪动for (int i = ps->size - 1; i >= 0; i--){ps->array[i + 1] = ps->array[i];}ps->array[0] = value;ps->size++;
}//尾插数据
void SeqPushback(SeqList* ps, SLDataType value)
{assert(ps);//插入前检查容量SeqCheckcapcity(ps);ps->array[ps->size] = value;ps->size++;
}
//任意下标位置的插入 
void SeqInsertPos(SeqList* ps, int position, SLDataType value)
{assert(ps);//确保正确插入assert(position >= 1 && position <= ps->size + 1);SeqCheckcapcity(ps);for (int i = ps-> size - 1 ; i >= position - 1; i--){ps->array[i + 1] = ps->array[i];}ps->array[position - 1] = value;ps->size++;
}//尾删数据
void SeqPopback(SeqList* ps)
{assert(ps);//删除前确保有效数据不为0assert(ps->size);ps->size--;
}//头删数据
void SeqPopfront(SeqList* ps)
{assert(ps);//确保有效数据不为0assert(ps->size);for (int i = 0; i < ps->size; i++){ps->array[i] = ps->array[i + 1];}ps->size--;
}//任意位置的删除void SeqErasePos(SeqList* ps,int position)
{assert(ps);assert(position >= 1 && position <= ps->size + 1);for (int i = position - 1; i < ps->size; i++){//从后往前挪动覆盖ps->array[i] = ps->array[i + 1];}ps->size--;
}int SeqFindelement(SeqList* ps, SLDataType value)
{assert(ps);for (int i = 0; i < ps->size; i++){if(value == ps->array[i]){return (i + 1);}}return 0;
}//销毁顺序表
void SeqDestory(SeqList* ps)
{//不为空则进行销毁assert(ps);free(ps->array);ps->array = NULL;ps->capcity = 0;ps->size = 0;
}

3.3:Test.c

#define  _CRT_SECURE_NO_WARNINGS
#include "Sequence_list.h"//测试尾插与头插与打印
void test1(SeqList * ps)
{//初始化SeqInit(ps);//尾插SeqPushback(ps, 1);SeqPushback(ps, 2);SeqPushback(ps, 3);SeqPushback(ps, 4);SeqPushback(ps, 5);printf("尾插之后:>");SeqPrint(ps);//头插SeqPushfront(ps, 40);SeqPushfront(ps, 30);SeqPushfront(ps, 20);SeqPushfront(ps, 10);printf("头插之后:>");SeqPrint(ps);
}//测试尾删与头删
void test2(SeqList* ps)
{//尾删SeqPopback(ps);SeqPopback(ps);SeqPopback(ps);printf("尾删之后:>");SeqPrint(ps);//头删SeqPopfront(ps);SeqPopfront(ps);printf("头删之后:>");SeqPrint(ps);
}//测试任意位置的插入与删除
void test3(SeqList * ps)
{SeqInsertPos(ps, 1, 20);printf("在第1个位置插入之后:>");SeqPrint(ps);SeqInsertPos(ps, 4, 3);printf("在第4个位置插入之后:>");SeqPrint(ps);SeqInsertPos(ps, 5, 4);printf("在第5个位置插入之后:>");SeqPrint(ps);SeqInsertPos(ps, 6, 5);printf("在第6个位置插入之后:>");SeqPrint(ps);SeqErasePos(ps, 3);printf("删除第3个位置的元素之后:>");SeqPrint(ps);SeqErasePos(ps, 7);printf("删除第7个位置的元素之后:>");SeqPrint(ps);}test4(SeqList * ps)
{int result = SeqFindelement(ps, 20);if (result){printf("在第%d个位置\n", result);}else{printf("无法找到\n");}}int main()
{SeqList s1;test1(&s1);test2(&s1);test3(&s1);test4(&s1);//销毁顺序表SeqDestory(&s1);
}

 好啦,uu们,数据结构顺表表这部分滴详细内容博主就讲到这里啦,如果uu们觉得博主讲的不错的话,请动动你们滴小手给博主点点赞,你们滴鼓励将成为博主源源不断滴动力,同时也欢迎大家来指正博主滴错误~


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

相关文章：

  • 代码随想录训练营Day35 | 452. 用最少数量的箭引爆气球 | 435. 无重叠区间 | 763.划分字母区间
  • 富格林：竭力击退欺诈守卫出金
  • Integer中的getInteger()方法和parseInt()方法有什么区别？
  • 【数据分享】全国文化-限额以上文化批发和零售业企业情况（2017-2021年）
  • 域名邮箱免费注册指南：烽火域名邮箱优势？
  • Windows系统上根据端口号查找对应进程
  • 5大主流方案对比：MySQL千亿级数据线上平滑扩容实战
  • 00 springboot项目创建
  • LSL常见应用场景及示例＜一＞
  • 2024最新的软件测试面试题（含答案+文档）
  • 开源模型应用落地-Qwen2.5-7B-Instruct与vllm实现离线推理-降本增效（一）
  • 国产单片机及其特点
  • 【TensorBoard】 菜鸟实用教程指南
  • JAVA 中的比较器
  • 软件测试学习笔记丨接口自动化测试-接口请求
  • spring/springboot获取resource目录下的文件
  • RAG中向量召回怎么做
  • 一个基于vue功能强大的表格组件--vxe-table的二次封装
  • Ascend C算子编程和C++基础 Lesson3-4 性能优化
  • spring boot 3.3.4 网关(gateway) 集成knife4j 4.4.0