数据结构与算法

研究数据结构的核心

研究数据结构的目标是设计高效的算法。核心内容包括：

• 逻辑结构：描述数据之间的逻辑关系。
• 存储结构：在计算机中实现逻辑结构的方式。
• 基本操作：在数据结构上的操作，如插入、删除、查找等。

逻辑结构

线性结构

元素之间有一对一的线性关系。

例子：

• 线性表：数据按顺序排列（如数组、链表）。
• 栈：后进先出（LIFO）。
• 队列：先进先出（FIFO）。
• 串：字符序列（字符串）。
• 数组：固定大小的连续存储单元。
• 广义表：允许元素为另一个线性表的特殊结构。

非线性结构

元素之间关系复杂，可能有层次或网络关系。

例子：

• 树：节点间有一对多的层次关系。
• 图：节点间有任意多对多的关系。

数据存储结构

顺序存储结构

用连续的内存单元存储数据。

特点：

• 易于通过索引访问。
• 插入和删除操作相对复杂，需要移动大量元素。

链式存储结构

用指针将不连续的内存单元链接在一起。

特点：

• 灵活，支持动态扩展。
• 插入和删除效率高，但随机访问速度慢。

算法的定义与五个特性

算法定义

解决特定问题的一系列明确的指令。

五个特性

• 有穷性：算法必须在有限步骤内完成。
• 确定性：每一步有明确的含义。
• 可行性：每一步都能在有限时间内完成。
• 输入：算法接受零个或多个输入。
• 输出：算法产生一个或多个输出。

数据结构中的关系

线性结构

元素之间一对一的关系，形成直线结构。

例子：链表、数组。

树形结构

元素之间一对多的关系，形成分支结构。

例子：二叉树、B树。

图形结构

元素之间多对多的关系，形成网络结构。

例子：社交网络中的好友关系图。

抽象数据类型(ADT)

定义了数据和操作，但与具体实现无关。

如栈，ADT定义了push和pop操作，而不涉及具体实现。