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

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优点和缺点

• 优点：

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

 

• 缺点：

插入和删除操作需要移动大量元素。

4.动态数组初始化实现

• 优点：

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

 

• 缺点：

插入和删除操作需要移动大量元素。

 

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

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

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

 

 

 

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

1. 概念解释：

1. 表头结点

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

1. 数据结点

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

1. 尾结点

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

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

6.动态数组删除实现

 

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

8.动态数组文件编写

9.链表设计

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

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

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

 

13.课程回顾

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

 

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

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