数据结构课件第1章绪论.ppt

为什么要学习数据结构 数据结构是计算机科学研究的基本课题。 数据结构是本专业的许多后续专业课的基础。 研究生及本专业重要证书的必考科目 本课程的教学目的： 介绍最常用的数据结构，阐明数据结构内在逻辑关系，讨论它们在计算机中的存储表示，并结合各种数据结构，讨论对它们实行各种运算（操作）的实现算法。 关于本课程的成绩评定方式 学习评价方式 1、作业 2、实验 3、考试 4、上课出勤率 参考文献 1.数据结构───C语言描述(教材） 耿国华主编 高等教育出版社 ２．数据结构与算法 　　　　　　　　许卓群 杨冬青等主编 　　　　　　高等教育出版社 ３．数据结构（Ｃ语言版） 　　　　　　　　严蔚敏等编 　　　　　清华大学出版社 （３）数据结构中常用的时间复杂度频率计算 类型定义实例 类型定义实例 类型定义实例 类型定义实例 ⑴参数传递方式：值参和变量（地址）参数的区别。 例 交换两个整数变量的算法 例 交换两个整数变量的算法 Void main( ) {int x=100,y=800; Swap1(x,y); printf(“\n调用swap1后x=%d,y=%d”,x,y); X=100;y=800; Swap2(x,y);　　//地址作为函数实参 printf(“\n调用swap2后x=%d,y=%d”,x,y); ⑵函数结果的带出方式 值传递无法带出结果值。 函数结果的带出的三种方式：全程变量、函数返回值（return)、传地址参数 返回多个函数值的方法： ⑴全局变量方式 ⑵通过地址传递带出（数组方式、结构体方式、指针方式） 多个函数值返回──全局变量方式 多个函数值返回──数组方式 多个函数值返回──结构体方式 多个函数值返回──指针方式 1.5 算法描述及分析 (1) 正确性 (correctness)。算法应满足具体问题需求，设计或选择的算法应能正确反映这种需求。 (2) 可读性 (readability)。算法主要是为了人的阅读及人与人之间的交流，其次才是机器执行。可读性好有助于人对算法的理解，晦涩难懂的程序易于隐藏较多错误难以调试和修改。 (3) 健壮性 (robustness)。当输入数据非法时，算法也能适当地作出反应或处理，而不会产生莫名其妙的输出结果。 (4) 高效率与低存储 (high efficiency and low memory)。效率指的是算法执行时间。一个问题若有多个算法可解决，则执行时间短的算法效率高。存储量需求指的是算法执行过程中所需的最大存储空间。 2. 算法的设计要求 * * 1.5 算法描述及分析 对解决问题的算法进行时间上的度量分析，或对解决同一问题的两种或两种以上的算法运行的时间加以比较，这种度量分析称为算法的时间复杂度分析。 3. 算法性能评价(算法效率的度量) 算法运行时间分析和程序运行时间分析的区别。同一个算法由不同的编程员所编出来的程序有优劣之分，程序运行时间也就不同；程序在不同计算机上运行的速度又和计算机本身的速度有关。 * 1.5 算法描述及分析 3. 算法效率的度量 (1) 估算算法运行时间的方法 估算算法运行时间方法：撇开所有与计算机硬件和计算机软件有关的因素，只确定依赖于问题的 “规模”（通常用整型量 n 表示）和确定算法执行 “基本操作” 的次数。一个算法的 “规模” 和 “基本操作” 要视具体算法而定。 “规模” 一般是指输入量的数目，比如在排序问题中，问题的规模可以是被排序的元素数目。 “基本操作” 一般是指在某个数据类型上的 “标准操作”，比如两个整数相加、比较两个整数的大小等都可以视为是基本操作。 * 1.5 算法描述及分析 3. 算法效率的度量 一个算法由控制结构（顺序、分支和循环）和原操作（固有数据类型的操作）构成，则算法时间取决于两者的综合效果。为了便于比较同一问题的不同算法，通常的做法是，从算法中选取一种对于所研究的问题（或算法类型）来说是 “基本操作” 的原操作，以该 “基本操作” 重复执行的次数(语句频度）作为算法运行时间的度量。 (2) 算法的时间复杂度 在一般情况下，算法中 “基本操作” 重复执行的次数是问题规模 n 的某个函数 f (n)，算法的时间度量记作：T (n) = O ( f (n) ) 此式表示随着问题规模 n 的增大，算法执行时间的增长率和