数据结构编程实验

出版时间：2012-4-1  出版社：机械工业出版社华章公司  作者：吴永辉,王建德  页数：403  
Tag标签：无  

前言

前言我们长期从事数据结构教学和竞赛培训，教学实践使我们萌发了对数据结构课程的教学模式进行改革的想法：  1）在课程中需要增加思维方式和解题策略的引导，引导学生思考各类数据结构的本质特征是什么；面对当前问题为什么要采用这样的数据结构而不宜采用那样的数据结构；当有多个数据结构可用时，怎样权衡时间复杂度、空间复杂度、编程复杂度和思维复杂度四个因素，寻找最合时宜的数据结构，将“知识导向”与“智慧导向”真正结合起来。 2）在课程中需要引入案例教学，通过模拟或者重现现实生活中的一些场景，让学生置身问题情境之中，通过思考、讨论和上机编程来进行学习。传统教学将数据结构“束之高阁”，在理论教学和笔试上兜来兜去，可能会使学生浑然不知数据结构在现实生活中究竟派什么用处，懵懵懂懂，最终失去了学习的意义。“纸上得来终觉浅，绝知此事要躬行”。案例教学则是一种以问题和动手编程驱动学习的方式：将知识置于问题情境和实践过程之中，变枯燥乏味为生动活泼。学生拿到试题后，先进行审题，然后温习或查阅各种他认为必要的数据结构知识，这无形中激发了他们的求知欲望，加深了他们对知识真谛的理解。捕捉到相关的理论知识后，学生还要经过缜密思考和动手编程，使之变为解决问题的程序方案。这个“认识-实践-再认识-再实践”的过程，应视为知识理解上的一种提高，知识学习与应用能力间的一种转变和升华。  基于上述想法，我们近年来开设了“数据结构实验”课程，并将ACM国际大学生程序设计竞赛和其他程序设计竞赛中的典型试题分门别类，精选了其中204道试题，翻译后作为学习数据结构知识的实验案例。这些试题不仅为相关知识创设了丰富有趣的问题背景，而且在相关网站上都有试题的在线测试。学生不仅可以带着问题学习数据结构，而且所编程序的正确性和效率也可以通过相关网站上的测试系统得到实时检验，达到“学以致用”的目的。……

内容概要

　　本书以知识体系结构和思维方式两个方面作为主线，分成四大篇14章介绍了基本编程能力的实验（基础）、线性数据结构的编程实验（线性表）、层次类非线性表的编程实验（树）以及群聚类非线性表的编程实验（图），并将“排序”和“搜索”的内容融合到相关章节中。每章节由实验范例和题库两个部分组成，试题全部选自ACM国际大学生程序设计竞赛和其他程序设计竞赛，共204题，并给出了试题来源和在线测试地址。每个实验范例不仅有详尽的知识要点阐述和试题解析，而且列出了写有详细注释的参考程序；而题库中的所有试题无论难易，都有清晰的提示。该书还附带了存储所有试题的英文原版描述和大部分试题的测试数据等资料的光盘。
　　本书的实验范例部分可以作为程序设计语言和数据结构的实验教材，供大学教学使用；题库部分则可以作为计算机专业学生的研修资料和程序设计竞赛的培训教材。

作者简介

　　吴永辉 博士，复旦大学计算机科学与工程系副教授，ACM-ICPC中国赛区指导委员会（ACM-ICPC Council
China）成员，复旦大学ACM程序设计竞赛队教练。作者自2001年起连续带队进入ACM-ICPC世界总决赛，并取得过世界第6名的佳绩。他的主要研究方向为数据库，在《计算机研究与发展》、《软件学报》以及重大学术会议上发表过多篇论文，参与翻译出版了《数据通信与网络》和《数据通信、计算机网络与开放系统》。
　　王建德，著名的信息学奥林匹克竞赛金牌教练，国务院特殊津贴专家，中学特级教师。他所辅导的学生在国际奥林匹克信息学竞赛（IOI）中获7金、3银、2铜的优异成绩，先后出版了24本关于程序设计和算法的学术专著，其中《实用算法的分析与程序设计》广受好评，长期以来是国内各类程序设计竞赛的必备教程。
　　ACM国际大学生程序设计竞赛（简称ACM／ICPC）是由美国计算机协会(ACM)主办的国际性大学生计算机学科竞赛，创办于1977年，竞赛以大学为单位，3人一队，先在各大洲进行各级预选赛，从中选拔优胜队参加全球总决赛。ACM／ICPC目前已经成为全世界范围内历时久远、规模宏大、影响最大的权威性的大学生程序设计竞赛。

