作业 考核方式 书面作业：每个单元3-5个题，树、图和查找单元5-10个题。 上机作业：从第三周起每周一次 , 大约14次

Presentation on theme: "作业 考核方式 书面作业：每个单元3-5个题，树、图和查找单元5-10个题。 上机作业：从第三周起每周一次 , 大约14次"— Presentation transcript:

1 作业 考核方式 书面作业：每个单元3-5个题，树、图和查找单元5-10个题。 上机作业：从第三周起每周一次 , 大约14次
总成绩=出勤占5%+书面和上机作业占(25%~30%)+期末考试成绩占(65%~70%)

2 算法与数据结构 Algorithms and Data Structures

3 教 材 数据结构（C语言版） 严蔚敏 吴伟民 编著 清华大学出版社

4 参考书目 1.《数据结构与算法分析》张铭、刘晓丹译 电子工业出版社 2.《数据结构—用面向对象方法与C++描述》 殷人昆著 清华大学出版社
3.《Computer Algorithms – Introduction to Design and Analysis 》Sara baase 高等教育出版社影印 4. 《Data Structures and Algorithms》 Alfred V. Aho 5. 《数据结构》许卓群 著，高等教育出版社 6. 网上阅读材料 7. 《数据结构习题集》 严蔚敏 吴伟民著

5 第一章 概述 1.1 数据结构的发展过程 1.2 什么是数据结构 1.3 数据的逻辑结构 1.4 抽象数据类型 1.5 数据的存储结构
第一章 概述 1.1 数据结构的发展过程 1.2 什么是数据结构 1.3 数据的逻辑结构 1.4 抽象数据类型 1.5 数据的存储结构 1.6 算法与算法分析 1.7 ADT的表示与实现间的问题

6 1.1 数据结构的发展过程 如：弹道计算<v0 ,α, …> 矩阵运算 M1* M2*M3… 函数计算 y=f(x) 方程组求解
1.1 数据结构的发展过程 早期：计算机主要用于数值计算. 如：弹道计算<v0 ,α, …> 矩阵运算 M1* M2*M3… 函数计算 y=f(x) 方程组求解 定积分：

7 定积分：牛顿插值法:

8 1.1 数据结构的发展过程 早期数据的特点: 数据量少，计算比较复杂，当时人们只注重求解方法，并不注重数据的组织 .
1.1 数据结构的发展过程 早期数据的特点: 数据量少，计算比较复杂，当时人们只注重求解方法，并不注重数据的组织 . 在这一阶段,《数据结构》还未形成一门系统的学科，而是零星地分布在程序设计、图论、集合、代数、操作系统和编译原理等课程中。

9 1.1 数据结构的发展过程 中期：70’s-80’s 非数值数据猛增 70’s 80’s 90’s

10 1.1 数据结构的发展过程 非数值数据的特点： 数据量大，计算比较简单，关系复杂,此时人们不得不把注意力集中于分析数据间的关系、数据的组织形式和数据的表示方法。 70年代中期《数据结构》形成了一门课程。 这一阶段，程序设计以数据为中心，数据库技术得到了飞速发展。

11 1.1 数据结构的发展过程 目前：计算机应用领域不断扩大，信息量越来越大, 问题越来越复杂。 如：声音和图象信息处理
1.1 数据结构的发展过程 目前：计算机应用领域不断扩大，信息量越来越大, 问题越来越复杂。 如：声音和图象信息处理 它们的特点是数据量空前庞大 关系异常复杂 不仅要注重求解方法而且要注重数据间的关系, 两者不可偏废一者。

12 1.1 数据结构的发展过程 因此可以说，数据结构是计算机的产物，是计算机 科学中一门综合性的专业基础课.它的研究不仅涉及
1.1 数据结构的发展过程 因此可以说，数据结构是计算机的产物，是计算机 科学中一门综合性的专业基础课.它的研究不仅涉及 到计算机硬件的研究范围，而且和计算机软件的研 究有着密切的关系,它也是os、编译原理、数据库 等课程的基础。

13 课 程 介 绍 算法与数据结构 涉及的领域： 相关的课程 程序设计 操作系统 编译原理 数据库 … 是专业核心课 ！ 数学 代数系统 硬件
数学 代数系统 硬件 存储装置 系统设计 软件 文件系统 数据组织 信息检索 编码理论 算子关系 数据类型 数据表示 数据运算 数据结构 数据存储 机器组织

