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