(C语言详细版)第一章什么是数据结构.pptVIP

1.2 基本概念和术语 数据结构的内容包括三个层次的五个“要素”，如图所示。 -*- 1.3 抽象数据类型的表示与实现 通过程序设计语言中的类型来实现 C 抽象数据类型 数据对象 结构体 基本操作 函数 C++，Java 抽象数据类型 类 class 数据对象 数据成员 基本操作 成员函数(方法) 一个例子 -*- 1.3 抽象数据类型的表示与实现 表示：伪语言 借用程序设计语言的结构描述---简洁、严谨 忽略程序设计语言的细节---简洁 伪C语言与C语言的区别 抽象数据类型：typedef 赋值：成组赋值、交换赋值 选择语句： switch的扩展 输入/输出：可以忽略格式串 头文件、辅助变量定义：忽略 C的扩展：引入C++的引用参数表示变参 -*- 1.3 抽象数据类型的表示与实现 伪C中的引用参数——C的扩展 C的虚实结合：单向的值传递 问题：如何简单地表示返回多个值？ C支持的策略： 全局变量、将形参定义为指针类型、将返回值定义为指针类型 C++的另一种处理：引用参数  类型说明符 引用参数名 引用参数与实在参数共享存储单元 利用引用参数表示变参(可以将在被调用函数体中改变了的值代回主调处） -*- 1.4 算法和算法分析-定义和特性 定义对特定问题的求解步骤的一种描述，指令的有限序列，其中每一条指令表示一个或多个操作。 特性 有穷性：算法在执行有穷步后能结束，且每一步都在有穷时间内完成。 确定性：每一指令有确切的含义，无二义。且算法只有一个入口和一个出口。 可行性：每一操作都可以通过已经实现的基本运算执行有限次来实现 输入：零个或多个输入 输出：一个或多个输出 -*- 1.4 算法和算法分析-算法评价标准 算法评价标准 正确性（Correctness） 首先，算法应当满足以特定的“规格说明”方式给出的需求。 其次，对算法是否“正确”的理解可以有以下四个层次： 程序不含语法错误； 对于几组输入数据能够得出满足要求的结果； 程序对于精心选择的、典型、苛刻且带有刁难性的几组输入数据能够得出满足要求的结果； 程序对于一切合法的输入数据都能得出满足要求的结果； 通常以第3层意义的正确性作为衡量一个算法是否合格的标准。 -*- 1.4 算法和算法分析-算法评价标准 可读性（Readability） 算法主要是为了人的阅读与交流，其次才是为计算机执行。因此算法应该易于人的理解；另一方面，晦涩难读的程序很容易隐藏较多错误而难以调试 健壮性（Robustness） 当输入的数据非法时，算法应当恰当地作出反映或进行相应处理，而不是产生莫名奇妙的输出结果。并且，处理出错的方法不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。——异常处理机制 -*- 1.4 算法和算法分析-算法评价标准 高效率与低存储量需求 通常，效率指的是算法执行时间；存储量指的是算法执行过程中所需的最大存储空间。两者都与问题的规模有关。 -*- 1.4 算法和算法分析-事后统计 算法效率的度量 一个可执行的正确的算法也有优劣之分，通常以算法执行时在时间和空间资源方面消耗的多寡作为评价算法优劣的标准。 事后统计 利用计算机内部的计时功能 double start, stop; time (start); mainprocess(n, …); time (stop); double runTime = stop - start; printf ( ”%d%d\n , n, runTime ); 缺陷 1、必须执行程序 2、其它因素掩盖算法本质 （时间统计量依赖于计算机的软硬件环境） -*- * 第一章 绪论 重点：数据结构的基本概念 难点：ADT、算法复杂度 -*- 第一章 绪论 1.1 什么是数据结构 1.2 基本概念和术语 1.3 抽象数据类型的表示与实现 1.4 算法和算法分析 1.4.1 算法 1.4.2 算法设计的要求 1.4.3 算法效率的度量 1.4.4 算法的存储空间的需求 作业 -*- 1.1 什么是数据结构 众所周知，二十世纪四十年代，电子数字计算机问世的直接原因是解决弹道学的计算问题。 在电子计算机发展的初期阶段，人们用计算机主要处理数值计算问题，用以解决人们用手工或机械计算机难以胜任的数值计算。 当时涉及的数据对象还比较简单，不外乎是整型、实型、布尔型等。——数学软件 。 随着计算机使用领域的扩大和深入，解决“非数值性问题”越来越引起人们的重视和关注。例