14 1.2 什么是数据结构 例1.1 6845678是谁的电话？ 太难找了！ 电话号码本1 党政机关 党政机关 党政机关 党政机关 大专院校
1.2 什么是数据结构 例1.1 是谁的电话？ 太难找了！ 电话号码本1 党政机关 党委总机 宣传部 组织部 大专院校 内蒙古大学 校务办公室 计算机学院 党政机关 党委总机 宣传部 组织部 大专院校 内蒙古大学 校务办公室 计算机学院 党政机关 党委总机 宣传部 组织部 大专院校 内蒙古大学 校务办公室 计算机学院 党政机关 党委总机 宣传部 组织部 大专院校 内蒙古大学 校务办公室 计算机学院

15 1.2 什么是数据结构 电话号码结构： 单位=>电话号码

16 6845678是老朋友Tom的电话？ 太容易找了！ 电话号码本2 党政机关 大专院校 党政机关 大专院校 党政机关 大专院校
党委总机 宣传部 组织部 大专院校 内蒙古大学 校务办公室 计算机学院 党政机关 党委总机 宣传部 组织部 大专院校 内蒙古大学 校务办公室 计算机学院 党政机关 党委总机 宣传部 组织部 大专院校 内蒙古大学 校务办公室 计算机学院 110 ……...匪警 119………火警 121………急救 …. ……. ….Tom ……… 按电话号码的大小排列 数据的安排直接影响到工作效率。

17 假设要在n个城市之间建立通信联络网，如何在最节省经费的前提下建立这个通信网?
例1.2 假设要在n个城市之间建立通信联络网，如何在最节省经费的前提下建立这个通信网? 28 1 2 3 4 5 6 7 10 16 14 18 12 25 24 22

18 数据结构的概念: 数据结构研究的对象包括三个方面: 数据的逻辑结构 指数据之间的逻辑关系,即指数据元素之间的关联方式或 邻接关系。
数据的存储结构 指数据在计算机中的存储方式。 运算 定义在该结构上的一组操作， 如输入/读取、检索/查找、插入、删除、更新等。

19 数据结构的基本概念与术语: 数据(Data)： 可被计算机表示、存储和加工处理的所有信息。 数据元素(Data Element)：
数据的基本单位，相对独立，通常作为一个整体看待。 例1.3 学生健康情况登记表如下： 姓 名 学 号 性 别 年龄 健康情况 王小林 790631 男 18 健康 陈 红 790632 女 20 一般 刘建平 790633 21 张立立 790634 17 神经衰弱 …….. ……. 每一行是一个数据元素，每一列是一个数据项，学生数据元素的集合是一个数据对象

20 数据结构的基本概念与术语: 数据项(Data Item)： 组成数据元素的不可分割的最小单位。 如：学号，姓名，年龄…
数据对象(Data Object)： 性质相同的数据元素的集合。 如 整数数据对象：包括{0,+1, +2, +3,…, +n,…,} 字母数据对象：包括{‘A’,’B’,…’Z’,’a’,’b’,…,’z’}

21 数据结构的基本概念与术语: 数据类型(Data Type)： 用于刻划数据对象的类型。 一个值的集合以及定义在该值的集合上的一组操作的总称.
空类型 整型 实型 字符型 枚举型 指针型 基本类型 在C语言中,数据类型 数组型 结构型 共用体 结构类型

22 数据结构（Data Structure)：
数据结构的基本概念与术语: 数据结构（Data Structure)： 数据结构 逻辑结构 存储结构 运算的集合 按某种逻辑关系组织起来的一批数据,按一定的存 储表示方式把它们存储在计算机的存储器中,并在这些 数据上定义了一个运算的集合,就称为一个数据结构. 相互之间存在一种或多种特定关系的数据元素的集合.

23 1.3 数据的逻辑结构(Logical Structure)
根据数据元素间的不同特性, 通常有以下4种基本逻辑结构： 1. 线性结构 逻辑结构 2 . 集合 非线性结构 3. 树形结构 4 . 图型或网状结构 数据元素间的逻辑结构可形式描述为： DS=(D，S) 其中：D 是数据元素的有限集合； 　　　S是 D上的有限关系集合；

