数据结构参考书目1.数据结构课程的地位2.“数据结构”课程的教学目标3.课程基本结构4.数据结构的兴起与发展第二阶段：结构化程序设计阶段20世纪60年代末至80年代，提出程序结构模块化，程序模块的内部以顺序、if-then分支和while循环为主。同时应用于非数值领域（操作系统、编译程序、数据库等系统软件的设计），对象/实体的数据表示法成为程序设计的重要问题，数据表示操作结构化，如表、栈、队、树、图等。数据结构及抽象数据类型的形成标志是1968D.E.Knuth<TheArtofComputerProgramming>.第三阶段：面向对象技术阶段兴起于20世纪80年代初，流行于90年代。对象是描述实体的属性与操作的，是二者的封装体，在面向对象技术中，数据是程序的“主人”，对象是划分与构造程序的主要单位，对象包含数据结构中的主要因素——数据成分与操作。NiklausWirthAlgorithm+DataStructures=Programs第一章绪论计算机是一门研究用计算机进行信息表示和处理的科学。这里面涉及到两个问题：信息的表示信息的处理而信息的表示直接关系到处理信息的程序的效率。随着计算机的普及，信息量的增加，信息范围的拓宽，使许多系统程序和应用程序的规模很大，结构又相当复杂。因此，为了编写出一个“好”的程序，必须分析待处理的对象的特征及各对象之间存在的关系，这就是数据结构这门课所要研究的问题。1.1什么是数据结构例1、电话号码查询系统设有一个电话号码薄，它记录了N个人的名字和其相应的电话号码，假定按如下形式安排：(a1，b1)(a2，b2)…(an，bn)其中ai，bi(i=1，2…n)分别表示某人的名字和对应的电话号码，要求设计一个算法，当给定任何一个人的名字时，该算法能够打印出此人的电话号码，如果该电话簿中根本就没有这个人，则该算法也能够报告没有这个人的标志。算法的设计，依赖于计算机如何存储人的名字和对应的电话号码，或者说依赖于名字和其电话号码的结构。数据的结构，直接影响算法的选择和效率。上述的问题是一种数据结构问题。可将名字和对应的电话号码设计成：二维数组、表结构、向量。假定名字和其电话号码逻辑上已安排成n元向量的形式，它的每个元素是一个数对(ai，bi)，1≤i≤n。数据结构还要提供每种结构类型所定义的各种运算的算法。例2、图书馆的书目检索系统自动化问题当你想借一本参考书但不知道书库中是否有当年你想找某一方面的参考书而不知图书馆内有哪些这方面的书的时候，都需要到图书馆去查阅图书目录卡片。图书馆的各种卡片：按书名编排，按作者编排，按分类编排，等等。每一张卡片上的书目信息由登录号、书名、作者名、分类号、出版单位和出版时间等若干项组成。在这类文档管理的数学模型中，计算机处理的对象之间通常存在的是一种最简单的线性关系，这类数学模型可称为线性的数据结构例3.信号灯问题：为这个路口设计一个安全有效的交通信号灯的管理系统（其中C和E为单行道）。信号灯问题－分析信号灯问题－分析信号灯问题－抽象贪心法的一个解：(1)红色：ABACADBADCED(2)蓝色：BCBDEA(3)绿色：DADB(4)白色：EBEC从上面的例题可见，描述这类非数值计算问题的数学模型不再是数学方程，而是诸如表，树和图之类的数据结构，因此数据结构的研究内容为：为在计算机上解决具体问题，应如何对所需的数据/信息及其关系进行组织（组织起来的数据就具有了结构关系），以及如何对他们进行基本操作。简言之，数据结构就是研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。着色问题－经典问题阅读资料——四色猜想1852年10月23日，他的弟弟就这个问题的证明请教他的老师、著名数学家德.摩尔根，摩尔根也没有能找到解决这个问题的途径，于是写信向自己的好友、著名数学家哈密尔顿爵士请教。哈密尔顿接到摩尔根的信后，对四色问题进行论证。但直到1865年哈密尔顿逝世为止，问题也没有能够解决。1872年，英国当时最著名的数学家凯利正式向伦敦数学学会提出了这个问题，于是四色猜想成了世界数学界关注的问题。世界上许多一流的数学家都纷纷参加了四色猜想的大会战。1878～1880年两年间，著名的律师兼数学家肯普和泰勒两人分别提交了证明四色猜想的论文，宣布证明了四色定理，大家都认为四色猜想从此也就解决了。11年后，即1890年，数学家赫伍德以自己的精确计算指出肯普的证明是错误的。不久，泰勒的证明也被人们否定了。后来，越来越多的数学家虽然对此绞尽脑汁，但一无所获。于是，人们开始认识到，这个貌似容易的题目，其实是一个可与费马猜想相媲美的难题：先辈数学大师们的努力，为后世的数学家揭示四色猜想之谜铺平了道路。进入20世纪以来，科学家