【王道数据结构笔记】顺序表的动态分配代码分析

2024-04-15 08:44
文章标签 分析 代码 数据结构 笔记 顺序 王道 动态分配

本文主要是介绍【王道数据结构笔记】顺序表的动态分配代码分析，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在这里插入图片描述

🎈个人主页：豌豆射手^
🎉欢迎 👍点赞✍评论⭐收藏
🤗收录专栏：数据结构
🤝希望本文对您有所裨益，如有不足之处，欢迎在评论区提出指正，让我们共同学习、交流进步！

【王道数据结构笔记】顺序表的动态分配代码分析

  • 引言
  • 一 代码
  • 二代码分析
    • 步骤1：
    • 步骤2：
    • 步骤3：
    • 步骤4：
    • 步骤5：
    • 步骤6：
    • 步骤7：
  • 总结

引言

一 代码

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include<stdlib.h>
#define InitSize  10
typedef struct {int *data;int MaxSize;int length;}SeqList;void InitList(SeqList& L) {L.data = (int*)malloc( InitSize * sizeof(int));L.length = 0;L.MaxSize = InitSize;}void IncreaseSize(SeqList& L, int len)
{int* p = L.data;L.data = (int*)malloc((L.MaxSize + len) * sizeof(int));for (int i = 0; i < L.length; i++) {L.data[i] = p[i];}L.MaxSize = L.MaxSize + len;free(p);
}int main(){SeqList L;InitList(L);IncreaseSize(L, 5);
}

二代码分析

下面是拆分后的代码，以及对每一步骤的分析：

步骤1：

#define _CRT_SECURE_NO_WARNINGS

分析：
定义了一个宏_CRT_SECURE_NO_WARNINGS，用于消除某些编译器关于安全性的警告，例如在使用malloc等函数时可能出现的警告。

步骤2：

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

分析：
包含了标准输入输出库stdio.h和标准库stdlib.h，前者用于输入输出操作，后者提供了内存分配函数如malloc和free。

步骤3：

#define InitSize  10

分析：
定义了一个宏InitSize，值为10，用于初始化顺序表（SeqList）的初始大小。

步骤4：

typedef struct {int *data;int MaxSize;int length;
} SeqList;

分析：
定义了一个结构体类型SeqList，包含一个整型指针data用于存储数据，整型MaxSize用于存储顺序表的最大容量，整型length用于存储顺序表当前的长度。

指针data

在结构体类型SeqList中，整型指针data用于存储顺序表中实际数据的内存地址。具体来说，data是一个指向整型数据的指针，它指向一个动态分配的内存区域，该区域用于存储顺序表中的元素。

在顺序表中，我们通常不知道事先需要存储多少个元素，或者元素的数量可能会在运行过程中变化。因此，使用动态内存分配（如malloc）来分配存储空间是一个灵活且有效的方法。data指针就是用来管理这块动态分配的内存的。

当创建或初始化一个SeqList对象时，我们通常会为data指针分配一块足够大的内存空间来存储初始的元素。随着顺序表中元素的增加或减少，我们可能需要重新分配data指针所指向的内存空间，以适应新的存储需求。这时，我们会使用realloc或再次调用malloc来重新分配内存，并更新data指针的指向。

通过data指针，我们可以方便地访问和修改顺序表中的元素。例如，通过计算元素的索引和data指针的偏移量，我们可以直接定位到某个元素的内存位置，并进行读取或写入操作。

总之，data指针在SeqList结构体中起到了桥梁的作用，它连接了顺序表的逻辑结构和实际存储数据的内存空间。

整型Maxsize:

在SeqList结构体中，整型MaxSize用于表示顺序表当前分配的最大容量。这个值通常用于在动态内存管理中跟踪已经为顺序表分配了多少内存空间。

