前言

用计算机求解实际问题时，必然涉及数据组织及数据处理，这些正是“数据结构”课程的主要学习内容。“数据结构”课程在计算机科学中是一门综合性的专业基础课。在计算机科学中，数据结构内容不仅作为一般程序设计的必备知识，而且是设计编译程序、操作系统、数据库系统及其他系统程序和大型应用程序的重要基础。

“数据结构”课程主要的学习内容有：数据的逻辑结构描述，即表示求解问题中的数据和数据元素之间的逻辑关系；数据的存储结构设计，即将数据逻辑结构在计算机内存中表示出来；运算算法设计，即实现求解问题的功能，如设计插入、删除、修改、查询和排序算法等。

很多学习“数据结构”课程的学生都感觉数据结构比较抽象，算法理解比较困难，这很大程度上是由于没有领会数据结构的特点。首先，一个学习计算机专业的学生必须具有某种计算机语言编程能力，能够将求解问题的思路转换成计算机可以执行的程序代码，会编写基本的程序就像一个小学生识字和掌握基本的词汇一样重要；其次，必须掌握用计算机求解问题的三个层次，即提取求解问题中数据的逻辑结构、设计相应的存储结构和在存储结构上实现求解问题的算法。在设计一个算法时，先要充分理解相关的存储结构，试想一下，一个图的邻接表存储结构还没有弄清楚，如何设计一个图的遍历算法呢？所以在写算法时脑海里要准确地呈现数据的存储结构，这样才会下笔有“神”，流畅地写出正确的代码，如同小学生在掌握相当量的词汇和写作技巧后才会写出高质量的作文。

本书是作者针对数据结构课程的特点，在总结自己长期教学经验的基础上编写的。本书的“简明”性主要体现在以下两个方面。

一是内容上的简明性。本书的内容基本涵盖了最新全国计算机专业联考大纲（2018年）数据结构部分的知识点，讲授上省去了一些难度较大的应用和扩展内容，如表达式求值和迷宫问题、串的KMP算法和广义表等。

二是写作上的简明性。作者在写作时遵循“简洁如iPhone”的风格，主要体现为知识点、知识结构和算法表述简明清晰。

本书的主要特色如下。

·力求实现从C/C++语言程序设计到数据结构算法设计的无缝对接，对算法设计中用到的一些C/C++语言难点如指针、引用类型等，结合算法设计的特点予以充分的讲述。实际上，算法描述中除了引用类型属于C++，其他均采用C语言的基本语法。

·通过通俗易懂的示例简单明了地讲解数据结构解决问题的一般性思路，如一些综合性示例统一从问题描述、设计存储结构、设计基本运算算法、设计主程序和程序运行结果几方面来讲解，突出数据结构求解问题的三个层次。

·采用大量图示描述算法设计的思路，如求最小生成树的Prim算法、求图中最短路径的Dijkstra算法和各种内排序算法中都通过直观的图示，不仅描述这些算法的设计思路，而且讲解这些算法为什么这样设计的精髓。

·注重算法设计的简洁和易懂特性，同一种算法可以有多种设计方法，本书中尽可能采用简单的设计方法，如二叉排序树查找、删除等都用非递归算法来实现。

·力求归纳数据结构算法设计的通用性方法，如单链表算法设计、递归算法设计、二叉树的算法设计和图算法设计等，都相应地总结出通用求解的方法，读者只要灵活运用这些通用方法，便可以举一反三自己设计求解较复杂问题的算法。

·书中提供了大量的练习题和上机实验题，各类练习题401道，各类上机实验题118道，便于读者练习和实训。

·书中所有算法都用C/C++语言编写并上机调试，并配套有较完整的教学资源（含教学PPT和所有算法和示例源程序），读者可以从清华大学出版社网站http://www.tup.edu.cn免费下载。对于学习计算机专业的学生，直接阅读程序代码可能比看“伪码”更简明。

·本书配套有《数据结构简明教程学习与上机实验指导》（李春葆等，清华大学出版社，2018），涵盖所有练习题和上机实验题的参考答案。

·本书配套有全部知识点的教学视频，视频采用微课碎片化形式组织（含141个小视频，累计25小时），读者通过扫描二维码即可观看相关视频讲解。

全书分为9章，第1章为概论，介绍数据结构的基本概念，特别强调了基本算法设计和分析的方法；第2章为线性表，介绍线性表的概念、两种存储结构即顺序表和链表，线性表基本运算的实现算法以及线性表的应用；第3章为栈和队列，介绍这两种特殊线性表的概念、存储结构和相关应用；第4章为串，介绍串的概念、串的两种存储结构和应用；第5章为数组和稀疏矩阵，介绍数组的概念、几种特殊矩阵的压缩方法、稀疏矩阵的定义和压缩存储结构；第6章为树和二叉树，介绍树的概念和性质，二叉树的概念，二叉树的两种主要存储结构，二叉树各种运算算法设计，哈夫曼树和哈夫曼编码，特别突出了二叉树递归算法设计方法；第7章为图，介绍图的概念、图的两种主要的存储结构、图遍历算法以及图的各类应用；第8章为查找，介绍各种查找算法的实现过程；第9章为排序，介绍各种主要的内排序算法设计方法和基本的外排序过程。附录A给出了书中部分算法清单，附录B给出了全国计算机专业数据结构2017年研究生联考大纲。

本书适合作为计算机及相关专业本、专科生“数据结构”课程的教材，也适合于各类计算机考试人员参考。

本书的编写得到湖北省教改项目“计算机科学与技术专业课程体系改革”的资助，清华大学出版社给予了大力支持，许多授课教师和同学提出建设性意见，编者在此一并表示衷心感谢。

由于水平所限，尽管编者不遗余力，书中仍可能存在疏漏和不足之处，欢迎读者联系并批评指正。

编者

2018年10月