数据结构与算法 课堂整理笔记（C++版）

一、数据结构与算法核心关系

数据结构和算法是计算机科学两大核心基础，相辅相成、缺一不可。

1. 数据结构：负责数据的组织与存储方式，分为逻辑结构和物理结构。合理的数据结构能提升数据存储、查询、修改效率，降低程序复杂度与出错率，海量数据场景下优化效果尤为明显。
2. 算法：负责解决问题的步骤与方法，决定程序执行效率和运行正确性。优质算法需具备：正确性、高效性、简洁性、可维护性。
3. 二者关联：算法设计必须依托合适的数据结构，才能发挥结构优势；数据结构为算法提供数据承载容器，算法本质是对容器内元素做增、删、改、查操作。
4. 场景举例：排序问题可选用冒泡、插入、选择、快速排序等算法，同时需要搭配适配的数据结构存储待排序数据，不同结构和算法适配不同业务场景，需按需选择。

二、数据的基本概念

1. 定义：数据是描述客观事物的符号，是计算机可操作、可输入、可被程序处理的对象。
2. 数据分类

• 数值类型：整数、小数等，可进行数值计算；
• 非数值类型：字符、声音、图像、视频等，可通过编码转换为字符数据，做非数值处理。

三、数据结构基础定义

1. 结构含义：本质就是关系，指组成整体的各单元之间的排列、关联方式。
2. 数据结构定义：是相互之间存在一种或多种特定关系的数据元素的集合。
   计算机中的数据元素不是孤立杂乱的，而是存在内在关联，这种关联就是数据的组织形式。
3. 两大核心分类：逻辑结构、物理（存储）结构。

四、数据逻辑结构

概念

只描述数据元素之间的逻辑关系，是面向用户的呈现形式，和计算机内部实际存储无关。

四种基本类型

1. 集合结构：数据元素同属一个集合，彼此之间无固定先后顺序、无关联；
2. 线性结构：数据元素之间一对一的先后关系；
3. 树状结构：数据元素之间一对多的层次关系；
4. 图形结构：数据元素之间多对多的任意关联关系。

五、数据物理结构（存储结构）

概念

又称存储结构，指数据在计算机内存中的实际存储形式。

两种基础类型

1. 顺序存储

• 特点：数据元素存放在连续的内存空间中；
• C++典型代表：数组；
• 优势：依靠索引可随机快速访问任意位置数据。

2. 链式存储

• 特点：数据元素散落在任意内存空间，无需连续；依靠指针/链接关联前后元素；
• C++典型代表：链表；
• 后续学习重点：顺序表、链表，深入掌握顺序存储与链式存储底层原理。