【数据结构】线性表之顺序表详解

news/2024/5/20 6:11:51 标签: 线性表, 顺序表, 算法

🧑‍💻作者： @情话0.0
📝专栏：《数据结构》
👦个人简介：一名双非研究生的编程菜鸟，在这里分享自己的编程学习笔记，欢迎大家的指正与点赞，谢谢！

顺序表

前言

数据的逻辑结构分为线性结构和非线性结构，线性结构中的线性表根据存储结构又分为顺序表和链表。这篇博客主要讲的是顺序表的定义和基本操作，以及它是如何实现的。

一、线性表的定义和基本操作

1. 线性表的定义

线性表是具有相同数据类型的 n (n>=0)个数据元素的有限序列，其中 n 为表长，当n=0时线性表是一个空表。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…

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

2. 线性表的特点

表中元素的个数有限。
表中元素具有逻辑上的顺序性，表中元素有其先后次序。
表中元素都是数据元素，每个元素都是单个元素。
表中元素的数据类型都相同，这意味着每个元素占有相同大小的存储空间。
表中元素具有抽象性，即讨论元素间的逻辑关系，而不考虑元素究竟表示什么内容。

注意：线性表示一种逻辑结构，表示元素之间一对一的相邻关系。顺序表和链表是指存储结构，两者属于不同层面的概念，因此不要将其混淆。

3. 线性表的基本操作

一个数据结构的基本操作是指其最核心、最基本的操作。其他较复杂的操作可通过调用其基本操作来实现。线性表的主要操作如下：

void ListInit(List* s); 初始化表。构造一个空的线性表。
void CheckCapacity(List* s); 检查空间，若表空间已满，进行扩容
void ListPushBack(List* s, SLDataType x) 线性表尾插
void ListPopBack(List* s); 线性表尾删
void ListPushFront(List* s, SLDataType x);线性表头插
void ListPopFront(List* s);线性表头删
int ListFind(List* s, SLDataType x); 线性表查找,返回查找元素的位置
void ListInsert(List* s, size_t pos, SLDataType x);线性表在pos位置插入x
void ListErase(List* s, size_t pos);线性表删除pos位置的值
void ListDestory(List* s);线性表销毁
void ListPrint(List* s);线性表打印

二、线性表的顺序表示（顺序表）

1. 顺序表的定义

线性表的顺序存储称为顺序表。它是用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。顺序表的特点是表中元素的逻辑顺序与其物理顺序相同。线性表的顺序存储结构是一种随机存取的存储结构。一般情况通过数组来描述顺序表结构。

顺序表一般可分为：

1. 静态顺序表：使用定长数组存储元素。

#define Maxsize 50 //定义顺序表的最大长度
typedef int SLDataType;
typedef struct SeqList
{
	SLDataType data[Maxsize];  //定长数组
	size_t size;  //有效数据个数
}SeqList;

在静态分配时，由于数组的大小和空间事先已经固定，一旦空间站满，再加入新的数据就会产生溢出，进而导致程序崩溃。

2. 动态顺序表：使用动态开辟的数组存储。

typedef int SLDataType;
typedef struct SeqList
{
  SLDataType* array;  // 指向动态开辟数组的指针
  size_t size ;       // 有效数据个数
  size_t capicity ;   // 容量空间的大小
}SeqList;

2. 顺序表的特点

顺序表最主要的特点是随机访问，即通过首地址和元素序号可在时间 O(1) 内找到指定的元素。
顺序表的存储密度高，每个节点只存储数据元素。
顺序表逻辑上相邻的元素物理上也相邻，所以插入和删除操作需要移动大量元素。

3. 顺序表的动态实现

typedef int SLDataType;
// 顺序表的动态存储
typedef struct SeqList
{
	SLDataType* array; // 指向动态开辟的数组
	size_t size; // 有效数据个数
	size_t capacity; // 容量空间的大小

}SeqList;

3.1 顺序表初始化

