全国计算机等级二级公共基础（数据结构与算法）.ppt

全国计算机等级二级公共基础 数据结构与算法 数据(Data) 是对客观事物的符号（文字、数字、其他）表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理、存储、输出的符号的总称。它是计算机程序加工的“原料”。 例如：文档、记录、数组、句子、单词、算式、符号等都是数据。 数据元素(Data Element) 是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据记录(Data Record) 是数据处理中组织数据的基本单位。 一个数据记录可由若干个数据项(Data ltem)组成，数据项可以是简单数据项（不可再分割），也可以是组合数据项（本身又是记录或数组）。 数据处理(Data Processing) 对数据进行检索、插入、删除、合并、拆分、排序、统计、计算、转换、输入、输出等的操作过程。 具体应用领域：计算机情报检索、信息管理系统、图书管理系统、物资调配系统、银行核算系统、财务管理系统、MRPII、ERP等。 综上所述： 数据处理的最小单位是数据项；由若干数据项组成数据元素；而数据是指能够被计算机识别、存储和加工处理的信息载体；数据结构是指数据之间的相互关系和数据运算。 数据结构概念一般包括3个方面的内容： 数据的逻辑结构 物理结构或存储结构 数据上的运算集合。 数据的逻辑结构就是数据元素之间的逻辑关系，它是从逻辑上描述数据元素之间的关系,而不管它在计算机中的存储表示形式。 数据的存储结构是指数据的逻辑结构在计算机存储空间中的存放形式。 在数据的存储结构中，不仅要存放各数据元素的信息，还需要存放各数据元素之间的前后件关系的信息。 数据结构由数据的逻辑结构的中各数据元素之间前后间关系的复杂程度，一般可分为： 线性结构 非线性结构 常用的存储表示方法有4种： 顺序存储 链式存储 索引存储 散列存储 对特定问题求解步骤的一种描述(流程图、伪码、程序），它是指令的有限序列，其中每一条指令表示一个或多个操作； (1)有穷性 一个算法必须总是(对任何合法的输入值)在执行有穷步之后结束，且每一步都可在有穷时间内完成； (2)确定性 算法中每一条指令必须有确切的含义，读者理解时不会产生二义性。 并且，在任何条件下，算法只有唯一的一条执行路径，即对于相同的输入只能得出相同的输出。 (3)可行性 一个算法是能行的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。 (4)输入 一个算法有零个或多个的输入，这些输入取自于某个特定的对象的集合。 (5)输出 一个算法有一个或多个的输出。这些输出是同输入有着某些特定的关系。 结构化程序设计方法的主要原则可以概括为自顶向下、逐步求精、模块化及限制使用goto语句，总的来说可使程序结构良好、易读、易理解、易维护。 一个好的算法应考虑达到以下目标： 1.正确性(Correctness) 算法应当满足具体问题的需求 2.可读性(Readability) 算法主要是为了人的阅读与交流，其次才是机器执行。 3.健壮性(Robustness) 当输入数据非法时，算法也能适当地作出反应或进行处 理，而不会产生莫明其妙的输出结果。 4. 简单性(Simplicity) 算法分析是指对一个算法的运行时间和占用空间做定量的分析，一般计算出相应的数量级，常用时间复杂度和空间复杂度表示。 分析算法的目的：降低算法的时间复杂度和空间复杂度，提高算法的执行效率。但算法的时间复杂度和空间复杂度并不相关. 算法的时间复杂度是指执行算法所需要的计算工作量；即算法执行过程中所需要的基本运算的次数。 算法的空间复杂度是对算法在运行过程中所需存储空间的量度。即指执行这个算法所需要的内存空间。 （1）存储空间的固定部分 程序指令代码的空间，常数、简单变量、定长成分(如数组元素、结构成分、对象的数据成员等)变量所占的空间 （2）可变部分 尺寸与实例特性有关的成分变量所占空间、引用变量所占空间、递归栈所用的空间、通过new和delete命令动态使用的空间