C++学习之动态数组和链表

devtools/2025/3/16 18:15:13/

1.课程回顾

2.数据结构基本概念

1.1数据结构概念

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下,精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。

数据结构是计算机存储、组织数据的方式。

1.2算法的概念

算法是特定问题求解步骤的描述,在计算机中表现为指令的有限序列,算法是独立存在的一种解决问题的方法和思想。

对于算法而言,语言并不重要,重要的是思想。

1.2.1算法和数据结构区别

数据结构只是静态的描述了数据元素之间的关系,高效的程序需要在数据结构的基础上设计和选择算法。

 

  1. 算法是为了解决实际问题而设计的。
  2. 数据结构是算法需要处理的问题载体。
  3. 数据结构与算法相辅相成

3.动态数组设计

操作要点:

  1. 插入元素算法
    1. 判断线性表是否合法
    2. 判断插入位置是否合法
    3. 判断空间是否满足
    4. 把最后一个元素到插入位置的元素后移一个位置
    5. 将新元素插入
    6. 线性表长度加1
  2. 获取元素操作
    1. 判断线性表是否合法
    2. 判断位置是否合法
    3. 直接通过数组下标的方式获取元素
  3. 删除元素算法
    1. 判断线性表是否合法
    2. 判断删除位置是否合法
    3. 将元素取出
    4. 将删除位置后的元素分别向前移动一个位置
    5. 线性表长度减1
  1. 元素的插入

 

  1. 元素的删除

 

注意: 链表的容量和链表的长度是两个不同的概念

示例代码\01 动态数组

2.2.2优点和缺点

  • 优点:
  1. 无需为线性表中的逻辑关系增加额外的空间。
  2. 可以快速的获取表中合法位置的元素。

 

  • 缺点:
  1. 插入和删除操作需要移动大量元素。

4.动态数组初始化实现

  • 优点:
  1. 无需为线性表中的逻辑关系增加额外的空间。
  2. 可以快速的获取表中合法位置的元素。

 

  • 缺点:
  1. 插入和删除操作需要移动大量元素。

 

2.3线性表的链式存储(单向链表)

前面我们写的线性表的顺序存储(动态数组)的案例,最大的缺点是插入和删除时需要移动大量元素,这显然需要耗费时间,能不能想办法解决呢?链表。

链表为了表示每个数据元素与其直接后继元素之间的逻辑关系,每个元素除了存储本身的信息外,还需要存储指示其直接后继的信息。

 

 

 

  1. 单链表
    1. 线性表的链式存储结构中,每个节点中只包含一个指针域,这样的链表叫单链表。
    2. 通过每个节点的指针域将线性表的数据元素按其逻辑次序链接在一起(如图)。

  1. 概念解释:
  1. 表头结点

链表中的第一个结点,包含指向第一个数据元素的指针以及链表自身的一些信息

  1. 数据结点

链表中代表数据元素的结点,包含指向下一个数据元素的指针和数据元素的信息

  1. 尾结点

链表中的最后一个数据结点,其下一元素指针为空,表示无后继。

5.动态数组插入和遍历功能实现

6.动态数组删除实现

 

7.动态数组销毁功能实现

8.动态数组文件编写

9.链表设计

10.链表初始化、插入和遍历功能实现

11.删除链表节点的功能实现

12.返回链表长度、清空销毁功能实现

 

13.课程回顾

14.单向链表企业版本设计思路

 

15.企业版本链表初始化、插入遍历功能实现

16.企业版本链表删除、销毁功能实现

 

 


http://www.ppmy.cn/devtools/167620.html

相关文章

【蓝桥杯】3514字串简写

暴力 发现只能通过20%测试点。 k int(input()) s, c1, c2 input().split() le len(s) s [0] [i for i in s] # 1 -- lecnt 0 for i in range(1, le - (k-1) 1):if s[i] c1:for j in range(i(k-1),le1):if s[j] c2:cnt 1 print(cnt)优化 if s[i] c1:for j in range(i…

Altium Designer——CHIP类元器件PCB封装绘制

文章目录 PCB封装组成元素:焊盘的属性 SS34肖特基二极管SMA(DO-214AC)封装绘制资料:步骤:1.绘制焊盘:用到的快捷键:资料: 2.绘制丝印:用到的快捷键:资料: PCB封装组成元素…

DeepSeek 与 ChatGPT的主要区别

DeepSeek 是由中国公司 DeepSeek AI (杭州深度求索人工智能基础技术研究有限公司)开发的 AI 聊天机器人,于 2024 年推出。相比之下,ChatGPT 是由美国 AI 研究实验室 OpenAI 创建的,自 2022 年以来就已上市。两者都是专…

深入理解HTTP与HTTPS:协议原理与C++实战指南

一、引言:HTTP与HTTPS是什么? HTTP(HyperText Transfer Protocol) 是互联网上应用最广泛的协议之一,用于客户端(如浏览器)与服务器之间的通信。它基于明文传输,简单高效&#xff0c…

Java在小米SU7 Ultra汽车中的技术赋能

目录 一、智能驾驶“大脑”与实时数据 场景一:海量数据的分布式计算 场景二:实时决策的毫秒级响应 场景三:弹性扩展与容错机制 技术隐喻: 二、车载信息系统(IVI)的交互 场景一:Android Automo…

创客匠人创始人IP变现大课将于3月在成都举办 助力知识付费转型

2025年3月15日至17日,由IP变现整体解决方案服务商创客匠人主办的“创始人IP变现大课”将在成都生物城凯悦嘉轩酒店举行。本次活动旨在为知识付费行业从业者提供系统化方法论与实战指导,解决创始人IP在流量获取、变现模式及同质化竞争中的核心痛点。 作为…

Python之if语句

闲暇之余,学学Python,整理成笔记分享给大家。 注:本文内容来源于《Python编程从入门到实践第3版》一书。 主要内容: # 一个简单的示例 cars [audi, bmw, subaru, toyota] for car in cars:if car bmw:print(car.upper())els…

Java泛型是什么?有什么作用?

Java泛型(Generics)是Java语言中一种类型参数化的机制,允许在类、接口、方法中使用类型参数,使代码能够处理多种数据类型,同时保证类型安全。泛型的主要目的是增强代码的复用性和安全性,避免类型转换错误。…