数据结构实验教程——C语言描述

（1）根据“数据结构”课程的核心知识点，按章对应编写。（2）各章包括基本知识点、内容要点及实践部分，以期帮助读者在尽可能短的时间内，对数据结构的知识与应用有一个比较全面和系统的认识，为进一步提高学生的应用编程能力在方法上提供指导。（3）本书所有程序都给出了完整的源代码，并在Microsoft Visual C 6.0下运行通过。（4）本书配套课程设计教材：《数据结构课程设计——C语言描述（第2版）》 ISBN 978-7-121-29645-1。 

本书是“数据结构”课程的实验教材，可与《数据结构》（C语言实现）相关主教材配合使用。全书共10章，其内容涵盖了数据结构课程中的全部重要知识点及主要基础实验。第1章实验概述，主要介绍了数据结构的基本术语及C语言的实现架构等；第2章～第10章，详细讲解了“数据结构”课程的核心知识点，每章由基本知识点、内容要点及课程实践三部分组成，其中实践部分给出了实验算法的参考程序，目的是帮助学生养成良好的程序设计风格及素养，逐步提高分析问题和解决问题的能力。 本书是在作者多年讲授“数据结构”课程及指导学生上机实践，积累了丰富的知识与经验的基础上编写而成的，算法力求精湛和规范。所有程序都给出了完整的源代码，并在Microsoft Visual C 6.0下运行通过。 本书适合计算机及其相关专业的学生学习“数据结构”课程上机实践使用，对软件开发爱好者也是一本很好的参考书。

阮宏一，教授，1982年至今，先后在湖北教育学院数学系、湖北教育学院计科系、湖北第二师范学院计算机学院任教。湖北高等学校计算机学会会员，《数据结构》校级精品课程负责人。曾出版过《数据库系统概论》、《数据结构C/C 描述》、《数据结构实践指导教程（C语言版）》、《C程序设计实训教程》、《Visual FoxPro 程序设计实训教程》、《大学计算机基础》、《大学计算机基础实训教程》、《数据结构课程设计（C/C 描述）》等多部教材。

第1章 实验概述
　　1.1 数据结构的基本概念与C语言的实现
　　　　1.1.1 数据元素
　　　　1.1.2 数据与数据对象
　　　　1.1.3 数据结构
　　　　1.1.4 数据类型
　　　　1.1.5 抽象数据类型
　　1.2 问题的求解与C语言的实现架构
　　　　1.2.1 问题的求解与实现
　　　　1.2.2 C语言的实现架构
　　　　1.2.3 应用程序主菜单的设计
　　1.3 C语言实现的相关技术
　　　　1.3.1 程序设计的原则
　　　　1.3.2 数据基本属性与数据处理
　　　　1.3.3 数据结构与算法
　　　　1.3.4 数据结构的C语言描述
第2章 线性表
　　2.1 内容要点
　　　　2.1.1 线性表的定义及基本运算
　　　　2.1.2 线性表的存储结构
　　2.2 线性表的实践
　　　　2.2.1 顺序表的实践
　　　　2.2.2 单链表的实践
　　　　2.2.3 双向链表的实践
第3章 栈和队列
　　3.1 内容要点
　　　　3.1.1 栈
　　　　3.1.2 队列
　　3.2 栈的实践
　　3.3 队列的实践
第4章 串
　　4.1 内容要点
　　　　4.1.1 串的定义及基本运算
　　　　4.1.2 串的存储结构
　　4.2 定长顺序串的实践
　　　　4.2.1 定长顺序串的存储结构
　　　　4.2.2 定长顺序串的实验
　　　　4.2.3 参考程序
　　4.3 堆串的实践
　　　　4.3.1 堆串的存储结构
　　　　4.3.2 堆串的实验
　　　　4.3.3 参考程序
第5章 数组和广义表
　　5.1 内容要点
　　　　5.1.1 数组
　　　　5.1.2 特殊矩阵、稀疏矩阵
　　　　5.1.3 广义表
　　5.2 数组的实践
　　5.3 稀疏矩阵的实践
　　5.4 广义表的实践
第6章 树和二叉树
　　6.1 内容要点
　　　　6.1.1 树
　　　　6.1.2 二叉树
　　　　6.1.3 树与二叉树的相互转换
　　　　6.1.4 哈夫曼树
　　6.2 二叉树的实践
　　　　6.2.1 顺序存储结构的实验
　　　　6.2.2 参考程序
　　　　6.2.3 链式存储结构的实验
　　　　6.2.4 参考程序
第7章 图
　　7.1 内容要点
　　　　7.1.1 图的定义及基本运算
　　　　7.1.2 图的存储结构
　　　　7.1.3 图的遍历
　　　　7.1.4 图的应用
　　7.2 图的实践
　　　　7.2.1 图的建立及遍历
　　　　7.2.2 图的应用实践
第8章 查找
　　8.1 内容要点
　　　　8.1.1 查找的基本概念
　　　　8.1.2 顺序查找
　　　　8.1.3 折半查找
　　　　8.1.4 分块查找
　　　　8.1.5 二叉排序树查找
　　　　8.1.6 平衡二叉树查找
　　　　8.1.7 哈希表查找
　　8.2 查找的实践
　　　　8.2.1 基于线性表的查找
　　　　8.2.2 基于树结构的查找
　　　　8.2.3 基于计算的查找
第9章 内部排序
　　9.1 内容要点
　　　　9.1.1 排序的基本概念
　　　　9.1.2 记录序列的存储方式
　　9.2 内部排序的分类
　　　　9.2.1 插入排序
　　　　9.2.2 交换排序
　　　　9.2.3 选择排序
　　　　9.2.4 归并排序
　　　　9.2.5 分配类排序
　　9.3 内部排序的实践
　　　　9.3.1 基于插入排序的实践
　　　　9.3.2 基于交换排序的实践
　　　　9.3.3 基于选择排序的实践
　　　　9.3.4 基于归并排序的实践
　　　　9.3.5 基于分配类排序的实践
第10章 文件与外部排序
　　10.1 内容要点
　　　　10.1.1 文件的基本概念
　　　　10.1.2 C程序文件的基本操作
　　　　10.1.3 外存信息的存取
　　　　10.1.4 外部排序的基本方法
　　10.2 文件与外部排序的实践
　　　　10.2.1 文件操作实践
　　　　10.2.2 外部排序的实践
参考文献

