数据结构第一章

《数据结构第一章》由会员分享，可在线阅读，更多相关《数据结构第一章（106页珍藏版）》请在金锄头文库上搜索。

1、数据结构主讲：尚文倩 参考书目v1. 数据结构（c语言版），严蔚敏，吴伟民著， 清华大学出版社，2007年3月。v2. 数据结构与算法，齐德昱著，清华大学出版社 ，2004年9月。1. 数据结构课程的地位 数据结构是计算机科学与技术专业的专业基础课，是十 分重要的核心课程。所有的计算机系统软件和应用软件都 要用到各种类型的数据结构。打好“数据结构”这门课程的 扎实基础，对于学习计算机专业的其他课程，如操作系统 、编译原理、数据库管理系统、软件工程、人工智能等都 是十分有益的。数据结构也是介于数学、计算机硬件和计算机软件之间的 一门课程。“算法数据结构程序” 程序就是在数据的某些特定的结构和表示

2、的基础上对于算 法的描述。 算法与数据结构是程序设计中相辅相成、不可分割的两个 方面。2. “数据结构”课程的教学目标“数据结构”课程的教学目标是要求学生学会分析数据对象特征，掌握数据组织方法和计算机的表示方法，以便为应用所涉及的数据选择适当的逻辑结构、存储结构及相应算法，初步掌握算法时间空间分析的技巧，培养良好的程序设计技能。3. 课程基本结构第一部分： 数据结构的基本概念（第1章）。第二部分： 基本的数据结构，包括：线性结构线性表、栈和队列、串、数组与广义表（第25章）；非线性结构树和二叉树、 图（第6、 7章）。第三部分： 基本技术，包括：查找技术与排序技术（第9、 10章）。4.数据结

3、构的兴起与发展v数据结构问题起源于程序设计的发展。程序 设计经历了三个阶段：v第一阶段：无结构阶段20世纪40年代至60年代，程序设计主要针 对科学计算，程序以算法为中心，设计技术 以机器语言/汇编语言为基础。v第二阶段：结构化程序设计阶段20世纪60年代末至80年代，提出程序结构模块化，程序模块的内部以顺序、if-then分支和while循环为主。同 时应用于非数值领域（操作系统、编译程序、数据库等系 统软件的设计），对象/实体的数据表示法成为程序设计的 重要问题，数据表示操作结构化，如表、栈、队、树、图 等。数据结构及抽象数据类型的形成标志是1968 D.E.Knuth.v第三阶段：面向对

4、象技术阶段兴起于20世纪80年代初，流行于90年代。对象是描述实 体的属性与操作的，是二者的封装体，在面向对象技术中 ，数据是程序的“主人”，对象是划分与构造程序的主要单 位，对象包含数据结构中的主要因素数据成分与操作 。Niklaus WirthAlgorithm + Data Structures = Programs程序设计:算法: 数据结构: 为计算机处理问题编制一组指令集 处理问题的策略问题的数学模型第一章 绪 论1.1 什么是数据结构 1.2 抽象数据类型的表示与实现 1.3 算法和算法分析1.3.1 算法1.3.2 算法设计的要求1.3.3 算法效率的度量1.3.4 算法的存储空

5、间的需求计算机是一门研究用计算机进行信息表 示和处理的科学。这里面涉及到两个问题： 信息的表示信息的处理而信息的表示直接关系到处理信息的程 序的效率。随着计算机的普及，信息量的增 加，信息范围的拓宽，使许多系统程序和应 用程序的规模很大，结构又相当复杂。因此 ，为了编写出一个“好”的程序，必须分析待 处理的对象的特征及各对象之间存在的关系 ，这就是数据结构这门课所要研究的问题。1.1什么是数据结构众所周知，计算机的程序是对信息进 行加工处理。在大多数情况下，这些信息 并不是没有组织，信息（数据）之间往往 具有重要的结构关系，这就是数据结构的 内容。那么，什么是数据结构呢？先看以下几个例子：例1

6、、电话号码查询系统设有一个电话号码薄，它记录了N个 人的名字和其相应的电话号码，假定按 如下形式安排：(a1，b1)(a2，b2)(an，bn)其中ai，bi(i=1，2n) 分别表示某 人的名字和对应的电话号码，要求设计 一个算法，当给定任何一个人的名字时 ，该算法能够打印出此人的电话号码， 如果该电话簿中根本就没有这个人，则 该算法也能够报告没有这个人的标志。算法的设计，依赖于计算机如何存储人 的名字和对应的电话号码，或者说依赖于名 字和其电话号码的结构。数据的结构，直接 影响算法的选择和效率。上述的问题是一种数据结构问题。可将 名字和对应的电话号码设计成：二维数组、 表结构、向量。假定名

