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

数据结构初探: 顺序表

article 2025/2/1 13:38:18

ps: 本文所有图均为博主亲手所画,本文所有代码基于vs2022实现

文章目录

  • 前言
  • 一、顺序表是什么？
  • 二、存储结构
    • 1.结构
      • 1.1静态顺序表:使用定长数组存储元素
      • 1.2 动态顺序表:使用动态开辟出来的数组进行元素存储
    • 三.准备工作
    • 四.顺序表增删查改的实现
      • 1.SeqList.h
      • 2.SeqList.c
        • 2.1顺序表的初始化
        • 2.2顺序表的销毁
        • 2.3检查并且扩容
        • 2.4顺序表的打印
        • 2.5顺序表的尾插
        • 2.6顺序表的尾删
        • 2.7顺序表的头插
        • 2.8顺序表的头删
        • 2.9顺序表的中间插入
        • 2.10顺序表的中间删除
        • 2.11 顺序表的查找
        • 2.12==SewList.c的完整代码==
      • 3.test.c
    • 五.顺序表的优缺点
      • 优点
      • 缺点
  • 总结

前言

在计算机科学的世界里，数据结构是构建高效算法和程序的基础。就像建筑师需要了解不同的建筑材料和结构一样，程序员需要掌握各种数据结构，以便根据不同的需求选择最合适的工具。谈及数据结构，线性表是其中极为基础且重要的概念，顺序表和链表正是线性表的两种典型实现方式。

线性表是具有相同数据类型的n个数据元素的有限序列，这里的n表示元素的个数，被称为线性表的长度。当n = 0时，该线性表为空表。在一个非空的线性表中，元素之间存在着一对一的逻辑关系。它有唯一的第一个元素，除第一个元素外，每个元素都有且仅有一个直接前驱；它也有唯一的最后一个元素，除最后一个元素外，每个元素都有且仅有一个直接后继 。例如，英文字母表(A, B, C, …, Z)就是一个线性表，其中A是第一个元素，Z是最后一个元素，B是A的直接后继，A是B的直接前驱。这种逻辑结构清晰、简单，为很多复杂数据处理提供了基础模型。

接下来，我们就深入探讨基于线性表实现的两种基础数据结构：顺序表和链表。

一、顺序表是什么？

顺序表，简单来说，是基于数组实现的数据结构。它将数据元素按照顺序依次存储在连续的内存空间中,一般来说就是对数组的应用。这种存储方式就好比一排紧密相连的公寓(物理地址的连续)，每个公寓都住着一个数据元素，而且它们的门牌号（内存地址）是连续的。
顺序表图示

二、存储结构

1.结构

顺序表一般可以分为:

1.1静态顺序表:使用定长数组存储元素

#define N 10
typedef int SLDataType;

//静态顺序表--开少了不够用,开多了浪费;
struct SeqList
{
	SLDataType* arr[N];//定长数组
	int size;          //有效数据个数
};

1.2 动态顺序表:使用动态开辟出来的数组进行元素存储

#define INT_CAPACITY 4
typedef int SLDatatype;

//顺序表的创建
typedef struct SeqList
{
	SLDatatype* arr;
	int size;       //有效数据个数
	int capacity;   //空间容量
}SL;

动态
在现实中,由于静态顺序表存在着开少了不够用,开多了浪费的弊端,所以我们一般使用动态顺序表,现在我们已经了解了顺序表的结构了,那么如何进行增删查改呢?

三.准备工作

