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

数据结构与算法——带小白详谈顺序表

article 2025/3/13 20:35:22

目录

一：线性表

二：顺序表

2.1：静态顺序表

2.2：动态顺序表

三：顺序表功能实现（动态）

3.1：对顺序表进行初始化

3.2：判断顺序表是否为空

3.3：打印顺序表数据

3.4：头插顺序表数据

3.5：尾插顺序表数据

3.6：头删顺序表数据

3.7：尾删顺序表数据

3.8：顺序表在中间某个位置插入数据

3.9：顺序表在中间某个位置删除数据

3.10：修改顺序表中某个数据

3.11：顺序表中查找数据

3.12：销毁顺序表

四：顺序表源码具体实现

4.1：Linear_Func.h 代码实现：

4.2：Linear_Func.cpp 代码实现：

4.3：Linear_Main.cpp 代码实现：

一：线性表

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

二：顺序表

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

顺序表一般可分为两种形态：静态和动态。

2.1：静态顺序表

所谓静态，即在顺序表中其数组内空间大小是固定的。所以静态顺序表就是使用定长数组存储元素。

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

2.2：动态顺序表

动态，即顺序表中数组内空间是可变的。可大可小。动态顺序表就是使用动态开辟的数组存储。

三：顺序表功能实现（动态）

3.1：对顺序表进行初始化

在对顺序表进行操作之前，必须要先对顺序表进行初始化。对其内元素变量初始化为空值。

3.2：判断顺序表是否为空

用来判断该顺序表是否为空，为空时则返回 true，非空时则返回 false。

3.3：打印顺序表数据

将顺序表中的数据按序打印出来。

3.4：头插顺序表数据

头插数据，在顺序表的第一个位置（下标为0）中插入数据，需要将全部数据向后移动一个位置。size++，再在第一个位置放那个数据。当顺序表中容量不足时，还需对顺序表进行扩容处理——Check_Capacity函数，一次扩容原来的2倍空间。

3.5：尾插顺序表数据

尾插顺序表数据和头插相似，不过尾插是简单的在数组后面加一个数据即可，并不需要移动该数组的全部数据。

3.6：头删顺序表数据

头删顺序表数据，将数组内第一个位置（下标为0）数据进行删除。将后面的数据向前移动一个位置。注意的是，删除数据时顺序表数组数据不能为空，即操作之前需要进行判空处理。

3.7：尾删顺序表数据

尾删顺序表数据，与头删顺序表不同，尾删只需要将size-1即可。

3.8：顺序表在中间某个位置插入数据

在顺序表的 pos 位置插入数据，只需将pos位置之后的数据向后移动一个单位。再在pos位置填入一个新的数据。注意：当空间不足时也是需要扩容的。

3.9：顺序表在中间某个位置删除数据

在顺序表的 pos 位置删除数据，只需将pos位置后的数据向前移动一个单位。size-1，注意：也是需要检测该顺序表中数组是否为空的。

3.10：修改顺序表中某个数据

在顺序表中的pos位置修改某个数据。

3.11：顺序表中查找数据

在顺序表中查找数据，若找到就返回其下标，若找不到就返回-1。

3.12：销毁顺序表

该程序结束时，顺序表内空间因为是malloc创建在堆上的，所以并不会被释放，即就需要在程序结束之前将顺序表销毁。

四：顺序表源码具体实现

4.1：Linear_Func.h 代码实现：

// Implementing a linear list

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

typedef int SLDatatype;
typedef struct SeqList
{
	SLDatatype* a;
	int size;
	int capacity;
}SL;

// 初始化顺序表
void SL_Init(SL* psl);

// 顺序表判空
bool Is_Empty(SL* psl);

// 打印数据
void SL_Print(SL* psl);

// 头插数据
void SL_Push_Front(SL* psl, SLDatatype x);

// 尾插数据
void SL_Push_Back(SL* psl, SLDatatype x);

// 头删数据
void SL_Pop_Front(SL* psl);

// 尾删数据
void SL_Pop_Back(SL* psl);

// 中间某个位置插入数据
void SL_Insert(SL* psl, int pos, SLDatatype x);

// 中间某个位置删除数据
void SL_Erase(SL* psl, int pos);

// 修改某一数据（将pos位置的数据修改为 x ）
void SL_Modify(SL* psl, int pos, SLDatatype x);

// 查找某一数据	(找到返回其下标，找不到返回-1)
int SL_Find(SL* psl, SLDatatype x);

// 销毁顺序表
void SL_Destroy(SL* psl);

4.2：Linear_Func.cpp 代码实现：

// Implementing a linear list

#include"Linear.h"

// 初始化顺序表
void SL_Init(SL* psl)
{
	psl->a = NULL;
	psl->capacity = psl->size = 0;
}

// 顺序表判空
bool Is_Empty(SL* psl)
{
	return psl->size == 0 ? true : false;
}

// 打印数据
void SL_Print(SL* psl)
{
	int i = 0;
	for (i = 0; i < psl->size; i++)
	{
		printf("%d ", psl->a[i]);
	}
	printf("\n");
}