void SeqListInit(SeqList* s)
{
	s->array = (SLDateType*)malloc(sizeof(SLDateType)* 5);//将顺序表中的数组元素个数初始化为5个
	
	if (s->array == NULL)
	{
		return;
	}
	s->capacity = 5;
	s->size = 0;
}

3.2 顺序表检查空间

void CheckCapacity(SeqList* s)
{
	assert(s);
	//当数组有效元素个数与数组容量相等时进行扩容，每次扩容后的元素个数为原来的2倍
	if (s->capacity == s->size)
	{
		SLDateType* array = (SLDateType*)realloc(s->a,sizeof(SLDateType)* (s->capacity*2));
		if(array==NULL)
		{
			return;
		}
		s->array = array;
		s->capacity *= 2;
	}
}

3.3 顺序表打印

void SeqListPrint(SeqList* s)
{
	assert(s);
	for (int i = 0; i < (s->size); i++)
	{
		printf("%d ", s->a[i]);
	}
	printf("\n");
}

3.4 顺序表尾插

void SeqListPushBack(SeqList* s, SLDataType x)
{
	assert(s);
	CheckCapacity(s);
	s->array[s->size] = x;
	s->size++;
}

3.5 顺序表头插

void SeqListPushFront(SeqList* s, SLDataType x)
{
	CheckCapacity(s);
	for (SLDataType i = s->size - 1; i >= 0; i--)
	{
		s->array[i + 1] = s->array[i];
	}
	s->array[0] = x;
	s->size++;
}

3.6 顺序表尾删

void SeqListPopBack(SeqList* s)
{
	s->size--;//对于尾删，只需要将数组元素个数减一就行，第一，在打印时不会再访问到该元素，第二，在插入时会将这个元素覆盖
}

3.7 顺序表头删

void SeqListPopFront(SeqList* s)
{
	for (size_t i = 1; i < s->size; i++)
	{
		s->array[i-1] = s->array[i];
	}
	s->size--;
}

3.8 顺序表任意位置插入

void SeqListInsert(SeqList* s, size_t pos, SLDataType x)
{
	assert(s);
	CheckCapacity(s);
	for (size_t i = s->size - 1; i >= pos; i--)
	{
		s->array[i + 1] = s->array[i];
	}
	s->array[pos] = x;
	s->size++;
}

3.9 顺序表任意位置删除

void SeqListErase(SeqList* s, size_t pos)
{
	assert(s);
	for (size_t i = pos; i < s->size; i++)
	{
		s->array[i] = s->array[i + 1];
	}
	s->size--;
}

3.10 顺序表查找

int SeqListFind(SeqList* s, SLDataType x)
{
	for (size_t i = 0; i < s->size; i++)
	{
		if (s->array[i] == x)
		{
			//找到
			return i + 1;
		}
	}
	//没找到
	return -1;
}

3.11 顺序表销毁

void SeqListDestory(SeqList* s)
{
	free(s->array);  //顺序表的数组是动态申请的，所以需要通过 free 函数进行释放
	s->array = NULL;
	s->size = 0;
	s->capacity = 0;
}

三、源代码及运行结果展示

1. SeqList.h

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLDataType;
// 顺序表的动态存储
typedef struct SeqList
{
	SLDataType* array; // 指向动态开辟的数组
	size_t size; // 有效数据个数
	size_t capacity; // 容量空间的大小
}SeqList;

// 基本增删查改接口
// 顺序表初始化
void SeqListInit(SeqList* s, size_t capacity);

// 顺序表销毁
void SeqListDestory(SeqList* s);

// 顺序表打印
void SeqListPrint(SeqList* s);

// 检查空间，如果满了，进行增容
void CheckCapacity(SeqList* s);

// 顺序表尾插
void SeqListPushBack(SeqList* s, SLDataType x);

// 顺序表尾删
void SeqListPopBack(SeqList* s);

// 顺序表头插
void SeqListPushFront(SeqList* s, SLDataType x);

// 顺序表头删
void SeqListPopFront(SeqList* s);

