数据结构基础：概念、结构与算法

基本概念

数据元素

数据元素是数据的基本单位。一个数据元素可由若干数据项组成；数据项还可以是组合项，是构成数据元素的不可分割的最小单位。

数据对象

数据对象是具有相同性质的数据元素的集合，是数据的一个子集。

数据结构

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。

数据结构三要素

逻辑结构

• 集合：各种元素同属一个集合，无其他关系。
• 线性：一对一的关系；除了第一个元素都有唯一前驱，除了最后一个元素都有唯一后继。
• 树形：一对多的关系。
• 图状：多对多的关系。

数据运算

结合逻辑结构和实际需求来定义基本运算。

物理结构（存储结构）

• 顺序存储：逻辑上相邻的数据元素在物理位置上也相邻。
• 链式存储：逻辑上可以不相邻，借助指示元素存储地址的指针表示元素之间的逻辑关系。
• 索引存储：建立索引表，每个索引项存储元素信息，如关键字和地址。
• 散列存储：也称哈希存储，通过关键字计算出元素的存储地址。

算法概述

算法是对特定问题求解步骤的一种描述，是指令的有限序列。

算法具有以下重要特性：

• 有穷性
• 确定性
• 可行性
• 输入
• 输出

评价一个算法时需要考虑：

• 正确性
• 可读性
• 健壮性
• 效率与低存储量需求