《数据结构》课件第1章 绪论

1、数 据 结 构课程介绍课程名称：数据结构教材：数据结构(C语言版)，严蔚敏 吴伟民 编著，清华大学出版社，2007年4月教学方式：授课（54）+上机实践（18）考核方式：期末闭卷70%，平时成绩30%平时成绩：考勤（10分，每次缺勤扣5分） 作业（10分） 实验（10分）以上三项任一项超过三次未到/交，取消考试资格！问题：课堂、课后、电子邮件参考书籍：算法与数据结构C语言描述(第2版) ，张乃孝 编著，高等教育出版社 ，2006数据结构与算法分析C语言描述(原书第2版)，(美)Mark Allen Weiss著，冯舜玺译，机械工业出版社，2004算法导论(原书第2版)，Thomas H. Co

2、rmen等著，潘金贵等译，机械工业出版社，2006课程结构第一部分：(第1章)基本概念数据结构、逻辑结构、存储结构、抽象数据类型、算法分析等第二部分：(第27章)各种基本类型的数据结构线性表、栈、队列、串、数组、广义表、树、二叉树和图第三部分：(第911章)讨论查找和排序的各种实现方法及其综合分析比较课程结束后：会分析数据结构的特性，能够在应用中选择适当的逻辑结构、存储结构以及算法。能够编写结构清楚、正确、易读、符合软件工程规范的应用程序。第1章 绪论学习要点: 熟悉各名词、术语的含义掌握基本概念，特别是数据的逻辑结构和存储结构之间的关系了解抽象数据类型的定义、表示和实现方法理解算法五个要素的

3、确切含义掌握计算语句频度和估算算法时间复杂度的方法用计算机解决问题的步骤？从具体问题抽象出适当的数学模型设计求解此模型的算法编出程序实现如何编写出一个“好”的程序？必须：分析待处理对象的特征以及它们之间的关系 建立数学模型Niklaus Wirth：Data Structures + Algorithm = Programs处理问题的策略问题的数学模型1.1 什么是数据结构非数值计算问题例1 书目自动检索系统书目文件按书名按作者名按分类号索引表线性表例2 人机对奕问题树.例3 多叉路口交通灯管理问题CEDABABACADBABCBDDADBDCEAEBECED图 数据结构是一门研究非数值计算的

4、程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。数据结构的发展简史及其在计算机科学中所处的地位发展史：“数据结构”作为一门独立的课程在国外是从1968年才开始设立的，1968年美国唐欧克努特教授开创了数据结构的最初体系，他所著的计算机程序设计技巧第一卷基本算法是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。20世纪60年代末到70年代初：Niklaus Wirth公式20世纪70年代中期到80年代初：迅速发展地位：“数据结构”在计算机科学中是一门综合性的专业基础课。数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。数据结构这一门课的内容不仅是一般程序

5、设计（特别是非数值性程序设计）的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序的重要基础。1.2 基本概念和术语数据(Data)： 所有能被输入到计算机中，且能被计算机处理的符号的集合。 是计算机操作的对象的总称。 是计算机处理的信息的某种特定的符号表示形式。数据元素(Data Element)： 是数据(集合)中的一个“个体”。 是数据结构中讨论的基本单位。数据项：是数据结构中讨论的最小单位。 不可再分割 数据元素可以是数据项的集合。例如：描述一本书的书目信息为一个数据元素，可以数据对象(Data Object)： 性质相同的数据元素的集合，数据的一个子集。数据结构(Da

6、ta Structure)： 相互之间存在一种或多种特定关系的数据元素的集合。登录号书名作者名分类号数据元素数据项结构.例4 假设用三个4位的十进制数表示一个含12位数的十进制数。 不同的“关系”构成不同的“结构”数据结构的形式定义：二元组Data_Structure=(D,S)其中，D是数据元素的有限集，S是D上关系的有限集。3214,6587,9345 a1(3214),a2(6587),a3(9345) 则在数据元素 a1、a2 和 a3 之间存在着“次序”关系 a1,a2、a2,a33214，6587，9345 a1 a2 a3 6587，3214，9345 a2 a1 a3 数据结构

