首页 > 其他分享 >数据结构: 顺序表(Seqlist篇) 手把手带你了解数据结构~

数据结构: 顺序表(Seqlist篇) 手把手带你了解数据结构~

时间：2024-09-20 23:22:56浏览次数：10  
标签：ps arr 顺序 手把手 Seqlist SL 数据结构 void size

文章目录

前言

在这里插入图片描述

在了解什么是顺序表之前，我们先来聊一聊什么是线性表?

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是⼀种数据结构，常⻅的线性表有：顺序表、链表、栈、队列、字符串…

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

如果底层结构使用的是数组来搭建，比如顺序表，那么开辟的就是一块连续的空间，线性表的物理结构就是连续的。如果底层结构是由指针来实现，每一个结构体中都有一个指向下一个数组地址的指针，如链表，那它的开辟的空间就不在一起，物理结构不连续。

一、顺序表的概念

1.顺序表是什么?

概念：顺序表是⽤⼀段物理地址连续的存储单元依次存储数据元素的线性结构，⼀般情况下采⽤数组存储。

在这里插入图片描述
这样看来顺序表是不是和数组很像？
没错，顺序表的底层逻辑就是数组~

2.顺序表和数组的区别

那么顺序表和数组有什么区别呢?

顺序表就像是将数组包装起来了一样，在顺序表中有多种功能满足我们的需求。

在这里插入图片描述

二、顺序表的实现

1.顺序表的结构

(1). 静态顺序表

概念：使⽤定⻓数组存储元素。

//静态顺序表
typedef int SLDataType;
#define N 7

typedef struct SeqList
{
    SLDataType a[N];      //开辟的数组为定长
    int size;             //记录数组中数据个数
}SL;

我们可以看到使用静态顺序表一个很大的弊端就是如果N太小了不够用还需要改变N，如果N太大了又会造成空间浪费。
在这里插入图片描述

(2). 动态顺序表

概念：动态申请空间的顺序表

typedef int SLDataType;   //将顺序表中储存元素的类型命名为SLDataType,方便后续统一替换

//动态顺序表
typedef struct Seqlist
{
	SLDataType* arr;
	int size;        //有效数据的多少
	int capacity;    //顺序表空间的大小
}SL;

在这里插入图片描述

因此我们推荐使用动态顺序表~

2. 顺序表的初始化

//初始化顺序表
void SLInit(SL* ps);

顺序表中有三个元素，我们默认初始顺序表为空，那它的元素个数和顺序表空间容量都为0.

//顺序表初始化
void SLInit(SL* ps)
{
	ps->arr = NULL;
	ps->size = 0;
	ps->capacity = 0;
}

3. 顺序表的销毁

//顺序表的销毁
void SLDestroy(SL* ps);

我们下面给顺序表申请内存空间的时候动态的开辟了内存，因此销毁时要手动释放，别忘了free结束将arr置空~

//顺序表的销毁
void SLDestroy(SL* ps)
{						
	free(ps->arr);
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
	
}

4.顺序表尾插

//尾插             
void SLPushBack(SL* ps, SLDataType x);

插入数据前我们要考虑到两个问题.

  1. 如果数据满了怎么办？
  2. 如果顺序表空间为零怎么办？
    在这里插入图片描述
    在这里插入图片描述

这就需要我们再插入之前先进行扩容操作，确保有足够的空间可以插入数据。