创建对应的三个文件夹:
1.SeqList.h:用于存储顺序表的结构和增删查改函数声明,以及对应的库函数;
2.SeqList.c:用于函数的实现;
3.test.c:用于测试和修改;
ps:2和3,均要包含头文件1,即(#include"SeqList.h").

四.顺序表增删查改的实现

1.SeqList.h

#pragma once

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>

//#define N 10
//typedef int SLDataType;
//
静态顺序表--开少了不够用,开多了浪费;
//struct SeqList
//{
//	SLDataType* arr[N];
//	int size;
//};

#define INT_CAPACITY 4
typedef int SLDataType;

//动态顺序表--按需分配
typedef struct SeqList
{
	SLDataType* arr;
	int size;          //有效数据个数;
	int capacity;      //空间容量;
}SL;

//初始化
void SLInit(SL* ps);
//销毁
void SLdestroy(SL* ps);
//打印
void SLprint(SL* ps);

//检查并扩容
void SLCheckCapacity(SL* ps);
//尾插
void SLPushBack(SL* ps, SLDataType x);
//尾删
void SLPopBack(SL* ps);
//头插
void SLPushFront(SL* ps, SLDataType x);
//头删
void SLPopFront(SL* ps);
//中间插入(配合SLFind查找pos使用)
void SLInsert(SL* ps, int pos, SLDataType x);
//中间删除
void SLErase(SL* ps, int pos);
//查找
int SLFind(SL* ps, SLDataType x);

先看个眼熟,等会我会挨个讲解,对应接口名称也是要熟练掌握的

2.SeqList.c

那么现在就到了我们的重头戏了-----具体函数增删查改的实现!

2.1顺序表的初始化
//首先我们先传我们的顺序表的结构体指针,从而找到我们创建的顺序表
//因为我们这样找到的是地址,所以就不存在形参无法影响实参的问题了
void SLInit(SL* ps)
{
	assert(ps);//对其进行断言,防止传空指针(NULL);
//进行动态内存开辟,在上文SeqList.h中,我已经将INT_CAPACITY给define为4了
	ps->arr = (SLDataType*)malloc(sizeof(SLDataType) * INT_CAPACITY);
	if (ps->arr == NULL)//检查是否开辟失败
	{
		perror("malloc fail");//失败返回错误行数
		return;//结束
	}
	ps->size = 0;//初始化为0,内部此时无有效数据个数
	ps->capacity = INT_CAPACITY;//capacity按照内存开辟大小赋值
	//后面扩容要记得及时更新内存容量capacity
}

以上就算初始化成功了;

2.2顺序表的销毁
void SLdestroy(SL* ps)
{
	assert(ps);

	free(ps->arr);//释放动态开辟的空间
	ps->arr = NULL;//并且置为空指针,防止野指针
	ps->capacity = ps->size = 0;//清空空间容量和有效数据个数
}

销毁还是很简单的,让我们继续!

2.3检查并且扩容
void SLCheckCapacity(SL* ps)
{
	assert(ps);
//如果有效数据个数与空间容量相等,说明此时数组已经满了,需要进行扩容;
	if (ps->size == ps->capacity)
	{//创建tmp指针,用于存储realloc的空间
	//通常realloc到原来空间容量的2倍
		SLDataType* tmp = (SLDataType*)realloc(ps->arr, sizeof(SLDataType) * ps->capacity * 2);
		if (tmp == NULL)
		{
			perror("realloc()");
		}

		ps->arr = tmp;//确定开辟成功后,赋给数组arr进行扩容;
		ps->capacity *= 2;//更新空间容量;
	}
}

这是一个在后面可以进行复用的函数,所以就单开出来了,在顺序表中,内存检查与扩容是必不可少的.

2.4顺序表的打印
void SLprint(SL* ps)
{
	assert(ps);
//对数组进行遍历
	for (int i = 0; i < ps->size; i++)
	{//打印出数组的每一个数
		printf("%d ", ps->arr[i]);
	}
	printf("\n");//防止多次调用函数时值连在一起,加入换行符
}

就像我们学习分支与循环结构时候的遍历一样,只不过在后面的增加和删除中一定要注意size++和size–,确保size正确,否则打印时可能会出问题哦

2.5顺序表的尾插
void SLPushBack(SL* ps, SLDataType x)
{
	assert(ps);
//这就是上面的扩容函数复用
	//if (ps->size == ps->capacity)
	//{

	//	SLDataType* tmp = (SLDataType*)realloc(ps->arr, sizeof(SLDataType) * ps->capacity * 2);
	//	if (tmp == NULL)
	//	{
	//		perror("realloc fail");
	//		return;
	//	}

	//	ps->arr = tmp;
	//	ps->capacity *= 2;
	//}

	//可直接复用;

	SLCheckCapacity(ps);

	ps->arr[ps->size++] = x;//直接赋值进入即可,注意size++哦!
}

这就是尾插啦,怎么样,是不是其实也没那么难?

2.6顺序表的尾删
void SLPopBack(SL* ps)
{
	assert(ps);

	//暴力检查
	//assert(ps->size > 0);

	//普通检查
	if (ps->size == 0)//两个检查都是检查是否为空
	{//为空就不能继续删除就直接结束;
		return;
	}
	//size为有效数据个数,减一后才是数组下标,这一步是将要删除的元素置为0;
	//但是没必要,我们只需要size--,将其排除在外即可,因为本来我们插入前,
	//这个位置就是随机值,排除在外后,它是什么数值都与我无关了,
	//所以置不置为0都没关系
	//ps->arr[ps->size - 1] = 0;
	ps->size--;//注意哦,出错的话影响还是很大的;
}
2.7顺序表的头插
void SLPushFront(SL* ps, SLDataType x)
{
	assert(ps);

	SLCheckCapacity(ps);//复用函数检查;

	int end = ps->size - 1;//找出尾部数值下标
	while (end >= 0)//利用循环,只要end的>=0,就继续循环
	{//将每个值都向后挪动
		ps->arr[end + 1] = ps->arr[end];
		--end;//并且--end,更新循环条件;
	}
	ps->arr[0] = x;//将第一个赋值
	ps->size++;//并且更新size;

}

在这里插入图片描述
在这里插入图片描述
如上图所示,这样比对是不是更容易理解了?

2.8顺序表的头删
void SLPopFront(SL* ps)
{
	assert(ps);
	//assert(ps->size > 0);

	if (ps->size == 0)//检查数组是否为空
	{
		return;
	}

	int begin = 1;//记住头元素的下一个元素的下标
	while (begin < ps->size)//构建循环,不断往下走
	{//将arr[begin]的赋值给上个位置,也就是把除了第一个元素以外的所有往前挪动一格
		ps->arr[begin - 1] = ps->arr[begin];
		++begin;//更新循环条件
	}
	ps->size--;//更新有效数据个数
}

在这里插入图片描述
不断挪动,覆盖前一个就可以达到删除头元素的效果;

2.9顺序表的中间插入
//搭配SLFind查找使用;
void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	//当pos满足两个条件才可以继续;
	assert(pos >= 0 && pos < ps->size);

	SLCheckCapacity(ps);//复用

	int end = ps->size - 1;//找出尾部数值下标
	while (end >= pos)
	{//把>=pos位置的所有数往后挪动给插入的数在对应位置腾出空间
		ps->arr[end + 1] = ps->arr[end];
		--end;//更新条件
	}
	ps->arr[pos] = x;//赋值
	ps->size++;//更新个数;
}