7、是相互之间存在着某种逻辑关系的数据元素的集合。逻辑结构集合结构线性结构树形结构图/网状结构例5 linear=(D,R) D=1,2,3,4,5,6,7,8,9,10 R=, ,例6 tree= (D,R) D=a, b, c, d, e, f, g, h, i, j, k, l R=, , ,物理结构(又称存储结构)： 逻辑结构在存储器中的映像。数据元素的映像：用二进制位(bit)的位串表示数据元素。如：数据元素之间关系的映像：顺序映像(顺序存储结构)：以相对的存储位置表示后继关系。非顺序映像(链式存储结构)：借助指针元素存储地址的指针表示数据元素之间的逻辑关系。(321)10 = (501

8、)8 = (101000001)2 A = (101)8 = (001000001)2任何一个算法的设计取决于数据(逻辑)结构，其实现取决于物理结构。数据类型(Data Type)：一个值的集合和定义在这个值集上的一组操作的总称。原子类型：其值不可分解。如C语言中的整型等结构类型：其值由若干成分按某种结构组成，可以分解。如数组、记录等不同类型的变量，其所能取的值的范围不同，所能进行的操作不同。抽象数据类型(Abstract Data Type, ADT)：一个数学模型以及定义在该模型上的一组操作。关键：使用它的人可以只关心它的逻辑特征，不需要了解它的存储方式；定义它的人同样不必要关心它如何存储

9、。因此，抽象数据类型的定义只取决于它的一组逻辑特性，与其在计算机内部如何表示和实现无关！分类：原子类型、固定聚合类型、可变聚合类型形式定义：三元组ADT=(D, S, P) 其中， D是数据对象；S是D上的关系的集合；P是对D的基本操作的集合。基本操作的定义格式为：基本操作名（参数表） 初始条件:初始条件描述 操作结果:操作结果描述两种参数：赋值提供输入值 引用提供输入值、返回操作结果特点：数据抽象：强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口（即外界使用它的方法）。数据封装：将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节。例7 抽象数据类型三元组的定义

10、：ADT Triplet 数据对象：D=e1,e2,e3|e1,e2,e3ElemSet(定义了关系运算的某个集合) 数据关系：R1=, 基本操作： InitTriplet(&T, v1, v2, v3) 操作结果：构造了三元组T, 元素e1,e2和e3分别被赋以参数v1,v2和v3的值。 DestroyTriplet(&T) 操作结果：三元组T被撤销。 Get(T, i, &e) 初始条件：三元组T已经存在，1i3。 操作结果：用e返回T的第i元的值。 Put(&T, i, e) 初始条件：三元组T已经存在， 1i3。 操作结果：改变T的第i元的值为e。 IsAscending(T) 初始条

11、件：三元组已经存在。 操作结果：如果T的3个元素按升序排列，则返回1，否则返回0。 .ADT Triplet数据类型名数据类型名1.3 抽象数据类型的表示与实现抽象数据类型可通过固有数据类型(高级编程语言中已实现的数据类型)来实现。本课程采用类C语言来描述，相关说明见教材P10P11。例8 抽象数据类型Triplet的表示和实现。课后作业1. 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。2. 试仿照三元组的抽象数据类型写出抽象数据类型复数的定义。1.3 算法和算法分析1.3.1 算法定义： 对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个

12、操作。特性：有穷性：一个算法必须在执行有限步骤之后结束确定性：算法的每一步必须是确切定义的,不能产生二义性可行性：算法是能行的输入：一个算法有零个或多个输入输出：一个算法有至少一个输出思考：算法与程序的区别！程序不一定满足有穷性；程序中的指令必须是机器可以执行的，算法中则不一定；算法代表了对问题的解，而程序是算法在机器上的特定实现。算法的描述：自然语言流程图程序设计语言，如C语言伪代码介于自然语言和程序设计语言之间的方法，它采用某一程序设计语言的基本语法，操作指令可以结合自然语言来设计。例9 欧几里德算法辗转相除法求两个自然数m和n的最大公约数。算法描述如下：自然语言： 输入m和n； 求m除以