书籍目录

前言
第一篇　 基本能力的编程实验
　第1章　 简单计算的编程实验
　　1.1　 改进程序书写风格的实验范例
　　1.2　 正确处理多组测试数据的实验范例
　　1.3　 提高实数精度的实验范例
　　1.4　 使用二分法提高计算时效的实验范例
　　1.5　 相关题库
　第2章　 简单模拟的编程实验
　　2.1　 直叙式模拟的实验范例
　　2.2　 筛选法模拟的实验范例
　　2.3　 构造法模拟的实验范例
　　2.4　 相关题库
　第3章　 简单递归的编程实验
　　3.1　 计算递归函数的实验范例
　　3.2　 用递归算法求问题解的实验范例
　　3.3　 求解递归数据的实验范例
　　3.4　 相关题库
　本篇小结
第二篇　 线性数据结构的编程实验
　第4章　 应用直接存取类线性表编程
　　4.1　 数组应用一：日期计算的实验范例
　　4.2　 数组应用二：高精度运算的实验范例
　　4.3　 数组应用三：多项式表示与处理的实验范例
　　4.4　 数组应用四：数值矩阵运算的实验范例
　　4.5　 字符串处理一：串的存储结构的实验范例
　　4.6　 字符串处理二：串模式匹配的实验范例
　　4.7　 相关题库
　第5章　 应用顺序存取类线性表编程
　　5.1　 顺序表应用的实验范例
　　5.2　 栈应用的实验范例
　　5.3　 队列应用的实验范例
　　5.4　 相关题库
　第6章　 应用广义索引类线性表编程
　　6.1　 使用词典解题的实验范例
　　6.2　 使用散列表与散列方法解题的实验范例
　　6.3　 相关题库
　第7章　 应用线性表排序编程
　　7.1　 利用STL中自带的排序功能编程的实验范例
　　7.2　 应用排序算法编程的实验范例
　　7.3　 相关题库
　本篇小结
第三篇　 层次类非线性表的编程实验
　第8章　 采用树结构的非线性表编程
　　8.1　 用树的遍历求解层次性问题的实验范例
　　8.2　 用树结构支持并查集的实验范例
　　8.3　 用树状数组统计子树权和的实验范例
　　8.4　 相关题库
　第9章　 应用二叉树的基本概念编程
　　9.1　 普通有序树转化为二叉树的实验范例
　　9.2　 计算二叉树路径的实验范例
　　9.3　 通过遍历确定二叉树结构的实验范例
　　9.4　 相关题库
　第10章　 应用经典二叉树编程
　　10.1　 二叉搜索树的实验范例
　　10.2　 二叉堆的实验范例
　　10.3　 哈夫曼树的实验范例
　　10.4　 相关题库
　本篇小结
第四篇　 群聚类非线性表的编程实验
　第11章　 应用图的遍历算法编程
　　11.1　 BFS算法的实验范例
　　11.2　 DFS算法的实验范例
　　11.3　 拓扑排序的实验范例
　　11.4　 计算无向图的连通性的实验范例
　　11.5　 相关题库
　第12章　 应用最小生成树算法编程
　　12.1　 Kruskal算法的实验范例
　　12.2　 Prim算法的实验范例
　　12.3　 相关题库
　第13章　 应用最佳路径算法编程
　　13.1　 Warshall算法和Floyed-Warshall算法的实验范例
　　13.2　 Dijkstra算法的实验范例
　　13.3　 Bellman-Ford算法的实验范例
　　13.4　 SPFA算法的实验范例
　　13.5　 相关题库
　第14章　 应用特殊图的经典算法编程
　　14.1　 二分图匹配的实验范例
　　14.2　 计算网络最大流的实验范例
　　14.3　 相关题库
　本篇小结