具体来说，MaxSize的作用体现在以下几个方面：

  1. 内存分配参考：当需要增加顺序表的容量时（例如，通过调用IncreaseSize函数），MaxSize会被用来计算需要分配多少额外的内存空间。这样，程序可以确保在扩展顺序表时分配足够的内存。

  2. 防止越界访问：在添加新元素到顺序表之前，通常会检查顺序表的当前长度是否已经达到MaxSize。如果达到或超过MaxSize，那么程序会知道需要增加顺序表的容量，以避免越界访问内存，这是一种常见的内存安全错误。

  3. 优化内存使用：通过跟踪MaxSize，程序可以更有效地管理内存。例如，如果顺序表的大小经常变化，但变化不大，那么可以通过适当地调整MaxSize来减少频繁的内存分配和释放操作，从而提高性能。

  4. 容量监控：MaxSize也可以用于监控顺序表的内存使用情况。通过比较MaxSize和顺序表的当前长度，程序可以了解顺序表是否接近满载，从而决定是否需要进行容量调整。

优化内存具体来说是在实际应用中，如果顺序表（例如一个动态数组）的大小经常会在一个较小的范围内变动，那么频繁地进行内存分配和释放操作可能会成为性能瓶颈。

为了优化性能，我们可以采取一种策略，即不是每次顺序表大小稍有变化就立即重新分配内存，而是预留一些额外的空间，即适当增加MaxSize的值。

具体来说，当顺序表需要增加元素时，我们并不立即按照新的大小重新分配内存，而是检查当前预留的空间是否足够。如果足够，我们就不会进行内存分配操作，而是直接在预留的空间中添加新元素。

只有当预留的空间不足时，我们才会进行一次较大的内存分配操作，以满足未来一段时间内可能的增长需求。

这种策略可以减少内存分配和释放的次数，因为内存分配和释放通常涉及系统调用和可能的内存碎片问题，这些操作相对耗时。

通过适当调整MaxSize的值，我们可以在一定程度上平滑这些操作对性能的影响，从而提高程序的执行效率。

需要注意的是，预留过多的空间也会浪费内存资源，因此需要在性能和内存使用之间找到一个平衡。这通常需要根据具体的应用场景和需求来决定。

总的来说，MaxSize在SeqList结构体中是一个重要的元数据成员，它帮助程序更好地管理顺序表的内存使用，确保内存安全，并优化性能。

整型length:

在顺序表（如SeqList）的数据结构中，整型length通常用于表示顺序表当前实际存储的元素个数，也就是顺序表的当前长度。这个值对于顺序表的操作和管理至关重要，具体体现在以下几个方面：

  1. 元素访问：通过length，我们可以快速知道顺序表中当前有多少个元素，从而安全地访问这些元素。例如，当我们要读取或修改顺序表中的某个元素时，需要确保该元素的索引在有效范围内（即小于length）。

  2. 添加和删除元素：当向顺序表中添加元素时，我们需要更新length以反映新添加的元素。同样地，当从顺序表中删除元素时，也需要减少length的值。通过length，我们可以方便地追踪顺序表的当前状态。

  3. 容量与长度比较：length和MaxSize的比较是顺序表管理中常见的操作。通过比较这两个值，我们可以判断顺序表是否已满（即length是否等于MaxSize），从而决定是否需要进行扩容操作。

  4. 空间效率监控：length也用于监控顺序表的空间使用情况。例如，如果length远小于MaxSize，这可能意味着顺序表分配了过多的内存，存在空间浪费的情况。根据应用的需求，可以考虑是否需要进行内存收缩操作。

总之，整型length在顺序表的数据结构中扮演了记录当前元素数量、辅助元素访问和修改、管理内存空间等重要角色。它是顺序表实现中不可或缺的一部分。

步骤5：

void InitList(SeqList& L) {L.data = (int*)malloc(InitSize * sizeof(int));L.length = 0;L.MaxSize = InitSize;
}

分析：

定义了初始化顺序表的函数InitList，它接受一个SeqList类型的引用L作为参数。函数内部使用malloc为L.data分配了InitSize个整数的空间，最后将L.length和L.MaxSize分别初始化为0和InitSize。

