数据结构与算法概论.pdfx.pdf

数据结构及其算法概论 全权 自动化科学与电气工程学院 北京航空航天大学 1982图灵奖 • 1971年，在他的论文 《The Complexity of Theorem Proving Procedures》，他整 理了NP 完备性的目标，亦产 生了古克定理——布尔可满 足性问题是NP 完备的证明。 • 因在计算复杂性理论方面的 贡献，尤其是在奠定NP 完全 性理论基础上的突出贡献而 荣获1982年度的图灵奖。 史提芬·A·古克 Stephen A. Cook ，1939年－ 本节课内容 • 计算机编程语言 • 数据结构概论 • 算法概论 3 1.计算机编程语言 /best-progra ing-language-jobs/ 1.计算机编程语言 Facebook: PHP, C++, Python, Java, Perl. High regard for dynamic/scripting languages. Google: officially C/C++, Java, Python, Javascript Amazon: Java, Javascript, Ruby, Python, Perl Microsoft: C++, C#, Java, Python 控制工程学科：C, Matlab /best-progra ing-language-jobs/ 2.数据结构概论  为什么学算法和数据结构  它们可以脱离任何的计算机程序设计语言  “程序设计 =  算法 +  数据结构” (瑞士计算机科学家 Niklaus Wirth) 算法:数据在计算机里如何运算\数据结构: 数据在计算机里如何组织  算法-数学, 数据结构-结构学  “房子=设计图纸+原材料”  大数据时代的优秀软件工程师 2.数据结构概论  什么是数据结构  数据（Data ） 能够被计算机识别、存储和加工处理 ，是计算机程序 加工的 “原料”。随着计算机应用领域的扩大，数据的 范畴包括：整数、实数、字符串、图像和声音等。  数据元素（Data Element） 数据元素是数据的基本单位。数据元素也称元素、结 点、顶点、记录。一个数据元素可以由若干个数据项 （也可称为字段、域、属性）组成。数据项是具有独立 含义的最小标识单位。比如：书名，人名 7 2.数据结构概论  什么是数据结构  数据元素之间的联系称之为结构 ，数据结构 就是具有结构的数据元素的集合。  数据结构是一个二元组 Data-Structure=( D, R ) 其中: D是数据元素的有限集合 ，R是D上的关 系的集合。