在这里插入图片描述

2.10顺序表的中间删除
void SLErase(SL* ps, int pos)
{
	assert(ps);
	//当pos满足两个条件才可以继续;
	assert(pos >= 0 && pos < ps->size);

	if (ps->size == 0)
	{
		return;
	}

	int begin = pos+1;//找到pos前一个的下标为开始
	while (begin <= ps->size)
	{//把<=size位置的所有数往前挪动并且覆盖掉删除的元素
		ps->arr[begin - 1] = ps->arr[begin];
		++begin;//更新条件
	}
	ps->size--;//更新个数
}

看图理清楚逻辑:
在这里插入图片描述

2.11 顺序表的查找
//暴力查找;
int SLFind(SL* ps, SLDataType x)
{
	assert(ps);

	for (int i = 0; i < ps->size; i++)//遍历
	{
		if (ps->arr[i] == x)//如果找到与x相等的值
		{
			return i;//就返回下标;
		}
	}

	return -1;//找不到则返回-1;

}
2.12SewList.c的完整代码
#define _CRT_SECURE_NO_WARNINGS 1

#include"SeqList.h"

//初始化
void SLInit(SL* ps)
{
	assert(ps);

	ps->arr = (SLDataType*)malloc(sizeof(SLDataType) * INT_CAPACITY);
	if (ps->arr == NULL)
	{
		perror("malloc fail");
		return;
	}
	ps->size = 0;
	ps->capacity = INT_CAPACITY;
}

//删除所有元素
void SLdestroy(SL* ps)
{
	assert(ps);

	free(ps->arr);
	ps->arr = NULL;
	ps->capacity = ps->size = 0;
}

//检查并且扩容
void SLCheckCapacity(SL* ps)
{
	assert(ps);

	if (ps->size == ps->capacity)
	{
		SLDataType* tmp = (SLDataType*)realloc(ps->arr, sizeof(SLDataType) * ps->capacity * 2);
		if (tmp == NULL)
		{
			perror("realloc()");
		}

		ps->arr = tmp;
		ps->capacity *= 2;
	}
}

//打印顺序表元素
void SLprint(SL* ps)
{
	assert(ps);

	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->arr[i]);
	}
	printf("\n");
}

