《数据结构 .ppt》由会员分享，可在线阅读，更多相关《数据结构 .ppt（39页珍藏版）》请在三一文库上搜索。
1、数据结构,课程说明,课程编号：09002041 授课学时：32学时（1至16周，2学时/周） 课程分类：选修 答疑地点：计算机楼532，每周1次(周一上午) 考核形式： 期末笔试80%+平时成绩20% 期末考试实行开卷方式 作业： 从布置作业起，到下一次课前两天(周日23:00) 电子版，提交到教务处网站上的课程中心 文件命名(04012501_肖迪)，文件格式(.pdf、.doc、.docx、.jpg)，大小500K 联系方式 电话: 13951855973 Email: ,2,教材,殷人昆,数据结构用面向对象方法与C+描述（第2版）, 清华大学出版社, 2007 参考书目 金远平，数据结构
2、C+描述，清华大学出版社，2005 W. Ford and W. Topp, Data Structures with C+, 清华大学出版社（影印版）, 1997,3,数据结构的重要性,计算机核心课程 许多课程的基础 考研、找工作须复习的一门课,4,第一章 绪论,东南大学计算机学院 方效林,本课件借鉴了清华大学殷人昆老师 和哈尔滨工业大学张岩老师的课件,本章主要内容,数据结构的基本概念 数据的逻辑结构 数据的存储结构 抽象数据类型 算法定义 算法性能分析与度量,6,数据结构的基本概念,数据 数据元素 数据结构,7,数据结构的基本概念,数据 信息的载体（殷人昆） 信息的一种符号表示（严蔚敏）
3、描述事物的符号记录（维基） 在计算机科学中，数据指能输入到计算机中并被计算机程序识别和处理的符号的集合。,8,数据结构的基本概念,数据 数据元素 数据的基本单位。在计算机程序中常作为一个整体进行考虑和处理。 如学生组成班级，学生是数据元素，班级是学生集合。,9,数据结构的基本概念,数据 数据元素 数据结构 某一数据元素集合中数据元素之间的关系。 形式化定义：Data_Structure = D, R D 是数据元素的集合； R 是数据元素之间关系的有限集合。,10,数据的逻辑结构,数据元素及其之间的抽象关系 集合 线状结构 树状结构 图或网状结构,11,数据的逻辑结构,数据元素及其之间的抽象关
4、系 集合 线状结构 树状结构 图或网状结构,12,数据的逻辑结构,数据元素及其之间的抽象关系 集合 线状结构 树状结构 图或网状结构,13,数据的逻辑结构,数据元素及其之间的抽象关系 集合 线状结构 树状结构 图或网状结构,14,数据的逻辑结构,数据元素及其之间的抽象关系 集合 线状结构 树状结构 图或网状结构,15,图结构,网状结构,数据的存储结构,数据及其逻辑结构在计算机中的表示，实质上是存储器的分配 顺序存储结构 链接存储结构 索引存储结构 散列存储结构,16,数据的存储结构,数据及其逻辑结构在计算机中的表示，实质上是存储器的分配 顺序存储结构 链接存储结构 索引存储结构 散列存储结构,
5、17,存储（bat, cat, eat）,bat,cat,eat,数据的存储结构,数据及其逻辑结构在计算机中的表示，实质上是存储器的分配 顺序存储结构 链接存储结构 索引存储结构 散列存储结构,18,存储（bat, cat, eat）,0320,0200,0256,数据的存储结构,数据及其逻辑结构在计算机中的表示，实质上是存储器的分配 顺序存储结构 链接存储结构 索引存储结构 散列存储结构,19,文件2,文件3,文件1,地址2,地址3,地址1,数据的存储结构,数据及其逻辑结构在计算机中的表示，实质上是存储器的分配 顺序存储结构 链接存储结构 索引存储结构 散列存储结构,20,100，400，5
6、00，800，900,1,2,9,8,3,4,5,6,7,100,400,500,800,900,hash(key)=key/100,抽象数据类型,数据类型：一组值的集合以及一组相关的操作 基本数据类型 C语言中int、float、double +、-、*、/、%、=、=、!=、= 构造数据类型,21,Typedef struct double data100; int length; DataList;,抽象数据类型,抽象数据类型：由用户定义，表示问题的数据模型 由其他数据类型组成，并包括一组相关操作 三大特征 信息隐藏、数据封装、使用与实现分离,22,class Circle / 对象:
7、几何圆 float r; / 圆的半径 public: Circle(float r); / 构造函数，创建一个半径为r的对象实例 float Circumference( ); / 返回该实例的周长 float Area( ); / 返回该实例的面积 ;,抽象数据类型,抽象数据类型三大特征 信息隐藏：把所有数据和操作分为公有和私有，可减少接口复杂性，从而减少出错机会。 数据封装：把数据和操作封装在一起，从语义上更加完整。 使用与实现相分离：使用者只能通过接口上的操作来访问数据，一旦将来修改数据结构，可以使得修改局部化，提高系统灵活性。,23,抽象数据类型,作业：二维向量的抽象数据类型 数据类
8、型 操作：加、减、点乘、叉乘,24,算法定义,是对特定问题求解步骤的一种描述，是指令的有限序列。 算法五大特性 输入：有0个或多个输入 输出：有1个或多个输出 有限性：算法有限步结束，指令有限时间完成 确定性：每条指令有确切含义 可行性：每个运算可由计算机有限条指令完成,25,算法定义,算法举例 “百钱买百鸡”问题：公鸡每只5钱，母鸡每只3钱，小鸡3只1钱，100钱买100只鸡，问各种鸡可买多少只? 令公鸡母鸡小鸡分别为x,y,z只,26,例：for(x=0;x=100;x+) for(y=0;y=100;y+) for(z=0;z=100;z+) if(x+y+z=100 ,算法定义,算法举
9、例 欧几里德算法辗转相除法求两个自然数m和n的最大公约数,27,输入: m,n 输出: m和n的最大公约数 r = m % n; 循环直到r等于0 m = n; n = r; r = m % n; 输出n,算法性能分析与度量,算法效率的评价方法： 事后统计 将算法实现，统计其时间和空间开销 事前分析 对算法所消耗时间和空间资源的一种估算方法 算法效率的分析 时间复杂度 空间复杂度,28,time (,算法性能分析与度量,算法的时间复杂度,29,算法的运行时间 = 每条语句执行时间之和,例：for(i=0;in;i+) for(j=0;jn;j+) cij=0; for(k=0;kn;k+) c
10、ij=cij+aik*bkj; ,算法性能分析与度量,算法的时间复杂度 算法的运行时间可表示为基本语句执行次数，它是问题规模的一个函数 称这个函数的渐进阶为算法的时间复杂度,30,问题规模：n 基本语句：cij=0 cij=cij+aik*bkj 时间复杂度: O(n3),例：for(i=0;in;i+) for(j=0;jn;j+) cij=0; for(k=0;kn;k+) cij=cij+aik*bkj; ,算法性能分析与度量,算法的时间复杂度 大O表示法：若存在两个正的常数c和n0，对于任意nn0，都有T(n) cf(n)，则称T(n)=O(f(n),31,表示当问题规模充分大时 在渐
11、进意义下的阶,算法性能分析与度量,算法的时间复杂度 大O表示法：若存在两个正的常数c和n0，对于任意nn0，都有T(n) cf(n)，则称T(n)=O(f(n) 例1：T(n) = 3n+2 当n2时，3n+2 3n+n = 4n 因此T(n)=O(n),32,算法性能分析与度量,算法的时间复杂度 大O表示法：若存在两个正的常数c和n0，对于任意nn0，都有T(n) cf(n)，则称T(n)=O(f(n) 例2：T(n) = 10n2+4n+2 当n2时，10n2+4n+2 10n2+5n 又有当n5时，10n2+5n 10n2+n2 = 11n2 因此T(n)=O(n2),33,算法性能分析
12、与度量,算法的时间复杂度 大O表示法：若存在两个正的常数c和n0，对于任意nn0，都有T(n) cf(n)，则称T(n)=O(f(n) 作业：求解T(n) = amnm+am-1nm-1+ a2n2+a1n+a0，并给出证明过程,34,算法性能分析与度量,算法的时间复杂度 T(n)=O(f(n) 若存在两个正的常数c和n0，对于任意nn0，都有T(n) cf(n)，则称T(n)=O(f(n) 给出算法复杂度的上界，不可能比c*f(n)更大 例：T(n) = 6*2n+n2 当n4时，6*2n+n2 6*2n+2n = 7*2n 因此T(n)=O(2n),35,算法性能分析与度量,算法的时间复杂
13、度 T(n)=(f(n) 若存在c 0，和正整数n01，使得当nn0时，有T(n)c*f(n)成立。 给出算法复杂度的下界，不可能比c*f(n)更小 例： T(n)=3n3+2n2，取c=3，n0=1，f(n)=n3，则当 nn0(=1)时，有3n3+2n23n3，T(n)=(n3),36,算法性能分析与度量,算法的时间复杂度 T(n)=(f(n) 若存在c1,c20，和正整数n01，使得当nn0时，总有 T(n)c1*f(n)且T(n)c2*f(n)成立，即T(n)=O(f(n)与T(n)=(f(n)都成立。 给出了算法时间复杂度的上界和下界 e.g.T(n)= 3n3+2n2，c1=5，取c2=3，n0=1，f(n)=n3，则当nn0(=1)时，有3n3+2n25n3及3n3+2n23n3（无穷多个），T(n)= (n3),37,算法性能分析与度量,算法的时间复杂度 常见的时间复杂度 (1)(log2n) (n) (nlog2n) (n2) (n3) (2n) (n!),38,算法性能分析与度量,算法的空间复杂度 指算法在执行过程中所需最大存储空间 空间复杂性的渐进分析,39,S(n)=O(f(n),O(log2n) ?= O(log3n) O(2n) ?= O(3n),