大学计算机重要课程第一章绪论.ppt

数 据 结 构,计算机工程学院 郑如滨 网络教研室 407QQ:398620541,课程介绍,课程名称：数据结构 教材：数据结构(C语言版)，严蔚敏 吴伟民 编著，清华大学出版社，2007年4月 教学方式：授课（54）+上机实践（18） 32 datastructure datastructure,课程考核方式,考核方式：期末闭卷60%，平时成绩40%。 平时成绩组成： 考勤: 缺勤1/3直接取消考试资格。请假需课前提前通知教师（电话或假条的方式）。无故未到一次，扣10%。 作业 ： 未交一次，扣10%。 未认真完成作业，敷衍交作业，一次10% 抄袭作业，一次20% 绝对禁止上课前，写本课程的作业。 实验：平时+最终的实验报告，以平时课堂上检查为主。完成情况良好，可加分。 平时表现：课堂回答问题、作业完成情况等、好的问题均可加分。 加分项可部分与扣分项相抵 问题：课堂、课后、电子邮件,参考书籍,编程类： 高质量C+编程 专解疑难杂症 算法类： 算法导论(建议：仅供查询) 程序员实用算法 代码较详细，对很多数据结构有详细的实现代码 Andrew Binstock、John Rex、陈宗斌 机械工业出版社 (建议：仅供查询),参考书籍(深入)： 算法与数据结构，傅清祥 王晓东 编著，电子工业出版社，2001 数据结构与算法分析C语言描述M，（美）Mike Allen Weiss著，机械工业出版社，2004 算法导论(第二版)，Thomas H. Cormen等著，高等教育出版社，2002,注意事项：今天回去的作业，自己复习,C+语言基础，尤其是指针部分最为重要，还有结构体、引用部分。c语言教科书：错误调试 常见问题：=与=，引用参数&(c+中的)的使用。 上交的作业应包含几部分内容： 班级，学号，姓名 作业不清楚的地方及时提问，善用baidu等搜索引擎 本课件内快速查找信息请按：CTRL+F 建议每个同学申请网络存储空间，如：金山快盘。用于存储自己的常用代码与文档,学习委员职责,1.收作业，按学号排序。统计未缴同学名单。 2.汇总同学的问题与意见，提交给老师。,课程结构,第一部分：(第1章) 基本概念数据结构、逻辑结构、存储结构、抽象数据类型 第二部分：(第27章) 各种基本类型的数据结构线性表、栈、队列、串、数组、广义表、树、二叉树和图 第三部分：(第911章) 讨论查找和排序的各种实现方法及其综合分析比较,学完该课程后应该掌握的能力,1.手写代码或者伪代码的能力。 2.利用伪代码或者自然语言描述自己想法的能力 3.熟练掌握基本数据结构的特性，并能利用基本数据结构思考问题、解决问题。 4.了解基本算法,第1章 绪论,学习要点: 熟悉各名词、术语的含义 掌握基本概念，特别是数据的逻辑结构和存储结构之间的关系 了解抽象数据类型的定义、表示和实现方法 理解算法五个要素的确切含义 掌握计算语句频度和估算算法时间复杂度的方法,用计算机解决问题的步骤？ 从具体问题抽象出适当的数学模型 设计求解此模型的算法 编出程序实现 如何编写出一个“好”的程序？ 必须：分析待处理对象的特征以及它们之间的关系 建立数学模型 Niklaus Wirth： Data Structures + Algorithm = Programs,处理问题的策略,问题的数学模型,1.1 什么是数据结构,非数值计算问题 例1 书目自动检索系统,书目文件,例2 人机对奕问题,例3 多叉路口交通灯管理问题,数据结构是一门研究非数值计算的程序设计问题中计算机 的操作对象以及它们之间的关系和操作等等的学科。,数据结构的发展简史及其在计算机科学中所处的地位 “数据结构”作为一门独立的课程在国外是从1968年才开始设立的，1968年美国唐欧克努特教授开创了数据结构的最初体系，他所著的计算机程序设计技巧第一卷基本算法是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。 20世纪60年代末到70年代初：程序设计的实质是选择一种好的结构，加上设计一种好的算法(DS+Algorithm) 20世纪70年代中期到80年代初：迅速发展 地位： “数据结构”在计算机科学中是一门综合性的专业基础课。 数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。 数据结构这一门课的内容不仅是一般程序设计（特别是非数值性程序设计）的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序的重要基础。,1.2 基本概念和术语,数据(Data)：P4 所有能被输入到计算机中，且能被计算机处理的符号的集合。 是计算机操作的对象的总称。 是计算机处理的信息的某种特定的符号表示形式。 数据元素(Data Element)： 是数据（集合）中的一个“个体”。 是数据结构中讨论的基本单位。 数据项：是数据结构中讨论的最小单位。 不可再分割,数据元素可以是数据项的集合。 例如：描述一本书的书目信息为一个数据元素，可以 数据对象(Data Object)： 性质相同的数据元素的集合。如，整数 数据结构(Data Structure)：P5 相互之间存在一种或多种特定关系的数据元素的集合。,数据元素,数据项,结构,.,例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,a3,3214，6587，9345 a1 a2 a3,6587，3214，9345 a2 a1 a3,数据结构是相互之间存在着某种逻辑关系的数据元素的集合。逻辑结构 集合结构 线性结构 树形结构 图/网状结构,例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)的位串表示数据元素。如： 数据元素之间关系的映像：P6 图 顺序映像(顺序存储结构)：以相对的存储位置表示后继关系。 非顺序映像(链式存储结构)：借助指针元素存储地址的指针表示数据元素之间的逻辑关系。,(321)10 = (501)8 = (101000001)2,A = (101)8 = (001000001)2,数据类型(Data Type)：一个值的集合和定义在这个值集上的一组操作的总称。如，整型变量. 原子类型：其值不可分解。如C语言中的整型等 结构类型：其值由若干成分按某种结构组成，可以分解。如数组等 不同类型的变量，其所能取的值的范围不同，所能进行的操作不同。 抽象数据类型(Abstract Data Type, ADT)：一个数学模型以及定义在该模型上的一组操作。 关键：使用它的人可以只关心它的逻辑特征，不需要了解它的存储方式；定义它的人同样不必要关心它如何存储。,分类：原子类型、固定聚合类型、可变聚合类型 p8 形式定义：三元组 ADT=(D, S, P) 其中， D是数据对象；S是D上的关系的集合；P是对D的基本操作的集合。P9 基本操作的定义格式为：基本操作名（参数表） 初始条件:初始条件描述 操作结果:操作结果描述 两种参数：赋值提供输入值 引用提供输入值、返回操作结果 特点： 数据抽象：强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口（即外界使用它的方法）。 数据封装：将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节。,1.3 抽象数据类型的表示与实现,抽象数据类型需要通过固有数据类型(高级编程语言中已实现的数据类型)来实现。 本书相关说明见教材P10P11，简介。,课后作业,0. 用自己的一句话说明白数据结构是什么？并列举三个例子说明ppt上面的三种数据结构分别帮我们解决了什么问题（不少于100字） 1.查询资料，分别说出： typedef的用法，并举出一例子 struct结构体的用法，并举出一例子 &引用类型参数(c+)的用法，并举出一例子 指向结构体的指针的用法，并举出一例子 指向函数的指针的用法，并举出一例子 背面还有,课后作业,2. 试仿照三元组的抽象数据类型(p12)写出抽象数据类型复数(内有加法与减法操作)的定义。 并尝试编写测试程序，可上机进行运行。(加分),1.3 算法和算法分析,1.3.1 算法 定义： 对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。 特性： 有穷性：一个算法必须在执行有限步骤之后结束 确定性：算法的每一步必须是确切定义的,不能产生二义性 可行性：算法是能行的 输入：一个算法有零个或多个输入 输出：一个算法有至少一个输出,注意：算法与程序的区别！,算法的描述： 自然语言 流程图 程序设计语言，如C语言 伪代码介于自然语言和程序设计语言之间的方法，它采用某一程序设计语言的基本语法，操作指令可以结合自然语言来设计。 例7 欧几里德算法辗转相除法求两个自然数m和n的最大公约数。 算法描述如下：,自然语言： 输入m和n； 求m除以n的余数r； 若r等于0，则n为最大公约数，算法结束；否则执行第步； 将n的值放在m中，将r的值放在n中； 重新执行第步。 流程图：,程序设计语言： 伪代码： 1. r = m % n; 2. 循环直到r = 0; 2.1 m = n; 2.2 n = r; 2.3 r = m % n; 3. 输出n;,#include int CommonFactor(int m, int n) int r = m % n; while (r!=0) m = n; n = r; r = m % n; return n; ,算法的评价衡量算法优劣的标准 正确性(correctness): 满足具体问题的需求 可读性(readability)： 易读、易理解 健壮性(robustness): 当输入数据非法时，算法能够做出反应或进行处理 效率与低存储量: 执行时间短、存储空间小,算法效率的度量,算法效率的度量 时间代价：算法在计算机上运行时消耗的时间来度量。有两种方法： 事后统计的方法：利用计算机内部计时功能，进行计时统计。 缺陷必须先运行程序；统计的时间依赖于计算机的软硬件环境，容易掩盖算法本身的优劣。,事前分析估算的方法 假设给定的是一台通用计算机，满足： 执行一条基本语句或一个基本运算需花一个单位时间 基本语句指：赋值语句、输入语句、输出语句 基本运算指：算术运算、一次比较（字符比较、数值比较） 做法：从算法中选取一种对于所研究的问题（或算法类型）来说是基本操作的原操作，以该基本操作重复执行的次数作为算法的时间量度。 例8-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; ,基本操作,时间复杂度：基本操作重复执行的次数是问题规模n的某个函数，记作 T(n)=O(f(n) “O” 标记的形式定义： 若f(n)是正整数n的一个函数，则xnO(f(n)表示存 在一个正的常数M，使得当nn0时都满足|xn|M|f(n)|； (换句话就是说，这当整型自变量n趋向于无穷大时，两者的比值是一个不等于0的常数。) 例8-2 NN矩阵相乘的算法的时间复杂度： 基本操作执行的次数：nnn=n3 T(n)=O(n3) 语句的频度：是指该语句重复执行的次数。与该语句包含的基本操作执行的次数相同。,例8 分析语句+x; s=0;的频度。 解：将“+x”看成是基本操作，则语句频度为，即时间复杂度为(1)；如果将“s=0”也看成是基本操作，则语句频度为，其时间复杂度仍为(1)，即常量阶。 例9 分析语句for (i=1; i=n; +i) +x; s+=x; 解：语句频度为：2n，其时间复杂度为：T(n)=O(n)。即时间复杂度为线性阶。 例10 分析语句for (i=1; i=n; +i) for (j=1; j=n; +j) +x; s+=x; 解：语句频度为：2n2，其时间复杂度为：O(n2)。即时间复杂度为平方阶。,定理：若A(n)=amnm +am-1nm-1 +a1n+a0是一个m次多项式，则A(n)=O(n m)。(证明略) 例11 for (i=2; i= (y + 1)(y + 1) y+;,以下六种计算算法时间复杂度的多项式是最常用的。其关系为： O(1)O(logn)O(n)O(nlogn)O(n2)O(n3) 指数时间的关系为： O(2n)O(n!)O(nn) 分析算法时间复杂性方法： 分析并确定：算法的哪些参数决定算法的“输入规模”？ 明确：被分析算法的“基本操作”是什么？ 算法分析的目标：考察算法的“基本操作”数，随“问题规模”而变化的规律。 算法时间复杂度的渐进表示。,算法的最坏情况下的复杂度 设：I是问题规模为n的所有输入的集合，iI是问题的一个输入实例。ti(n)是输入i下，算法A的“关键操作”数。则，算法A的最坏情况复杂度： WA(n) = 平均复杂度 设：I是问题规模为n的所有输入的集合， iI是问题的一个输入实例。ti(n)是输入i下，算法A的“关键操作”数。Pi(n)是输入i出现在I中的概率。则，算法A的平均时间复杂度： AVA(n) = (Pi(n)ti(n) iI,例12 冒泡排序算法。 Void bubble-sort(int a, int n) for(i=n-1;change=TURE;i1 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)* 0+1+2+.+n(n-1)/2=O(n2),总结： 确定算法问题规模； 找出基本操作； 分析基本操作是否只依赖于问题规模？ 是，就直接建立基本操作执行次数的求和表达式，并求解、用渐进符号表示； 否则，分别对该算法的最好、最坏和平均情况的时间复杂度进行分析。 算法的存储空间代价 一个算法的空间效率是指在算法的执行过程中，所占据的辅助空间数量。 空间复杂度：算法所需存储空间的度量，记作 S(n)=O(f(n) 其中，n为问题的规模。,本章小结,本章主要介绍了如下一些基本概念： 数据 数据元素 数据对象 物理结构 数据类型 抽象数据类型 算法的概念、特性以及描述 算法的分析,课后作业,1.设n为正整数，试确定下列各程序段中前置以记号的语句的频度。 (1)i=1; k=0; while (ij) j+; else i+;,2.假设n为2的乘幂，并且n