数据结构实训教程

出版时间：2003-8  出版社：科学出版社  作者：孙巧萍 编  页数：160  字数：239000  

前言

“数据结构”作为一门课程，在20世纪70年代末进入大学课堂。它不仅是计算机专业的核心课程，也是其他理工科专业的热门选修课。作者在长期讲授“数据结构”这门课程的过程中深切地体会到，在整个教学活动中，学生解题能力和上机操作能力的培养是两个至关重要的环节，后者显得更为重要。学生仅仅学好本课程的理论知识是远远不够的，必须加强实践环节，从实验的成功和失败中获得锻炼，以提高复杂程序设计的技能及解决实际应用问题的能力。但从现状来看，目前国内“数据结构”实验课程教材比较缺乏，适合高职高专的此类教材更是寥寥无几，难以跟上教学实践的需求。没有合适的实训教程的指导，学生在做实验时往往会感到无从下手，达不到理想的实验效果，为此，作者结合自己多年来的教学经验编写了这本《数据结构实训教程》。本书力求在加强实验课教学环节上能有所突破，确保从抓实践环节上入手，注重培养学生的实际应用技能和综合解决问题的能力，使学生能熟练掌握和运用理论知识解决实际问题，达到学以致用的目的，能真正地为培养新世纪的适用型人才出一份力。本书紧扣数据结构的理论知识，每类数据结构相关内容各成一章，结构清晰，内容按由易到难、逐层深入的方式安排，以激发读者探讨问题的兴趣。每章内容除包括实训知识准备、实训案例分析和实训项目三部分外，还单独列出习题，供学生课后复习巩固使用。为体现实训特色、突出实训重点，尤其是培养学生应用理论知识解决实际问题的能力，在每章的实训案例分析中，都给出了若干个实际问题的算法要点、算法及程序，从而让学生熟悉综合应用所学理论知识解决实际问题的方法和一般过程，达到锻炼综合应用能力的目的。本书的宗旨是真正地教会学生如何做数据结构实验，怎样做好数据结构实验，书中所有算法及程序均采用C语言编写，可与各种版本用C语言描述的“数据结构”教材配套使用。本实训教程由孙巧萍老师统编全稿，其中前3章由王爱冬老师执笔，第4、5章由孙巧萍老师执笔，第6、7章由刘鲁楣老师执笔。本书中的所有程序都在Visual C++ 6.0中调试通过。由于编者水平有限、时间仓促，书中难免存在一些不足之处，殷切希望广大读者批评指正。

内容概要

本书是数据结构实验课教材，为“数据结构”课程上机实践提供理论与操作指导，可与采用C语言进行算法描述的各种版本的“数据结构”教材配套使用。    全书共分7章，前5章分别讨论线性表、栈和队列、串和数组、树、图等内容，第6章和第7章讨论各种查找和排序方法的算法实现与应用。本书内容由浅入深，采取循序渐进的方式培养学生的实践技能。    本书不仅可作为高职、高专计算机专业的配套教材，也是对本、专科相关专业学生，自考学员和专业教师颇有帮助的辅助教材。

书籍目录

第1章 线性表　1.1 实训知识准备　　1.1.1 顺序表　　1.1.2 链表　　1.2 实训案例分析　　1.2.1 学生成绩管理　　1.2.2 求两个集合的差　　1.2.3 顺序表归并　　1.2.4 一元多项式相加　1.3 实训项目一　　1.3.1 顺序表操作验证　　1.3.2 单链表操作验证　1.4 实训项目二　　1.4.1 有序表插入　　1.4.2 求两集合交集　1.5 实训项目三　　1.5.1 约瑟夫(Joseph)问题　　1.5.2 单链表的应用　　习题第2章 栈和队列　2.1 实训知识准备　　2.1.1 栈　　2.1.2 队列　2.2 实训案例分析　　2.2.1 算术表达式转换为波兰表达式　　2.2.2 算术表达式求值　　2.2.3 利用队列解决分油问题　　2.2.4 迷宫问题　2.3 实训项目一　　2.3.1 栈操作的验证　　2.3.2 队列操作的验证　2.4 实训项目二　　2.4.1 判别表达式中括弧是否正确配对　　2.4.2 公用栈问题　2.5 实训项目三　　2.5.1 队列元素倒置　　2.5.2 双端队列操作　　习题第3章 串和数组　3.1 实训知识准备　　3.1.1 串及其存储结构　　3.1.2 数组　3.2 实训案例分析　　3.2.1 中心串对称问题　　3.2.2 文字研究助手　　3.2.3 稀疏矩阵相加　　3.2.4 矩阵相乘　　3.2.5 稀疏矩阵相乘　　3.3 实训项目一　　3.3.1 字符串操作验证　　3.3.2 三元组表示矩阵的转置　3.4 实训项目二　　3.4.1 删除串中的字符　　3.4.2 统计子串在字符串中出现的次数　3.5 实训项目三　　3.5.1 三元组表示矩阵的相加　　3.5.2 求两条对角线元素乘积　　习题第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.2.4 哈夫曼编码　4.3 实训项目一　……第5章 图第6章 查找第7章 排序主要参考文献

章节摘录

插图：2.2.3 利用队列解决分油问题问题描述：设有大小不等的三个无刻度的油桶，分别能盛满x，y，z公升油。初始时，第一个油桶盛满油，第二、三个油桶为空，寻找一种最少步骤的分油方式，在某一个油桶上分出targ公升油。算法输入：三个油桶的盛油量，要分出的油量targ。算法输出：分油的结果。算法要点：分油过程中，由于油桶上没有刻度，只能将油桶倒满或者倒空。三个油桶盛油的总量始终等于初始时第一个油桶盛满的油量。算法的主要思想：每次判断当前油桶是不是可以倒出油，以及其他某个油桶是不是可以倒进油。如果满足以上条件，那么当前油桶的油或全部倒出，或将另一油桶倒满，针对两种不同的情况作不同的处理。使用一个队列p，记录每次分油时各个油桶的盛油量和倒油过程等信息，队列中只记录互不相同的盛油状态（各个油桶的盛油量）。如果列举出倒油过程的所有不同的盛油状态，经考察全部状态后，未能分出targ公升油的情况，就确定这个分油问题无解。队列p通过指针he和ta实现倒油过程的控制。

编辑推荐

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