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