24 1.3 数据的逻辑结构(Logical Structure)
线性结构(Linear Structure)：LS=(D, {R}) D={d1,d2,…, dn} R={<di,di+1>| i=1,2,3,…, n-1} 例1.4 DS=(D, {R}) D={d1, d2, d3, d4,d5,d6 ,d7} R={< d1, d2 >, < d2, d3 >, < d3, d4 >, < d4, d5 >, < d5, d6 >, < d6, d7 >} d d d d d d d7 线性结构

25 线性结构 线性结构特点: 一对一的关系 在非空的线性表中: 1)有且仅有一个开始结点d1，它没有直接前趋.
2)有且仅有一个终端结点dn，它没有直接后继. 3)其余的内部结点di(2in-1)都有且仅有一个 直接前趋di-1和一个直接后继di+1。 d d d d d d d7 线性结构

26 集合： 例1.5 DS=(D, {R}) D={d1, d2, d3, d4,d5,d6 ,d7}
d D , d D , d3 D , d D , d D , d D , d D d d d3 d d d6 d7 集合 集合特点： 结构中的数据元素只具有 “同属于一个集合”的关系

27 树形结构 例1.6 DS=(D, S={R}) D={d1, d2, d3, d4 ,d5,d6,d7}
R={< d1, d2 >, < d1, d3 >, < d2, d4 >, < d2, d5 >,< d2, d6 >, < d3, d7 >} 开始结点:无前驱的结点， 如d1 d4 d1 d2 d3 d5 d6 d7 树形结构 终端结点: 无后继的结点， 如d4,d5,d6,d7 树形结构的特点： 结构中的数据元素存在一对多的关系

28 < d2, d3 >, < d3, d5 >, < d4, d5 >}
图型或网状结构 例1.7 DS=(D, {R}) D={d1, d2, d3, d4,d5} R={< d1, d2 >, < d1, d3 >, < d1, d4 >, < d1, d5 >, < d2, d3 >, < d3, d5 >, < d4, d5 >} d1 d2 d3 d4 d5 图型结构 图型结构的特点： 结构中的数据元素存在多对多的关系

29 1.4 抽象数据类型（Abstract Data Type 简称 ADT）
抽象数据类型： (1) 数学模型 (2) 定义在该模型上的一组操作 数据类型和抽象数据类型的区别: 数据类型仅局限于计算机中定义并实现的数据类型,而抽象 数据类型还包括用户在设计软件系统时自己定义的数据类型. 抽象数据类型是 面向对象技术核心概念； 面向对象程序设计的基础（C++,Java, VB,….）; 抽象层次高，模块复用度高； 使用ADT有极大的优势

30 ADT的描述格式： ADT ADT-name { 数据对象: <数据对象定义> 数据关系: <数据关系定义>
数据对象: <数据对象定义> 数据关系: <数据关系定义> 基本操作: <基本操作定义> } ADT ADT-name 基本操作的定义: 基本操作名(参数表) 初始条件:<初始条件描述> 操作结果:<操作结果描述>

