数 据 结 构 与 算 法.

Presentation on theme: "数 据 结 构 与 算 法."— Presentation transcript:

1 数 据 结 构 与 算 法

2

3 数据结构课程的地位 它是计算机专业及相关专业的核心课程之一，是计算机及相关专业的重要骨干基础课程。 它针对非数值计算的程序设计问题，研究计算机的操作对象以及它们之间的关系和操作。即其研究目的是研究有效地组织和处理非数值类型数据的理论、技术和方法。

4 数据结构的核心研究内容 数据的逻辑结构、存储结构及它们之间的关系和相应的基本操作运算的定义和实现。
本书围绕数据结构的三种基本结构：线性结构（第2-5章）、树形结构（第6章）和图形结构（第7章）展开讨论，研究解决如下问题：一个具体问题的逻辑数据结构是什么？适宜选用什么样的存储结构？采用什么样的操作实现算法效率更高？

5 学时数：50（30学时授课＋20学时上机） 学 分： 3 教材：严蔚敏等，数据结构（C语言版），清华大学出版社 参考书： [1]朱战立编著，数据结构（使用C语言）第3版，西 安交通大学出版社 ，2003年 [2] 数据结构学习指导与典型题解，朱战立等编著，西安交通大学出版社 ，2002年

6 内 容 安 排 1 2 6 4 7 3 8 9 5 10 20 章 内 容 学时 绪 论 树和二叉树 线性表 图 栈和队列 排序 串 查找
内 容 学时 1 绪 论 2 6 树和二叉树 4 线性表 7 图 3 栈和队列 8 排序 串 9 查找 5 数组 10 上机（共十次） 20

7 对学生的几点要求 1、上课认真听讲，适当做好笔记，按时交作业。
2、考试成绩分两部分：平时成绩（包括出勤和上机实验）占30%，期末成绩占70%。 3、课后需要多读课文和参考书，上网查看相关内容，在理解基本内容的基础上，多看、多做习题。 4、上机实验十分重要，一定要在上机前做好充分准备，多采用不同的数据存储结构和不同的实现算法解决一个问题。

8 第1章 绪 论 讨论5个问题： 1.1 数据结构的基本概念 1.2 学习数据结构的意义 1.3 数据结构涵盖的主要内容
第1章　绪　论 讨论5个问题： 1.1 数据结构的基本概念 1.2 学习数据结构的意义 1.3 数据结构涵盖的主要内容 1.4 什么是抽象数据类型 1.5 算法效率的度量

9 1.1 数据结构的基本概念 1、举例 建立一个学生档案。学生表包括学号、姓名、性别、籍贯。要求：查找“王红”是否存在。 解决的方法步骤：
1.1 数据结构的基本概念 1、举例 建立一个学生档案。学生表包括学号、姓名、性别、籍贯。要求：查找“王红”是否存在。 解决的方法步骤： 如何记录所有学生记录（及选择何种逻辑数据结构）？ 选择何种存储结构？ 若把所有记录依次存储在一个数组中——采用顺序存储结构 若采用指针链表——采用链式存储结构

10 2、基本术语 (1)数据：所有能被计算机识别、存储和处理的符号的集合（包括数字、字符、声音、图像等信息 ）。
(2)数据元素:是数据的基本单位，具有完整确定的实际意义。在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据项组成。 (3)数据项:构成数据元素的项目。它是数据不可分割的最小单位。 (4)数据类型：指一个类型和定义在这个类型上的操作集合。例：C语言（基本类型：整型、浮点型、字符型等构造类型：数组、结构、联合、指针、枚举等） (5)抽象数据元素：抽象定义的、没有实际含义的数据元素。 (6)抽象数据类型：用户自己定义的数据类型。

