01数据结构---绪论

本章为绪论部分,其中包括数据结构的基本概念:数据,数据元素,数据结构;数据的逻辑结构:集合,线状结构,树状结构,图或网状结构;数据的存储结构:顺序存储结构,链接存储结构,索引存储结构,散列存储结构;抽象数据类型;算法定义;算法性能分析与度量,等
展开查看详情

1. 数据结构 东南大学计算机学院 方效林 方效林 本课件借鉴了清华大学殷人昆老师 和哈尔滨工业大学张岩老师的课件

2. 课程说明  课程编号: 09002041  授课学时: 32 学时( 1 至 16 周, 2 学时 / 周)  课程分类:选修  答疑地点:计算机楼 532 ,每周 1 次 ( 周一上午 )  考核形式:  期末笔试 80%+ 平时成绩 20%  期末考试实行开卷方式  作业:  从布置作业起,到下一次课前两天 ( 周日 23:00)  电子版,提交到教务处网站上的课程中心  文件命名 (04012501_ 肖迪 ) ,文件格式 (.pdfpdf 、 .pdfdoc 、 .pdfdocx 、 .pdfjpg)) ,大小 ≤ 500K  联系方式  电话 : 13951855973  Email: xiaolin@seu.pdfedu.pdfcn 2

3. 教材  殷人昆 , 《数据结构——用面向对象方法与 C++ 描述(第 2 版)》 , 清华大学出版社 , 2007  参考书目  金远平,《数据结构 C++ 描述》,清华大学出版 社, 2005  W.pdf Ford and W.pdf Topp, Data Structures with C+ +, 清华大学出版社(影印版) , 1997 3

4. 数据结构的重要性  计算机核心课程  许多课程的基础  考研、找工作须复习的一门课 数据结构 操作系统  编译原理 软件工程 人工智能 图形学 数据库 ●●●●●● 4

5. 第一章 绪论 东南大学计算机学院 方效林 方效林 本课件借鉴了清华大学殷人昆老师 和哈尔滨工业大学张岩老师的课件

6. 本章主要内容  数据结构的基本概念  数据的逻辑结构  数据的存储结构  抽象数据类型  算法定义  算法性能分析与度量 6

7. 数据结构的基本概念  数据  数据元素  数据结构 7

8. 数据结构的基本概念  数据  信息的载体(殷人昆)  信息的一种符号表示(严蔚敏)  描述事物的符号记录(维基)  在计算机科学中,数据指能输入到计算机中并被计 算机程序识别和处理的符号的集合。 8

9. 数据结构的基本概念  数据  数据元素  数据的基本单位。在计算机程序中常作为一个整体 进行考虑和处理。  如学生组成班级,学生是数据元素,班级是学生集 合。 9

10. 数据结构的基本概念  数据  数据元素  数据结构  某一数据元素集合中数据元素之间的关系。  形式化定义: Data_Structure = {D, R}  D 是数据元素的集合;  R 是数据元素之间关系的有限集合。 10

11. 数据的逻辑结构  数据元素及其之间的抽象关系  集合  线状结构  树状结构  图或网状结构 11

12. 数据的逻辑结构  数据元素及其之间的抽象关系  集合  线状结构  树状结构  图或网状结构 12

13. 数据的逻辑结构  数据元素及其之间的抽象关系  集合  线状结构  树状结构  图或网状结构 13

14. 数据的逻辑结构  数据元素及其之间的抽象关系  集合  线状结构  树状结构  图或网状结构 14

15. 数据的逻辑结构  数据元素及其之间的抽象关系  集合  线状结构  树状结构  图或网状结构 图结构 11 7 5 4 17 12 3 6 8 网状结构 15

16. 数据的存储结构  数据及其逻辑结构在计算机中的表示,实质上 是存储器的分配  顺序存储结构  链接存储结构  索引存储结构  散列存储结构 16

17. 数据的存储结构  数据及其逻辑结构在计算机中的表示,实质上 是存储器的分配 存储( bat, cat, ea  顺序存储结构 t)  链接存储结构 起始地址 …  索引存储结构 bat  散列存储结构 cat eat … 17

