逻辑结构与存储结构

数组可以被当做存储结构来看待，对应存储结构中的顺序存储，其本身是为了实现顺序存储而产生的工具。并不是任何数据结构都只有两种存储结构，线性和链式只是整体的描述，还会根据具体情况分成多种存储结构。

逻辑结构分类

根据逻辑结构可以将数据结构分为以下大类：

• 线性结构：表（顺序表、链表）、广义表、栈、队列
• 树形结构：二叉树、二叉搜索树、堆
• 图结构：有向图、无向图
• 其他：哈希

每种结构都可以有两种基本的存储结构：

• 顺序存储：用数组实现，数据元素在内存中连续存放
• 链式存储：用指针实现，数据元素在内存中不连续存放，通过指针链接

例如，表可以分为顺序表和链表；图可以用邻接矩阵（顺序存储）或邻接表（链式存储）来表示。

常见考点总结

• 广义表表示
• 哈夫曼树：不唯一
• 最小生成树：Prim 算法 / Kruskal 算法，边权和最小，不一定唯一，适用于无向连通图，无负权环
• 拓扑排序：AOV 网，不一定唯一
• 关键路径：AOE 网，最早开始时间、最迟开始时间，关键路径不一定唯一
• 最短路径：Dijkstra（无负权边环，路径不唯一），Floyd（无负权环，路径不唯一，矩阵唯一）

链接到

• 上一个知识点：1.1 抽象数据类型
• 下一个知识点：无（本章最后一个知识点）
• 相关知识点：生成树和最小生成树、树