数据结构——顺序表专题

目录

    • 1. 数据结构的相关概念
      • 什么是数据结构
      • 为什么需要数据结构？
    • 2. 顺序表
      • 顺序表的概念及结构
      • 顺序表分类
        • 静态顺序表
        • 动态顺序表
    • 3. 动态顺序表的实现
      • 准备工作
      • 顺序表的初始化
      • 顺序表的扩容
      • 尾插
      • 头插
      • 尾删
      • 头删
      • 指定位置插入数据
      • 指定位置删除数据
    • 4. 全部完整代码
      • **test.c**
      • **seqlist.c**
      • seqlist.h

1. 数据结构的相关概念

什么是数据结构

数据结构是由“数据”和“结构”两词组合而来的。

数据：常见的数值、网页中肉眼可见的信息，这些都是数据。

结构：当我们想要使用大量同一类型的数据时，通过手动定义大量的独立的遍历对于程序来说，可读性非常差，我们可以借助数组这样的数据结构将大量的数据组织在一起，结构也可以理解为组织数据的方式。

概念：数据结构是计算机存储、组织数据的方式。数据结构是指相互之间在一种或多种特定关系的数据元素的集合。数据结构反映数据的内部构成，即数据由那部分构成，以什么方式构成，以及数据元素之间呈现的结构。

总结：

  1. 能够存储数据（顺序表，链表等结构）
  2. 存储的数据能够方便查找

为什么需要数据结构？

在程序中如果不对数据进行管理，可能会导致数据丢失、操作数据困难、野指针等情况。
通过数据结构，能够有效将数据组织和管理在一起。按照我们的方式任意对书记进行增删改查等操作。

最基础的数据结构：数组

假设数据量非常庞大，频繁的获取数组有效数据个数会影响程序执行效率。

结论：最基础的数据结构能够提供已经不能完全满足复杂算法实现。

2. 顺序表

顺序表的概念及结构

线性表是n个具有相同特征的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…

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

顺序表分类

顺序表和数组的区别

顺序表的底层结构是数组，对数组的分装，实现了常用的增删改查等接口

在这里插入图片描述

静态顺序表

概念：使用定长数组存储元素

静态顺序表：给定数组的长度，若不够，会导致后续的数据保存失败；给多了，会导致空间大量的浪费

数据丢失----非常严重的技术事故！！

在这里插入图片描述
静态顺序表缺陷：空间给少了不够用，给多了造成空间浪费

动态顺序表

在这里插入图片描述

在这里插入图片描述

3. 动态顺序表的实现

准备工作

在这里插入图片描述

typedef int SLDataType;
//动态顺序表
typedef struct Seqlist
{
	SLDataType* arr;//存储数据的底层结构
	int capacity;//记录顺序表的空间大小
	int size;//记录顺序表当前有效的数据个数
}SL;

顺序表的初始化

//初始化和销毁
void SLInit(SL* ps)
{ 
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}

顺序表的扩容

实现动态顺序表，当size和capacity相等时，有2中情况，第一种：一开始为0的时候，第二种情况是：当空间不足时
若是第一种情况就给4个字节的空间，若是第二种情况使用二倍思想来处理

oid SLCheckCapacity(SL* ps)
{
	if (ps->size == ps->capacity)
	{
		int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		SLDataType* tmp = ps->arr = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));
		if (tmp == NULL)
		{
			perror("realloc");
			exit(1);
		}
		//说明扩容成功
		ps->arr = tmp;
		ps->capacity = newCapacity;
	}
}

在这里插入图片描述

尾插

//顺序表的插入
void SLPushBack(SL* ps, SLDataType x)
{
	//断言
	//assert(ps != NULL);
	assert(ps);
	//空间不够，扩容
	SLCheckCapacity(ps);
	//空间足够，直接插入
	//空间没有满，直接进行尾插
	ps->arr[ps->size] = x;
	ps->size++;

}

在这里插入图片描述

头插

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[1]=pa->arr[0]
	}
	ps->arr[0] = x;
	ps->size++;

}

在这里插入图片描述

尾删

void SLPopBack(SL* ps)
{
	assert(ps);
	assert(ps->size);

	//顺序表不为空
	//ps->arr[ps->size - 1] = -1;
	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);

	//pos及之后的数据往后挪动一位，pos空出来
	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(pos >= 0 && pos < ps->size);

	//pos以后的数据往前挪动一位
	for (int i=pos;i<ps->size-1;i++)
	{
		ps->arr[i] = ps->arr[i + 1];//ps->arr[i-2]=ps->arr[i-1]
	}
	ps->size--;
}