11 2、基本术语 (续） (7)数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。或按照一定逻辑关系组织，并按一定存储方法存储的数据的集合，且需要定义一系列运算。逻辑结构、存储结构和运算合称为三要素。表示为： Data_Structure=（D, R） 其中，D—元素有限集，R—关系有限集

12 1.2 学习数据结构的意义 程序设计＝好算法＋好结构 同样的数据对象，用不同的数据结构来表示，运算效率可能有明显的差异。
1.2 学习数据结构的意义 计算机内的数值运算依靠方程式，而非数值运算（如表、树、图等）则要依靠数据结构。 数据结构是一门学科，针对非数值计算的程序设计问题，研究计算机的操作对象以及它们之间的关系和操作等等。 　　同样的数据对象，用不同的数据结构来表示，运算效率可能有明显的差异。 程序设计＝好算法＋好结构

13 1.3 数据结构涵盖的内容

14 解释1： 什么叫数据的逻辑结构？ 逻辑结构可细分为4类：
　　答：指数据元素之间的逻辑关系。即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。 逻辑结构可细分为4类： 集合结构： 仅同属一个集合 线性结构: 一对一（1:1) 树 结 构: 一对多（1:n) 图 结 构: 多对多 (m:n) 线 性 非线性

15 b c a e f d 例：用图形表示下列数据结构，并指出它们是属于线性结构还是非线性结构。 （1） S=(D, R)
　　例：用图形表示下列数据结构，并指出它们是属于线性结构还是非线性结构。 （1） S=(D, R) D={ a, b, c, d, e, f } R={(a,e), (b,c), (c,a), (e,f), (f,d)} 解： 上述表达式可用图形表示为： b c a e f d 此结构为线性的。

16 d1 d5 d2 d4 d3 （2） S=(D, R) D={di | 1≤i≤5} R={(di , dj ), i<j}
解：上述表达式可用图形表示为： d1 d d2 d d3 该结构是非线性的。

17 顺序、链式、索引、散列 解释2：什么叫数据的物理结构？ 例：复数3.0－2.3i 的两种存储方式：
　　　答：物理结构亦称存储结构，是数据的逻辑结构在计算机存储器内的表示（或映像）。它依赖于计算机。 存储结构可分为4大类： 顺序、链式、索引、散列 例：复数3.0－2.3i 的两种存储方式： 法1：地址 内容 法2：地址 内容 0415 0302 3.0 0300 －2.3 －2.3 0302 3.0 0300 2字节

18 插入、删除、修改、查找、排序 解释3：什么是数据的运算？ 答：在数据的逻辑结构上定义的操作算法。 它在数据的存储结构上实现。
最常用的数据运算有 5 种： 插入、删除、修改、查找、排序

19 1.4 什么是抽象数据类型 讨论： 1 数据类型与抽象数据类型的区别？ 2 抽象数据类型如何定义？ 3 抽象数据类型如何表示和实现？

20 1 数据类型与抽象数据类型的区别 数据类型：是一个值的集合和定义在该值上的一组操作的总称。 抽象数据类型：由用户定义，用以表示应用问题的数据模型。它由基本的数据类型构成，并包括一组相关的服务（或称操作） 它与数据类型实质上是一个概念，但其特征是使用与实现分离，实行封装和信息隐蔽（独立于计算机）

21 2 抽象数据类型如何定义 抽象数据类型可以用以下的三元组来表示： ADT = （D，R，P） 数据对象 D上的关系集 D上的操作集
2 抽象数据类型如何定义 抽象数据类型可以用以下的三元组来表示： ADT = （D，R，P） 数据对象 D上的关系集 D上的操作集 ADT抽象数据类型名{ 数据对象：<数据对象的定义> 数据关系：<数据关系的定义> 基本操作 ：<基本操作的定义> } ADT抽象数据类型名 ADT常用定义格式

22 例：给出自然数(Natural Number )的抽象数据类型定义。
ADT Natural_Number is objects: 一个整数的有序子集合，它开始于0，结束于机器能表示的最大整数 (MAX INT) functions: 对于所有的 x, y  Natural_Number； TRUE, FALSE  Boolean； +, -, <, = = ,=等都是可用的服务。 Zero ( )： Natural Number 返回 0 IsZero(x)： Boolean if (x==0) 返回TRUE else 返回 FALSE Add(x, y)： Natural Number if (x+y <= MAX INT)返回 x+y else 返回 MAX INT Subtract(x,y): Natural Number if (x<y)返回0 else 返回x-y Equal(x,y): Boolean if (x== y)返回TRUE else 返回FALSE Successor(x) : Natural Number if (x == MAX INT)返回x else 返回x+1 end Natural_Number

