《数据结构域算法设计-第一章绪论 数据 课件》由会员分享，可在线阅读，更多相关《数据结构域算法设计-第一章绪论 数据 课件（37页珍藏版）》请在金锄头文库上搜索。
1、第1章 绪论,信息安全系 王靖亚,本章的主要内容,基本概念和术语,数据结构的概念,抽象数据类型的表示与实现,算法和算法分析,2数据元素（data element） 数据元素是组成数据的基本单位。 数据元素是一个数据整体中相对独立的单位。但它还可以分割成若干个具有不同属性的项（字段），故不是组成数据的最小单位。,基本概念和术语 1 数据（data） 数据是指能够输入到计算机中，并被计算机识别和处理的符号的集合。,例如：数字、字母、汉字、图形、图像、声音都称为数据。,3 数据对象（data object） 是性质相同的数据元素组成的集合，是数据的一个子集。 例如，整数数据对象的集合可表示为N0，1
2、，2.，字母字符数据对象的集合可表示为C=A,B,Z。,4 数据类型（data type） 一组性质相同的值的集合以及定义于这个值集合上的一组操作的总称。语言中已经实现了的数据结构。 例如，高级语言中用到的整数数据类型，是指由32768到32767中值构成的集合及一组操作（加、减、乘、除、乘方等）的总称。,什么是数据结构,“数据结构”形成的背景,早期电子计算机的应用范围，主要局限于工程和科学计算，其处理的对象是纯数值性的信息。近三十年，计算机广泛用于情报检索、企业管理、系统工程等方面，处理的对象由纯粹的数值发展到字符、表格和图像等具有一定结构的数据。 因此，为了编写出一个好程序，必须分析待处理
3、的对象的特性及其相互之间的关系。,计算机解决问题的步骤,计算机解决一个具体问题时，大致需要经过下列几个步骤： 首先要从具体问题中抽象出一个适当的数学模型； 然后设计一个解此数学模型的算法； 最后编出程序、进行测试、调整直至得到最终解答。,寻求数学模型的实质是分析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系。,由上面例子可知，描述这类非数值计算问题的数学模型不再是数学方程，而是诸如表、树、图之类的数据结构。,数据结构的发展简史及其在计算机科学中所处的地位,发展史： “数据结构”作为一门独立的课程在国外是从1968年才开始设立的。 1968年美国唐欧克努特教授开创了数据结构的最初体系
4、，他所著的计算机程序设计技巧第一卷基本算法是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作,地位： “数据结构”在计算机科学中是一门综合性的专业基础课。 数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。 数据结构这一门课的内容不仅是一般程序设计（特别是非数值性程序设计）的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序的重要基础。,C）数据结构的定义 定义：数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。 D) 数据结构研究的范畴 数据的逻辑结构独立于计算机，是数据本身所固有的。 存贮结构是逻辑结构在计算机存贮器中的映像，必须依赖于计算
5、机。 运算是指所施加的一组操作总称。运算的定义直接依赖于逻辑结构，但运算的实现必依赖于存贮结构。,例1.1 线性表示例,例1.2 树形结构示例,图12家庭成员结构示意图,例1.3 图形结构示例,图,1,-,3,城市交通示意图,从逻辑结构划分数据结构 数据结构从逻辑结构划分为： （1）线性结构元素之间为一对一的线性关系，第一个元素无直接前驱，最后一个元素无直接后继，其余元素都有一个直接前驱和直接后继。 （2）非线性结构元素之间为一对多（树形结构）或多对多（图形结构）的非线性关系，每个元素有多个直接前驱或多个直接后继。,从存贮结构划分数据结构 数据结构从存贮结构划分为： (1) 顺序存贮所有元素存
6、放在一片连续的存贮单元中，逻辑上相邻的元素存放到计算机内存仍然相邻。 (2) 链式存贮所有元素存放在可以不连续的存贮单元中，但元素之间的关系可以通过地址确定，逻辑上相邻的元素存放到计算机内存后不一定是相邻的。,抽象数据类型（Abstract Data Type） 是指一个数学模型以及定义在该模型上的一组操作。,在本书中，描述一种抽象数据类型将采用如下书写格式：ADT 抽象数据类型名 数据对象:数据关系:基本操作: ADT 抽象数据类型名,数据结构的抽象描述数据结构可用二元组D=(K,R)的形式来描述。其中，K=a1,a2,an为元素集合，R=r1,r2,rm为关系的集合。 例1-4 设有一个数
7、据结构的抽象描述可表示为D=(K,R),其中K=a1,a2,a3,a4,a5,R=,， 则它的逻辑结构用图描述见图1-4 。,图1-4 线性表的逻辑结构描述,例1-5 设一个数据结构的抽象描述为D=(K,R),其中K=a,b,c,d,e,f,g,h,r=,则它的逻辑结构用图描述见图1-5。,例 1-6 设一个数据结构的抽象描述为D=(K,R),其中K=1,2,3,4,而R=(1,2),(1,3),(1,4),(2,3),(2,4),(3,4), 则它的逻辑结构用图描述见图1-6。,算法和算法分析,1算法（algorithm） 算法是对特定问题求解步骤的一种描述，是指令的有限序列，其中每条指令表
8、示一个或多个操作。算法具有五大特性： （1）输入：具有0个或多个输入 （2）输出：至少产生一个输出，它们是算法执行完后的结果。 （3）有穷性：一个算法总是在有穷步之后结束，且每一步都可在有穷时间内完成。 （4）确定性：每条指令的含义都必须明确，无二义性。在任何条件下，算法只有唯一的一条执行路径，对于相同的输入得出相同的输出。 （5）可行性：算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。,1 正确性：正确”的含义在通常的用法中有很大的差别，大体可分为以下四个层次：程序不含语法错误；程序对于几组输入数据能够得出满足规格说明要求的结果；程序对于精心选择的典型、苛刻而带有刁难性的几
9、组数据能够得出满足规格说明要求的结果；程序对一切合法的输入数据都能产生满足规格说明要求的结果。,2可读性 健壮性 效率和低存储容量需求,设计一个好的算法应考虑以下几个方面：,算法的描述-类C语言 简单赋值： 变量名=表达式；它表示将表达式的值赋给左边的变量；变量+；它表示变量加1后赋值给变量变量-；它表示变量减1后赋值给变量,成组赋值： 1.（变量1，变量2，变量3，变量k）=（表达式1，表达式2，表达式3，表达式k）； 2.数组名1下标1下标2=数组名2下标1下标2,串联赋值： 变量1=变量2=变量3=变量k= 表达式；条件赋值： 变量名=条件表达式？表达式1：表达式2；交换赋值： 变量1变
10、量2，表示变量1和变量2互换；,4条件选择语句 条件语句1 if （表达式） 语句； 条件语句2 if （表达式） 语句1；else 语句2； 开关语句 switch （表达式）case 判断值1：语句组1； break；case 判断值2：语句组2； break； case 判断值n：语句组n； break；default：语句组； break； ,注意：switch case语句是先计算表达式的值，然后用其值与判断值相比较，若它们相一致时，就执行相应的case下的语句组；若不一致，则执行default下的语句组；其中的方括号代表可选项。,5循环语句 for语句for（表达式1；表达式2；表
11、达式3）循环体语句； 首先计算表达式1的值，然后求表达式2的值，若结果非零则执行循环体语句，最后对表达式3运算，如此循环，直到表达式2的值为零时止。, while语句while （条件表达式） 循环体语句； while循环首先计算条件表达式的值，若条件表达式的值非零，则执行循环体语句，然后再次计算条件表达式，重复执行，直到条件表达式的值为假时退出循环，执行该循环之后的语句。, do-while语句do 循环体语句 while（条件表达式）该循环语句首先执行循环体语句。然后再计算条件表达式的值，若条件表达式成立，则再次执行循环体，再计算条件表达式的值，直到条件表达式的值为零，即条件不成立时结束循
12、环。,6输入、输出语句 输入语句：用函数scanf实现，特别当数据为字符时，用getchar函数实现。 输出语句：用printf函数实现，当要输出字符数据时，用putchar函数实现。,7其他一些语句 （1）return表达式或return：用于函数结束。 （2）break语句：可用在循环语句或case语句中结束循环过程或跳出情况语句。 （3）exit语句：表示出现异常情况时，控制退出语句,8注释形式可用 /*字符串*/ 或者 单行注释 或 /文字序列。,9一些基本的函数 如： max函数，用于求一个或几个表达式中的最大值；min函数，用于求一个或几个表达式中的最小值；abs函数，用于求表达式
13、的绝对值；eof函数，用于判定文件是否结束；eoln函数，用于判断文本行是否结束。,算法分析,时间复杂度 时间频度（语句频度）,一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。,例1-8 求下列算法段的语句频度for(i=1; i=n; i+) for(j =1; j =i ; j+)x=x+1;分析：该算法
14、为一个二重循环，执行次数为内、外循环次数相乘，但内循环次数不固定，与外循环有关，因些，时间频度T(n)=1+2+3+n=,时间复杂度设n为问题的规模，当n不断变化时，时间频度T(n)也会不断变化。为了研究它的变化呈现什么规律。我们引入时间复杂度概念。把 T(n)表示成数量级的形式为：T(n)=(g(n),其中大写字母为英文Order（即数量级）一词的第一个字母。,例如，若T(n)=n(n+1)/2,则有 1/2T(n)/n21，故它的时间复杂度为(n2), 即(n)与n2 数量级相同。,例1-9 分析下列算法段的时间频度及时间复杂度for （i=1;i=n;i+） for (j=1;j=i;j
15、+) for ( k=1;k=j;k+)x=i+j-k;,分析算法规律可知时间频度T(n)=1+(1+2)+(1+2+3)+.+(1+2+3+n)= += + 由于有1/6 T（n)/ n3 1，故时间复杂度为(n3)。,在各种不同算法中，若算法中语句执行次数为一个常数，则时间复杂度为O(1),另外，在时间频度不相同时，时间复杂度有可能相同，如T(n)=n2+3n+4与T(n)=4n2+2n+1它们的频度不同，但时间复杂度相同，都为O(n2)。,按数量级递增排列，常见的时间 复杂度有： 常数阶O(1),对数阶O(log2n),线性阶O(n), 线性对数阶O(nlog2n),平方阶O(n2)，立方阶O(n3),.， k次方阶O(nk),指数阶O(2n)。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。,空间复杂度,空间频度一个算法在执行时所占有的内存开销，称为空间频度，但我们一般是讨论算法占用的辅助存储空间。讨论方法与时间频度类似，不再赘述。,