在这里插入图片描述

4. 全部完整代码

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include "seqlist.h"

void s1Test1()
{
	SL s1;
	SLInit(&s1);

	//测试尾插
	SLPushBack(&s1, 1);
	SLPushBack(&s1, 2);
	SLPushBack(&s1, 3);
	SLPushBack(&s1, 4);
	SLPrint(&s1);
	/*SLPushBack(&s1, 9);
	SLPrint(&s1);*/

	//测试头插
	SLPushFront(&s1, 5);
	SLPushFront(&s1, 6);
	SLPushFront(&s1, 7);
	SLPrint(&s1);

	//测试尾删
	SLPopBack(&s1);
	SLPrint(&s1);
	SLPopFront(&s1);
	SLPrint(&s1);

	//指定位置插入数据
	SLInsert(&s1, 0, 100);
	SLPrint(&s1);

	//删除指定位置的数据
	SLErase(&s1, 0);
	SLPrint(&s1);
}

int main()
{
	s1Test1();
	return 0;
}

seqlist.c

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include "seqlist.h"

//初始化和销毁
void SLInit(SL* ps)
{ 
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}

void SLCheckCapacity(SL* ps)
{
	if (ps->size == ps->capacity)
	{
		int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		SLDataType* tmp = ps->arr = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));
		if (tmp == NULL)
		{
			perror("realloc");
			exit(1);
		}
		//说明扩容成功
		ps->arr = tmp;
		ps->capacity = newCapacity;
	}
}

//顺序表的插入
void SLPushBack(SL* ps, SLDataType x)
{
	//断言
	//assert(ps != NULL);
	assert(ps);
	//空间不够，扩容
	SLCheckCapacity(ps);
	//空间足够，直接插入
	//空间没有满，直接进行尾插
	ps->arr[ps->size] = x;
	ps->size++;

}

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[1]=pa->arr[0]
	}
	ps->arr[0] = x;
	ps->size++;

}

//顺序表的删除
void SLPopBack(SL* ps)
{
	assert(ps);
	assert(ps->size);

	//顺序表不为空
	//ps->arr[ps->size - 1] = -1;
	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);

	//pos及之后的数据往后挪动一位，pos空出来
	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(pos >= 0 && pos < ps->size);

	//pos以后的数据往前挪动一位
	for (int i=pos;i<ps->size-1;i++)
	{
		ps->arr[i] = ps->arr[i + 1];//ps->arr[i-2]=ps->arr[i-1]
	}
	ps->size--;
}

void SLDestroy(SL* ps)
{

}

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

seqlist.h

#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include <stdio.h>
#include <assert.h>

//静态顺序表
//#define N 100
//typedef int SLDataType;
//struct Seqlist
//{
//	SLDataType a[N];
//	int size;
//};

typedef int SLDataType;
//动态顺序表
typedef struct Seqlist
{
	SLDataType* arr;//存储数据的底层结构
	int capacity;//记录顺序表的空间大小
	int size;//记录顺序表当前有效的数据个数
}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);

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/388804.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

【sgSearch】自定义组件：常用搜索栏筛选框组件（包括表格高度变化兼容）。

【sgSearch】自定义组件：常用搜索栏筛选框组件（包括表格高度变化兼容）。

sgSearch源码 <template><div :class"$options.name" :expand"expandSearch" :showCollapseBtn"showCollapseBtn"><!-- v-clickoutside"(d) > (expandSearch false)" --><ul class"search-list"&…
阅读更多...
【Python】通过conda安装Python的IDE

【Python】通过conda安装Python的IDE

背景 系统&#xff1a;win11 软件&#xff1a;anaconda Navigator 问题现象&#xff1a;①使用Navigator安装jupyter notebook以及Spyder IDE 一直转圈。②然后进入anaconda prompt执行conda install jupyter notebook一直卡在Solving environment/-\。 类似问题&#xff1a; …
阅读更多...
《UE5_C++多人TPS完整教程》学习笔记16 ——《P17 菜单类（The Menu Class）》

《UE5_C++多人TPS完整教程》学习笔记16 ——《P17 菜单类（The Menu Class）》