// 顺序表查找
int SeqListFind(SeqList* s, SLDataType x);

// 顺序表在pos位置插入x
void SeqListInsert(SeqList* s, size_t pos, SLDataType x);

// 顺序表删除pos位置的值
void SeqListErase(SeqList* s, size_t pos);

2. SeqList.c

#include "Seqlist.h"

// 对数据的管理:增删查改 
void SeqListInit(SeqList* s)
{
	s->array = (SLDateType*)malloc(sizeof(SLDateType)* 5);
	if (s->array == NULL)
	{
		return;
	}
	s->capacity = 5;
	s->size = 0;
}

void SeqListDestroy(SeqList* s)
{
	assert(s);
	free(s->array);
	s->array = NULL;
	s->capacity = 0;
	s->size = 0;
}

void CheckCapacity(SeqList* s)
{
	assert(s);
	//当数组有效元素个数与数组容量相等时进行扩容，每次扩容后的元素个数为原来的2倍
	if (s->capacity == s->size)
	{
		SLDateType* array = (SLDateType*)realloc(s->a,sizeof(SLDateType)* (s->capacity*2));
		if(array==NULL)
		{
			return;
		}
		s->array = array;
		s->capacity *= 2;
	}
}

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

//顺序表尾插
void SeqListPushBack(SeqList* s, SLDataType x)
{
	assert(s);
	CheckCapacity(s);
	s->array[s->size] = x;
	s->size++;
}

//顺序表头插
void SeqListPushFront(SeqList* s, SLDataType x)
{
	CheckCapacity(s);
	for (SLDataType i = s->size - 1; i >= 0; i--)
	{
		s->array[i + 1] = s->array[i];
	}
	s->array[0] = x;
	s->size++;
}

//顺序表尾删
void SeqListPopBack(SeqList* s)
{
	s->size--;//对于尾删，只需要将数组元素个数减一就行，第一，在打印时不会再访问到该元素，第二，在插入时会将这个元素覆盖
}

void SeqListPopFront(SeqList* s)
{
	for (size_t i = 1; i < s->size; i++)
	{
		s->array[i-1] = s->array[i];
	}
	s->size--;
}

// 顺序表查找
int SeqListFind(SeqList* s, SLDataType x)
{
	for (size_t i = 0; i < s->size; i++)
	{
		if (s->array[i] == x)
		{
			//找到
			return i + 1;
		}
	}
	//没找到
	return -1;
}

// 顺序表在pos位置插入x
void SeqListInsert(SeqList* s, size_t pos, SLDataType x)
{
	assert(s);
	CheckCapacity(s);
	for (size_t i = s->size - 1; i >= pos; i--)
	{
		s->array[i + 1] = s->array[i];
	}
	s->array[pos] = x;
	s->size++;
}

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

void SeqListTest()
{
	SeqList s;
	SeqListInit(&s);
	SeqListPushBack(&s, 1);
	SeqListPushBack(&s, 2);
	SeqListPushBack(&s, 3);
	SeqListPushBack(&s, 4);
	SeqListPushBack(&s, 5);
	SeqListPrint(&s);

	SeqListPushFront(&s, 0);
	SeqListPrint(&s);

	SeqListPopFront(&s);
	SeqListPrint(&s);

	SeqListPopBack(&s);
	SeqListPrint(&s);

	SeqListInsert(&s, 1, 6);
	SeqListPrint(&s);

	SeqListErase(&s, 1);
	SeqListPrint(&s);
}

3. test.c

#include "seqlist.h"
int main()
{
	SeqListTest();
	return 0;
}

结果展示:

在这里插入图片描述

总结

对于顺序表来说，它有着自己的特点：可在时间 O(1) 内查找元素，存储密度高。
但是，顺序表的插入删除，时间复杂度为O(N)；
增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗；
增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。
对于上述的问题，我们可通过链表进行解决，下篇博客将会对链表进行详细讲解。


http://www.niftyadmin.cn/n/1623.html

相关文章

算法详解之深度优先搜索算法

