计算机导论-7-数据结构与算法.pptVIP

1 1 多了解一些 高德纳——唐纳德 ? 克努斯算法和程序设计技术的先驱者 1938年出生于密尔沃基。 1956年就读凯斯理工学院，1960年同时获学士和硕士学位，之后在伯克利攻读数学博士学位。1963年毕业后，在伯克利任教。 1962年，世界著名出版社Addison-Wesley向他约稿，他原计划出7卷。 1968年《计算机程序设计艺术》第一卷出版（基本算法）。同年，到斯坦福任教。第二年，第二卷出版（半数值算法）。1973年，第三卷出版（排序与查找）。 高德纳——唐纳德 ? 克努斯算法和程序设计技术的先驱者 1974年，仅36岁就因《计算机程序设计艺术》而获图灵奖。之后辍笔，但创造了字体设计系统METAFONT、文学化编程、排版系统TEX。 1979年，获美国国家科学金奖；1996年，获京都奖。 1992年，为专心写作提前退休。2008年，第四卷面世（组合算法）。 第五卷（语法算法）、第六卷（语言理论）、第七卷（编译程序）在准备？ 《计算机程序设计艺术》被《科学美国人》评为20世纪最重要的12部科学著作之一。到现在共出19部著作和160余篇论文。 高德纳——唐纳德 ? 克努斯算法和程序设计技术的先驱者 如果你认为你是一名真正优秀的程序员……读Knuth的《计算机程序设计艺术》，如果你能读懂整套书的话，请给我发一份你的简历。 —— Bill Gates 这是一套集所有基础算法之大成的经典之作。当今软件开发人员所掌握的绝大多数计算机程序设计的知识都来源于此。 ——Byte 迪杰斯特拉（Edsger Wybe Dijkstra ） 1930年出生于荷兰阿姆斯特丹，2002年逝世于荷兰纽南。理论物理学博士。 发明最短路径算法（Dijkstra算法）、ALGOL第二代编程语言、结构化定理等。 ——如今的大部分语言都属于类ALGOL语言。 ——ALGOL是图灵奖机器，围绕ALGOL语言共产生了十几位图灵奖得主。 1972年获得图灵奖。 约翰·霍泼克洛夫特（John Edward Hopcroft） 1939年生于西雅图。1961年获西雅图大学电气工程学士学位，1962年获斯坦福大学硕士学位，1964年获博士学位。曾先后在普林斯顿大学、康乃尔大学、斯坦福大学工作。 提出“最坏情况渐近分析法” ，以此衡量算法的效率和优劣。 在高德纳名下与塔扬一起研究图的连通性和平面性测试难题，提出“深度优先有哪些信誉好的足球投注网站算法”。 提出“双堆栈叠”数据结构，提出“2-3树”数据结构。 主要著作：《计算机算法的设计与分析》、《数据结构和算法》、《自动机理论，语言和计算的导论》和《计算机科学：成就与机遇》。 1986年获得图灵奖。 罗伯特·塔扬 （Robert Endre Tarjan） 1948年4月30日生于加里福尼亚州的波莫纳。 1965年在加州理工学院学习数学，同时辅修计算机课程。 1969年进入斯坦福大学研究生院，师从高德纳。1972年获博士学位。之后随霍泼克洛夫特去康奈尔大学工作。后来又在伯克利、斯坦福、贝尔实验室工作。 与霍泼克洛夫特共同提出“深度优先有哪些信誉好的足球投注网站”算法。 提出“合并-有哪些信誉好的足球投注网站”算法，用发明的“动态树”解决最大网络流问题，提出“八字树”数据结构，提出“持久性数据结构”。 1986年获得图灵奖。 辽宁科技学院电气与信息工程学院 辽宁科技学院电气与信息工程学院 * 第 7 讲 数据结构与算法 数据结构（data structure） 数据结构的基本概念 典型的数据结构 算法（algorithm） 算法的基本概念 算法的描述方法 衡量算法的优劣 数据结构与算法 1、数据结构的基本概念 数据结构（data structure）： 数据元素之间抽象化的关联构造。 （重在元素之间的逻辑关系及数据处理） 数据结构的作用 （1）Pascal之父——Nicklaus Wirth：算法 + 数据结构 = 程序 （2）数据结构是程序设计之前必须先考虑好的问题 （3）以数据为中心设计程序，因此，数据结构是关键。数据结构设计 得当，程序设计得心应手，事半功倍；数据结构设计不好，程序 设计事倍功半，甚至无从下手。 数据结构 1、数据结构的基本概念 数据结构的使用 强调灵活运用，《数据结构》课程讲授典型的数据结构与处理算法，但 实际应用中要综合，要变通，要深刻理解数据结构的思想，要有自己的 设计。要学会将看似截然不同的问题抽象成相同的数据结构。 例如：（1）某班级学生信息表的处理：线性表 （2）某单位组织结构信息的处理：树 （3）某地区公路网信息的处理：图 以上问题都能在《数据结构》课程中找到标准