本文为B站系列教学视频 《UE5_C多人TPS完整教程》 —— 《P17 菜单类&#xff08;The Menu Class&#xff09;》 的学习笔记&#xff0c;该系列教学视频为 Udemy 课程 《Unreal Engine 5 C Multiplayer Shooter》 的中文字幕翻译版&#xff0c;UP主&#xff08;也是译者&#x…
阅读更多...
单片机基础入门：简单介绍51单片机的工作原理

单片机基础入门：简单介绍51单片机的工作原理

在电子技术领域&#xff0c;单片机是实现智能化控制不可或缺的关键元件。它们集成了许多功能于一身&#xff0c;成为了各种电子系统的心脏。为了更好地理解单片机如何工作&#xff0c;本文将重点介绍51单片机的基本组成和工作原理。 51单片机是一种广泛使用的微控制器&#xf…
阅读更多...
【JavaScript】面试手写题精讲之数组(上)

【JavaScript】面试手写题精讲之数组(上)

专题缘由 该专题主要是讲解我们在面试的时候碰到一些JS的手写题, 确实这种手写题还是比较恶心的。有些时候好不容易把题目写出来了&#xff0c;突然面试官冷不丁来一句有没有更优的解法&#xff0c;直接让我们僵在原地。为了解决兄弟们的这些困扰&#xff0c;这个专题于是就诞…
阅读更多...
计算机网络——12DNS

计算机网络——12DNS

DNS DNS的必要性 IP地址标识主机、路由器但IP地址不好记忆&#xff0c;不便于人类用使用&#xff08;没有意义&#xff09;人类一般倾向于使用一些有意义的字符串来标识Internet上的设备存在着“字符串”——IP地址的转换的必要性人类用户提供要访问机器的“字符串”名称由DN…
阅读更多...
Linux学习（三）shell编程

Linux学习（三）shell编程

1.echo指令 用于将后面的字体内容回显到控制台&#xff0c;将后面的字体用单引号或双引号引起来都会忽略引号 2.expr数学运算 3.第一个shell脚本 一般shell脚本以.sh为后缀&#xff0c;通过sh命令来执行shell脚本。 4.shell脚本的命令行参数 $1 $2 $3 $4 $5 $6 $7 $8 $9 $0 &…
阅读更多...
C语言学习day14：数组定义和使用

C语言学习day14：数组定义和使用

定义变量&#xff1a; 数据类型 变量 值 数组定义&#xff1a; 数据类型 数组名[元素个数]{值1,值2,值3} 代码&#xff1a; int main() {//定义变量//数据类型 变量 值//数组定义//数据类型 数组名[元素个数]{值1,值2,值3}//数组下标 数组名[小标]//数组下标是…
阅读更多...
相机图像质量研究(16)常见问题总结：光学结构对成像的影响--IRCUT

相机图像质量研究(16)常见问题总结：光学结构对成像的影响--IRCUT

系列文章目录 相机图像质量研究(1)Camera成像流程介绍 相机图像质量研究(2)ISP专用平台调优介绍 相机图像质量研究(3)图像质量测试介绍 相机图像质量研究(4)常见问题总结&#xff1a;光学结构对成像的影响--焦距 相机图像质量研究(5)常见问题总结&#xff1a;光学结构对成…
阅读更多...
Unity基础 -- 更新中(2.15)

Unity基础 -- 更新中(2.15)

Unity基础 文章目录 Unity基础3D数学 -- 基础一些方法插值运算三角函数坐标系 3D数学 -- 向量理解常用函数线性插值 3D数学 -- 四元数看向四元数计算 延迟函数协同程序 3D数学 – 基础 一些方法 float value01 Mathf.PI; // Π int value03 Mathf.Abs(-2); // 绝对值 int v…
阅读更多...
MySQL安装及环境配置

MySQL安装及环境配置

目录 下载安装检验安装是否成功配置环境变量 下载 MySQL下载链接 安装 点击安装包进行安装 选择Server only&#xff0c;点击Next 点击Execute 点击Next 提示我们需要进行一些配置&#xff0c;点击Next 输入管理员密码&#xff0c;点击Next 点击Execute&#xff0c;安装配…
阅读更多...
【类与对象（1）】类的引入、访问及封装、定义、作用域、实例化、类大小的计算、this指针

【类与对象（1）】类的引入、访问及封装、定义、作用域、实例化、类大小的计算、this指针