18. 数据的存储结构  数据及其逻辑结构在计算机中的表示,实质上 是存储器的分配 存储( bat, cat, ea  顺序存储结构 t) cat  链接存储结构 0200 0320  索引存储结构 …  散列存储结构 0256 bat 0200 … 0320 eat ∧ … 18

19. 数据的存储结构  数据及其逻辑结构在计算机中的表示,实质上 是存储器的分配  顺序存储结构  链接存储结构  索引存储结构 文件名 1 地址 文件名 2 地址 文件名 3 地址  散列存储结构 1 2 3 文件 2 ∙∙∙ 文件 3 ∙∙∙ 文件 1 地址 地址 地址 2 3 1 19

20. 数据的存储结构  数据及其逻辑结构在计算机中的表示,实质上 是存储器的分配  顺序存储结构  链接存储结构  索引存储结构 { 100 , 400 , 500 , 800 , 900 }  散列存储结构 hash(key)=key/100 100 400 500 800 900 1 2 3 4 5 6 7 8 9 20

21. 抽象数据类型  数据类型:一组值的集合以及一组相关的操作  基本数据类型  C 语言中 int 、 float 、 double  + 、 - 、 * 、 / 、 % 、 < 、 > 、 <= 、 >= 、 == 、 != 、=  构造数据类型 Typedef struct { double data[100]; int leng)th; } DataList; 21

22. 抽象数据类型  抽象数据类型:由用户定义,表示问题的数据 模型  由其他数据类型组成,并包括一组相关操作 class Circle { // 对象 : 几何圆 float r; // 圆的半径 public: Circle(float r); // 构造函数,创建一个半径为 r 的对象实例 float Circumference( ); // 返回该实例的周长 float Area( ); // 返回该实例的面积 };  三大特征  信息隐藏、数据封装、使用与实现分离 22

23. 抽象数据类型  抽象数据类型三大特征  信息隐藏:把所有数据和操作分为公有和私有,可 减少接口复杂性,从而减少出错机会。  数据封装:把数据和操作封装在一起,从语义上更 加完整。  使用与实现相分离:使用者只能通过接口上的操作 来访问数据,一旦将来修改数据结构,可以使得修 改局部化,提高系统灵活性。 23

24. 抽象数据类型  作业:二维向量的抽象数据类型  数据类型  操作:加、减、点乘、叉乘 24

25. 算法定义  是对特定问题求解步骤的一种描述,是指令的 有限序列。  算法五大特性  输入:有 0 个或多个输入  输出:有 1 个或多个输出  有限性:算法有限步结束,指令有限时间完成  确定性:每条指令有确切含义  可行性:每个运算可由计算机有限条指令完成 25

26. 算法定义  算法举例  “ 百钱买百鸡”问题:公鸡每只 5 钱,母鸡每只 3 钱,小鸡 3 只 1 钱, 100 钱买 100 只鸡,问各种 鸡可买多少只 ?  令公鸡母鸡小鸡分别为 x,y,z 只 例: for(x=0;x<=100;x++) { for(y=0;y<=100;y++) { for(z=0;z<=100;z++) { if(x+y+z==100 && 5*x+3*y+z/3==100 && z%3==0) { printf(“%d,%d,%d”,x,y,z); } } } 26

27. 算法定义  算法举例  欧几里德算法——辗转相除法求两个自然数 m 和 n 的最大公约数 输入 : m,n 输出 : m 和 n 的最大公约 数 r = m % n; 循环直到 r 等于 0 { m = n; n = r; r = m % n; } 27

28. 算法性能分析与度量 time (&start);  算法效率的评价方法: alg)orithm(); time (&stop);  事后统计 runTime = stop - start;  将算法实现,统计其时间和空间开销  事前分析  对算法所消耗时间和空间资源的一种估算方法  算法效率的分析  时间复杂度  空间复杂度 28

29. 算法性能分析与度量  算法的时间复杂度 算法的运行时间 = 每条语句执行时间之和 每条语句执行次数之和 执行次数 × 执行一次的时间 基本语句执行次数 指令系统、代码质量有关 例: for(i=0;i<n;i++) { for(j=0;j<n;j++) { c[i][j]=0; for(k=0;k<n;k++) { c[i][j]=c[i][j]+a[i][k]*b[k][j]; } } } 29