数据结构chapter资料PPT学习教案

1、会计学1 数据结构数据结构chapter资料资料 学时数： 48学时 教 材：数据结构C语言版严蔚敏、吴伟民 -清华大学出版社 教学参考书： 1 殷人昆等，数据结构（用面向对象方法与殷人昆等，数据结构（用面向对象方法与C+描述），清华描述），清华 大学出版社大学出版社 2数据结构题集数据结构题集（C语言版），严蔚敏，清华大学出版社语言版），严蔚敏，清华大学出版社 3 丁宝康等，数据结构自学考试指导，清华大学出版社丁宝康等，数据结构自学考试指导，清华大学出版社 2 第1页/共26页 第1章 绪论 第2章 线性表 第3章 栈和队列 第4章 串 第5章 数组和广义表 第6章 树和二叉树 第7章 图

2、第9章 查找 3 第2页/共26页 1.1 什么是数据结构什么是数据结构 1.2 基本概念和术语基本概念和术语 1.3 抽象数据类型的表示和实现抽象数据类型的表示和实现 1.4 算法和算法分析算法和算法分析 4 第3页/共26页 一、数据结构课程的研究内容一、数据结构课程的研究内容 电子计算机的主要用途：电子计算机的主要用途： 早期：早期： 主要用于数值计算。主要用于数值计算。 后来：后来： 处理逐渐扩大到非数值计算领域（能处理处理逐渐扩大到非数值计算领域（能处理 多种复杂的具有一定结构关系的数据）多种复杂的具有一定结构关系的数据） 数学模型数学模型选择计算机语言选择计算机语言编出程序编出程序

3、测试测试最终解答最终解答 数据元素之间的相互关系一般无法用数学方程加以描述数据元素之间的相互关系一般无法用数学方程加以描述 5 第4页/共26页 非数值计算问题 例1.1 电话号码查询问题。 例1.2 田径赛的时间安排问题： 设有六个比赛项目，规定每个选手至多可参加三个项目，有设有六个比赛项目，规定每个选手至多可参加三个项目，有 五人报名参加比赛（如下表所示）。要求设计比赛日程表，五人报名参加比赛（如下表所示）。要求设计比赛日程表， 使得在尽可能短的时间内完成比赛。使得在尽可能短的时间内完成比赛。 6 第5页/共26页 （1）设用如下六个不同的编码代表不同的项目： 跳高跳高 跳远跳远 标枪标枪

4、 铅球铅球 100100米米 200200米米 A BA B C D E C D E F F 姓名姓名项目项目1项目项目2项目项目3 丁一丁一 A B E 马二马二 C D 张三张三 C E F 李四李四 D F A 王五王五 B F （2）用顶点（圆圈）代表比赛项目 不能同时进行比赛的项目之间连上一条边。不能同时进行比赛的项目之间连上一条边。 比赛比赛 时间时间 比赛比赛 项目项目 1A，C 2B，D 3E 4F 7 第6页/共26页 因此，可以认为：数据结构是一门研究非数值计算 的程序设计问题中计算机的操作对象以及它们 之间的关系和操作等的学科。 由此可见：对于解决非数值计算的问题首先要考

5、虑 对相关的各种信息如何表示、组织和存储？对相关的各种信息如何表示、组织和存储？ 8 第7页/共26页 1.许卓群，张乃孝，杨冬青，唐世渭，许卓群，张乃孝，杨冬青，唐世渭，数据结构数据结构，国防科技大学，国防科技大学 计算机研究所，计算机研究所，1985年年 “按某种逻辑关系组织起来的一批数据，按一定的存储表示方式把它按某种逻辑关系组织起来的一批数据，按一定的存储表示方式把它 存储在计算机的存储器中，并在这些数据上定义了一个运算的集合，存储在计算机的存储器中，并在这些数据上定义了一个运算的集合， 就叫做一个数据结构。就叫做一个数据结构。” 特点：从三个方面来看数据结构。特点：从三个方面来看数据

6、结构。 2.李春葆，李春葆，数据结构（数据结构（C语言篇）习题与解析语言篇）习题与解析，清华大学出版社，清华大学出版社， 2000年年 “数据结构是指同一数据元素类中各数据元素之间存在的关系。数据结构数据结构是指同一数据元素类中各数据元素之间存在的关系。数据结构 又可以分为下述三个组成部分，它们分别是数据的逻辑结构、数据的存储又可以分为下述三个组成部分，它们分别是数据的逻辑结构、数据的存储 结构和数据的运算。结构和数据的运算。” 特点：明确强调特点：明确强调“关系关系”，且细分，且细分“关系关系”。 9 第8页/共26页 3.黄国瑜，叶乃菁，黄国瑜，叶乃菁，数据结构数据结构，清华大学出版社，清

