数据结构 DATA STRUCTURE.

Presentation on theme: "数据结构 DATA STRUCTURE."— Presentation transcript:

1 数据结构 DATA STRUCTURE

2 课程基本情况与要求 课程属性：必修； 学时：总学时64，讲课46，上机18；
上机：双周二晚7:00~9:00，实验楼， 数学101，信计102； 三人一组，每组完成一份实验报告； 实验报告：上机时交电子版和打印版； 成绩组成：平时上机30分，上机考试20分， 期末笔试50分； 课堂纪律：人所共知 研究作业：分组查文献，写综述。

3 第一章 绪论 1 数据结构讨论的范畴 2 数据结构的基本概念 3 数据类型和抽象数据类型 4 C语言的数据类型 5
第一章 绪论 1 数据结构讨论的范畴 2 数据结构的基本概念 3 数据类型和抽象数据类型 4 C语言的数据类型 5 算法设计目标和算法效率度量

4 数据结构也称信息结构，是一门随着计算机科学的发展而逐渐形成的学科，目前也成为计算机类各专业的基础课、核心课之一。
40年代，计算机所能处理的数据非常简单，只有0、1组成的二进制数； 50年代到60年代中期，各种高级语言纷纷出现，所能描述的数据类型也逐渐繁多； 如FORTRAN语言中允许复数类型的量，用两个有序的实数<x,y>表示一个复数，这已有点“结构”的雏形了；BASIC等语言中出现了数组；当计算机应用领域有数值计算扩充到非数值计算后，各种新的结构因运而生，其中最重要的是COBOL等语言出现的记录类型，

5 60年代中期以后，在数据结构发展史上发生了几个重要的事件。首先，美国计算机界出现了信息结构这一名称；1968年，美国计算机协会颁发了建设性的计算机教学计划，其中规定《数据结构》作为独立的一门课，这在世界上还是第一次；同年，世界著名的计算机科学家D.E.Knuth教授的巨著《计算机程序设计的技巧》，第一卷《基本算法》出版，系统地论述了数据的逻辑结构和存储结构，并且给出了各种典型的算法。它把许多不同类型的数据组合起来构成一个新的类型。

6 从60年代到70年代初，出现了大型的程序和大规模的文件系统，结构程序设计成为程序设计方法学的主要内容。
人们对数据结构越来越重视，认为程序设计的实质就是要对处理的问题选择一种好的数据结构，同时在此结构上施加一种好的算法；著名计算机科学家N.Wirth写的 《算法+数据结构=程序》 一书正是体现了这种观点。

7 1.1 数据结构讨论的范畴 Niklaus Wirth： 程序设计:为计算机处理问题编制一组指令集
1.1 数据结构讨论的范畴 概括地说： 数据结构是一门讨论“描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现”的学科。 Niklaus Wirth： Algorithm + Data Structures = Programs 程序设计:为计算机处理问题编制一组指令集 算 法:处理问题的策略 数据结构:问题的数学模型

8 数据结构研究的主要内容： 研究数据结构目的：
1、数据的逻辑结构 2、数据的存储结构 3、对各种数据结构进行的运算 研究数据结构目的： 1、提高数据处理的速度 2、尽量节省在数据处理过程中所 占用的计算机存储空间

9 第一章 绪论 1 数据结构讨论的范畴 2 数据结构的基本概念 3 数据类型和抽象数据类型 4 C语言的数据类型 5
第一章 绪论 1 数据结构讨论的范畴 2 数据结构的基本概念 3 数据类型和抽象数据类型 4 C语言的数据类型 5 算法设计目标和算法效率度量

10 1.2 数据结构的基本概念 数据：数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合。
1.2 数据结构的基本概念 数据：数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合。 数值性数据 非数值性数据 数据对象：数据的子集。具有相同性质的数据成员（数据元素）的集合。 整数数据对象 N = { 0, 1, 2, … } 学生数据对象:初等项（不可分割）、组合项（可再划分）

