1.1什么是数据结构 ●一般来说,用计算机解决一个具体问题时,大致需要经多下 列几个步骤 ●首先要从具体问题抽象出一个适当的数学模型 然后设计一个解此数学模型的算法, ●最后编出程序、进行测试、调整直至得到最终解答。 ●寻求数学模型的实质是分析问题,从中提取操作的对象,并 找出这些操作对象之间含有的关系,然后用数学的语言加以 描述 然而,更多的非数值问题无法用数学方程描述。什么是数据 结构呢?先看以下几个例子。 北京邮电大学自动化学院 11
北京邮电大学自动化学院 11 ⚫ 一般来说，用计算机解决一个具体问题时，大致需要经多下 列几个步骤： ⚫ 首先要从具体问题抽象出一个适当的数学模型 ⚫ 然后设计一个解此数学模型的算法， ⚫ 最后编出程序、进行测试、调整直至得到最终解答。 ⚫ 寻求数学模型的实质是分析问题，从中提取操作的对象，并 找出这些操作对象之间含有的关系，然后用数学的语言加以 描述。 ⚫ 然而，更多的非数值问题无法用数学方程描述。什么是数据 结构呢？先看以下几个例子。 1.1 什么是数据结构
例1书目自动检索系统(书目文件 001 高等数学樊映川 S01 002 理论力学罗远祥 L01 003 高等数学华罗庚 SO1 004 线性代数栾汝书 书目卡片 登录号 索引表 书名 作者名 分类号 按书名 出版单位 按分类号 出版时间 高等数 价格 002, 理论力学002 华罗庚|002, 001,003, 线性代数|004 栾汝书004, 北京邮电大学自动化学院
北京邮电大学自动化学院 12 001 高等数学 樊映川 S01 002 理论力学 罗远祥 L01 003 高等数学 华罗庚 S01 004 线性代数 栾汝书 S02 …… …… …… …… 书目文件 按书名 按作者名 按分类号 高等数学 001，003…… 理论力学 002，…….. 线性代数 004，…… …… …….. 樊映川 001,… 华罗庚 002,…. 栾汝书 004,…. ……. ……. L 002,… S 001,003, …… …… 索引表 线性表 例1 书目自动检索系统 登录号： 书名： 作者名： 分类号： 出版单位： 出版时间： 价格： 书目卡片
例2人机对奕问题 树 京邮电大学自动化学院 13
北京邮电大学自动化学院 13 树 …….. …….. …... …... …... …... 例2 人机对奕问题
例3多叉路口交通灯管理问题 对于一个多叉路口,设计一 个交通信号灯的管理系统。 C D 首先需要分析一下所有车辆 的行驶路线的冲突问题 这个问题可以归结为对车辆 的可能行驶方向作某种分 E 组,对分组的要求是使任一 A 个组中各个方向行驶的车辆 可以同时安全行驶而不发生 碰撞。 北京邮电大学自动化学院 14
北京邮电大学自动化学院 14 ⚫ 对于一个多叉路口，设计一 个交通信号灯的管理系统。 ⚫ 首先需要分析一下所有车辆 的行驶路线的冲突问题。 ⚫ 这个问题可以归结为对车辆 的可能行驶方向作某种分 组，对分组的要求是使任一 个组中各个方向行驶的车辆 可以同时安全行驶而不发生 碰撞。 C E D A B 例3 多叉路口交通灯管理问题
例3多叉路口交通灯管理问题 C 可通行方向 B ●A→BA→CA→>D ●B→AB→>CB→>D ●D→>AD→>BD→C E ●E→)AE→>BE→>CE→D A 北京邮电大学自动化学院
北京邮电大学自动化学院 15 可通行方向 ⚫ A→B A→C A →D ⚫ B →A B→C B→D ⚫ D→A D→B D →C ⚫ E →A E→B E→C E→D C E D A B 例3多叉路口交通灯管理问题