教育部高校计算机科学与技术教学委员会指出 “数据结构与算法是计算机学科本科教学计划中的骨干基础课程，对学生基本的计算机问题求解能力的培养具有重要意义。作为一门必修课程，该课程既是对以往课程的深入和扩展，也是为将来更加深入学习其他专业课程打下基础。课程中所学习的排序问题的算法以及基本的树、图等数据结构，是计算机学科的基本功。B+树、散列等高级数据结构，也是数据库、操作系统、编译原理、计算机网络等后续课程的基础。”上述论述充分说明了“数据结构与算法”课程在整个计算机学科领域中的地位和意义。
计算机学科通常可以用来涵盖计算机科学、计算机技术和计算机工程3个方面，而科学性、技术性和工程性实际上是从不同侧面反映了计算机学科的本质特征，也是从不同角度和层面描述刻画和处理实现各类计算问题。数学基础的建立和数学思想方法的运用是学科科学性的重要标志。首先，对于计算机学科而言，构造性数学(如离散数学)是其主要理论的展开框架。数据结构以集合、树和图等数学概念为框架支柱，以形式化语言表述数据模型，以整体统一视野研究抽象数据类型，这些都集中体现了数学对计算机应用的指导，充分展示着计算机学科的科学性态。其次，计算机技术的灵魂是算法，在计算机技术发展过程中，发现或创立一种有效的算法通常都被视作是对计算机学科的一种实质性贡献。数据结构课程的核心内容是计算模型的建立(建立计算对象的逻辑与存储模型)、计算方法的设计和计算效率的评估，特别是其中大量充满人类智慧和科学美感的实例算法，这些对于学习者计算机技术基本素质技巧的培养和训练有着至关重要的意义，发挥着不可替代的作用。另外，计算机工程是对实际应用问题中相应科学分析结论和技术设计方案的实现，其中的基本前提就是程序设计语言复杂而灵活的运用。数据必须在计算机中进行处理，计算机处理数据的前提是数据的存储，数据存储和相应数据操作的实现需要灵活高效地操纵高级程序设计语言，因此，“数据结构与算法”课程使得学习者获得综合的体验机会和难得的训练环境。数据结构在一门课程当中自然而完美地整合了计算问题的数学分析建模、基本算法构建和基于高级程序设计语言的具体实现，从而体现出课程的重要意义和强大魅力。
教材建设是教学改革的基本组成部分，也是提高教学质量、培养高素质人才的重要前提和评估指标之一。在本书编写过程中，我们借鉴国内外优秀教材和相关材料，努力做到下述几个方面。
理念决定成败人们进行某项工作，特别是完成某些比较困难而又具有意义的工作，都需要一种内在的驱动力量，否则就难以保持坚忍不拔的意志去面对和克服出现的问题、困难与挫折。这种内在的驱动力量在日常生活中就是信仰，在学习和研究过程中就是理念。相对于其他计算机课程，“数据结构与算法”有着数学抽象性、算法多样性和程序语言实现灵活性等显著特点，这些都会让学习过程出现不少困难与艰辛。怎样在这些问题面前保持正确的理念导向，从而采取相应的积极正确应对措施呢？我们的理解是，需要从整个计算机学科的全局上明确课程的重要地位。首先，“数据结构”课程可看作是众多计算机前修基础课程的汇集处与深化点。研究数据的集合、线性表、树和图等组织形式和相互之间的关系，是“离散数学”课程的深化与扩展； 研究各种算法的设计与实现，为“程序设计语言”等课程提供各类设计方法与技巧在更高层面上和更广阔语境中的总结与升华； 研究算法的时间与空间复杂性，在具体平台上展开“计算概论”等课程中算法可行性和复杂度的基本原理，同时也为在应用环境中理解掌握“概率统计”原理方法提供实战训练。其次，“数据结构”也是计算机专业“编译原理”、“计算机网络”、“数据库技术”和“图形图像处理”等重要应用课程的基础，单就树结构来说，就有操作系统中多级菜单的层次树、算法程序设计中的递归树、数据库查询优化中的语法分析树以及数据挖掘中的决策树等。明确了所学课程对于“前驱”课程基点的升华和对于“后继”课程学习的支撑，就明确了所学课程对于专业人才培养的重要意义，从而就有助于从本质上不断增强和升华一种明确的学习理念，提升学习的内在驱动力量。
前言
数据结构基础教程(C语言)
关联主导内容学习理念和学习驱动力量的缺失还可能在于对整个学习内容茫无头绪，不明确课程“到底”讲什么、怎样讲，所涉及内容之间如何进行梳理，所学课程众多内容模块之间怎样形成“链接”。因此，本书在材料组织和内容展开等方面就特别注意突出这种关联或链接的知识建构。实际上，“数据结构”课程的要点是研究如何为数据对象建立4种逻辑组织结构： 线性表、树、图和集合，其中前三者主要是基于内存的逻辑组织形式，而集合既可以基于内存也可以基于外存。由于外存中数据组织没有像内存中具有多种形式之分，因此外存中数据集合就统称为文件。对于数据集合而言，主要采用4种存储方式： 顺序、链式、索引和散列，前两种是基于内存的，索引和散列主要基于外存(索引也可以基于内存，如基于内存的有二叉查找树，基于外存的有B+树)。基于线性表、树和图的数据操作形式多样，内容丰富，通常采用ADT进行统一描述； 基于集合的数据操作相对单纯，对于内存数据来说，主要有排序和检索，对于外存来说，主要是检索。掌握了的知识应该是理解了的知识，理解了的知识实际上就是具有清晰关联和严谨结构的知识。
细节成就品质文学作品的生命在于具体情节与生动细节。作为一门重要的专业基础课程，在明确大局、梳理关联的前提下，注重基本概念的实际区别和实现技术的关键细节就关乎到相应的学习品质，即通常所说的讲“透”或讲到“点子”上。实际上，“数据结构与算法”作为众多前修课程的深化与发展，其自身品质在很大程度上都是凭借各种算法中精细构思和程序细节而实现的，如果剥离或弱化了其中具有闪光点的细节，那就不易与“离散数学”或“程序设计”课程相区分了。这些细节可分为概念内涵细节与技术实现细节。例如，概念内涵细节就有数据项与数据记录，数据元素与数据对象，数据类型与基本数据类型、抽象数据类型，数组与顺序表的联系与区别，头结点、头指针与表头结点，串和数组为什么通常采取顺序存储，二叉树与树的联系与区别，内存中的数据表与外存中的文件等； 技术实现细节就有给定存储结构中数据插入/删除时相应指针(地址或下标)调换操作在程序设计语言(C或C++)中的具体描述和实现，栈在递归中所起到的存储工作记录的作用，循环队列在杨辉三角形显示中的作用，稀疏矩阵十字链表存储的行/列循环链表头结点与整个链表头结点，树的前序、中序和后序遍历与图的深度与广度优先遍历等。类似的细节在课程中相当丰富多彩，需要细心揣摩和认真梳理。当然，细节应当是相应内容模块的“点子”，讲细节的前提是要讲到“点子”上，需要围绕所涉及主题，通过细节将其“讲透”，注意避免枝蔓丛生，掩盖或冲淡主旨。
实例驱动兴趣如同数学课程中定理的证明过程与实例的求解描述是其核心内容一样，数据结构中的算法细致讲解与实例验证说明也是本课程的主导和灵魂，抽掉了算法讲解与实例验证，就像一本数学教材只罗列定义与定理一样失去了意义。实际上，不仅算法和实例讲解部分蕴含着课程的重点，而且更可能是课程的难点。在对相关概念与方法基本了解的基础上，只有从直观上感知，才能从本质上把握。对于学生来说，一个基于程序语言实现的重要算法的细致讲解胜过对算法原理的抽象描述，一个好的实例验证更是胜过千言万语的抽象说教。对于老师来说，一个关键细节的程序语言描述和一个恰到好处的实例说明，也会带来教学热情的骤然高涨，智慧灵感的瞬间显现。课程中的实例讲解可以分为两个部分：一是实例中体现的算法(如栈在递归中的应用实例、队列在作业排队中的应用实例以及Huffman树等重要应用实例)； 再就是算法中的实例解释验证(如各种排序和查找算法等的基本实例)。对于前一种情形，需要强化问题引入的背景分析，注重相应算法的关键点展示； 对于后一种情形，需要借鉴现有优秀教材的做法，比较详细介绍算法的图示解释，特别强调图示解释中的描述到程序设计语言的转换，同时教材中所有程序都是实际可运行的编码，以实现课程到(验证模仿型)实验的无缝连接。
本书在逻辑上可以分为两块： 基于内存的数据结构和基于外存的文件结构。前者包括数据的线性结构(第2章线性表、第3章栈与队列、第4章数组、串与广义表)、数据的树形结构(第5章二叉树、第6章树与森林)、数据的图型结构(第7章图)和数据的集合结构(第8章查找、第9章排序)； 后者包括文件的组织与查找(第10章文件)。其中，第1~4章和第10章主要由陈瑛编写，其余各章主要由叶小平编写，全书由叶小平统稿。
在教材编写与课程实践中，笔者参考了国内外众多数据结构与算法方面的优秀教材，其中大多列举在书后的参考文献中。在此，我们对这些教材的编著者表示衷心感谢。另外，在教材编写过程中，虽然有如上所述的一些基本考虑，并试图将这些考虑体现在教材的内容组织与编写当中，但限于作者水平和其他条件约束，疏漏和不周之处在所难免，希望专家学者、选用此书的教师和同学不吝赐教。
清华大学出版社计算机与信息分社的领导和编审老师给予本书编写以很大的支持与细心指导，在此也表示衷心的感谢！
本书的程序都在常规平台(如VC)上进行了验证运行。另外，本书还配有相应的学习与实验指导书供选用者参考。
本书得到华南师范大学增成学院教材立项资金资助(2011005)。
作者2012年5月
more >