前言

当前，随着社会信息化的迅猛发展，程序设计已经成为实现信息化社会的关键技术。为此，世界各国都从国家战略层面对编程教育给出对应措施和高额经费支持。2020年11月6日，我国教育部公布了《关于政协十三届全国委员会第三次会议第3172号（教育类297号）提案答复的函》，针对全国政协委员提出的《关于稳步推动编程教育纳入我国基础教学体系，着力培养数字化人才的提案》予以回应：教育部高度重视学生信息素养提升，已制定相关专门文件推动和规范编程教育发展，培养培训能够实施编程教育的相关师资，将包括编程教育在内的信息技术内容纳入中小学相关课程。

程序设计竞赛是“编程解决问题”的比赛，发展数十年来，累积了海量的试题。将这些试题用于教学和实验中，可以系统、全面地提高学生编程解决问题的能力。程序设计竞赛所覆盖的知识体系可以概括为1984年图灵奖得主尼克劳斯·沃思（Niklaus Wirth）提出的著名公式“算法+数据结构=程序”，这也是计算机学科知识体系的核心部分。然而，程序设计竞赛的算法和数据结构与传统的教学大纲相比，已经有了很大的拓展。

程序设计解题策略是在编程解题过程中，面对非标准、非模式化的问题时，采用高级数据结构优化传统算法，发挥创造性的思维进行解题，是对解题方法的综合性、智能性和个性化的认识。

笔者编写“大学程序设计课程与竞赛训练教材”系列，旨在将程序设计竞赛的训练和程序设计类课程的教学、实验相结合，系统、全面地提高学生通过编程解决问题的能力。一方面，该系列的《程序设计实践入门》《数据结构编程实验》《算法设计编程实验》，从知识体系的角度系统论述编程解决问题的方法，其知识体系不仅覆盖传统的程序设计语言、数据结构、算法的教学大纲，而且基于程序设计竞赛进行了很大的拓展；另一方面，我们从程序设计解题策略的角度，对该系列2015年版的《程序设计解题策略》进行全面改写，对该书的前半部分的改写形成了本书。

数据结构是在程序设计语言中存储和组织数据的方式，包含3种类型：线性表、树和图。本书共16章，以面对复杂问题时如何厘清数据关系，选择适宜高效的数据结构和解题方法为背景，分别阐述线性表、树、图的解题策略。每一章基于知识体系展开为若干节，在每一节中，以实验为基本单元：首先，阐述解题策略和算法原理，给出分析和证明，以及算法的时间复杂度；然后，给出相应的程序设计竞赛试题，包括试题来源和在线测试地址、试题解析，以及带详尽注释的解答程序。我们对大学程序设计竞赛、在线程序设计竞赛以及中学生信息学奥林匹克竞赛的各类试题进行了分析和整理，从中精选出125道试题作为数据结构解题策略的实验试题。

本书共分为三篇。第一篇“线性表的解题策略”由3章组成，内容包括利用快速幂提高幂运算效率、高斯消元法，以及单调栈和单调队列。第二篇“树的解题策略”由7章组成，内容包括利用划分树查找有序数、利用线段树解决区间计算问题、最小生成树的拓展、利用改进型的二叉搜索树优化动态集合的操作、利用左偏树实现优先队列的合并、利用动态树维护森林的连通性和利用跳跃表替代树结构。第三篇“图的解题策略”由6章组成，内容包括：网络流算法，二分图匹配，平面图、图的着色与偏序关系，分层图，可简单图化与图的计数，挖掘和利用图的性质。

本书注重编程能力的培养，“实践出真知”。对于本书的使用，建议基于编程解题的实验进行案例教学或案例学习：让同学们把自己置入程序设计竞赛试题的情境之中，通过思考、讨论和上机编程来学习和实践数据结构解题策略；而在线测试系统则是同学们磨炼编程能力的平台。

本书将提供所有试题的英文原版以及大部分试题的官方测试数据和解答程序。

本书可以作为大学本科、研究生的教材，也可以作为程序设计竞赛选手的训练指导教材，还可以作为IT研发人员提高编程能力的辅导教材。

感谢在5年前发起成立ICPC训练联盟的20所大学：东北大学、大连理工大学、大连海事大学、哈尔滨工程大学、东北师范大学、东北农业大学、山东大学、中国海洋大学、中国石油大学（华东）、中国石油大学（北京）、西北工业大学、西安电子科技大学、长安大学、西安交通大学、南开大学、广西大学、新疆大学、贵州大学、郑州大学、厦门大学。现在，ICPC训练联盟已经发展成为有全国300多家大学参加，并有南亚、东南亚的大学作为观察员的学术组织。ICPC训练联盟不仅为本书书稿，也为笔者的系列著作及其课程建设提供了一个实践的平台。本书中的内容曾在ICPC训练联盟2022冬令营和夏令营上讲授。

感谢教育部-华为“智能基座”程序设计课程虚拟教研室（电子科技大学主持）、泉州信息工程学院、头歌教学研究中心组织ICPC训练联盟2022夏令营，使本书的书稿在实战中得到了改进。感谢华东交通大学的周娟教授，她在ICPC训练联盟2022冬令营和夏令营中担任主讲。

特别感谢这些年来和我们风雨同舟、并肩作战的海内外同仁，在大家的共同努力下，大学程序设计课程与竞赛训练教材的建设、相应课程的建设，以及跨校、跨区域的教学实验体系的建设得以逐步完善。

本书获得复旦大学计算机学院专著和教材出版资助。

由于时间和水平所限，书中难免存在缺点和错误，表述不当和笔误也在所难免，恳请学术界同人和读者指正。如果您在阅读中发现了问题，恳请通过电子邮件告诉我们，以便我们在课程建设和再版时进行改进。我们的联系方式如下。

通信地址：上海市邯郸路220号复旦大学计算机科学技术学院吴永辉（邮编：200433）

电子邮件：yhwu@fudan.edu.cn

吴永辉 王建德

2022年12月1日于上海

注：本书试题的在线测试地址如下。