//查看空间是否需要扩容
void SLCheckCapacity(SL* ps)
{
	if (ps->size == ps->capacity)
	{
		//申请空间(增容用realloc)
		//三目运算符，如果空间为零默认赋给4个空间大小
		int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		SLDataType* tmp = (SLDataType*)realloc(ps->arr, sizeof(SLDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail!");
			exit(1);
		}
		ps->arr = tmp;
		ps->capacity = newcapacity;
	}
}

//尾插             
void SLPushBack(SL* ps, SLDataType x)
{
	assert(ps);
	//插入数据前先看空间够不够
	SLCheckCapacity(ps);
	ps->arr[ps->size++] = x;
}

5. 顺序表头插

//头插
void SLPushFront(SL* ps, SLDataType x);

顺序表头插的实现要遍历我们的顺序表，将顺序表所有的元素向后移动一位。当然如果顺序表满了要进行扩容~
在这里插入图片描述

//头插
void SLPushFront(SL* ps, SLDataType x)
{
	assert(ps);
	//插入数据前先看空间够不够
	SLCheckCapacity(ps);
	//向后走就从后往前遍历
	for (int i = ps->size; i > 0; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[0] = x;
	ps->size++;
}

6. 顺序表尾删

void SLPopBack(SL* ps);

尾删的操作很简单，当前的size–就可以了~
注意传过来的ps和ps->size不能为空！
在这里插入图片描述

//尾删
void SLPopBack(SL* ps)
{
	assert(ps);
	assert(ps->size);
	ps->size--;
}

7. 顺序表头删

//头删
void SLPopFront(SL* ps)

类似头插，头删需要顺序表所有元素向前移动覆盖掉第一个数据~
在这里插入图片描述

//头删
void SLPopFront(SL* ps)
{
	assert(ps);
	assert(ps->size);
	for (int i = 0; i < ps->size-1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}

8. 顺序表获取元素下标

//顺序表的查找
int SLFind(SL* ps, SLDataType x)；

查找就是遍历，比较简单，我们就一笔带过了~

//顺序表的查找
int SLFind(SL* ps, SLDataType x)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		if (x == ps->arr[i])
		{
			//找到了
			return i;
		}
	}
	//没找到
	return -1;
}

9. 顺序表任意位置插入

//在指定位置前插入
void SLInsert(SL* ps, int pos, SLDataType x);

类似于头插，但任意位置插入要对插入的位置pos做要求，pos范围是[0,ps->size]。在插入前，pos位置后的每一个数据都要向后挪一位。
在这里插入图片描述

//在指定位置前插入
void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);
	SLCheckCapacity(ps);
	for (int i = ps->size; i > pos; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[pos] = x;
	ps->size++;
}

10. 顺序表任意位置删除

//删除指定位置的数据
void SLErase(SL* ps, int pos);

类比头删
删除同样对pos和ps->size有做要求，要进行断言。
删除要将pos后的数据向前挪动一位.
在这里插入图片描述

//删除指定位置的数据
void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(ps->size);
	assert(pos >= 0 && pos < ps->size);
	for (int i = pos; i < ps->size -1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}

11. 顺序表打印

//顺序表打印
void SLPrint(SL s);

最后来到我们顺序表的打印，顺序表打印遍历数组就可以做到啦~

//顺序表打印
void SLPrint(SL s)
{
	for (int i = 0; i < s.size; i++)
	{
		printf("%d ", s.arr[i]);
	}
	printf("\n");
}

三、小试牛刀，顺序表练习

1. 移除元素

https://leetcode.cn/problems/remove-element/description/

2. 删除有序数组中的重复项

https://leetcode.cn/problems/remove-duplicates-from-sorted-array/description/

3. 合并两个有序数组

https://leetcode.cn/problems/merge-sorted-array/description/

四、 顺序表问题的思考

顺序表问题与思考

• 中间/头部的插⼊删除，时间复杂度为O(N)

• 增容需要申请新空间，拷⻉数据，释放旧空间。会有不⼩的消耗。

• 增容⼀般是呈2倍的增⻓，势必会有⼀定的空间浪费。例如当前容量为100，满了以后增容到200，
我们再继续插⼊了5个数据，后⾯没有数据插⼊了，那么就浪费了95个数据空间。

总结

到这里相信大家对顺序表有一个深入的了解了，最后的总结顺序表实现的源码奉上需要的小伙伴们自取哦~

//SeqList.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

typedef int SLDataType;   //将顺序表中储存元素的类型命名为SLDataType,方便后续统一替换

//动态顺序表
typedef struct Seqlist
{
	SLDataType* arr;
	int size;        //有效数据的多少
	int capacity;    //顺序表空间的大小
}SL;

//初始化顺序表
void SLInit(SL* ps);       