L.data = (int*)malloc(InitSize * sizeof(int));这行代码是C语言中用于动态内存分配的一行关键代码，它用于为一个顺序表（在这里是SeqList类型的对象L）分配初始的内存空间。具体地，这一行代码做了以下几件事：

  1. malloc(InitSize * sizeof(int))：

    • malloc 是一个标准库函数，用于在堆上动态分配指定字节大小的内存。
    • InitSize 是一个变量（或常量），表示要分配的整型元素（int）的数量。
    • sizeof(int) 是一个运算符，返回int类型在特定系统或编译器上所占用的字节数。
    • InitSize * sizeof(int) 计算了总共需要分配的字节数。

  2. (int*)：

    • 这是一个类型转换（或称为强制类型转换）。malloc 函数返回的是一个指向void的指针（void*），因为malloc可以分配任何类型的内存。但是，在C语言中，我们不能直接将void*类型的指针赋给其他类型的指针。因此，这里使用(int*)将void*类型的指针转换为int*类型的指针。这样，我们就可以将这个指针赋值给指向整型的指针变量。

  3. L.data = ...：

    • L 是一个SeqList类型的对象。
    • L.data 是SeqList结构体中的一个成员，它是一个指向整型的指针，用于存储顺序表数据的实际内存地址。
    • 这一行代码将malloc返回的指针（即新分配的内存地址）赋值给L.data，这样L.data就指向了新分配的内存区域。

综上所述，这一行代码的目的是为顺序表L分配一个可以存储InitSize个整数的内存区域，并将这块内存的地址赋值给L.data。此后，顺序表L就可以通过L.data指针来访问和操作这些内存中的元素了。

需要注意的是，在使用malloc分配内存后，应始终检查返回值是否为NULL，以确保内存分配成功。此外，当不再需要这块内存时，应使用free函数来释放它，以防止内存泄漏。

步骤6：

void IncreaseSize(SeqList& L, int len) {int* p = L.data;L.data = (int*)malloc((L.MaxSize + len) * sizeof(int));

分析：

定义了增加顺序表大小的函数IncreaseSize，它接受一个SeqList类型的引用L和一个整数len作为参数。首先，它保存了L.data的当前地址到指针p中，以便稍后释放这块内存。然后，它使用malloc为L.data重新分配了一块更大的内存空间，新的大小是原来的L.MaxSize加上增加的len个整数的大小。

步骤7：

    for (int i = 0; i < L.length; i++) {L.data[i] = p[i];}

分析：
使用循环遍历原顺序表L的每一个元素，并将这些元素复制到新分配的内存空间中。

步骤8：

    L.MaxSize = L.MaxSize + len;free(p);
}

分析：
更新顺序表L的最大容量L.MaxSize，然后释放原来L.data指向的内存空间。

步骤9：

int main() {SeqList L;InitList(L);IncreaseSize(L, 5);
}

分析：
定义了程序的主函数main。首先，创建了一个SeqList类型的变量L，然后调用InitList函数初始化L，最后调用IncreaseSize函数将L的大小增加5个单位。

总结

这篇文章到这里就结束了

谢谢大家的阅读！

如果觉得这篇博客对你有用的话，别忘记三连哦。

我是豌豆射手^，让我们我们下次再见

在这里插入图片描述

在这里插入图片描述

这篇关于【王道数据结构笔记】顺序表的动态分配代码分析的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/905363。

相关文章

python panda库从基础到高级操作分析

python panda库从基础到高级操作分析

《pythonpanda库从基础到高级操作分析》本文介绍了Pandas库的核心功能,包括处理结构化数据的Series和DataFrame数据结构,数据读取、清洗、分组聚合、合并、时间序列分析及大数据... 目录1. Pandas 概述2. 基本操作：数据读取与查看3. 索引操作：精准定位数据4. Group
阅读更多...
Python使用Tenacity一行代码实现自动重试详解

Python使用Tenacity一行代码实现自动重试详解