算法详解之深度优先搜索算法

14天阅读挑战赛 文章目录1、深度优先搜索&#xff08;Depth-First Search&#xff0c;DFS&#xff09;介绍2、深度优先搜索算法思想3、深度优先搜索算法步骤&#xff1a;4、深度优先搜索算法的应用1、深度优先搜索&#xff08;Depth-First Search&#xff0c;DFS&#xff09;介…
阅读更多...
数字IC秋招—终章

数字IC秋招—终章

秋招末尾&#xff0c;简单地写个总结&#xff0c;也算是对写了几个月的博客有个交代&#xff0c;另外也希望可以对同样是自学转行的朋友有一点帮助。 简单说下我的学习背景&#xff0c;双非本&#xff0c;末流211硕&#xff0c;劝退专业&#xff0c;由于硕士期间做的方向的原因…
阅读更多...
（附源码）计算机毕业设计SSM教师教学质量评价系统

（附源码）计算机毕业设计SSM教师教学质量评价系统

&#xff08;附源码&#xff09;计算机毕业设计SSM教师教学质量评价系统 项目运行 环境配置&#xff1a; Jdk1.8 Tomcat7.0 Mysql HBuilderX&#xff08;Webstorm也行&#xff09; Eclispe&#xff08;IntelliJ IDEA,Eclispe,MyEclispe,Sts都支持&#xff09;。 项目技术…
阅读更多...
小侃设计模式（一）-设计模式七大原则

小侃设计模式（一）-设计模式七大原则

1.概述 设计模式&#xff08;Design Pattern&#xff09;是软件设计领域的一棵长青树&#xff0c;它是一套被反复使用、多人知晓、经过分类编目的、优秀代码设计经验的总结。使用设计模式是为了设计出易理解、可复用、可靠的代码&#xff0c;增强程序的可复用性。设计模式由Er…
阅读更多...
基于STM32的自动重装载auto-reload preload以及影子寄存器

基于STM32的自动重装载auto-reload preload以及影子寄存器

目录 写在前面 正文 总结 写在前面 在使用cubeMX开发stm32&#xff0c;会经常用到定时器&#xff0c;并通过定时器产生中断计数来定期地执行某些任务。在配置时会遇到auto-reload preload 。这让熟悉51开发时解触到的定时器产生中断后自动重装载计数值让其产生下一次中断名字…
阅读更多...
毛球修剪器方案开发的工作原理和构成

毛球修剪器方案开发的工作原理和构成

本文介绍了毛球修剪器方案开发的工作原理&#xff1b;不管是羊毛衫、兔子衫还是普通纤维衫&#xff0c;时间一长都不可避免地会有很多毛球。它看起来脏又乱&#xff0c;穿起来特别不雅观。用除毛器剃毛球可以轻松去除毛衣的原始绒毛&#xff0c;而毛衣将失去其原有的保暖性。 原…
阅读更多...
中学生作文指导杂志中学生作文指导杂志社中学生作文指导编辑部2022年第22期目录

中学生作文指导杂志中学生作文指导杂志社中学生作文指导编辑部2022年第22期目录

中学生作文指导杂志中学生作文指导杂志社中学生作文指导编辑部2022年第22期目录 教法探索 试论高中语文阅读教学中批判性思维的培养 (2) 陈生泽 巧用批注式阅读法, 提升高中语文阅读教学效率 (6) 邓晓莉 高中语文课堂学习评价方法探微 (10) 刘秀娟 高中语文“思辨…
阅读更多...
饲料板块毛利润分析主逻辑SQL

饲料板块毛利润分析主逻辑SQL

/dialect/ select “MLR”.“FL” “FL”, “MLR”.“productGroupNumA” “productGroupNumA”, —物料大类代码 “MLR”.“productGroupNameA” “productGroupNameA”, —物料大类名称 “MLR”.“productGroupNum” “productGroupNum”, —物料大类代码 “MLR”.“product…
阅读更多...
最新文章

Copyright @ 2022~2023