文档介绍：数据结构与算法数据结构与算法分析分析 D D ata ata S S tructure and tructure and Algorithm Analysis Algorithm Analysis ?数据结构与算法的基本原理?基本的数据结构?计算机应用中的各种常用算法?计算机领域不同问题的一系列基本算法?评价算法的准则和方法?设计和分析算法的基本原理、方法和技巧?提高分析问题、解决问题的能力主要内容一、什么是数据结构一、什么是数据结构? ? 计算机解决具体问题时,一般经过下列几个步骤: 首先要对具体问题进行分析,从中进行模型抽象,然后设计算法,最后编出程序、进行测试、调整直至得到最终解答。问问题题分分析析模模型型抽抽象象算算法法设设计计编编程程、、调调试试得得到到解解答答? Sartaj Sahni 称: “数据结构是数据对象、以及存在于该对象的实例和组成实例的数据元素之间的各种联系。这些联系可以通过定义相关的函数来给出。”(《数据结构、算法与应用》) ? Clifford 的定义是: “数据结构是 ADT (抽象数据类型)的物理实现”(《数据结构与算法分析》) ? Lobert 将一个数据结构的设计过程分成抽象层、数据结构层和实现层。其中,抽象层是指抽象数据类型层,它讨论数据的逻辑结构及其运算,数据结构层和实现层讨论一个数据结构的表示和在计算机内的存储细节以及运算的实现( 《数据结构与程序设计》) ?计算机程序是用于对信息进行加工处理的。一般而言,这些信息并不是没有组织的,信息之间往往具有重要的结构关系,这就是数据结构需要研究的内容。?计算机算法与数据的结构密切相关,算法无不依附于具体的数据结构,数据结构直接关系到算法的选择和效率 Niklaus Wirth : Algorithm + Data Structures = Programs [例1]电话号码查询问题电话号码查询问题方法方法 1 1:顺序存储,顺序查找:顺序存储,顺序查找 ((a ((a 1 1,b ,b 1 1 ), (a ), (a 2 2,b ,b 2 2 ), (a ), (a 3 3,b ,b 3 3 ), ), ……, (a , (a n n,b ,b n n) )) ) 姓名电话号码 a 1b 1a 2b 2…… a nb n 问题:效率低问题:效率低方法方法 2 2:有序顺序存储,二分查找:有序顺序存储,二分查找( ((李(李 1 1,a ,a 1 1 ), ( ), ( 李李 2 2,a ,a 2 2 ), ), ……, ( , (王王 1 1,a ,a i i ), ( ), ( 王王 2 2,a ,a i+1 i+1 ), ), ……) ) 姓名电话号码李1 1 a 1李2 2 a 2…………王1 1 a i王2 2 a i+1 …………张1 1 a k张2 2 a k+1 …………问题:修改不方便问题:修改不方便方法方法 3 3:部分有序,建立索引表:部分有序,建立索引表李1a 1李2a 2…………姓地址李……王张王1a i王2a i+1 …………张1a k张2a k+1 ………………[例2]文件系统的组织( 文件系统的组织( UNIX UNIX 为例) 为例)