//顺序表的销毁
void SLDestroy(SL* ps);

//顺序表打印
void SLPrint(SL ps);

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

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

//顺序表指定位置之前插入/删除数据
void SLInsert(SL* ps, int pos, SLDataType x);
void SLErase(SL* ps, int pos);

//顺序表查找
int SLFind(SL* ps, SLDataType x);



//SeqList.c
#include"SeqList.h"

//顺序表初始化
void SLInit(SL* ps)
{
	ps->arr = NULL;
	ps->size = 0;
	ps->capacity = 0;
}

//顺序表的销毁
void SLDestroy(SL* ps)
{						
	free(ps->arr);
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
	
}

//顺序表打印
void SLPrint(SL s)
{
	for (int i = 0; i < s.size; i++)
	{
		printf("%d ", s.arr[i]);
	}
	printf("\n");
}

//查看空间是否需要扩容
void SLCheckCapacity(SL* ps)
{
	if (ps->size == ps->capacity)
	{
		//申请空间(增容用realloc)
		int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		SLDataType* tmp = (SLDataType*)realloc(ps->arr, sizeof(SLDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail!");
			exit(1);
		}
		ps->arr = tmp;
		ps->capacity = newcapacity;
	}
}

//尾插             
void SLPushBack(SL* ps, SLDataType x)
{
	assert(ps);
	//插入数据前先看空间够不够
	SLCheckCapacity(ps);
	ps->arr[ps->size++] = x;
}

//头插
void SLPushFront(SL* ps, SLDataType x)
{
	assert(ps);
	//插入数据前先看空间够不够
	SLCheckCapacity(ps);
	for (int i = ps->size; i > 0; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[0] = x;
	ps->size++;
}

//尾删
void SLPopBack(SL* ps)
{
	assert(ps);
	assert(ps->size);
	ps->size--;
}

//头删
void SLPopFront(SL* ps)
{
	assert(ps);
	assert(ps->size);
	for (int i = 0; i < ps->size-1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}

//在指定位置前插入
void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);
	SLCheckCapacity(ps);
	for (int i = ps->size; i > pos; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[pos] = x;
	ps->size++;
}

//删除指定位置的数据
void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(ps->size);
	assert(pos >= 0 && pos < ps->size);
	for (int i = pos; i < ps->size -1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}

//顺序表的查找
int SLFind(SL* ps, SLDataType x)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		if (x == ps->arr[i])
		{
			//找到了
			return i;
		}
	}
	//没找到
	return -1;
}

//测试代码
#include"SeqList.h"

void test01()
{
	SL s;
	SLInit(&s);
	SLPushBack(&s, 1);
	SLPushBack(&s, 2);
	SLPrint(s);
	SLPushFront(&s, 0);
	SLPushFront(&s, 0);
	SLPrint(s);
	SLInsert(&s, 0, 99);
	SLInsert(&s, 2, 100);
	SLInsert(&s, 6, 77);
	SLPrint(s);
	SLPopBack(&s);
	SLPrint(s);
	SLPopFront(&s);
	SLPrint(s);
	SLErase(&s, 3);
	SLPrint(s);
}

void test02()
{
	SL s;
	SLInit(&s);
	SLPushBack(&s, 0);
	SLPushBack(&s, 1);
	SLPushBack(&s, 2);
	SLPushBack(&s, 3);
	int tem = SLFind(&s, 2);
	printf("%d\n", tem);
	printf("%d\n", s.arr[tem]);
}

int main()
{
	test01();
	printf("----------------------------\n");
	test02();
	return 0;
}

真相永远只有一个！

在这里插入图片描述

标签：ps,arr,顺序,手把手,Seqlist,SL,数据结构,void,size
From： https://blog.csdn.net/Jdxxwu/article/details/142396968

