数据结构与算法－定义与分类

数据结构分类

什么是数据结构

数据结构是为了高效访问数据而设计出的一种数据的组织和存储方式。更具体的说，一个数据结构包含一个数据元素的集合、数据元素之间的关系以及访问和操作数据的方法。

数据结构的分类

逻辑结构

数据的逻辑结构反映了数据元素之间的逻辑关系。逻辑结构可分为线性和非线性两大类。

线性数据结构中的元素之间是一对一的顺序关系，在一对一的顺序关系中，除了第一个元素没有前驱元素，最后一个元素没有后继元素外，其余每个元素都有且仅有一个直接前驱元素和一个直接后继元素。这种关系使得数据元素可以按照一个线性的顺序依次排列，就像排成一列的队伍，每个成员前后都有明确的相邻成员（队首和队尾除外）如数组、列表、栈、队列等。

非线性数据结构中的元素之间具有多个对应关系，如树、图等。

物理结构

数据的物理结构反映了数据在计算机内存中的存储结构。一般而言，数据结构针对的是内存中的数据。内存由许多存储单元组成，每个存储单元可以存储一个固定大小的数据块，通常以字节（Byte）为单位。每个存储单元都有一个唯一的地址，操作系统正是根据这一地址去访问内存中的数据的。数据在内存中的存储结构可分为连续存储（数组）与分散存储（链表）。

连续存储借助数据之间的相对位置来表示数据元素之间的逻辑关系。

分散存储借助指示数据位置的指针来表示数据元素之间的逻辑关系。

所有数据结构都是基于数组、链表或二者的组合实现的。例如，栈和队列既可以使用数组实现，也可以使用链表实现；而哈希表的实现可能同时包含数组和链表。

算法

什么是算法

算法是一个用于解决特定问题的有限指令序列（计算机可以执行的操作）。也可以理解为：可以解决特定问题的方法。

算法的五大特性

输入：算法具有0个或多个输入

输出：算法至少有一个输出

有穷性：算法在有限的步骤之后会自动结束而不会无限循环，并且每一个步骤可以在可接受的时间内完成。

确定性：算法中的每一步都有确定的含义，不会出现二义性。

可行性：算法的每一步都是清楚且可行的，能让用户用纸笔计算而求出答案。

算法的分类

按照应用目的分类：搜索算法（深度优先搜索、广度优先搜索等）、排序算法（冒泡排序、插入排序、选择排序、快速排序、归并排序等）、最优化算法等。

按照实现策略分类：暴力法、增量法、分治算法、动态规划算法、贪心算法等。