章节摘录

版权页：3.2用递归算法求问题解的实验范例如果问题给出了初始状态、目标状态，且扩展子状态的规则和约束条件同一的话，则可以使用递归算法找出一个由初始状态至目标状态的求解方案。使用递归算法需要注意几个问题：怎样将求解过程中每一步的状况组合成值参或局部变量，以便回溯时能恢复递归前的状态。若这些参数的存储量大（例如数组）且初始值需由主程序传入，为避免内存溢出，则必须将其设为全局变量，且回溯前需恢复其递归前的值。  确定边界条件，即程序在什么情况下不再递归下去。确定搜索的范围和约束条件，即在当前状态未达边界的情况下，在什么范围内扩展子状态，这些子状态应满足什么条件方可继续递归下去。上述递归算法简称回溯法。实际上这种方法与第四篇中图的深度优先搜索本质上是一致的，只不过深度优先搜索一般用于现成的显式图，而回溯法一般用于递归问题的求解，两者都是采用纵深搜索的递归策略。【3.2.1Red and Black】有一个矩形房间，覆盖正方形瓷砖。每块瓷砖涂成了红色或黑色。一名男子站在黑色的瓷砖上，由此出发，可以移到四个相邻瓷砖之一，但他不能移动到红砖上，只能移动到黑砖上。编写一个程序，计算他通过重复上述移动所能经过的黑砖数。输入输入包含多个数据集。一个数据集开头行包含两个正整数W和H，W和H分别表示矩形房间的列数和行数，且都不超20。每个数据集有H行，其中每行包含W个字符。每个字符的含义如下所示：'. '—黑砖；'#'—红砖；'@'—男子（每个数据集仅出现一次）。两个0表示输入结束。输出对每个数据集，程序应该输出一行，包含男子从初始瓷砖出发可到达的瓷砖数。

编辑推荐

《数据结构编程实验:大学程序设计课程与竞赛训练教材》编辑推荐：204道试题全部从ACM国际大学生程序设计竞赛和其他程序设计竞赛中精选而出，并给出详尽试题解析。由浅入深、循序渐进地引入基本能力、线性表、树、图的编程实验，同时注重从思维方式上历练读者的编程能力。

用户评论 (总计17条)

•   吴老师搞竞赛有一套
•   刚开始看，应该不错，希望可以提高自己的编程能力~
•   好书，很用心，也很全面。勤练算法心不慌。
•   辅导学生参考用较好.
•   案例比较丰富，希望通过对这本书的学习能得到进步
•   买了这一套书，感觉挺不错的，题目很多，有讲解，对比赛很有帮助
•   很好，帮同学买的，正借来看看
•   数据结构之类的学习，除了练习外还是练习。
•   还是一本不错的书，算法挺全的，刚学算法的同志们可以考虑
•   有错误代码
•   书中的内容按照数据结构的类型分为了14章，每章会选取一些比较有代表性的ACM题目来讲解数据解构。这些ACM题目比较简单，初学者做起来有一定挑战性，但是不会觉得特别困难。 做过在线OJ题目的人可能知道，如果题目通不过测试数据，系统会提示Wrong Answer，但是不会提示是那什么测试数据引发的错误。一般初学者只有反复思考自己错在哪，这样差错非常耗时间。可贵的是，光盘中除了提供题目的源代码，还有大部分题目的测试数据，可以让做题人比较快速的发现自己程序的错误。
•   感觉蛮不错的，题型很多。
•   非常不错。。内容很好。
•   很好，适合初学者，好好做，肯定有收获的
•   很好，书的前面一章写得不错，都有详细代码。后面的要马虎一些。没有代码了。
•   很满意，书选得很好，配送也很及时。
•   本书第一个范例程序 就出错了 我在线测试过 伤心呀 这么贵的书