11 数据元素：是数据的最小单位，有时一个数据元素由数据项组成（具有独立含义的最小标识单位）
数据类型：具有相同性质的计算机数据集合及在这个集合上的一组操作。 数据结构：由某一数据对象及该对象中所有数据成员之间的关系组成。记为： Data_Structure = {D, R} 其中，D是某一数据对象，R是该对象中所有数据成员之间的关系的有限集合。

12 数据的逻辑结构： 对数据元素之间的逻辑关系的描述 只抽象地反映数据元素之间的逻辑关系， 与计算机中的存储无关 分为线性结构和非线性结构
两个要素： 数据元素的集合，通常记为D； 数据关系的集合，通常记为R

13 数据的存储结构或物理结构 数据的逻辑结构在计算机存储空间中的存放形式 常用的存储结构： 顺序存储 链式存储 索引存储 散列存储
一种数据结构可根据需要采用不同的存储结构。采用不同的存储结构，其数据处理的效率是不同

14 “学生”表格

15 “课程”表格

16 线性结构中各数据成员之间的线性关系: 有直接前驱和直接后继(除最前、最后一个元素)
例：电话号码查询问题 方法1：顺序存储，顺序查找

17 方法2：有序顺序存储，二分查找 姓名 地址 李1 李2 …… 张1 张2 王1 王2

18 方法3：部分有序，建立索引表 姓名 地址 李1 李2 …… 张1 张2 王1 王2 姓 地址 李 张 ……

19 非线性结构中各数据成员之间的没有线性关系: 前驱和后继可能多于一个
非线性结构中各数据成员之间的没有线性关系: 前驱和后继可能多于一个 选课单包含如下信息 学 号 课程编号 成 绩 时 间 学生选课系统中实体构成的网状关系

20 文件系统的系统结构图

21 树形结构 树 二叉树 二叉搜索树

22 堆结构 “最大”堆 “最小”堆

23 图结构 网络结构

24 1、任一选手所选中的项目中应该两两有边相连； 2、任一两个有边相连的顶点颜色（时间）不能相同。
例：田径赛的时间安排问题 跳高 跳远 姓名 项目1 项目2 项目3 丁1 跳高 跳远 100M 马2 标枪 铅球 张3 200M 李4 王5 100M 200M 铅球 标枪 1、任一选手所选中的项目中应该两两有边相连； 2、任一两个有边相连的顶点颜色（时间）不能相同。

25 第一章 绪论 1 数据结构讨论的范畴 2 数据结构的基本概念 3 数据类型和抽象数据类型 4 C语言的数据类型 5
第一章 绪论 1 数据结构讨论的范畴 2 数据结构的基本概念 3 数据类型和抽象数据类型 4 C语言的数据类型 5 算法设计目标和算法效率度量

26 1.3 数据类型和抽象数据类型 数据类型 定义：一个数据的集合, 以及定义于这个数据集合上的一组操作的总称。 C语言中的数据类型
1.3 数据类型和抽象数据类型 数据类型 定义：一个数据的集合, 以及定义于这个数据集合上的一组操作的总称。 C语言中的数据类型 基本数据类型、指针类型、数组类型、结构体类型、公用体类型、枚举类型

27 抽象数据和抽象数据类型 (ADTs: Abstract Data Types)
由用户定义，用以表示应用问题的数据模型 由基本的数据类型组成, 并包括一组相关的服务（或称操作） 信息隐蔽和数据封装，使用与实现相分离（物理实现封装）

28 ADT： 抽象数据类型名 数据对象：数据对象的定义 数据关系：数据逻辑关系的定义 基本操作：基本操作的定义
抽象数据类型的定义： ADT： 抽象数据类型名 数据对象：数据对象的定义 数据关系：数据逻辑关系的定义 基本操作：基本操作的定义 基本操作的定义： 操作名（参数表） 操作结果：操作结果描述

29 抽象数据类型