//顺序表尾部插入
void SLPushBack(SL* ps, SLDataType x)
{
	assert(ps);

	//if (ps->size == ps->capacity)
	//{

	//	SLDataType* tmp = (SLDataType*)realloc(ps->arr, sizeof(SLDataType) * ps->capacity * 2);
	//	if (tmp == NULL)
	//	{
	//		perror("realloc fail");
	//		return;
	//	}

	//	ps->arr = tmp;
	//	ps->capacity *= 2;
	//}

	//可直接复用;

	SLCheckCapacity(ps);

	ps->arr[ps->size++] = x;
}

//顺序表的尾部删除;
void SLPopBack(SL* ps)
{
	assert(ps);

	//暴力检查
	//assert(ps->size > 0);

	//普通检查
	if (ps->size == 0)
	{
		return;
	}
	//ps->arr[ps->size - 1] = 0;
	ps->size--;
}

//顺序表的头部插入
void SLPushFront(SL* ps, SLDataType x)
{
	assert(ps);

	SLCheckCapacity(ps);

	int end = ps->size - 1;
	while (end >= 0)
	{
		ps->arr[end + 1] = ps->arr[end];
		--end;
	}
	ps->arr[0] = x;
	ps->size++;

}

//顺序表的头部删除
void SLPopFront(SL* ps)
{
	assert(ps);
	//assert(ps->size > 0);

	if (ps->size == 0)
	{
		return;
	}

	int begin = 1;
	while (begin < ps->size)
	{
		ps->arr[begin - 1] = ps->arr[begin];
		++begin;
	}
	ps->size--;
}

//顺序表的中间位置插入;
void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);

	SLCheckCapacity(ps);

	int end = ps->size - 1;
	while (end >= pos)
	{
		ps->arr[end + 1] = ps->arr[end];
		--end;
	}
	ps->arr[pos] = x;
	ps->size++;
}

//顺序表的中间位置删除
void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);

	if (ps->size == 0)
	{
		return;
	}

	int begin = pos+1;
	while (begin <= ps->size)
	{
		ps->arr[begin - 1] = ps->arr[begin];
		++begin;
	}
	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;

}

接下来让我们来测试一下;

3.test.c

直接上完整代码:

#define _CRT_SECURE_NO_WARNINGS 1

#include"SeqList.h"

void testseqlist1()
{
	SL s;
	SLInit(&s);
	SLPushBack(&s, 1);
	SLPushBack(&s, 2);
	SLPushBack(&s, 3);
	SLPushBack(&s, 4);
	SLPushBack(&s, 5);
	SLPushBack(&s, 6);
	SLPushBack(&s, 7);
	SLPushBack(&s, 8);
	SLPushBack(&s, 9);
	SLprint(&s);

	SLPopBack(&s);
	SLPopBack(&s);
	SLPopBack(&s);
	SLPopBack(&s);
	SLPopBack(&s);
	SLPopBack(&s);
	SLPopBack(&s);
	SLPopBack(&s);
	SLPopBack(&s);
	SLPopBack(&s);
	SLPopBack(&s);
	SLPopBack(&s);
	SLPopBack(&s);
	SLprint(&s);

	SLPushBack(&s, 10);
	SLPushBack(&s, 20);

	SLprint(&s);

	SLdestroy(&s);
}

void testseqlist2()
{
	//SL* ptr = NULL;
	//SLInit(ptr);
	SL s;
	SLInit(&s);

	SLPushFront(&s, 1);
	SLPushFront(&s, 2);
	SLPushFront(&s, 3);
	SLPushFront(&s, 4);
	SLPushFront(&s, 5);
	SLPushFront(&s, 6);
	SLprint(&s);

	SLPopFront(&s);
	SLPopFront(&s);
	SLPopFront(&s);
	SLPopFront(&s);
	SLPopFront(&s);
	SLPopFront(&s);
	SLPopFront(&s);
	SLprint(&s);

	SLPushFront(&s, 10);
	SLPushFront(&s, 6);

	SLprint(&s);

}

void testseqlist3()
{
	SL s;
	SLInit(&s);

	SLPushBack(&s, 1);
	SLPushBack(&s, 2);
	SLPushBack(&s, 3);
	SLPushBack(&s, 4);
	SLPushBack(&s, 5);
	SLPushBack(&s, 6);
	SLprint(&s);

	SLInsert(&s, 3, 20);
	SLprint(&s);

	SLInsert(&s, 1, 40);
	SLprint(&s);

	SLErase(&s, 3);
	SLprint(&s);

	SLErase(&s, 2);
	SLprint(&s);

	SLFind(&s, 40);
}