《Python使用Tenacity一行代码实现自动重试详解》tenacity是一个专为Python设计的通用重试库,它的核心理念就是用简单、清晰的方式,为任何可能失败的操作添加重试能力,下面我们就来看... 目录一切始于一个简单的 API 调用Tenacity 入门：一行代码实现优雅重试精细控制：让重试按我
阅读更多...
MySQL中EXISTS与IN用法使用与对比分析

MySQL中EXISTS与IN用法使用与对比分析

《MySQL中EXISTS与IN用法使用与对比分析》在MySQL中,EXISTS和IN都用于子查询中根据另一个查询的结果来过滤主查询的记录,本文将基于工作原理、效率和应用场景进行全面对比... 目录一、基本用法详解1. IN 运算符2. EXISTS 运算符二、EXISTS 与 IN 的选择策略三、性能对比
阅读更多...
MySQL 内存使用率常用分析语句

MySQL 内存使用率常用分析语句

《MySQL内存使用率常用分析语句》用户整理了MySQL内存占用过高的分析方法,涵盖操作系统层确认及数据库层bufferpool、内存模块差值、线程状态、performance_schema性能数据... 目录一、 OS层二、 DB层1. 全局情况2. 内存占js用详情最近连续遇到mysql内存占用过高导致
阅读更多...
深度解析Nginx日志分析与499状态码问题解决

深度解析Nginx日志分析与499状态码问题解决

《深度解析Nginx日志分析与499状态码问题解决》在Web服务器运维和性能优化过程中,Nginx日志是排查问题的重要依据,本文将围绕Nginx日志分析、499状态码的成因、排查方法及解决方案展开讨论... 目录前言1. Nginx日志基础1.1 Nginx日志存放位置1.2 Nginx日志格式2. 499
阅读更多...
Spring Bean初始化及@PostConstruc执行顺序示例详解

Spring Bean初始化及@PostConstruc执行顺序示例详解

《SpringBean初始化及@PostConstruc执行顺序示例详解》本文给大家介绍SpringBean初始化及@PostConstruc执行顺序,本文通过实例代码给大家介绍的非常详细,对大家的... 目录1. Bean初始化执行顺序2. 成员变量初始化顺序2.1 普通Java类（非Spring环境）(
阅读更多...
Olingo分析和实践之EDM 辅助序列化器详解(最佳实践)

Olingo分析和实践之EDM 辅助序列化器详解(最佳实践)

《Olingo分析和实践之EDM辅助序列化器详解(最佳实践)》EDM辅助序列化器是ApacheOlingoOData框架中无需完整EDM模型的智能序列化工具,通过运行时类型推断实现灵活数据转换,适用... 目录概念与定义什么是 EDM 辅助序列化器？核心概念设计目标核心特点1. EDM 信息可选2. 智能类
阅读更多...
Olingo分析和实践之OData框架核心组件初始化(关键步骤)

Olingo分析和实践之OData框架核心组件初始化(关键步骤)

《Olingo分析和实践之OData框架核心组件初始化(关键步骤)》ODataSpringBootService通过初始化OData实例和服务元数据,构建框架核心能力与数据模型结构,实现序列化、URI... 目录概述第一步：OData实例创建1.1 OData.newInstance() 详细分析1.1.1
阅读更多...
Olingo分析和实践之ODataImpl详细分析(重要方法详解)

Olingo分析和实践之ODataImpl详细分析(重要方法详解)

《Olingo分析和实践之ODataImpl详细分析(重要方法详解)》ODataImpl.java是ApacheOlingoOData框架的核心工厂类,负责创建序列化器、反序列化器和处理器等组件,... 目录概述主要职责类结构与继承关系核心功能分析1. 序列化器管理2. 反序列化器管理3. 处理器管理重要方
阅读更多...
Python实现MQTT通信的示例代码

Python实现MQTT通信的示例代码

《Python实现MQTT通信的示例代码》本文主要介绍了Python实现MQTT通信的示例代码,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一... 目录1. 安装paho-mqtt库‌2. 搭建MQTT代理服务器（Broker）‌‌3. pytho
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2