31 例1.8 抽象数据类型复数的定义 ADT Complex { 数据对象: D={C1,C2| C1,C2 R}
例1.8 抽象数据类型复数的定义 ADT Complex { 数据对象: D={C1,C2| C1,C2 R} 数据关系: S={< C1,C2 >| C1,C2 D} 基本操作: Create(x,y,&z) 初始条件: 已知两个实数x,y 操作结果: 生成一个复数z=x+iy Add(z1,z2,&sum) 初始条件: 已知两个复数z1=x1+iy1, z2=x2+iy2 操作结果: 得到z1和 z2两个复数的和 sum=(x1 +x2)+i(y1+y2)

32 例1.8 抽象数据类型复数的定义 Subtract (z1,z2,&dif) 初始条件:已知两个复数z1=x1+iy1, z2=x2+iy2
例1.8 抽象数据类型复数的定义 Subtract (z1,z2,&dif) 初始条件:已知两个复数z1=x1+iy1, z2=x2+iy2 操作结果: 得到z1和 z2两个复数的差 dif=(x1 -x2)+i(y1- y2) Multiply(z1,z2,&pro) 操作结果: 得到z1和 z2两个复数的积 pro=(x1. x2 - y1.y2 )+i(x1. y2+ x2 .y1) Get_Realpart(z) 初始条件:已知复数z=x+iy 操作结果: 得到复数z的实部x Get_Imagpart(z) 操作结果: 得到复数z的虚部y }ADT Complex

33 1.5 数据的存储结构（Store Structure）
存储结构: MS=(D，M) 其中: D 是数据元素的有限集合； 　　　 M是存储器的地址集合； D={di| i=1,2,3,…n} M={0,1,2,3,…,n-1} d1 d2 d3 d4 .. dn-1 dn 1 2 3 存储结构 顺序存储结构 链式存储结构 n-1 MS: D M

34 1.5 数据的存储结构（Store Structure）
顺序存储结构（Sequential Structure） 例1.9 LS={D,{R}} D={a,b,c,d,e} R={<a,b>,<b,c>,<c,d>,<d,e>} a b c d e 1024 1025 1026 1027 1028 逻辑结构上相邻的两个元素在物理位置上也相邻 数据元素的存储位置 a b c d e 线性结构

35 数据元素的存储位置 e NULL b a d c 1024 1026 1028 1030 1032 1034 1036 1038 1040 存储空间不一定连续 保持了逻辑关系 LS 链式存储结构（Linked Structure） 例1.10 LS={D,{R}} D={a,b,c,d,e} R={<a,b>,<b,c>,<c,d>,<d,e>} 数据元素 指针 结点（node）：存储一个数据元素及附加信息的存储空间 指针（pointer）：存储地址 不考虑具体地址，抽象为： a b c d e ^ LS

36 1.6 算法与算法分析 算法（Algorithms）: 是对具体问题求解步骤的一种描 述, 是指令的有限序列。 算法有五个特点：
1.6 算法与算法分析 算法（Algorithms）: 是对具体问题求解步骤的一种描 述, 是指令的有限序列。 算法有五个特点： 有穷性：执行有限步骤后终止，每步都在有限时间完成。 确定性：指令有确切含义，无二义性。 可行性：指方法对, 即算法中所描述的操作都是可以通过已经 实现的基本运算执行有限次来完成. 输入： 有0个或多个输入数据。 输出： 至少有1个输出数据。

37 算法分析的目的： 评价算法“好坏”的几个标准： 对算法作出一个客观的评价； 比较算法，选择算法； 改进算法；
通常有以下五个标准，但这不是绝对的。 正确性（Correctness） 时间工作量（Amount of work done） 空间占用量（Amount of space used） 简单性和清晰性（Simplicity, Clarity） 最优性（Optimality）

38 1. 正确性: 对任一个合法的输入，算法结束后得到正确结果。 求解问题方法的正确性 由问题领域的理论和定理保证和证明。 如高斯迭代法，其正确性是由线性代数的理论证明。 程序的正确性 是通过软件测试来定，但测试无法保证程序是绝对正的。

39 2. 时间工作量： 算法的效率越高，工作量就越少，执行时间越短。 我们不能用日常生活中的时间来度量。 它指的是算法的工作量。
在算法中时间的单位指的是算法中的基本运算。 对不同的问题，其求解算法的基本运算是不同的。 例如： 问题 基本运算 在数组中查找元素X 元素比较 两实数矩阵相乘 乘 排序 元素比较,移动 求多项式P(x)的值 加、乘 循环 循环体

40 2. 时间工作量 算法所做工作量也称“时间复杂度（Time Complexity）” 影响算法时间代价的因素:
依赖于输入规模(元素个数),是输入尺寸的函数f(n),用T(n)表示，T(n)=f(n), n是输入尺寸。 如何衡量问题的输入尺寸 ？ 因问题而异 例如： 问题 输入尺寸 在数组中查找元素X 元素个数 两实数矩阵相乘 阶数 排序 元素个数 求多项式P(x)的值 阶数

41 影响算法时间代价的因素: (2) 与算法本身有关: 例 求多项式P(x) =p0+p1x+p2x2+p3x3+…+pnxn的值 算法1 按一般理解，需做 次乘法，n次加法 算法2 P(x) =(…(((pnx+pn-1)x+pn-2)x+pn-3)x+…+p1)x+p0 则只需做n次乘法，n次加法

42 影响算法时间代价的因素: (3) 与输入有关 例如 在查找中,若输入的数据杂乱无章,则在查找中只能从头 到尾顺序比较;若输入的数据已排序,则可采用折半查找, 减少时间. (4) 与机器有关 不作为重要因素 (5) 与设计者有关

43 时间复杂度 最坏情况下时间复杂度（Worst-case Complexity）: Dn 是问题的所有尺寸为n的输入集，
I 是 Dn 的元素， t(I)是算法对输入I 所做工作量 用W(n)=max{t(I)| I属于Dn} 表示 最坏情况下时间复杂度

44 例 在n个数a0,a1,…,an-1中找K。 算法思想：K依次和a0,a1,…,an-1比较，直到找到K或全部比较完. 算法： int seqSearch(int [ ] E, int n, int K) { ans=-1; for (i=0; i<n; i++) if (K==E[i]) { ans=i; break } // return ans; } //end of seqSearch() 基本操作：两元素比较. 最坏情况分析：K在最末尾或无K. W(n)=n

45 时间复杂度 平均情况下时间复杂度（Average Complexity）: Pr(I)是输入I出现的概率, t(I)是算法对输入I所做工作量
则： 表示平均情况下时间复杂度

46 平均情况分析： 例1.12 设K在E中出现的概率是p，则K不在E中出现的概率是（1-p）， 设K在任一位置的概率是相等的（K在E中时）
是：Pr(Ii)=p/n 显然 t(Ii)=i+1 所以： 当p=1时

47 例1.13 两矩阵相乘 算法： Void matMult(A,B,&C,m,n,p) { for (i=0; i<m; i++)
例 两矩阵相乘 算法： Void matMult(A,B,&C,m,n,p) { for (i=0; i<m; i++) for (j=0; j<p; j++) { C[i,j]=0; for (k=0; k<n; k++) C[i,j]+=A[i,k]*B[k,j] } 分析： W(n,m,p)=A(m,n,p)=nmp 我们经常用最坏情况下时间复杂度来描述算法的好坏。

48 3. 空间占用量（Space Used）： 算法执行中占用的存储空间。 通常我们只分析额外的占用空间量 （除了程序和输入占用的之外）
它和T(n) 一样是输入规模n的函数 用S(n)表示 也分最坏情况和平均情况

49 4. 简单性和清晰性（Simplicity, Clarity）
简单的算法 易于验证正确性 易于实现（编写程序） 易于调试、修改 5. 最优性（Optimality）（略）：

50 复杂度的表示： 表示算法的增长率: 分析算法的复杂度是为了比较算法，那么T(n)和 S(n) 精确到什么程度为好？
大O(Big-Oh)

51 算法的描述: 对算法可以在不同的抽象层次上进行描述；
基于数学模型 基于逻辑结构 基于存储结构 描述语言可以是： 自然语言； 形式化语言； 类似高级语言 高级语言； 本课程对算法的描述主要是基于存储 结构这个层次上； 语言采用类C语言，它的特点是： 忽略一些烦琐的语法细节； 表达式用习惯方式书写表达式； 个别时候使用少量的自然语言；

52 1.7 ADT的表示与实现间的问题 1个数学模型可用多个不同的逻辑结构表示； 逻辑结构是对数学模型的实现；
ADT ADTname 数学模型 操作1 操作2 ….. 操作k ADT ADTname 逻辑结构 算法1 算法2 ….. 算法k class ADTname 存储结构 函数1 函数2 ….. 函数k n n 1个数学模型可用多个不同的逻辑结构表示； 逻辑结构是对数学模型的实现； 1个逻辑结构可有多种不同的存储结构； 存储结构是对逻辑结构实现； 算法是基于逻辑结构对操作的实现；

53 函数是基于存储结构对算法的实现，是程序； 逻辑结构直接影响到算法的效率，如例1.1中电话号码簿。
有时存储结构会影响到算法的基本操作及算法的实现，从 而影响到算法的效率。 设计与选择合理相互吻合的 逻辑结构、存储结构与算法 是十分重要的问题，也是我 们学习本课程的目的之一。 110 112 … 按行政机构排列 找 是谁的 按号码大小构排列 逻辑 结构 存储 结构 算法

54 学习《算法与数据结构》的目的 好的 程序 好的解决 问题的方案 支持 设计选择好的数据逻辑结构 设计选择好的数据存储结构 设计选择好的算法
开发 好的 程序

55 本章小结 1、数据结构的定义 2、逻辑结构 3、ADT 4、存储结构以及与逻辑结构的关系 5、算法基本分析技术 6、学习数据结构的目的