7、字和其电话号码逻辑上已安排成n 元向量的形式，它的每个元素是一个数对(ai ，bi)， 1in 。 数据结构还要提供每种结构类型所定义 的各种运算的算法。例2、图书馆的书目检索系统自动化问题v当你想借一本参考书但不知道书库中是否有v当年你想找某一方面的参考书而不知图书馆内有 哪些这方面的书的时候，都需要到图书馆去查阅 图书目录卡片。v图书馆的各种卡片：按书名编排，按作者编排， 按分类编排，等等。v每一张卡片上的书目信息由登录号、书名、作者 名、分类号、出版单位和出版时间等若干项组成 。v在这类文档管理的数学模型中，计算机处理的对 象之间通常存在的是一种最简单的线性关系，这 类数学模型可称为线性

8、的数据结构例3.信号灯问题：为这个路口设计一个安全有效的交通信号灯的管理系统（其中C和E为单行道）。 信号灯问题分析 v分析所有车辆的行驶路线的冲突问题。v这个问题可以归结为对车辆的可能行驶方向 作某种分组，v对分组的要求：使任一个组中各个方向行驶 的车辆可以同时安全行驶而不发生碰撞。信号灯问题分析v可以确定13个可能通行方向： AB，AC，AD， BA，BC，BD， DA，DB，DC， EA，EB，EC，ED。交叉路口行驶冲突的抽象（不 能同时行驶的用线连接）信号灯问题 抽象v要求将图中的结点分组，使有线相连(互相冲突)的 结点不在同一个组里。v这个问题的解有许多“可行解”。v我们希望能够设

9、计一个最佳（分组数最少）的方 案。称作“最优解”。v这类交通、道路问题的数学模型是一种称为“图”的 数据结构。等价为对图的顶点着色问题，要求对 图上的每个顶点染一种颜色，并且要求有线相连 的两个顶点不能具有相同的颜色，而总的颜色种 类尽可能地少。 v贪心法的一个解：v(1) 红色：AB AC AD BA DC ED (2) 蓝色：BC BD EA (3) 绿色：DA DB (4) 白色：EB ECv从上面的例题可见，描述这类非数值计算问 题的数学模型不再是数学方程，而是诸如表 ，树和图之类的数据结构，因此v数据结构的研究内容为：为在计算机上解决 具体问题，应如何对所需的数据/信息及其 关系进行

10、组织（组织起来的数据就具有了结 构关系），以及如何对他们进行基本操作。v简言之，数据结构就是研究非数值计算的程 序设计问题中计算机的操作对象以及它们之 间的关系和操作等的学科。着色问题经典问题v把上图中的一个结点理解为一个国家，结点 之间的连线看作两国有共同边界，v上述问题就变成著名的“着色问题”：即求出 （最少）要几种颜色可将图中所有国家着色 ，使得任意两个相邻的国家颜色都不相同。阅读资料四色猜想v世界近代三大数学难题之一。四色猜想的提出来 自英国。1852年，毕业于伦敦大学的弗南西斯.格 思里来到一家科研单位搞地图着色工作时，发现 了一种有趣的现象：“看来，每幅地图都可以用四 种颜色着色，

11、使得有共同边界的国家着上不同的 颜色。”这个结论能不能从数学上加以严格证明呢 ？他和在大学读书的弟弟格里斯决心试一试。兄 弟二人为证明这一问题而使用的稿纸已经堆了一 大叠，可是研究工作没有进展。 v1852年10月23日，他的弟弟就这个问题的证明请 教他的老师、著名数学家德.摩尔根，摩尔根也没 有能找到解决这个问题的途径，于是写信向自己 的好友、著名数学家哈密尔顿爵士请教。哈密尔 顿接到摩尔根的信后，对四色问题进行论证。但 直到1865年哈密尔顿逝世为止，问题也没有能够 解决。1872年，英国当时最著名的数学家凯利正 式向伦敦数学学会提出了这个问题，于是四色猜 想成了世界数学界关注的问题。世界

