第2版前言

在确定完稿的时刻，严老师那熟悉的音容笑貌浮现在眼前。我默默地祈盼: 严老师，请在天堂给咱们新书把关！近些年，她一直希望在我放下那繁重的科研、教学和行政工作退下来后，一起修编《数据结构》(C语言版)和《数据结构题集》(C语言版)这套教材。在2024年春节前，和清华大学出版社商定后我们启动了这项工作。

起初的重点是录制一套严老师讲授的微课。在严老师长期积累的网课脚本基础上，我全时投入编制PPT动画。严老师审查这些PPT和录制的微课视频样片的同时亲自撰写讲稿。在这过程中，我们也形成对教材算法和内容更新的共识，同步展开修编工作。正当与清华大学出版社协调配合严老师录音录像的时候，也就是从2024年8月中旬起，严老师和我的微信由几乎每天多次渐渐减少了。到了11月初，她和我说: “前一阵子跑医院较多，工作都停了下来……”在11月25日的微信: “磨蹭了那么多天，我很抱歉，刚签合同时我还信心百倍以为还能在这世上留下我的声音，可没想到最近这两个月我的病情会发展得那么快……”11月30日最后的微信: “你要有新的文稿可以发给我，但恐怕起不了审稿的作用了。”我顿时泪如雨落，痛哭不已。12月10日不幸消息传来，严老师驾鹤西去，和我们永别了！

我非常自责自己未能更早投入这项工作，给世间留下严老师宝贵的授课音像！让她能亲眼看到这套新版教材出版发行！

严老师年近90岁高龄仍生命不息、奋斗不止的敬业精神永远激励我前行。

在严老师家人和清华大学出版社支持下，5个月来我按照严老师确认的教材算法和内容更新计划以及已做的工作，全力以赴，现在终于完稿了。接下来还要修编题集。而微课，自觉能力还难以胜任，更替代不了严老师，故暂不制作。但按照严老师生前的建议和指导，决定把AnyviewC可视交互教学软件引入这套新版教材: 一是支持对书中算法的可视交互跟踪运行和观察数据结构形态的即时变化动画，帮助读者直观理解算法和数据结构原理；二是支持对题集的算法设计题的可视交互调试和测评，帮助做题者提速增效完成编程作业。

从2000年起，严老师就一直关注我做的AnyviewC，认为是她20世纪90年代初主持研发的数据结构算法演示系统的最好延伸。多次对曾因各种原因中断了AnyviewC的开发和推广表示惋惜。在做微课的时候，她时常和我说，要继续AnyviewC的发展，要用起来，应该比微课的作用还大，甚至比修编教材更有意义。

新版教材删除第2章的静态链表等少量内容。新增或修订了堆(优先队列)、并查集、二部图、红黑树、跳跃表、B+树、布隆过滤器等内容，并且详尽讨论存储结构的定义和相关算法的实现。

改用纯C语言作为描述语言，算法都用可编译运行的源代码描述。在AnyviewC为算法提供测试运行的main函数和数据结构类型的实现代码，读者可直接打开源码文件，编辑(修改)、编译和可视交互运行。

加强了对数据存储结构的内存分配、回收和管理的讲解，更新了类型定义和基本操作实现。全书的数据结构的实现都支持所分配的内存完整回收，不发生内存泄漏。

对全书原有算法进行的优化更新主要如下。

 优化了最小生成树、最短路径、关键路径的表示形式(存储结构)和输出算法。

 用堆和并查集等数据结构优化了赫夫曼树、最小生成树、最短路径、关键路径等算法。

 新增或实现一批主要算法——C库函数串复制和比较算法，短串的留子串算法，稀疏矩阵(十字链表)加法算法，递归构建m元多项式广义表算法，组建二叉树算法，替换右子树算法，图的邻接表构建算法，求强连通分量算法，求最小生成树克鲁斯卡尔算法，平衡二叉树删除算法，B树插入算法的完整实现，B树删除算法，B+树的查找、插入和删除算法，双链键树的初建和插入算法，Trie树的初建和插入算法，若干散列函数，拉链散列表的初建、查找、插入、删除和重建算法，开放定址散列表的删除和重建算法，布谷鸟散列表初建、查找、插入和重建算法，非顺序索引文件的创建、查找、插入和删除算法，支持全文检索的散列倒排索引的构建算法，等等。

从1983年开始，我跟随严老师进行数据结构系列教材及教学软件建设42年，有些版本的教材和软件曾在海外发行，获得“第二届普通高等学校优秀教材全国特等奖”和“1996年度国家科学技术进步奖三等奖”。严老师“把教材建设作为科研来做”的从严治学风范引领和培养了我，令我终身受益。