13、n的余数r； 若r等于0，则n为最大公约数，算法结束；否则执行第步； 将n的值放在m中，将r的值放在n中； 重新执行第步。流程图：N开始输入m和n r=m % nr=0m=n；n=r 输出n结束Y程序设计语言：伪代码： 1. r = m % n; 2. 循环直到r = 0; 2.1 m = n; 2.2 n = r; 2.3 r = m % n; 3. 输出n;#includeint CommonFactor(int m, int n) int r = m % n; while (r!=0) m = n; n = r; r = m % n; return n;算法的评价衡量算法优劣的标准正确性

14、(correctness):满足具体问题的需求可读性(readability)：易读、易理解健壮性(robustness):当输入数据非法时，算法能够做出反应或进行处理效率与低存储量:执行时间短、存储空间小算法效率的度量时间代价：用算法在计算机上运行时消耗的时间来度量。有两种方法：事后统计的方法：利用计算机内部计时功能，进行计时统计。缺陷必须先运行程序；统计的时间依赖于计算机的软硬件环境，容易掩盖算法本身的优劣。事前分析估算的方法假设给定的是一台通用计算机，满足：执行一条基本语句或一个基本运算需花一个单位时间基本语句指：赋值语句、输入语句、输出语句基本运算指：算术运算、一次比较(字符比较、数值

15、比较)做法：从算法中选取一种对于所研究的问题（或算法类型）来说是基本操作的原操作，以该基本操作重复执行的次数作为算法的时间量度。例10-1 两个NN矩阵A和B相乘的算法。 for (i=0;in;i+) for (j=0;jn;j+) cij=0; for (k=0;kn;k+) cij=cij+aik*bkj; 基本操作时间复杂度T(n)：基本操作重复执行的次数是问题规模n的某个函数f(n)，记作T(n)=O(f(n)“O” 标记的形式定义： 若f(n)是正整数n的一个函数，则xnO(f(n)表示存在一个正的常数M，使得当nn0时都满足|xn|M|f(n)|；(换句话就是说，当整型自变量n趋

16、向于无穷大时，两者的比值是一个不等于0的常数。)例10-2 NN矩阵相乘的算法的时间复杂度： 基本操作执行的次数：nnn=n3 T(n)=O(n3)语句的频度：是指该语句重复执行的次数。与该语句包含的基本操作执行的次数相同。渐近时间复杂度例11 分析语句+x; s=0;的频度。解：将“+x”看成是基本操作，则语句频度为，即时间复杂度为(1)；如果将“s=0”也看成是基本操作，则语句频度为，其时间复杂度仍为(1)，即常量阶。例12 分析语句for (i=1; i=n; +i) +x; s+=x;解：语句频度为：2n，其时间复杂度为：T(n)=O(n)。即时间复杂度为线性阶。例13 分析语句for

17、 (i=1; i=n; +i) for (j=1; j=n; +j) +x; s+=x;解：语句频度为：2n2，其时间复杂度为：O(n2)。即时间复杂度为平方阶。总结：语句频度和基本操作重复执行的次数相等，且是关于n的一个精确的函数表达式；时间复杂度仅仅是取上述函数表达式的最高阶，用O进行标记，且没有任何系数！定理：若A(n)=amnm +am-1nm-1 +a1n+a0是一个m次多项式，则A(n)=O(n m)。(证明略)例14 for (i=2; i=n; +i) for (j=2; j= (y + 1)(y + 1) y+;以下六种计算算法时间复杂度的多项式是最常用的。其关系为：O(1)

18、O(logn)O(n)O(nlogn)O(n2)O(n3)指数时间的关系为：O(2n)O(n!)1 & change;-i) change=false; for(j=0;jaj+1) ajaj+1; change=TURE 分析：问题的输入规模：n；基本操作：“交换序列中相邻两个整数”；实例：5 1 9 7 3 2 3 1 2 5 9 7“基本操作”数随n变化的规律：a中序列自小至大有序时，“基本操作”数为0；a中序列自大至小有序时，“基本操作”数为 = =(1+2+3+.+(n-1)=n(n-1)/2算法的时间复杂度：最好情况下的时间复杂度：0最坏情况下的时间复杂度：W(n) =n(n-1)/2平均情况下的时间复杂度： AV(n) = 1/n