30 第一章 绪论 1 数据结构讨论的范畴 2 数据结构的基本概念 3 数据类型和抽象数据类型 4 C语言的数据类型 5
第一章 绪论 1 数据结构讨论的范畴 2 数据结构的基本概念 3 数据类型和抽象数据类型 4 C语言的数据类型 5 算法设计目标和算法效率度量

31 1.4 C语言的数据类型 1、基本数据类型 int short; long; unsigned
float float; double; long double 2、指针类型 3、数组类型 4、字符串 5、结构体类型 6、共用体类型 7、枚举类型 8、自定义类型

32 第一章 绪论 1 数据结构讨论的范畴 2 数据结构的基本概念 3 数据类型和抽象数据类型 4 C语言的数据类型 5
第一章 绪论 1 数据结构讨论的范畴 2 数据结构的基本概念 3 数据类型和抽象数据类型 4 C语言的数据类型 5 算法设计目标和算法效率度量

33 1.5 算法设计目标和算法效率度量 定义：一个有穷的指令集，这些指令为解决某一特定任务规定了一个运算序列 特性： 输 入 有0个或多个输入
输 入 有0个或多个输入 输 出 有一个或多个输出(处理结果) 确定性 每步定义都是确切、无歧义的 有穷性 算法应在执行有穷步后结束 有效性 每一条运算应足够基本 算法的描述:c++,c,PASCAL等语言

34 算法的特点： 1、有穷性：要求序列中的指令是有限的；每条指令的执行包含有限的工作量；整个指令序列的执行在有限的时间内结束。
2、确定性：算法中的每一个步骤都必须是确定的，而不应当含糊、模棱两可。 3、有零个或多个输入 4、有一个或多个输出 5、有效性：算法中的每一个步骤都应当能被有效的执行，并得到确定的结果。例如：被零除的计算动作是不能被有效执行的。