20世纪80年代前期，只有少数部属院校开办计算机本科专业，国内刚开始开设数据结构课程，且大多采用国外教材或编译的讲义。清华大学是极少数具有上机实习条件的院校。我到清华大学进修时唐泽圣主任给了我难得机会，有幸成为严老师的助教，每周严老师批改了我提前完成的作业之后，我再批改全班的作业，在实验室指导学生的上机实验，并向严老师提交学生作业和实验情况分析周报。严老师还让我给全班上习题讲评课。同时我整理和编写了一批习题和实习题及其参考答案，并在机房完成了参考答案算法的调试。临近期末我交给严老师一份题集及答案汇编。她非常惊喜，让我多待半年，一起编写教材。第二个学期，在编写数据结构教材的同时，还协调安排我给蒋国南老师做编译原理课程的助教，得到可随时进实验室用计算机的机会。我当时只觉得是一个难得的学习提高的机会，要好好珍惜。但严老师将我视为“合作者”，作为第二作者署名，这为我带来了一系列奖励和荣誉。

1994年我从国外做公派高级访问学者回来，向严老师汇报与Pascal语言作者、图灵奖得主N. Wirth教授交流情况和国外已出现C语言替代Pascal语言的趋势。她当即决定启动C语言版教材的编写。这一次是她来到广州，得到我所在学校教务处领导大力支持，安排住在外教公寓。严老师夜以继日修编全书文字内容，我编写测试数据存储结构的C语言定义和算法实现。因受熟悉好用的Pascal语言变量形参的影响，选择了在C语言中添加C++类似的引用形参。如果有同行或读者质疑这一做法，这责任全在我。

1998年秋我申请到清华大学严老师工作室做访问学者。我们完成了C语言版题集的撰写，并将数据结构算法演示系统移植为C语言版。

借此机会，对之前的几版教材省略算法中的变量声明和简化描述语言的做法也做一个说明。20世纪80年代到90年代，我国高校的计算机专业属于“精英”教育阶段(2003年前后的大扩招之后，进入了“普及”教育阶段)，而且实验用机比较紧缺，学生上机实验机时不多。因此，算法表述尽量简明，学生算法设计主要形式是提交书面作业，老师改本子。同期的国外主流教材也大多采用伪代码描述算法，所以这是符合当时的实际情况的。而现在的学生或读者都有自己的台式计算机或笔记本计算机。在新版中，直接采用C语言作为描述语言，算法都是可直接编译运行的代码。

进入2000年之后，严老师的主要精力放在了网课建设和主持某些全国统考每年的数据结构命题。而我本想以上面提及的AnyviewC的研发及理论模型作为科研选题，继续参与这套教材和软件的后续建设，申报了国家自然科学基金项目。专家回馈意见中，认为有难度和创新，值得支持的意见未过半；其他意见则分别是“国外还没有，不适合立项”“难度大，不可能做出来”“难度和工作量都很大，难以完成”。得不到科研立项，只能选择别的研究课题，这也得到严老师的理解。除了每年参加严老师主持的教育部考试中心的命题，我就抽不出时间从事教材工作了。我们也曾有过Java版的初稿，最终也遗憾没有定稿出版。

本套教材得以持续出版，累计发行量超千万册，并一直是研究生入学统考科目的主要参考教材，除了严老师在数据结构界的地位和影响之外，内容覆盖全面也是重要原因之一。从20世纪80年代至今，出国留学者行囊中几本书里大多有这本《数据结构》，从事专业工作的毕业生也大多把书留在案头作为重要工具书。一本专业基础教材不应限于课时或办学层次而减缩内容，应能支持学生或读者在课程之后对可持续学习提高和应用参考的需求。在新版中，除了少量调整，基本保留了全部内容，但对算法进行了全面优化和扩展。保持递归和非递归算法的适当比例，并适当加强对非递归算法实现的讨论，以适应实际应用，特别是追求时效的大数据应用的需求。新版的另一项重要工作是适当增补了近年“热门”内容，尤其是注意与大数据的对接，以更全面的内容供计算机大类的不同专业各有合适的选择。

各类不同层次院校都可选用本套新版教材，根据实际情况选择授课内容即可，可尝试用AnyviewC支持教学过程。像图的那些“大”算法，以及AVL树、红黑树、B树和B+树等较复杂的插入和删除算法可不在课堂细讲，选定一些让学生在AnyviewC进行可视交互学习。

对于备考研究生的读者，本套教材更是适合复习、自学和自测。

数据结构的发展仍在继续，各种需求不断涌现。数据结构课程内容应包括基础必修部分和面向专业方向的专业基础部分。课程教学方式则应提倡“提速增效”原则，可尝试选择随书提供的AnyviewC进行可视交互学习，把算法的抽象和结构“看不见”转化为算法的行为细节及其对结构的作用效果实时可见，以提高算法学习和做题的时效。

