数据结构课程设计

　　本书将数据结构课程设计与数据结构理论课程有机结合，以传统数据结构的主要内容为主线，精心设计多个案例。在描述各个案例的同时，采用三元式(D，S，P)的方式，完成对线性表、栈、队列、字符串、广义表、二叉树、图、集合等抽象数据类型的定义、描述和封装。这些基本数据结构类型不仅应用于教材中的各个案例，也可将之作为工具或平台，复用于其它应用中。

　　本书中每一个算法或程序的编写力求高效、易读。并遵循程序设计的规范，从而能够帮助读者顺利完成学习、模仿、提高、应用的过程。

　　本书可作为计算机类专业数据结构课程设计教材，也可作为学习数据结构及其算法的C程序设计的参考教材，还可供从事计算机应用工作的相关人员参考

　　一、概述

　　数据结构的概念*早由C．A．R．Hoare于1966年提出。在他的经典论文《数据结构笔记》中，首次系统地论述了一组数据结构的构造、表示和操作等问题。1973年，D.E.Knuth在《计算机程序设计技巧》*卷中给出了关于“信息结构”的系统论述。1976年，N.Wirth用“算法 数据结构=程序”这个公式表达了算法与数据结构的联系及它们在程序设计中的地位，从此确立了数据结构在计算机相关专业中的核心基础课程地位。

　　“数据结构”是一门关于非数值数据在计算机中表示、变换及处理的课程。这里的数据实质是指计算机所能表示的各种不同数据对象的集合。对于每一具体的数据对象，通常其数据元素之间的关系不是孤立的，数据元素之间的内在联系被称为结构。从数据元素之间的关系特征分析，各种数据对象中的数据元素之间的关系仅呈现以下四种结构之一：集合结构、线性结构、树形结构、图形结构。

　　历经40多年的发展，“数据结构”课程的主要讨论范畴已基本取得共识。尽管计算机应用领域仍在不断地扩大并产生了许多新的数据结构和算法，但“数据结构”课程*基本和*核心的内容还是讨论上述四种结构在计算机中表示、变换和处理的过程。2006年，教育部高等学校计算机科学与技术教学指导委员会编制了《高等学校计算机科学与技术专业发展战略研究报告暨专业规范》。其中，算法与数据结构涉及AL1、AL2、AL3、AL4、AL5、PF2、PF3、PF4等多个知识单元，知识点包括：基本数据结构(包括：堆栈、队列、链表、哈希表、串、数组和广义表、树型结构及应用、图型结构及应用)、递归、常用排序算法、常用查找技术、算法分析基础等。2009年，教育部考试中心制订了全国硕士研究生入学统一考试关于“数据结构”科目的考试大纲。以上内容通常构成了编写数据结构相关教材的大纲依据。

　　没有不包含数据结构的程序！显然，数据结构还应是一门兼具理论性与实践性的课程。在理解数据结构的基础上，运用数据结构加强并提高程序设计的能力显得尤为重要。因此，“数据结构课程设计”这门课程应运而生。

　　二、教材的特色

　　鉴于授课对象的高级语言基础，教材主要选用C语言作为描述算法或程序设计的工具。同时，为增强语言的描述功能，对传统C做了若干扩充。如：在算法或程序的编写中使用了程序设计语言C 的引用调用&，动态内存分配、释放语句new、delete，输入输出流cin、cout等。读者在学习时请注意甄别。

　　本教材以传统数据结构的主要内容为主线，强调数据结构的应用。在每一章节中设计多个案例，且在每一案例的描述过程中，依据以下步骤循序渐进展开讲解。

　　【需求分析】

　　对课程设计题目进行充分的描述，阐明选题的目的及意义。

　　【概要设计】

　　对课程设计题目中数据对象的逻辑属性予以充分的认知，并为之设计解题的抽象数据类型，简述解题的方法。

　　【详细设计】

　　选择合适的存储结构实现各个基本操作，封装抽象数据类型；描述解题的算法，编写解题的程序。

　　【调试分析】

　　讨论解题的要点、难点，思考并比较解题的不同算法，运用时间、空间的分析手段分析算法的合理性及准确性。

　　【测试运行结果及用户手册】

　　说明程序的使用方法，列出测试的输入输出数据，使面对苛刻的、刁难式的测试数据程序也能正确运行。

　　【附录】

　　源程序文件名清单。

　　本书将数据结构课程设计与数据结构理论课程有机结合。在描述各个案例的同时，采用三元式(D，S，P)的方式，完成对线性表、栈、队列、字符串、广义表、二叉树、图、集合等抽象数据类型的定义、描述和封装。借助于这些基本数据结构类型，不仅实现了教材中的各个案例，也可将之作为工具或平台，复用于其它应用中。

　　书中每一个算法或程序的编写力求高效、易读并遵循程序设计的规范，从而能够帮助读者顺利完成学习、模仿、提高、应用的过程。

　　本教材中的所有案例的源程序均可通过扫描二维码或登录出版社网站(www.xduph.com)获取。

　　三、结束语

　　本书作为与理论课程“数据结构”配套的实践课程“数据结构课程设计”的教材，希望读者通过学习，既能更好地认知数据结构的理论，又能更好地运用数据结构提高程序设计的能力。但限于能力和经验，书稿虽经多次修改，仍难免存在缺陷，恳请读者予以批评指正。

　　编者

　　2017年6月