23 抽象数据类型如何表示和实现 抽象数据类型可以通过固有的数据类型（如整型、实型、字符型等）来表示和实现。 （参看课本P28，线性表的抽象数据类型，思考用具体C语言如何实现） 注意：上机时要必须用具体语言实现，如C或C++等

24 1.5 算法效率的度量 讨论： 1 什么是算法？如何评判算法的好坏？ 2 时间复杂度和空间复杂度如何表示？ 3 计算举例

25 1 什么是算法？如何评判一个算法的好坏？ 算法：是对特定问题求解步骤的一种描述，它是指令的有限序列，是一系列输入转换为输出的计算步骤。
1 什么是算法？如何评判一个算法的好坏？ 　　算法：是对特定问题求解步骤的一种描述，它是指令的有限序列，是一系列输入转换为输出的计算步骤。 好的程序设计：好算法＋好结构 算法的基本特性： 有穷性、确定性、可行性、必有输出 算法评价指标： 正确性、可读性、健壮性、高效率与低存储量需求(见课本P20) 常用时间复杂度来衡量 常用空间复杂度来衡量

26 2 时间复杂度和空间复杂度如何表示？ 多项式阶 时间复杂度T(n)按数量级递增顺序为： 注： 1） O（）为渐近符号。
2 时间复杂度和空间复杂度如何表示？ 多项式阶 时间复杂度T(n)按数量级递增顺序为： 复杂度低 复杂度高 注： 1） O（）为渐近符号。 2） 空间复杂度S(n)按数量级递增顺序也与上表类似。

27 渐进符号（O）的定义：当且仅当存在一个正的常数 C，使得对所有的 n  n0 ，有 f(n)  Cg(n)，则： f(n) = O(g(n))
例： 3n+2=O(n) 因为 3n+24n for n2 6*2n+n2=O(2n) 因为6*2n+n2 7*2n for n4

28 算法的时间复杂度由嵌套最深层语句的频度决定
3 计算举例 例：分析以下程序段的时间复杂度。 　　i=1; ① while(i<=n) 　　 i=i*2; ② 解： 该算法的运行时间由程序中所有语句的频度（即该语句重复执行的次数）之和构成。 算法的时间复杂度由嵌套最深层语句的频度决定 分析：显然，语句①的频度是1。设语句2的频度是f(n)，则有： 即f(n)≤log2n，取最大值f(n)=log2n 所以该程序段的时间复杂度T(n)=1+f(n)=1+ log2n= O( log2n)

29 本章小结 数据结构课程—— 数据结构＋算法＝程序，涉及数学、计算机硬件和软件。
数据结构定义——指互相有关联的数据元素的集合，可用data_Structure=(D,R)表示。 数据结构内容——数据的逻辑结构、存储结构和基本运算 。 数据结构描述工具——抽象数据类型和C语言。 算法效率——时间效率和空间效率 。

30 课后作业 一、简答题 1 设有数据逻辑结构为： B=（K，R）；K={K1，K2…Kn};
R={<K1,K3>,<K1,K8>, <K2,K3>, <K2,K4>, <K2,K5>, <K3,K9>, <K5,K6>, <K8,K9>, <K9,K7>, <K4,K7>, <K4,K6>} 画出这个逻辑结构的图示，并确定相对于关系R，哪些结点是开始结点，哪些结点是终端结点

31 2 有下列几种用二元组表示的数据结构，画出它们分别对应的逻辑图形表示，并指出它们分别属于何种结构。
A=（K，R），其中K={a,b,c,d,e,f,g,h}; R={r}，r={<a,b>,<b,c>, <c,d>, <d,e>, <e,f>, <f,g>, <g,h>} B=(K,R),其中K={a,b,c,d,e,f,g,h}; R={r}， r={<d,b>,<d,g>, <d,a>, <b,c>, <g,e>, <g,h>, <e,f>}

32 二、求下列程序段的时间复杂度 (1) for (I=0;I<n;I++) (4) fact(int n) for (j=0;j<m;j++) {if (n<=1) A[I][j]=0; return 1; (2) I=s=0; else While (s<n) return(n*fact(n-1)); { I++; } s+=I; (5) s=0; } for(I=0;I<=n;I++) (3) I=1; for(j=0;j<=n;j++) While (I<=n) for(k=0;k<I+j;k++) I=I*3; s++;