相关文章

  • 数据结构：顺序表
    顺序表顺序表的概念与结构静态顺序表动态顺序表动态顺序表的实现SeqList.h的创建测试文件（test.c）初始化动态顺序表（LS_Init）动态顺序表的销毁（LS_Destry）检查动态内存空间是否已满（SL_CheckCapacity）动态顺序表打印有效数据（SL_Print）在末尾存放数据（SL_PushBack）在起始位置添加有......
  • 数据结构 ——— 常见的时间复杂度计算例题（上篇）
    目录前言例题1：例题2：例题3：例题4：前言在上一章讲解了时间复杂度的概念，以及用大O的渐进表示法表示时间复杂度数据结构———算法的时间复杂度-CSDN博客接下来利用C语言代码的例题，更深一步的掌握用大O的渐进表示法表示代码的时间复杂度例题1：代码演示：voidFunc......
  • en造数据结构与算法C# 用Unity实现简单的群组行为算法 之 对齐
    en造数据结构与算法C#用Unity实现简单的群组行为算法之聚集-CSDN博客en造数据结构与算法C#用Unity实现简单的群组行为算法之聚集-CSDN博客演示思路1.检测自然是沿用前两节的检测范围2.对齐朝向对齐朝向就是邻居鸟的forward加起来再除总数得到平均数3.对齐速度......
  • en造数据结构与算法C# 群组行为优化 和 头鸟控制
    实现：1.给鸟类随机播放随机动画使得每一只鸟扇翅膀的频率都不尽相同2.可以自行添加权重，并在最后 sumForce=separationForce+cohesionForce+alignmentForce;分别乘上相应权重，这样鸟就能快速飞行和转向辣usingSystem.Collections.Generic;usingUnityEngine;usingS......
  • 【学习笔记】数据结构（六 ①）
    树和二叉树（一）文章目录树和二叉树（一）6.1树(Tree)的定义和基本术语6.2二叉树6.2.1二叉树的定义1、斜树2、满二叉树3、完全二叉树4、二叉排序树5、平衡二叉树（AVL树）6、红黑树6.2.2二叉树的性质6.2.3二叉树的存储结构6.3遍历二叉树和线索二叉树6.3.1遍历二叉树......
  • Python中的树与图：构建复杂数据结构的艺术
    引言随着大数据时代的到来，我们面临的数据不再是简单的线性关系，而是错综复杂的网状结构。树和图正是用于表示这类复杂关系的最佳工具。树是一种特殊的图，它具有层次结构；而图则更加灵活，能够表达任意节点之间的连接关系。掌握树与图的实现方法，不仅有助于提高算法设计能力，还能为......
  • FLUENT离心风机仿真手把手零基础入门进阶有声解说教程（#331）
    本文摘要（由AI生成）：本文主要介绍了FLUENT中旋转机械仿真方法，包括旋转坐标系模型、多参考坐标系模型、混和平面模型、滑移网格模型和重叠网格模型。其中，多重参考系法与滑移网格法设置几乎相同，两者相互转换容易。本文以离心风机为例，介绍了使用WORKBENCH19.2平台及其对应的DM、ICEM......
  • 基于Java中的SSM框架实现数据结构课堂考勤管理平台项目【项目源码+论文说明】
    基于java中的SSM框架实现数据结构课堂考勤管理平台演示【内附项目源码+LW说明】摘要高校的不断扩张让在校学生数量不断的增加，对于教师和管理人员的需求也在不断地增强，对日常的学生考勤管理的工作量也在日益增加，传统的人工点名签到的考勤管理模式已经给无法适用于当前高校......
  • 手把手教你自己动手写cpu（六）--算术操作指令实现
    目录1.加法指令（Addition）实现思路Verilog实现示例2.减法指令（Subtraction）实现思路Verilog实现示例3.乘法指令（Multiplication）实现思路Verilog实现示例4.除法指令（Division）实现思路Verilog实现示例ALU模块乘法器模块除法器模块顶层模块测试模块总结 ......
  • 集合框架底层使用了什么数据结构
    1.是什么        集合框架（CollectionFramework）是Java标准库的一部分，它提供了一系列接口和实现类，用于处理不同类型的集合。这些集合可以用于存储和操作对象，如列表、集合、映射等。集合框架的底层数据结构是多种多样的，具体取决于集合实现类的选择。1.List（列表）Array......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99