7、华大学出版社，2001年年 “在程序语言中，在程序语言中，“数据类型数据类型”是指程序语言中变量所能表示并存储的是指程序语言中变量所能表示并存储的 数据种类，数据种类，“数据实体数据实体”则是指在一种数据类型中的所有可能元素的集则是指在一种数据类型中的所有可能元素的集 合。而合。而“数据结构数据结构”，大致上说来，就是数据实体中元素之间的关系，大致上说来，就是数据实体中元素之间的关系， 包括数据的表示法和运算。包括数据的表示法和运算。” 特点：指出特点：指出“关系关系”为表示法和运算。为表示法和运算。 4.陈慧南，陈慧南，数据结构数据结构C语言描述语言描述，西安电子科技大学出版社，西安电子科技

8、大学出版社， 2003年年 “从数学概念上讲，一个数据结构是由数据元素依据某种逻辑联系组织起从数学概念上讲，一个数据结构是由数据元素依据某种逻辑联系组织起 来的。来的。 研究数据结构是为了解决应用问题，所以讨论数据结构必须同时讨论在数研究数据结构是为了解决应用问题，所以讨论数据结构必须同时讨论在数 据结构上执行的相关运算及其算法才有意义。据结构上执行的相关运算及其算法才有意义。” 特点：从逻辑联系入手，兼顾其它方面。特点：从逻辑联系入手，兼顾其它方面。 10 第9页/共26页 计算机内的数值运算依靠方程式，而非数值运算计算机内的数值运算依靠方程式，而非数值运算 则要依靠数据结构。则要依靠数据结

9、构。 同样的数据对象，用不同的数据结构来表示，运算同样的数据对象，用不同的数据结构来表示，运算 效率可能有明显的差异。效率可能有明显的差异。 程序设计实质程序设计实质 = 好算法好算法 + 好结构好结构 二、学习数据结构课程的用处二、学习数据结构课程的用处 11 第10页/共26页 是介于数学、计算机硬件和计算机软件三者 之间的一门核心课程 数学数学 硬件硬件 软件软件 三、数据结构课程的地位三、数据结构课程的地位 12 第11页/共26页 数据数据-是对客观事物的符号表示，在计算机科学中是指所是对客观事物的符号表示，在计算机科学中是指所 有有（Data） 能输入到计算机中并被计算机程序处理能

10、输入到计算机中并被计算机程序处理 的符号的总的符号的总 称称(整数、实数、字符串、图像、声音等整数、实数、字符串、图像、声音等)。 数据元素数据元素-是数据的是数据的基本基本单位，具有完整确定的实际意义，单位，具有完整确定的实际意义， （Data Element） 在计算机程序中通常作为一个整体进行考虑和在计算机程序中通常作为一个整体进行考虑和 处理处理(又称记录、结点等又称记录、结点等)。 数据项数据项- 一个数据元素可由若干个数据项组成，一个数据元素可由若干个数据项组成， 是数据的是数据的 （Data Item） 不可分割的不可分割的最小最小单位单位(又称字段等又称字段等)。 三者之间的关

11、系：数据三者之间的关系：数据数据元素数据元素数据项数据项 例：例：学生档案学生档案 个人记录个人记录 姓名、性别、籍贯姓名、性别、籍贯 13 第12页/共26页 数据对象数据对象（Data ObjectData Object）-是性质相同的数据元素的集合，是性质相同的数据元素的集合， 是数据的一个子集。是数据的一个子集。 数据结构数据结构（Data StructureData Structure）-是相互之间存在一种或多种是相互之间存在一种或多种 特定特定关系关系的的数据元素数据元素的集合。的集合。 表示为：表示为： Data_Structure = ( D, S ) 元素有限集元素有限集关系

12、有限集关系有限集 例例1：用数据结构表示一周中的七天。用数据结构表示一周中的七天。 Data_Structure=(D,S),其中，其中， D= S= Mon,Tue, Wen, Thu, Fri, Sat, Sun , 14 第13页/共26页 （1）Data_Structure=(D,S)，其中，其中， D= 01，02，03，04，05 S= （2） S=(D, R) D= a, b, c, d, e, f R= , , , , 解解: 上述表达式可用图形表示为：上述表达式可用图形表示为： aebcfd 例2：将下述表达式用图形的形式表示出来 集合结构 线性结构 15 第14页/共26页

13、 （3） Data_Structure=(D,S),其中，其中， D= 01，02，03，04，05 ，06，07 S=(01,02)，(01,03)，(01,04)，(02,05)，(02,06)，(03,07) （4） S=(D,R) D=di | 1i5, 1j5 R=, ij d1 d2 d3 d4 d5 01 020304 0506 07 树形结构 图状结构 16 第15页/共26页 逻辑结构逻辑结构-数据元素之间的逻辑关系，即结构中定义的数据元素之间的逻辑关系，即结构中定义的“关系关系”。 逻辑结构可细分为逻辑结构可细分为4类：类： 集合结构集合结构 线性结构线性结构 树形结构树形

