数据结构的产生和发展.doc

第1章 绪 论 计算机是处理信息的机器。数据结构不仅研究这些信息的数学性质，也关心如何在计算 机屮有效地存储和处理这些信息。当今，随着计算机信息量的增加，信息范囤的拓宽和信息 结构复杂化的加深，为了编写出高质量的稈序，还必须分析这些信息的特征以及它们Z问存 在的关系。稈序设计的实质就是为确定的问题选择一种适当的数据结构并设计一个好的算 法。 本章介绍数据结构的基木概念与基木术语。要求掌握这些概念和术语，为后续章节的学 习与理解打下基础。 1?1数据结构的产生和发展 数据结构是随着电了计算机的产生和发展而发展起来的一门计算机学科。最近20年来， 电了计算机技术飞速发展，这不仅体现在计算机木身运算速度的不断提高、信息存储量II益 扩大、而且更重要的是其应用范围的扩展。 早期的电子计算机主要用于科学计算，所处理的对象是纯数值性的信息。这类问题解题 的算法比较复杂，但数据量较少，结构也简单。因此，计算机科学是以研究程序及所描述的 算法为屮心。 目前，计算机已广泛地应用于情报检索、事务管理、系统工程等领域。与此相应，计算 机加工处理的对象也从简单的纯数值性信息发展到数，字符，字符串，表，文件，图像，声 音等各种复杂的，具有一定结构的数据。人们称前者为数值问题，而后者为非数值问题。 非数值问题要求用复杂的数据结构来描述系统的状态，它们的运算是实现对数据结构的 访问或修改。当前要设计出效率高，可靠性强的非数值程序，要求程序设计人员不但要掌握 一般的程序设计技巧，而且还必须研究计算机程序加工的对象 即研究各种数据的特性以及 数据Z间的关系，这就促进了数据结构这一学科的发展。然而，数据必须在计算机屮进行处 理，因此，不仅要考虑数据木身的数学性质，还必须考虑数据在计算机内的存储方式和相应 的运算，从而扩大了数据结构研究的范围。随着数据库系统、情报检索系统的不断发展，在 数据结构的技术屮又增加了文件结构，特别是增加了大型文件的组织和B树、B+树的知识, 使得数据结构逐步成为了一门比较完整的学科。 数据结构是计算机以专业及其相关专业木、专科生必修的核心课稈，是研究计算机稈序 设计的重要理论和技术的专业基础课稈。 什么是数据结构 什么是数据结构 什么是数据结构呢？先举一个简单的例了予以说明，然后再给出明确的定义。 假定有一个职工通信录，记录了某单位全体职工的姓名和相应的住址，现要求设计一个 算法：当给定某一位职T的姓名时、计算机能够查出该职工的住址，如果根木就没有这个人, 计算机也能报告“杏无此人”。 这种任务称为“杏找”。我们可以发现，这个算法的设计完全依赖于通信录中职工姓名 和相应住址在计算机内的存储方式。 一种方法是通信录中职T的姓名是随意扌非列的，其次序没行任何规律。那么，当给定一 个姓名时，就只能从通信录的第一个姓名开始，逐个与给定的姓名进行比较，直至找到指定 的姓名，接着打印出他的住址，或者杳完整个通信录还没找到此人、这时应给出相应的标志,这种方法很简单，当职工人数较少时是可行的、但对于一个大单位来说，就相当费时间，效 率太低。 然而，我们可对职T通信录进行适当的组织，如图1.1(b)所示，即按字母的顺序排列姓 名和相应的住址，而且还可以再构造一个索引表，用这个表来登记姓名屮每个具有相同开头 字母的第1个姓名在通信录屮的起始位置，见图1.13)。这样情况可大为改善。这时，若杏 找某个职工，例如，查“Min Rui”的住址，则可先从索引表屮找到以“M”开头的姓名的 起始位置，然后，就从此位置开始住下顺序查找，而不必去查看其他字母开头的职工姓名。 由于采用了新的结构，于是，可以设计出一个完全不同的算法。 A1B1811 a iM907111 a索引 指针(a)索引表Ai Xiaoming 艾小明 A 1 B 181 1 a i M 9071 1 1 a 索引 指针 (a)索引表 Ai Xiaoming 艾小明 中山路 1036 号 An Ji ng安静 中北路 128号 1 a i 1 a i Ban Lili班莉莉 南三街 72号 Bao Changqing 包长青 东一路 89号 Bi Zhenghua 毕正华 北大街 101号 1 a i 1 I 1 Ma Xiaoshan 马小山 西小巷 51号 Mi Gu米谷 东方大道 甲1号 Min Jie闵洁 大红门 3号 Min Rui闵锐 南市口 227号 1 1 1 1 1 1 姓名 住址 I II 181 191 201 9071 9081 9091 9101 (b)职工通讯录 图1.1职工通信录在计算机屮的存储 上述职工通信录的组织方式问题就是一个数据结构问题.两种不同的数据结构，得出两 个完全不问的算法。由此可见，计算机的算法与数据结构密切相关，即每一个算法无不依赖 于具体的数据结