12、上许多一流 的数学家都纷纷参加了四色猜想的大会战。1878 1880年两年间，著名的律师兼数学家肯普和泰 勒两人分别提交了证明四色猜想的论文，宣布证 明了四色定理，大家都认为四色猜想从此也就解 决了。11年后，即1890年，数学家赫伍德以自己 的精确计算指出肯普的证明是错误的。不久，泰 勒的证明也被人们否定了。v后来，越来越多的数学家虽然对此绞尽脑汁，但 一无所获。于是，人们开始认识到，这个貌似容 易的题目，其实是一个可与费马猜想相媲美的难 题：先辈数学大师们的努力，为后世的数学家揭 示四色猜想之谜铺平了道路。进入20世纪以来， 科学家们对四色猜想的证明基本上是按照肯普的 想法在进行。1913

13、年，伯克霍夫在肯普的基础上 引进了一些新技巧，美国数学家富兰克林于1939 年证明了22国以下的地图都可以用四色着色。 1950年，有人从22国推进到35国。1960年，有人 又证明了39国以下的地图可以只用四种颜色着色 ；随后又推进到了50国。看来这种推进仍然十分 缓慢。v电子计算机问世以后，由于演算速度迅速提高， 加之人机对话的出现，大大加快了对四色猜想证 明的进程。1976年，美国数学家阿佩尔与哈肯在 美国伊利诺斯大学的两台不同的电子计算机上， 用了1200个小时，作了100亿判断，终于完成了 四色定理的证明。四色猜想的计算机证明，轰动 了世界。它不仅解决了一个历时100多年的难题， 而

14、且有可能成为数学史上一系列新思维的起点。 不过也有不少数学家并不满足于计算机取得的成 就，他们还在寻找一种简捷明快的书面证明方法 。哥德巴赫猜想v1742年6月7日，德国数学家哥德巴赫在写给著名数 学家欧拉的一封信中，提出了两个大胆的猜想： 一、任何不小于6的偶数，都是两个奇质数之和 ； 二、任何不小于9的奇数，都是三个奇质数之和 。 这就是数学史上著名的“哥德巴赫猜想”。显然， 第二个猜想是第一个 的推论。因此，只需在两个猜想中证明一个就足够了 。 同年6月30日，欧拉在给哥德巴赫的回信中， 明确 表示他深信哥德 巴赫的这两个猜想都是正确的定理，但是欧拉当时 还无法给出证明。由于欧 拉是当时

15、欧洲最伟大的数学家，他对哥德巴赫猜想 的信心，影响到了整个欧 洲乃至世界数学界。从那以后，许多数学家都跃跃 欲试，甚至一生都致力于 证明哥德巴赫猜想。可是直到19世纪末，哥德巴赫 猜想的证明也没有任何 进展。证明哥德巴赫猜想的难度，远远超出了人们 的想象。有的数学家把哥 德巴赫猜想比喻为“数学王冠上的明珠”。 v我们从633、835、1055、 10039711891783、这些具体 的例子中，可以看出哥德巴赫猜想都是成立的。 有人甚至逐一验证了3300万以内的所有偶数，竟 然没有一个不符合哥德巴赫猜想的。20世纪，随 着计算机技术的发展，数学家们发现哥德巴赫猜 想对于更大的数依然成立。可是自

16、然数是无限的 ，谁知道会不会在某一个足够大的偶数上，突然 出现哥德巴赫猜想的反例呢？于是人们逐步改变 了探究问题的方式。 1900年，20世纪最伟大的数学家希尔伯特 ，在国际数学会议上把“哥德巴赫猜想”列为23个 数学难题之一。此后，20世纪的数学家们在世界 范围内“联手”进攻“哥德巴赫猜想”堡垒，终于取 得了辉煌的成果。 v20世纪的数学家们研究哥德巴赫猜想所采用的主 要方法，是筛法、圆法、密率法和三角和法等等 高深的数学方法。解决这个猜想的思路，就像“缩 小包围圈”一样，逐步逼近最后的结果。1920年，挪威数学家布朗证明了定理“99” ，由此划定了进攻“哥德巴赫猜想”的“大包围圈”。 这个“99”是怎么回事呢？所谓“99”，翻译成数 学语言就是：“任何一个足够大的偶数，都可以表 示成其它两个数之和，而这两个数中的每个数， 都是9个奇质数之和。” 从这个“99”开始，全世