35 算法设计 自顶向下，逐步求精 设计算法的基本方法:把一个具体问题转变成一个算法 事例学习：选择排序问题 明确问题：非递减排序
解决方案：逐个选择最小数据 算法框架： for ( int i=0; i<=n-2; i++ ) { //n-1趟 从a[i]检查到a[n-1]; 若最小的整数在a[k], 交换a[i]与a[k]; } 细化程序：程序 SelectSort

36 性能分析与度量 算法的性能标准 算法的后期测试 算法的事前估计

37 分析评价算法时应考虑的因素： 1、正确性 在给定有效的输入数据后，算法经过有穷时间 的计算能给出正确的答案。 2、复杂度 时间复杂度
1、正确性 在给定有效的输入数据后，算法经过有穷时间 的计算能给出正确的答案。 2、复杂度 时间复杂度 3、简单性 4、最优性 算法A是最优的是指：在给定问题的所有算法中，A执行的进步运算次数最少 5、可读性 要求算法易于理解，便于分析 6、可修改可扩展性 如果问题P 的一个算法是A，为了解答一个与P类似的问题，希望对A稍做改动就可正确运行，如算法A满足这一点，则说A的可修改性好。

38 与算法效率有关的因素 定期集体上自习,讨论学习问题 4.问题的规模 1.程序设计语言 3.机器执行指令的速度 2.编译的代码质量

39 如何评价算法的好坏 首先算法必须是正确的。此外还需考虑： 1、算法易于理解，易于编程（在计算机上实现）, 易于调试。
2、要求算法高效，节省时间与空间。 一个算法运行所需时间的长短、空间的大小具有非常重要的意义。 时间和空间相互之间有一种制约关系，何者为重需视具体情况而定。

40 这两个要求有时互相矛盾。因此，对反复运行特别是实时的算法，首先考虑的是高效性，对偶尔运行的算法，则需突出算法易理解和易编程。
算法高效与算法易理解、易编程之间也有一种制约关系 这两个要求有时互相矛盾。因此，对反复运行特别是实时的算法，首先考虑的是高效性，对偶尔运行的算法，则需突出算法易理解和易编程。

41 我们重点考虑时间因素。 一个算法所耗费的时间，应该是该算法中每条语句的执行时间之和，而每条语句的执行时间又是该语句的执行次数（频度）与该语句执行一次所需时间的乘积。 我们假定，每条语句一次执行的时间都是相同的，为单位时间。这样我们对时间的分析就可以独立于软硬件系统。

42 我们将算法求解问题的输入量称为问题的规模，用一个整数来表示，一个算法的时间复杂度是该算法的时间耗费，一般地说，时间复杂度是问题规模的函数 － T( n )。
当问题的规模n 趋于无穷大时，把时间复杂度T( n )的数量级（阶）称为算法的渐进时间复杂度（有时简称为时间复杂度）。 严格的数学定义为：若T( n ) 和 f( n ) 是定义在正整数集合上的两个函数，当存在两个正的乘数C和n0时，使得对所有的 都有 成立，则 这时称T( n )的时间复杂度为f( n )数量级。

43 算法运行所需要的时间与两个因素有关： 1、问题实例的大小（如1000个数的排序）； 2、实例的具体情况（如1000个数的排列情况）

44 算法分析 1、假定每条语句的执行时间为单位时间。算法的时间复杂度是该算法中所有语句的执行频度之和。 例：求两个方阵的乘积 C＝A*B
＃define n 自然数 MATRIXMLT(float A[n][n],float B[n][n],float C[n][n]) { int i,j,k; for(i=0;i<n;i++) //n+1 for(j=0;j<n;j++) //n(n+1) C[i][j]=0; //n*n for( k=0;k<n;k++) //n*n*(n+1) C[i][j]=A[i][k]*B[k][j] //n*n*n } }

45 2、一般情况下，对步进循环语句只考虑循环体语句的执行次数，而忽略该语句中步长加一、终值判别、循环转移等成份。因此，当有若干个循环语句时，算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度所决定的。 例 1：x=0;y=0; for (k=1;k<=n;k++) x++; for (i=1;i<=n;i++) for (j=1;j<=n;j++) //n*n y++; 一般情况下，对步进循环语句只需考虑循环体中语句的执行次数，而忽略循环体中步长加1、终值判断、控制转移等成分。

46 例 2 ： x=1; for (i=1;i<=n;i++) for (j=1;j<=i;j++) for (k=1;k<=j;k++) x++;

47 3、选择执行的成分，如 if 语句的执行时间，决定于then 子句、else 子句耗时较多的部分
4、如果算法的执行时间是一个与问题规模n无关的常数，则算法的时间复杂度为常数阶，记作T(n)=O(1) 。 例： temp = i; i = j; j = temp;

48 while ((i>=0)&&A[i]!=k)) j--; return i;
5、很多算法的时间复杂度不仅与问题的规模有关，而且还与它所处理的数据集的状态有关。通常是根据数据集中可能出现的最坏情况估计出算法的最坏时间复杂度。 例 1 ： i=n-1; while ((i>=0)&&A[i]!=k)) j--; return i; 此问题不仅与规模 n 有关，而且与数组A中各元素的取值有关。

49 例 2 ： fact(n) { if (n <= 1) return 1; else return (n*fact(n-1)); } 设 fact 的运行时间函数为T（n），则有

50 常见的时间复杂度，按数量级递增排序： 常数阶 对数阶 线性阶 线性对数阶 平方阶 立方阶 ……… K次方阶 指数阶

51 算法的后期测试 在算法中的某些部位插装时间函数 time ( ) 测定算法完成某一功能所花费的时间

52 第一章 绪论 1 数据结构讨论的范畴 2 数据结构的基本概念 3 数据类型和抽象数据类型 4 C语言的数据类型 5
第一章 绪论 1 数据结构讨论的范畴 2 数据结构的基本概念 3 数据类型和抽象数据类型 4 C语言的数据类型 5 算法设计目标和算法效率度量