//头删/头插时间复杂度为O(N^2);
//尾删/尾插时间复杂度尾O(N);

int main()
{
	//testseqlist1();
	//testseqlist2();
	testseqlist3();
	return 0;
}

头删/头插时间复杂度为O(N^2);
尾删/尾插时间复杂度尾O(N);

五.顺序表的优缺点

顺序表具有自身独特的优缺点，具体如下：

优点

  • 随机访问效率高：由于顺序表中的元素在内存中是连续存储的，可通过简单的公式计算直接访问任意位置的元素，时间复杂度为O(1)，能快速获取所需数据，适用于需要频繁随机访问元素的场景，如数组作为缓存结构快速查找数据。
  • 存储密度高：顺序表中元素紧密排列，除了存储数据本身外，不需要额外的空间来存储指针等信息，存储密度大，空间利用率高，在存储大量同类型数据时优势明显，如存储大规模的学生成绩数据。
  • 实现简单：基于数组实现，数据结构和操作的实现都相对简单，容易理解和掌握，对于一些简单的数据处理任务，使用顺序表可以快速实现功能，如小型数据统计程序。

缺点

  • 插入和删除操作效率低：在顺序表中间插入或删除元素时，需要移动大量元素来保持连续性，平均时间复杂度为O(n)，当数据量较大时，性能开销大，如在一个大型有序数组中插入新数据。
  • 空间大小固定：创建顺序表时通常需要预先分配固定大小的空间，如果事先无法准确预估数据量，可能会导致空间浪费或空间不足的问题，若分配空间过大，会闲置浪费；分配过小，又需要频繁进行扩容操作，影响性能。
  • 不适合频繁动态变化的数据：对于数据元素频繁增加或减少的情况，顺序表需要不断进行元素移动和空间调整，会导致整体性能下降，不如链表等动态数据结构灵活。

总结

顺序表，以其独特的连续存储特性，在数据结构的领域中占据着重要的位置。它赋予我们快速随机访问的能力，为高效的数据读取提供了有力支持。尽管在插入和删除操作上存在一定的局限性，但在许多特定场景下，如需要频繁读取数据的应用场景中，顺序表的优势得以充分彰显。通过深入了解顺序表的原理、操作以及其优缺点，我们能够更加明智地在实际编程中运用它，让这一基础的数据结构为我们的程序开发发挥更大的价值。我也希望我的这篇博客可以带给你帮助,祝大家天天开心,在编程这条路上一日千里!(我会尽快更新链表的!!!)


http://www.kler.cn/a/527205.html

相关文章：

  • jinfo命令详解
  • 电子电气架构 --- 在智能座舱基础上定义人机交互
  • 图论——floyd算法
  • 阿里巴巴Qwen团队发布AI模型，可操控PC和手机
  • 适配器模式
  • sem_wait的概念和使用案列
  • Mysql的主从复制及扩展功能
  • 代发考试战报：1月22号 1月23号 CCDE考试通过
  • 深入解析JUnit中的@ClassRule注解
  • 代码随想录算法训练营第十五天| 二叉树3
  • Python-操作列表
  • 38【2进制与ascall码】
  • 今日头条公域流量引流新径：开源 AI 智能名片 2 + 1 链动模式 S2B2C 商城小程序融合之道
  • 【C++语言】卡码网语言基础课系列----2. A+B问题II
  • 【漫话机器学习系列】072.异常处理（Handling Outliers）
  • 算法题（53）：对称二叉树
  • 基于PLC的变频调速系统设计
  • 鸿蒙HarmonyOS实战-ArkUI动画（页面转场动画）_鸿蒙arkui tab 切换动画
  • K8S学习笔记
  • PDF 擦除工具
  • 【Leetcode 热题 100】62. 不同路径
  • “LoRA技术中参数初始化策略：为何A参数采用正态分布而B参数初始化为0”
  • 解锁维特比算法：探寻复杂系统的最优解密码
  • 青少年编程与数学 02-008 Pyhon语言编程基础 04课题、开始编程
  • 【图床配置】PicGO+Gitee方案
  • 17.2 图形绘制3