前言

“数据结构”是计算机科学与技术专业、软件工程及相关专业的核心课程之一，是计算机科学与技术、软件工程等专业研究生考试必考科目之一，也是IT公司面试或笔试考核的主要内容。数据结构主要分析计算机中数据组织的方式和相关操作算法，涉及数据结构和算法的基本概念与技术，线性表、栈、队列、串、数组与广义表、树、二叉树、图等常用数据结构及相关算法，以及排序、查找等重要技术。本课程既是对前导的程序设计类课程、离散数学等课程的深入和拓展，也为继续深入学习数据库、操作系统、编译原理、计算机网络等后续专业课程打下了重要基础。

“数据结构”是一门直接面向实际应用、解决实际问题的课程，它的教学目标是，让学习者学会从问题入手，分析研究计算机加工的数据结构的特性，以便为应用所涉及的数据选择适当的逻辑结构、存储结构及其相应的操作算法，并初步掌握时间和空间分析技术。

笔者从事“数据结构”课程的教学已有二十多年，深切了解学习者对于学习“数据结构”课程的普遍体会是，概念难理解、算法难设计、编程难实现、知识难应用。如何帮助学习者实现两个跨越：从实际应用问题到数据结构抽象的跨越和从数据结构概念到程序实现的跨越，是我们一直努力的目标。近年来，我们以“问题导学”模式进行了该课程教学的探索和实践，本书是这些工作的成果。

“问题导学”模式是以问题解决为主线，以学生学习为主体，使学生在解决问题的过程中掌握知识，形成自主学习能力的一种教学模式。该模式的具体过程是：引导学生分析问题中的已知信息，提炼数据及数据之间的关系（数据的逻辑结构），选择合适的存储方式（数据的存储结构）将待处理的数据保存到计算机中，然后在存储结构之上按照自顶向下逐步细化的方法设计算法，给出程序实现，并进行测试和调试分析。

本书的每一章以若干典型的导学问题为主线贯穿组织，由“知识学习”“知识应用”和“知识拓展”等部分组成。围绕导学问题，引导学习者思考问题、对实际问题进行抽象建模、实现模型和应用模型。与高级程序设计语言课相比，数据结构在培养学生的数据抽象能力方面有着更高的要求，通过本书不同层次的导学问题示例培养学生逐步掌握数据抽象的能力，学会数据结构和数据类型的使用方法，为今后的学习和提高编程水平打下扎实的基础。

本书以学生学习为主体，在内容的组织和选材上指导学生通过思考、比较、建构，逐步形成学生自己的知识框架，并发展相应的能力。为此，本书在每一章开头设置了学习导图，指导学生体验思考问题、初步解决问题、进一步解决复杂问题这一学习过程。每章学习过程中设置了一些书写填空题，让学生不仅耳动起来、嘴动起来，还要手动起来，真正成为课堂的主人，积极主动地进行学习和思考。每章课后安排的思考与练习、应用实战让学生能够进行达标检测、巩固知识、查漏补缺。

本书以学生学习为主体，还体现在重视对学生进行复杂程序设计的训练，指导学生书写符合软件工程规范的文件，编写结构清晰、正确易读的程序，上机调试并排除错误代码等。全书采用C语言作为数据结构和算法的基本描述工具，同时采用了C++对C的非面向对象的增强功能。例如，输入/输出采用了cin、cout运算符，函数参数传递采用了引用、动态分配和释放，存储结构采用了new和delete运算符等。这些措施使得数据类型的定义和数据结构相关操作算法的描述更加简明清晰，可读性好，易于学习掌握。学习者也可把类型定义和操作算法稍加处理，这样就很容易将其封装成类，并进一步转化成面向对象的程序。全书算法和导学问题的源程序使用Visual C++ 6.0集成环境完成并提供下载。

本书在内容组织和设计上进行了创新，一方面可以帮助学习者把学习的新知识形成网、织成块、用起来；另一方面，也对教师有效地组织课堂教学提供了便利。教师可以根据教材资源，对学习者进行问题引导、疑难精讲、质疑点拨、检测评估。

本书由于泠和陈波执笔完成。全书共9章，第1章简要介绍数据结构和算法的基本概念；第2～4章介绍了线性结构及其算法，包括线性表、栈和队列、串；第5～7章介绍了非线性结构及其算法，包括矩阵和广义表、树和二叉树、图；第8章介绍了常用的查找算法；第9章介绍了常用的排序算法。本书可作为计算机专业、软件工程专业及其他相关专业“数据结构”课程的教材以及研究生入学考试辅导书，也可供计算机软件开发人员或编程爱好者参考和使用。

本书作为江苏省高等教育教学改革重点课题：面向社会化学习的移动虚拟学习社区建设和应用研究（2015 JSJG034）、南京师范大学教改重点项目：以计算思维为导向的信息与计算科学专业实践教学研究与探索、南京师范大学重点教材建设项目：数据结构导学教程（C/C++版），已经建成了包含本课程教学课件、实验指导、习题解答、算法源程序、参考资料等资源。读者可登录http://www.cmpedu.com下载本书配套资源。读者可以使用移动设备的相关软件（如“QQ”）中的“扫一扫”功能扫描书中提供的二维码，在线查看问题提示或解答。如果 “ 扫一扫 ” 后在微信端无法打开文档 ， 请选择用手机浏览器直接打开 。移动设备的相关软件，请从Android市场或苹果App Store等进行下载安装。

在编写本书的过程中，查阅和参考了大量的文献和资料，限于篇幅，未能在书后的参考文献中全部列出，在此一并致谢。

由于编者水平有限，书中难免有疏漏之处，恳请广大读者批评指正。读者在阅读本书的过程中若有疑问，也欢迎与作者联系，电子邮箱是：SecLab@163.com。

编者