大连工业大学：《数据结构》课程教学资源（PPT课件讲稿，共十章，路莹）

数据结构 辽宁省第十一届教育软件大赛参赛作品 大连工业大学信息学院计算机教研室路莹刘娜 2021年2月5日

辽宁省第十一届教育软件大赛参赛作品 大连工业大学 信息学院 计算机教研室 路莹 刘娜 数据结构 2021年2月5日

数据结构 第1章绪论 第2章线性表 第3章栈和队列 第4章串 第5章数组和广义表 第6童树和二叉树 第7童图 第9章杳找 第10章内部推序 数据结构 ③◎@

3 第1章 绪论 第2章 线性表 第3章 栈和队列 第4章 串 第5章 数组和广义表 第6章 树和二叉树 第7章 图 第9章 查找 第10章 内部排序 数据结构

第1章绪论 G11什么是数据结构 G12基本概念和术语 G13抽象数据类型的表示和实现 G14算法和算法分析 数据结构 ③◎@

4  1.1 什么是数据结构  1.2 基本概念和术语  1.3 抽象数据类型的表示和实现  1.4 算法和算法分析 第1章 绪论

1.1什么是数据结构 、数据结构课程的研究内容 电子计算机的主要用途: 早期:主要用于数值计算 数学模型→选择计算机语言→编出程序→测试→最终解答 后来:处理逐渐扩大到非数值计算领域(能处理 多种复杂的具有一定结构关系的数据 数据元素之间的相互关系一般无法用数学方程加以描述 数据结构 ③@

5 一、数据结构课程的研究内容 电子计算机的主要用途： 早期： 主要用于数值计算。 后来： 处理逐渐扩大到非数值计算领域（能处理 多种复杂的具有一定结构关系的数据） 数学模型→选择计算机语言→编出程序→测试→最终解答 数据元素之间的相互关系一般无法用数学方程加以描述 1.1 什么是数据结构

1.1什么是数据结构 非数值计算问题 例1.1电话号码查询问题。 例1.2田径赛的时间安排问题: 设有六个比赛项目,规定每个选手至多可参加三个项目,有 五人报名参加比赛(如下表所示)。要求设计比赛日程表, 使得在尽可能短的时间内完成比赛。 姓名 项目1 项目2 项目3 跳高 跳远 米 标枪 铅球 张 标抢 米200米 李四 铅球 200米 跳高 「王五「跳远200米十 数据结构 ③◎@

6  非数值计算问题 例1.1 电话号码查询问题。 例1.2 田径赛的时间安排问题： 设有六个比赛项目，规定每个选手至多可参加三个项目，有 五人报名参加比赛（如下表所示）。要求设计比赛日程表， 使得在尽可能短的时间内完成比赛。 姓 名 项目 1 项目 2 项目 3 丁 一 跳 高 跳 远 100 米 马 二 标 枪 铅 球 张 三 标 抢 100 米 200 米 李 四 铅 球 200 米 跳 高 王 五 跳 远 200 米 1.1 什么是数据结构

1.1什么是数据结构 (1)设用如下六个不同的编码代表不同的项目:比赛比赛 时间项目 跳高跳远标枪铅球100米200米 1 A, C D E F B, D (2)用顶点(圆圈)代表比赛项目 234 E 不能同时进行比赛的项目之间连上一条边。 姓名项目1项目2项目3 丁马张 E ACCDB BDEFF A B F E 李四 A 王五 D 数据结构 ③◎@

7 （1）设用如下六个不同的编码代表不同的项目： 跳高 跳远 标枪 铅球 100米 200米 A B C D E F 姓名 项目1 项目2 项目3 丁一 A B E 马二 C D 张三 C E F 李四 D F A 王五 B F （2）用顶点（圆圈）代表比赛项目 不能同时进行比赛的项目之间连上一条边。 A E B F D C 比赛 时间 比赛 项目 1 A，C 2 B，D 3 E 4 F 1.1 什么是数据结构

1.1什么是数据结构 由此可见:对于解决非数值计算的问题首先要考虑 对相关的各种信息如何表示,组织和存储? 因此,可以认为:数据结构是一门研穷非数值计算 的程序设计问题中计算机的操作对象以及它们 之间的关系作筹的学科。 数据结构 ③@

8 因此，可以认为：数据结构是一门研究非数值计算 的程序设计问题中计算机的操作对象以及它们 之间的关系和操作等的学科。 由此可见：对于解决非数值计算的问题首先要考虑 对相关的各种信息如何表示、组织和存储？ 1.1 什么是数据结构

1.1什么是数据结构 1许卓群,张乃孝,杨冬青,唐世渭,《数据结构》,国防科技大学 计算机研究所,1985年 “按某种逻辑关系组织起来的一批数据,按一定的存储表示方式把它 存储在计算机的存储器中,并在这些数据上定义了一个运算的集合, 就叫做一个数据结构。” 特点:从三个方面来看数据结构 2李春葆,《数据结构(C语言篇)习题与解析》,清华大学出版社, 2000年 “数据结构是指同一数据元素类中各数据元素之间存在的关系。数据结构 又可以分为下述三个组成部分,它们分别是数据的逻辑结构、数据的存储 结构和数据的运算。” 特点:明确强调“关系”,且细分“关系” 数据结构 ③@

9 1.许卓群，张乃孝，杨冬青，唐世渭，《数据结构》，国防科技大学 计算机研究所，1985年 “按某种逻辑关系组织起来的一批数据，按一定的存储表示方式把它 存储在计算机的存储器中，并在这些数据上定义了一个运算的集合， 就叫做一个数据结构。” 特点：从三个方面来看数据结构。 2.李春葆，《数据结构（C语言篇）习题与解析》，清华大学出版社， 2000年 “数据结构是指同一数据元素类中各数据元素之间存在的关系。数据结构 又可以分为下述三个组成部分，它们分别是数据的逻辑结构、数据的存储 结构和数据的运算。” 特点：明确强调“关系”，且细分“关系”。 1.1 什么是数据结构

1.1什么是数据结构 3黄国瑜,叶乃菁,《数据结构》,清华大学出版社,2001年 “在程序语言中,“数据类型”是指程序语言中变量所能表示并存储的 数据种类,“数据实体”则是指在一种数据类型中的所有可能元素的集 合。而“数据结构”,大致上说来,就是数据实体中元素之间的关系, 包括数据的表示法和运算。” 特点:指出“关系”为表示法和运算。 4陈慧南,《数据结构—C语言描述》,西安电子科技大学出版社, 2003年 从数学概念上讲,一个数据结构是由数据元素依据某种逻辑联系组织起 来的。 研究数据结构是为了解决应用问题,所以讨论数据结构必须同时讨论在数 据结构上执行的相关运算及其算法才有意义。” 特点:从逻辑联系入手,兼顾其它方面。 数据结构 ③@

10 3.黄国瑜，叶乃菁，《数据结构》，清华大学出版社，2001年 “在程序语言中，“数据类型”是指程序语言中变量所能表示并存储的 数据种类，“数据实体”则是指在一种数据类型中的所有可能元素的集 合。而“数据结构”，大致上说来，就是数据实体中元素之间的关系， 包括数据的表示法和运算。” 特点：指出“关系”为表示法和运算。 4.陈慧南，《数据结构——C语言描述》，西安电子科技大学出版社， 2003年 “从数学概念上讲，一个数据结构是由数据元素依据某种逻辑联系组织起 来的。 研究数据结构是为了解决应用问题，所以讨论数据结构必须同时讨论在数 据结构上执行的相关运算及其算法才有意义。” 特点：从逻辑联系入手，兼顾其它方面。 1.1 什么是数据结构

1.1什么是数据结构 学习数据结构课程的用处 计算机内的数值运算依靠方程式,而非数值运算则 要依靠数据结构。 同样的数据对象,用不同的数据结构来表示,运算 效率可能有明显的差异。 程序设计实质〓好算法+好结构 数据结构 ③◎@

11 计算机内的数值运算依靠方程式，而非数值运算则 要依靠数据结构。 同样的数据对象，用不同的数据结构来表示，运算 效率可能有明显的差异。 程序设计实质 = 好算法 + 好结构 二、学习数据结构课程的用处 1.1 什么是数据结构