数据结构 机电工程学院 程艺苑
数据结构 机电工程学院 程艺苑
第1章绪论 1.1什么是数据结构 1.2基本概念和术语 1.3抽象数据类型 1.4算法和算法分析
第1章 绪论 1.1 什么是数据结构 1.2 基本概念和术语 1.3 抽象数据类型 1.4 算法和算法分析
“数据结构”学科形成和发展背景 ● 1946年第一台计算机问世，计算机产业的飞速发展，深 入到人类社会的各个领域。 ● 计算机的应用已不再局限于科学计算，而更多地用于控 制、管理及数据处理等非数值计算的处理工作。 。计算机加工处理的对象由纯粹的数值发展到字符、表格 和图像等各种具有一定结构的数据，这就给程序设计带 来一些新的问题。 ● 为了编写一些“好”的程序，必须分析待处理对象的特 性以及各处理对象间的关系。这就是“数据结构”这门 学科形成和发展的背景
“数据结构”学科形成和发展背景 ⚫ 1946年第一台计算机问世，计算机产业的飞速发展，深 入到人类社会的各个领域。 ⚫ 计算机的应用已不再局限于科学计算，而更多地用于控 制、管理及数据处理等非数值计算的处理工作。 ⚫ 计算机加工处理的对象由纯粹的数值发展到字符、表格 和图像等各种具有一定结构的数据，这就给程序设计带 来一些新的问题。 ⚫ 为了编写一些“好”的程序，必须分析待处理对象的特 性以及各处理对象间的关系。这就是“数据结构”这门 学科形成和发展的背景
1.1什么是数据结构 数值计算解决问题的一般步骤： 数学模型→选择计算机语言→编出程序→测试→最 终解答。 ·数值计算的关键是：如何得出数学模型（方程）？ ·程序设计人员比较关注程序设计的技巧。 ●1 非数值计算问题中，数据元素之间的相互关系一般 无法用数学方程加以描述
1.1 什么是数据结构 ⚫ 数值计算解决问题的一般步骤： ⚫ 数学模型→选择计算机语言→编出程序→测试→最 终解答。 ⚫ 数值计算的关键是：如何得出数学模型（方程）？ ⚫ 程序设计人员比较关注程序设计的技巧。 ⚫ 非数值计算问题中，数据元素之间的相互关系一般 无法用数学方程加以描述
例1-1书目自动检索系统 线性表 书目文件 001 高等卡映川 S01 002 理论力学 登 罗远祥 L01 003 高等数学 华罗庚 S01 索引表 004 书饿性代数 栾汝书 S02 者名： 按书名 分类号： 按作者名 按分类号 高等数学 001,003.出版单位：樊映川 001, L 002,… 理论力学 002, …出版时间 华罗庚 002, S 001,003, 线性代数 004, 价格 栾汝书 004,…
9 –例1-1 书目自动检索系统 登录号： 书名： 作者名： 分类号： 出版单位： 出版时间： 价格： 001 高等数学 书目卡片 樊映川 S01 002 理论力学 罗远祥 L01 003 高等数学 华罗庚 S01 004 线性代数 栾汝书 S02 …… …… …… …… 书目文件 按书名 按作者名 按分类号 高等数学 001，003…… 理论力学 002，…….. 线性代数 004，…… …… …….. 樊映川 001,… 华罗庚 002,…. 栾汝书 004,…. ……. ……. L 002,… S 001,003, …… …… 索引表 线性表
例1-2 井字棋
树 …….. …….. …... …... …... …... –例1-2 井字棋
例1-3多叉路口交通灯管理问题 AB BA
–例1-3 多叉路口交通灯管理问题 C E D A B AB AC AD BA BC BD DA DB DC EA EB EC ED 图
综上三个例子可见，描述这类非数值计算问题 的数学模型不再是数学方程，而是诸如表、树 和图之类的数据结构。因此，简单说来，数据 结构是一门研究非数值计算的程序设计问题中 计算机的操作对象以及它们之间的关系和操作 等等的学科
⚫ 综上三个例子可见，描述这类非数值计算问题 的数学模型不再是数学方程，而是诸如表、树 和图之类的数据结构。因此，简单说来，数据 结构是一门研究非数值计算的程序设计问题中 计算机的操作对象以及它们之间的关系和操作 等等的学科
数据结构课程的形成和发展 形成阶段： 60年代初期，“数据结构”有关的内容散见于操作系统、 编译原理和表处理语言等课程。1968年，“数据结构” 被列入美国一些大学计算机科学系的教学计划。 发展阶段： 数据结构的概念不断扩充，包括了网络、集合代数论、 关系等“离散数学结构”的内容。 70年代后期，我国高校陆续开设该课程
形成阶段： 60年代初期，“数据结构”有关的内容散见于操作系统、 编译原理和表处理语言等课程。1968年，“数据结构” 被列入美国一些大学计算机科学系的教学计划。 发展阶段： 数据结构的概念不断扩充，包括了网络、集合代数论、 关系等“离散数学结构”的内容。 70年代后期，我国高校陆续开设该课程。 数据结构课程的形成和发展
数据结构所处的地位 数学 代数系统 编码理论 算子关系 数据类型 数据表示法 数据的运算 文件系统 存储装置 数据结构 数据组织 数据存取 信息检索 硬件 机器组织 软件 (计算机系统 (计算机程序 设计) 设计)
数据结构所处的地位