// 检查顺序表容量
void Check_Capacity(SL* psl)
{
	if (psl->capacity == psl->size)
	{
		int newcapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
		SLDatatype* tmp = (SLDatatype*)realloc(psl->a, sizeof(SLDatatype) * newcapacity);
		if (tmp == NULL)
		{
			perror("Check_Capacity realloc fail");
			return;
		}
		psl->a = tmp;
		psl->capacity = newcapacity;
	}
}

// 头插数据
void SL_Push_Front(SL* psl, SLDatatype x)
{
	Check_Capacity(psl);

	for (int i = psl->size-1; i >= 0 ; i--)
	{
		psl->a[i+1] = psl->a[i];
	}
	psl->a[0] = x;
	psl->size++;
}

// 尾插数据
void SL_Push_Back(SL* psl, SLDatatype x)
{
	Check_Capacity(psl);

	psl->a[psl->size] = x;
	psl->size++;
}

// 头删数据
void SL_Pop_Front(SL* psl)
{
	assert(!Is_Empty(psl));

	for (int i = 1; i < psl->size; i++)
	{
		psl->a[i-1] = psl->a[i];
	}
	psl->size--;
}

// 尾删数据
void SL_Pop_Back(SL* psl)
{
	assert(!Is_Empty(psl));

	psl->size--;
}

// 中间某个位置插入数据
void SL_Insert(SL* psl, int pos, SLDatatype x)
{
	Check_Capacity(psl);

	for (int i = psl->size-1; i >= pos; i--)
	{
		psl->a[i+1] = psl->a[i];
	}
	psl->a[pos] = x;
	psl->size++;
}

// 中间某个位置删除数据
void SL_Erase(SL* psl, int pos)
{
	assert(!Is_Empty(psl));

	for (int i = pos+1; i < psl->size; i++)
	{
		psl->a[i-1] = psl->a[i];
	}
	psl->size--;
}

// 修改某一数据（将pos位置的数据修改为 x ）
void SL_Modify(SL* psl, int pos, SLDatatype x)
{
	assert(pos >= 0 && pos < psl->size);
	psl->a[pos] = x;
}

// 查找某一数据	(找到返回其下标，找不到返回-1)
int SL_Find(SL* psl, SLDatatype x)
{
	assert(!Is_Empty(psl));

	for (int i = 0; i < psl->size; i++)
	{
		if (psl->a[i] == x)
			return i;
	}
	return -1;
}

// 销毁顺序表
void SL_Destroy(SL* psl)
{
	free(psl->a);
	psl->a = NULL;
	psl->capacity = psl->size = 0;
}

4.3：Linear_Main.cpp 代码实现：

// Implementing a linear list

#include"Linear.h"

int main()
{
	SL s;
	SL_Init(&s);

	// 前插数据
	SL_Push_Front(&s, 1);
	SL_Push_Front(&s, 2);
	SL_Push_Front(&s, 3);
	SL_Push_Front(&s, 4);

	SL_Print(&s);

	// 尾插数据
	SL_Push_Back(&s, 11);
	SL_Push_Back(&s, 22);
	SL_Push_Back(&s, 33);
	SL_Push_Back(&s, 44);

	SL_Print(&s);

	// 前删数据
	SL_Pop_Front(&s);
	SL_Pop_Front(&s);

	SL_Print(&s);

	// 尾删数据
	SL_Pop_Back(&s);
	SL_Pop_Back(&s);

	SL_Print(&s);

	// 在pos位置插入数据
	SL_Insert(&s, 1, 1000);
	SL_Insert(&s, 0, 2000);

	SL_Print(&s);

	// 删除pos位置上的数据
	SL_Erase(&s, 3);
	SL_Erase(&s, 1);

	SL_Print(&s);

	// 查找某一数据
	int i = SL_Find(&s, 11);
	s.a[i] = 666;

	SL_Print(&s);

	// 销毁顺序表
	SL_Destroy(&s);

	return 0;
}

4.4：运行结果：


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

相关文章：

  • 面试—JavaSE
  • AcWing算法基础课-787归并排序-Java题解
  • 讨论：无法访问不同网段的Kafka问题
  • Pygame中Sprite类实现多帧动画3-3
  • 【秒达开源】多功能中文工具箱源码：自部署 全开源 轻量级跨平台 GPT级支持+高效UI+Docker
  • Centos7.9 安装Elasticsearch 8.15.1（图文教程）
  • AIGC之GAN生成器和判别器的公式
  • 【信创】统信UOS1070根目录占满后无法进入系统的解决方法
  • LabVIEW重构其他语言开发的旧系统
  • 详细步骤！分享6款AI论文写作助手自动生成器实例操作！
  • 记录下Linux宝塔安装java后无法执行命令，mysql和redis外网无法连接的问题。
  • qt配合halcon深度学习网络环境配置
  • 【开发工具】Maven Dependency Helper：IntelliJ IDEA的贴心助手，助力梳理依赖关系
  • JavaScript(进阶篇）
  • html+css+js网页设计 故宫7个页面 ui还原度100%
  • go基础知识归纳总结
  • 微信小程序 ——入门介绍及简单的小程序编写
  • Node启动问题～
  • 大数据-123 - Flink 并行度 相关概念 全局、作业、算子、Slot并行度 Flink并行度设置与测试
  • flask下https教程