数据结构和算法2.ppt

第一章 绪论;1.1 引言;1.2 数据结构的地位;1.3 什么是数据结构 ;例2 人机对奕问题;例3 多叉路口交通灯管理问题; 数据结构: 是研究（程序设计中）计算机的操作对象以及它们之间关系和运算的一门学科。;数据:计算机中描述客观事物的符号。 节点（数据元素）:数据的基本单位。;图状结构——多个对多个，如，图。;4.存储结构（物理结构） ：数据在计算机中的存储表示。;;7.数据类型:数据的取值范围及其操作的总称。;8.算法;1.5 算法和算法的描述; 一个算法可以用自然语言、数字语言或约定的符号来描述，也可以用计算机高级程序语言来描述，如Pascal语言、C语言或伪代码等。; # define TRUE 1； # define FALSE -1； # define ERROR NULL；; [数据类型] 函数名 （[形式参数]） [形式参数说明；] { 内部数据说明； 执行语句组； } /*函数名*/ ;简单赋值： 〈变量名〉=〈表达式〉，它表示将表达式的值赋给左边的变量； 〈变量〉++，它表示变量加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〉←→〈变量2〉，表示变量1和变量2互换； ;情况语句: switch （〈表达式〉） { case 判断值1； 语句组1； break； case 判断值2；语句组2； break； …… case 判断值n；语句组n； break； [default：语句组； break；] };⑴ for语句 for（〈表达式1〉；〈表达式2〉；〈表达式3〉）{循环体语句；}; while循环首先计算条件表达式的值，若条件表达式的值非零，则执行循环体语句，然后再次计算条件表达式，重复执行，直到条件表达式的值为假时退出循环，执行该循环之后的语句。; 该循环语句首先执行循环体语句。然后再计算条件表达式的值，若条件表达式成立，则再次执行循环体，再计算条件表达式的值，直到条件表达式的值为零，即条件不成立时结束循环。; 输入语句：用函数scanf实现，当数据为字符时，用getchar函数实现。 输出语句：用printf函数实现，当要输出字符数据时，用putchar函数实现。;（1）return表达式或return：用于函数结束。 （2）break语句：可用在循环语句或case语句中结束循环过程或跳出情况语句。 （3）exit语句：表示出现异常情况时，控制退出语句。 8．注释形式 可用 /*字符串*/ 单行注释 或 //文字序列。 ;如： max函数，用于求一个或几个表达式中的最大值； min函数，用于求一个或几个表达式中的最小值； abs函数，用于求表达式的绝对值； eof函数，用于判定文件是否结束； eoln函数，用于判断文本行是否结束。 ;设计一个好的算法应考虑以下几个方面： 1．正确性 “正确”的含义在通常的用法中有很大的差别，大体可分为以下四个层次：①程序不含语法错误；②程序对于几组输入数据能够得出满足规格说明要求的结果；③程序对于精心选择的典型、苛刻而带有刁难性的几组数据能够得出满足规格说明要求的结果；④程序对一切合法的输入数据都能产生满足规格说明要求的结果。; 运行时间是指一个算法在计算机上运算所花费的时间。它大致等于计算机执行一种简单操作（如赋值操作、转向操作、比较操作等等）所需要的时间与算法中进行简单操作次数的乘积。 通常把算法中包含简单操作次数的多少叫做算法的时间复杂性，它是一个算法运行时间的相对量度。;时间复杂度的计算：;void factorsum（n） int n； { int i，j； int f，w； f=0； for （i=1，i〈=n；i++） { w=1； for（j=1，j〈=i；j++）