数据结构实训教程

出版时间：2005-4  出版社：科学出版社  作者：付百文 编  页数：198  

前言

“数据结构”是计算机类各专业的核心课程，也是其他诸多类专业的重要选修课，是程序设计的基础。开设这门课可以为理解、应用和开发程序提供技术和方法支持，为后续课程的学习提供思想和方法基础。然而在多年的教学实践中我们发现，在实际的学习和应用实践中，很多同学认为“数据结构”很难学，碰到实际问题不知从何处下手，缺乏针对性的实践训练是主要原因之一。本书就是为了解决“数据结构”课程的实践教学问题而编写的，是作者多年教学经验的总结。本书有以下几个方面的特点。①突出算法，淡化程序。强调设计思路、算法，描述算法的工具灵活多样，对复杂的算法，给出图形化的描述方式，使算法与编程语言相对独立开来，从而使实现工具的编程语言可灵活自选。②注重题目的实用性和现实性。注重在相关课程和实际生活和学习中的应用，题目生动、接近学习和生活实际，学生容易接受和理解，易调动学习积极性。多数问题一般都分成若干个要求，由浅入深，可根据具体情况完成部分或全部要求。③强调学生思考。实训题目强调学生思考、理解和分析，多数题目都给出了思考和扩展空间，强调开放性思维。④以问题为中心。应用基本知识，进行案例分析，指导学生理解、完成和拓展实训题目，进一步理解和掌握数据结构的基本知识，提高分析问题和解决问题的能力。根据实际学时、教学要求和实际情况，可以灵活选择实训项目。减少部分要求和难度，实训项目既可以当做较为简单的实验，又可以当做综合实训。虽然本书的实训案例是用c语言实现的，但读者可以很容易地用其他编程语言实现。因为本书重点讨论的是算法，所以本书也很适宜作为“程序设计”课程实践的参考书。本书第1、7、8、9章由付百文编写，第2、3章由祁宇翔编写，第4章由季全芝编写，第5章由张宇宏编写，第6章由张冰峰编写。付百文负责全书的统稿。在此感谢鲍宏、鲍有文、周海燕、彭涛对本书的编写工作所给予的帮助和支持。由于作者水平有限，书中难免有疏漏和错误之处，敬请读者批评指正。

内容概要

本书包括实训基础知识介绍、线性表、栈和队列、字符患 和多维数组、树、图、排序、查找以及综合实训等章节。在内容安排上既有各章节的知识要点，又有案例解析、实训项目，同时还有与实例相关的练习与思考题。实训案例既有分析、设计和具体的解决方案，同时又提出了讨论、思考和练习的题目。在算法描述上，尽量采用直观的描述形式，如自然语言、图形等，突出算法，淡化程序。案例和实训项目既涵盖知识点，又较贴近学习和实际生活。    本书可与用面向过程的各种语言描述的数据结构教材配套使用，也可作为高职高专程序设计类专业的实验实训参考教材，同时也可供从事计算机工程与应用的科技工作者参考。

书籍目录

第1章  实训基础知识介绍  1.1 程序设计的一般步骤  1.2 算法的描述工具    1.2.1 图表方式    1.2.2 语言方式  1.3 编辑程序    1.3.1 Windows下编辑程序    1.3.2 Turbl C下编辑程序    1.3.3 程序的风格  1.4 调试程序    1.4.1 常用的调试技术    1.4.2 常用的调试策略  1.5 实训报告的主要内容第2章  线性表  2.1 知识要点    2.1.1 顺序表    2.1.2 单链表    2.1.3 循环单链表    2.1.4 双链表    2.1.5 线性表存储结构的比较和选用  2.2 案例分析     2.2.1 体育彩票的模拟生成和兑奖    2.2.2 列车时刻表管理系统    2.2.3 信息的合并  2.3 实训项目    2.3.1 学成成绩管理    2.3.2 一元多项式的加法    2.3.3 求两个集合的交集和并集    2.3.4 猴子选大王第3章  栈和队列  3.1 知识要点    3.1.1 基本概念    3.1.2 栈的存储实现和运算实现    3.1.3 队列的存储实现及运算实现  3.2 案例解析    3.2.1 数制转换问题    3.2.2 利用栈实现迷宫问题的求解    3.2.3 利用队队求迷宫的最短路径  3.3 实训项目    3.3.1 表达式求值    3.3.2 表达式中括号的配对问题    3.3.3 八皇后问题    3.3.4 运动会比赛日程安排第4章  字符串和多维数组  4.1 知识要点    4.1.1 基本概念    4.1.2 串的存储结构    4.1.3 串的基本运算    4.1.4 数组的内存映像    4.1.5 特殊矩阵的压缩存储  4.2 案例解析    4.2.1 文本的查找与替换    4.2.2 稀疏矩阵的加法    4.2.3 字符图形的保存与输出  4.3 实训项目    4.3.1 字符串中年份的识别与分离    4.3.2 班级学期成绩的管理与统计    4.3.3 稀疏矩阵的转置    4.3.4 稀疏矩阵的乘法运算第5章  树  5.1 知识要点    5.1.1 树、二叉树的基本概念    5.1.2 二叉树的性质及其存储结构    5.1.3 二叉树的遍历    5.1.4 树的存储结构  5.2 案例解析    5.2.1 二叉家族树的建立与输出    5.2.2 求某个成员的所有祖先成员    5.2.3 哈夫曼编码与译码    5.2.4 公司组织结构树的建立  5.3 实训项目第6章  图第7章  排序第8章  查找表第9章  综合实训参考文献

章节摘录

插图：2.2.3 信息的合并1.案例描述小王喜欢交友，他把高中时的朋友的情况记在了一个小记录本上，大学时的朋友的情况记在了另一个小记录本上。现在小王想把这两本记录合到一个大记录本上。请帮忙设计算法，解决这个问题。假设人名中无同名现象。2.案例分析每个记录本上的朋友列表就是一个线性表，记录的合并就是两个线性表的合并。对于两个线性表中的不同记录，都要复制到结果表中，而对于两个线性表中相同的记录，只复制一个到结果表中即可。由于通常的朋友列表都是按姓名排序的，因此也将表示朋友列表的线性表按朋友姓名组织成有序的，这样也可以简化、合并操作。由于本案例所涉及的两个线性表和结果表的长度不易确定，表长变化较大，因此可以采用单链表表示各个线性表。

编辑推荐

《数据结构实训教程》为科学出版社出版发行。