14、结构 图状结构图状结构 一对一关系一对一关系 一对多关系一对多关系 多对多关系多对多关系 非线性非线性 结构结构 17 第16页/共26页 0100 0101 物理结构物理结构-也称存储结构，是也称存储结构，是数据的逻辑结构在计算机存数据的逻辑结构在计算机存 储器内的表示（映像）。储器内的表示（映像）。 顺序映像顺序映像 非顺序映像非顺序映像 特点是借助元素在存储器中的特点是借助元素在存储器中的相对位置相对位置来表示数来表示数 据元素之间的逻辑关系。据元素之间的逻辑关系。 特点是借助指示元素存储地址的特点是借助指示元素存储地址的指针指针表示数据表示数据 元素之间的逻辑关系。元素之间的逻辑关系。

15、 例：例：复数复数 3.0-2.3i 的存储形式的存储形式 3.0 -2.3 0100 0201 0101 0201 3.0 -2.3 算法的设计取决于选定的数据（逻辑）结算法的设计取决于选定的数据（逻辑）结 构构 算法的实现依赖于采用的存储结构算法的实现依赖于采用的存储结构 -顺序存储结构顺序存储结构 -链式存储结构链式存储结构 18 第17页/共26页 数据类型数据类型-是一个是一个值的集合值的集合和定义在这个值集上的和定义在这个值集上的一组操作一组操作 的总称。的总称。 抽象数据类型抽象数据类型由用户定义，用以表示应用问题的数据模由用户定义，用以表示应用问题的数据模 型。它由基本的数据类

16、型组成，并包含一组相关的操作。型。它由基本的数据类型组成，并包含一组相关的操作。 抽象数据类型抽象数据类型可用可用ADT=（D，S，P）三元组表示三元组表示 数据对象数据对象 D上的关系集上的关系集 D上的操作集上的操作集 ADT 抽象数据类型名 数据对象：数据对象的定义 数据关系：数据关系的定义 基本操作：基本操作的定义 ADT 抽象数据类型名 ADT 常用常用 定义定义 格式格式 19 第18页/共26页 例：例：给出自然数（给出自然数（Natural NumberNatural Number）的抽象数据类型定义。）的抽象数据类型定义。 IsZero(x) : Boolean if (x=

17、0) 返回True else 返回False Add (x, y) : NaturalNumber if (x+y=MaxInt)返回 x+y else 返回MaxInt Subtract (x, y) : NaturalNumber if (x y) 返回 0 else 返回 x - y Equal (x, y) : Boolean if (x=y) 返回True else 返回 False ADT NaturalNumber NaturalNumber 数据对象数据对象: 数据关系数据关系: 数据操作数据操作: 一个整数的有序子集合一个整数的有序子集合,它开始于它开始于0, 结束于机器能表

18、示的最大整数。结束于机器能表示的最大整数。 20 第19页/共26页 一、算法：一、算法： 算法是对特定问题求解步骤的一种描述，它是指令的有算法是对特定问题求解步骤的一种描述，它是指令的有 限序列，其中每一条指令表示一个或多个操作。限序列，其中每一条指令表示一个或多个操作。 二、算法的二、算法的5 5个特性：个特性： 三、算法设计的要求：三、算法设计的要求： 正确性、可读性、健壮性、效率与低存储需求正确性、可读性、健壮性、效率与低存储需求 时间复杂度时间复杂度 空间复杂度空间复杂度 21 第20页/共26页 第21页/共26页 时间复杂度： 一个算法花费的时间与算法中语句的执行次数成正比例，哪

19、一个算法花费的时间与算法中语句的执行次数成正比例，哪 个算法中语句执行次数多，它花费时间就多。个算法中语句执行次数多，它花费时间就多。一个算法中语一个算法中语 句的执行次数称为语句频度或时间频度，记为句的执行次数称为语句频度或时间频度，记为T(n)T(n)。 算法中基本操作重复执行的次数是算法中基本操作重复执行的次数是问题规模问题规模n的某个函数，的某个函数， 算法的时间量度记作算法的时间量度记作 T（n）=O（f（n） 随着问题规模的增大，算法执行时间的增长率和随着问题规模的增大，算法执行时间的增长率和f（n）的增）的增 长率相同，称为长率相同，称为算法的渐近时间复杂度算法的渐近时间复杂度，简称，简称时间复杂度时间复杂度。 23 第22页/共26页 +x;s=0; +x;s=0; for(i=1