AnyviewC起步于1993年，当时我在国外担任高级访问学者。在向国外同行介绍严老师组织开发的数据结构算法演示系统(Pascal版)的时候，他们都认为对数据结构教学很有帮助。有位教授提出，是否考虑过发展为能对输入的任意算法也能演示？这激励我开始考虑挑战这一难题。当年给蒋国南老师做编译原理助教时，我指导学生的课程设计就是对N. Wirth的一个Pascal子集的教学型编译程序进行扩充。在回国前，花了3个月对该程序进行扩展，实现了一个初具可视化运行功能的可视虚拟机原型。在C语言版教材出版后，又移植为AnyviewC，并申请了两个软件著作权证书。但这都属于业余习作，各种原因未能得到科研立项，也不是商业软件。虽然在广东工业大学等院校的数据结构、C语言程序设计、离散数学等课程已使用了20年，也还需要继续完善。随新版主教材和题集供读者选择试用，既是得到严老师生前的鼓励认可，也因为教材的算法基本都能在其上可视交互运行，也确实帮助我大大加快了这次优化和添加算法的进度。或许很快就会有大模型也具有这样的可视交互功能，甚至更强。不过我把这次添加的一些新算法(线上线下未能查到的)“求助”多个顶流AI大模型，基本都还得不到完全正确的代码。但它们的学习能力还是很强，多次交互指出它们的不足后，都有所进步。就这一结果而言，AI目前可能还处于“懂的都懂，不懂的还基本不懂”的状况，还取代不了编写有新意代码的程序员工作。

限于本人的能力，新版教材的编写难免有疏漏或错误。敬请各位专家、老师、同行和读者批评指正！

吴伟民广东工业大学计算机学院

2025年4月20日凌晨3时于广州第1版前言

　　数据结构是计算机程序设计的重要理论技术基础，它不仅是计算机学科的核心课程，而且已成为其他理工专业的热门选修课。本书是为数据结构课程编写的教材，其内容选取符合教学大纲要求，并兼顾学科的广度和深度，适用面广。

    本书的第1章综述数据、数据结构和抽象数据类型等基本概念；第2～7章从抽象数据类型的角度，分别讨论线性表、栈、队列、串、数组、广义表、树和二叉树以及图等基本类型的数据结构及其应用；第8章综合介绍操作系统和编译程序中涉及的动态存储管理的基本技术；第9～11章讨论查找和排序，除了介绍各种实现方法之外，并着重从时间上进行定性或定量的分析和比较；第12章介绍常用的文件结构。用过《数据结构》（第二版）的读者容易看出，本书内容和章节编排与1992年4月出版的《数据结构》（第二版）基本一致，但在本书中更突出了抽象数据类型的概念。对每一种数据结构，都分别给出相应的抽象数据类型规范说明和实现方法。

    全书中采用类C语言作为数据结构和算法的描述语言，在对数据的存储结构和算法进行描述时，尽量考虑C语言的特色，如利用数组的动态分配实现顺序存储结构等。虽然C语言不是抽象数据类型的理想描述工具，但鉴于目前和近一两年内，“面向对象程序设计”并非数据结构的先修课程，故本书未直接采用类和对象等设施，而是从C 语言中精选了一个核心子集，并增添C++语言的引用调用参数传递方式等，构成了一个类C描述语言。它使本书对各种抽象数据类型的定义和实现简明清晰，既不拘泥于C语言的细节， 又容易转换成能上机执行的C或C++程序。

　　从课程性质上讲，数据结构是一门专业技术基础课。它的教学要求是： 一方面，学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及其相应的算法，并初步掌握算法的时间分析和空间分析的技术。另一方面，本课程的学习过程也是复杂程序设计的训练过程，要求学生编写的程序结构清楚和正确易读，符合软件工程的规范。如果说高级语言程序设计课程对学生进行了结构化程序设计（程序抽象）的初步训练，那么数据结构课程就要培养他们的数据抽象能力。本书将用规范的数学语言描述数据结构的定义，以突出其数学特性，同时，通过若干数据结构应用实例，引导学生学习数据类型的使用，为今后学习面向对象的程序设计做一些铺垫。

　　本书可作为计算机类专业的本科或专科教材，也可以作为信息类相关专业的选修教材，讲授学时可为50～80。教师可根据学时、专业和学生的实际情况，选讲或不讲目录页中带**的章节，甚至删除第5、8、11和12章。本书文字通俗，简明易懂，便于自学，也可供从事计算机应用等工作的科技人员参考。只需掌握程序设计基本技术便可学习本书。若具有离散数学和概率论的知识，则对书中某些内容更易理解。如果将本书《数据结构》（C语言版）和《数据结构》（第二版）作为关于数据结构及其算法的C和Pascal 程序设计的对照教材，则有助于快速且深刻地掌握这两种语言。

　　与本书配套的还有《数据结构题集》(C语言版)，由清华大学出版社出版。书中提供配套的习题和实习题，并可作为学习指导手册。

严蔚敏清华大学计算机科学与技术系

吴伟民广东工业大学计算机学院