1.类的引入 C兼容了C语言结构体的用法&#xff0c;但是同时又升级成了类。结构体中只能定义变量&#xff0c;类中不仅可以定义变量&#xff0c;还可以定义函数。 例如&#xff0c;数据结构中实现栈&#xff0c;结构体stack中只定义了变量&#xff0c;要实现的函数在结构体外定…
阅读更多...
FastAI 之书（面向程序员的 FastAI）（一）

FastAI 之书（面向程序员的 FastAI）（一）

原文&#xff1a;www.bookstack.cn/read/th-fastai-book 译者&#xff1a;飞龙 协议&#xff1a;CC BY-NC-SA 4.0 序言 原文&#xff1a;www.bookstack.cn/read/th-fastai-book/README.md 译者&#xff1a;飞龙 协议&#xff1a;CC BY-NC-SA 4.0 在很短的时间内&#xff0c;深度…
阅读更多...
建筑工程如何找答案？ #职场发展#笔记#职场发展

建筑工程如何找答案？ #职场发展#笔记#职场发展

这些软件以其强大的搜索引擎和智能化的算法&#xff0c;为广大大学生提供了便捷、高效的解题方式。下面&#xff0c;让我们一起来了解几款备受大学生欢迎的搜题软件吧&#xff01; 1.易解题 这是一个网站 是我在百度搜题&#xff0c;经常会出现的一个网站&#xff0c;它里面…
阅读更多...
K8S集群实践之十：虚拟机部署阶段性总结

K8S集群实践之十：虚拟机部署阶段性总结

目录 1. 说明&#xff1a; 2. 安装准备 2.1 每个节点设置双网卡&#xff0c;一卡做网桥&#xff08;外部访问&#xff09;&#xff0c;一卡做NAT&#xff08;集群内网访问&#xff09; 2.2 准备一个可用的代理服务器 3. 由于虚拟机崩溃&#xff08;停电&#xff0c;宿主机…
阅读更多...
Gemini 1.5 Pro揭秘：Google DeepMind新一代AI模型如何突破千万级别词汇限制？

Gemini 1.5 Pro揭秘：Google DeepMind新一代AI模型如何突破千万级别词汇限制？

Gemini 1.5 Pro 发布&#xff01; 这款模型凭借其超长的上下文处理能力脱颖而出&#xff0c;支持10M tokens。 它的多模态特性意味着&#xff0c;无论面对多么庞大复杂的内容&#xff0c;Gemini 1.5 Pro都能游刃有余地应对。 在AI的世界里&#xff0c;上下文的理解如同记忆的…
阅读更多...
如何创建和填写 PDF 表单，简化您的文档工作流

如何创建和填写 PDF 表单，简化您的文档工作流

阅读本文&#xff0c;了解如何在开源办公套件 ONLYOFFICE 中创建和填写 PDF 表单。 ONLYOFFICE表单发展小史 ONLYOFFICE 表单首个版本发布于2022年1月18日&#xff0c;是 ONLYOFFICE 版本 7.0 更新的一部分。 您可以使用 ONLYOFFICE 表单&#xff0c;创建各种类型的模板文档&a…
阅读更多...
DS Wannabe之5-AM Project: DS 30day int prep day18

DS Wannabe之5-AM Project: DS 30day int prep day18

Q1. What is Levenshtein Algorithm? Levenshtein算法&#xff0c;也称为编辑距离算法&#xff0c;是一种量化两个字符串之间差异的方法。它通过计算将一个字符串转换成另一个字符串所需的最少单字符编辑操作次数来实现。这些编辑操作包括插入、删除和替换字符。Levenshtein距…
阅读更多...
备战蓝桥杯---图论之最短路Bellman-Ford算法及优化

备战蓝桥杯---图论之最短路Bellman-Ford算法及优化

目录 上次我们讲到复杂度为&#xff08;nm)logm(m为边&#xff0c;n为点&#xff09;的迪杰斯特拉算法&#xff0c;其中有一个明显的不足就是它无法解决包含负权边的图。 于是我们引进Bellman-Ford算法。 核心&#xff1a;枚举所有的点&#xff0c;能松弛就松弛&#xff0c;直…
阅读更多...
使用radial-gradient完成弧形凹陷的绘制

使用radial-gradient完成弧形凹陷的绘制

1、效果如下图 我在微信小程序中制作的 2、代码如下 <style>.header {position: relative;width: 200px;height: 200px;overflow: hidden;}.header .circle {--circleValue: 500px;position: absolute;bottom: 0;left: 50%;width: 100%;height: var(--circleValue);trans…
阅读更多...
最新文章

Copyright @ 2022~2023