第1章绪论 1.1什么是数据结构？《算法与数据结构（C＆Java）（第2版）》 同步教学（电子工业出版社）

6学科网 第一章绪论 什ㄙ是数据结构 基本概念和术语 算法和算法分析 6学科网 WWW.ZXXK.CO 1.1 什么是数据结构？ 一、为什么要学习数据结构？ &电子计算机的主要用途 早期： 主要用于数值计算。 后来： 处理逐渐扩大到非数值计算领域（能 处理多种复杂的具有一定结构关系的数据)。 6学科 WWW.ZXXK. -ar ● 数值计算解决问题的一般步骤： 学模型→选择计算机语言→编出程序→测试→最终解 答 数值计算的关键是：如何得出数学模型 （方程)？ ● 程序设计人员比较关注程序设计的技巧 非数值计算问题： 数据元素之间的相互关系一般无法用数学方程加以描述 6学科网 WWW.ZXXK.CON 非数值计算问题： 。例1.1 电话号码查询问题 (1)按顺序存储方式：需逼历表 (2)按姓氏索引方式：索引 要写出好的查找算法，取决于这张表的结构 及存储方式 电话号码表的结构和存储方式决定了查找 (算法)的效率。 6学科网 WWW.ZXXK.CON 非数值计算问题： ●例1.2 田径赛的时间安问题（无向图的着色问 题) 设有六个比赛项目，规定每个选手至多可参加三个项 自，有玉人报名参加此赛（如下表所示）设计比赛白程 表，使得在荩可能短的时间内完成此赛。 姓名 项目1 项目2 项目3 教工1 跳高 跳远 100米 教工2 标枪 铅球 教工3 标枪 100米 200米 教工4 铅球 200米 跳高 教工5 跳远 200米 6学科网 WWW.ZXXK.CON 非数值计算问题 一---田径赛的时间安排问题 解法 (1) 设用如下六个不同的代号代表不同的项 目 跳高 跳远 标枪 铅球 100米 200米 A B C D E F (2)) 用顶点代表比赛项目 不能同时进行比赛的项目之间连上一条边。 (3)某选手比赛的项目必定有边相连 (不能同 时比赛)。 6学科网 姓名 项目1 项目2 项目3 只需 教工1 A B E 安排四 教工2 C D 个单位 教工3 C E F 教工4 D F A 时间进 教工5 B F 行比赛 比赛时间 比赛项目 A B 1 A,C 2 B,D F E 3 E D C 4 F 6学科网 求解非数值计算的问题： 主要考虑的是设计出合适的数据结构及相应的算法。 即：首先要考虑对相关的各种信息如何表示、组织和 存储？ 因此，可以认为：数据结构是一门研究非数值计算的 程序设计问题中计算机的操作对象以及它们之间的关 系和操作的学科。 学科网 一、学习数据结构有什么用？ 答：计算机内的数值运算依靠方程式，而 非数值运算（如表、树、图等)则要依 靠数据结构。 同样的数据对象，用不同的数据结构来表示，运 算效率可能有明显的差异。 程序设计的实质是对实际问题选择一个好的数据 结构，加之设计一个好的算法。而好的算法在很 大程度上取决于描述实际问题的数据结构。 6学科网 WWW.ZXXK.CON 二、数据结构课程的形成和发展 形成阶段 60年代初期，. “数据结构”有关的内容散见于 操作系统、编译原理和表处理语言等课程。 1968年，“数据结构”被列入美国一些大学计 算机科学系的教学计划。 发展阶段 数据结构的概念不断扩充，包括了网络、集合 代数论、关系等“离散数学结构”的内容 70年代后期，我国高校陆续开设该课程