基本概念

程序 = 数据结构 + 算法

算法 = 逻辑 + 控制

软件 = 数据结构 + 算法 + 文档

数据结构的两大用途：

• 存放要处理的数据。
• 实现算法策略，如迷宫地图中探索方向的增量数。

常见的数据结构：数组、栈、队列、表、串、树、图、文件

如何区分数据结构和算法？

        假设我们要设计一个可以查询电话号码的号码簿，那么

• 如何表示和存储电话号码簿的所有信息—数据结构设计
• 如何实现快速查找----算法设计

相关术语:

• 数据：能够被计算机识别的符号的集合。
• 数据元素：数据集合中的一个“个体”
• 数据项：数据结构中讨论的最小单位，数据元素可以是数据项的集合。

数据结构

        我们通过一个数据表来看一看常见的数据结构有哪些，假设某单位有如下职工，从中我们可以得到3种数据结构关系。

线性结构

树形结构 

 

图形结构

 集合

集合是另外一种数据结构，他是一种散列结构。

数据的4种逻辑结构

        综上，数据共有4种逻辑结构，结构图如下：

数据结构由一个四元组来表示：

Data_Structure ＝（D，L，S，O）， 数据元素、数据元素之间的逻辑关系、逻辑关系在计算机中的存储 表示、以及所规定的操作这四部分。

存储结构

逻辑结构侧重于算法分析和设计，存储结构侧重于算法实现

存储结构分类：

• 顺序存储：把逻辑上相邻的元素存储在物理位置相邻的存储单元中
• 链式存储：在数据元素中添加一些地址域或辅助结构，用于存放数据元素之间的关系。
• 哈希存储

关系图

数据类型

 

迷宫游戏与数据结构算法

思考：如何通过编程找到如下迷宫的出口？

 

迷宫游戏引出算法问题：

• 如何表示给定的空间和可行路径？
• 如何表示出口和入口？
• 当有多条路径的时候如何选择？
• 当某路径在某点之后再无可走路径该如何处理？
• 某点重复经过吗，如何避免兜圈？