“数据结构”是计算机科学与技术专业的一门重要的基础课程。计算机科学各领域及相关的应用软件都要用到各种数据结构。语言编译要使用栈、散列表及语法树；操作系统中要使用队列、存储管理表及目录树；数据库系统要运用线性表、多链表及索引树等进行数据管理；而在人工智能领域也会涉及各种不同的数据结构，如广义表、集合、搜索树及各种有向图等。
        “数据结构”课程对理论与实践的要求都非常高，目的是希望通过该课程的学习，使学生学会分析、研究各种数据结构及其内在的逻辑关系，掌握它们在计算机中的存储表示及其相应的算法，并初步掌握算法的时间分析和空间分析技术。由于该课程对计算机学科起到承前启后的作用，因此学生学好“数据结构”这门课程至关重要。
        “数据结构”课程内容的难度之大是公认的，其所涉及的理论及算法也相对抽象，对于只具有计算机程序设计基础知识的学生，要他们很好地理解和掌握其中的原理相对会比较困难，特别是理解数据的存储结构、相关算法，以及理解将算法转化为相应的程序的过程，往往是学生学习的难点。针对这种情况及C语言在教学中的广泛应用，我们编写了《数据结构实验教程——C语言描述》这本书，供计算机专业的学生及其他相关专业的学生上机实验参考。希望能够帮助学生在尽可能短的时间内，对数据结构的知识与应用有一个比较全面和系统的认识，为进一步提高学生的应用编程能力在方法上提供指导。
        全书共10章，可以与使用C语言描述算法的《数据结构》教材配套使用。第1章实验概述，针对数据结构的基本概念及C语言的实现、C语言程序设计规范等进行了阐述。第2章～第10章，详细讲解了“数据结构”课程的核心内容，每章按照如下思路组织内容：“基本知识点”部分，给出该章应该掌握的基本术语；“内容要点”部分，从实践的角度总结相应数据结构的基本概念、基本运算、存储结构及相应的图示；“实践”部分，给出本书主要算法的全部实验，也是该书的重点内容，对于每个实验，均给出了实验目的、实验内容、实验要点及说明、参考程序及思考题，希望学生能够在实践的过程中，自主完成，达到举一反三、提高编程能力的目的。
        本书算法力求精湛及规范，以期帮助学生养成良好的程序设计风格及素养。全书程序设计的主要贯穿思想为：数据结构算法的实现，一般由数据结构（抽象数据类型ADT）的实现与实例（一种数据结构可以表示的具体问题）的实现两部分组成。本书的源程序全部用C语言编写，所有程序都在Microsoft Visual C 6.0下运行通过，方便学生学习和使用。
        本书的配套资源可以登录华信教育资源网注册免费下载。
        本书由阮宏一负责全书的总体策划与统稿、定稿工作。各章主要编写人员分工如下：第1章、第4章、第6章、第8章、第9章由张绪辉、张天奇编写；第2章、第3章、第5章、第7章、第10章由阮宏一、夏汇川编写；参加本书前期编写的人员还有：杜发启、文中林、鲁静、宋婉娟、张琪，在此一并对他们表示感谢。
        由于作者水平有限，书中难免存在错误和疏漏之处，敬请广大读者批评指正。
        作  者      
       2017年1月