算法分析与设计

出版时间：2012-9  出版社：清华大学出版社  作者：肖南峰　等编著  页数：302  字数：493000  

内容概要

　　《算法分析与设计──数据结构实践》是为广东省教育厅“数据结构”精品课程配套的辅助教材。全书共11章，主要内容包括绪论、线性表、栈和队列、串、多维数组和广义表、树和二叉树、图、查找、排序以及几种典型算法(贪婪算法、分而治之算法、动态规划、回溯、分支限界法)实现等。本书内容翔实，算法和例题非常经典且给出了对应的visual
c++6．0源程序。
　　《算法分析与设计──数据结构实践》既可作为计算机学科各专业学生的辅助教材，也可作为广大工程技术人员和自学考试人员的参考书。

书籍目录

第1章绪论
1．1相关知识
1．1．1软件开发方法
1．1．2web程序设计
1．1．3基本概念
1．2例题解析
1．3算法的描述与实现
1．3．1算法的描述
1．3．2算法的实现
1．4实验环境介绍
1．4．1创建项目
1．4．2编辑源程序文件
1．4．3调试程序
习题1
第2章线性表
2．1相关知识
2．2存储结构和基本运算
2．2．1线性表的顺序存储结构
2．2．2线性表的链式存储结构
.2．3例题解析
2．4线性表实践
习题2
第3章栈与队列
3．1相关知识
3．2存储结构和基本运算
3．2．1栈的顺序存储结构
3．2．2栈的链式存储结构
3．2．3队列的顺序存储结构
3．2．4队列的链式存储结构
3．3例题解析
3．4栈与队列实践
习题3
第4章串
4．1相关知识
4．2存储结构和基本运算
4．3例题解析
4．4串实践
习题4
第5章多维数组与广义表
5．1相关知识
5．1．1数组
5．1．2矩阵
5．1．3广义表
5．2存储结构和基本运算
5．2．1数组
5．2．2特殊矩阵
5．2．3广义表
5．3例题解析
5．4多维数组与广义表实践
习题5
第6章树与二叉树
6．1相关知识
6．1．1树
6．1．2二叉树
6．2存储结构和基本运算
6．2．1树
6．2．2二叉树
6．3例题解析
6．4树与二叉树实践
习题6
第7章图
7．1相关知识
7．2存储结构和基本运算
7．2．1邻接矩阵
7．2．2邻接表
7．2．3十字链表(有向图)
7．2．4邻接多重表(无向图)
7．3例题解析
7．4图实践
习题7
第8章查找
8．1相关知识
8．2存储结构和查找方法
8．2．1静态表的查找
8．2．2动态树的查找
8．2．3哈希表的查找
8．3例题解析
8．4查找实践
习题8
第9章排序
9．1相关知识
9．2数据类型和内部排序
9．2．1插入排序
9．2．2交换排序
9．2．3选择排序
9．2．4归并排序
9．2．5基数排序
9．2．6各种排序的测试结果和比较
9．3例题解析
9．4排序实践
习题9
第10章典型算法实现
10．1贪婪算法
10．2分而治之算法
10．3动态规划
10．4回溯
10．5分支限界法
习题10
第11章课程设计与acm大赛
11．1课程设计要求
11．2课程设计实践例题
11．3acm大赛
11．3．1acm历史
11．3．2acm简要规则
11．3．3acm题目分类
11．3．4acm例题解析
习题11
附录aacm大赛系统使用说明
附录bacm大赛例题
参考文献

章节摘录

版权页：   插图：   8.2.2 动态树的查找 动态查找表可以使用各种树结构表示。树结构在进行插入或删除操作时，可以方便地维护表的有序性，无须移动大量记录，减少了移动记录的时间开销。这里介绍4种树结构的查找方法：二叉排序树、平衡二叉树、B树和B+树。 1.二叉排序树 二叉排序树（Binary Sort Tree，BST）又称二叉查找树，是一种常用的动态查找表。二叉排序树可以用递归的形式定义，即二叉排序树或一颗空树，或具有如下性质的二叉树： （1）若它的左子树非空，则其左子树所有结点的关键字均小于其根结点的关键字值。 （2）若它的右子树非空，则其右子树所有结点的关键字值均大于其根结点的关键字值。 （3）它的左、右子树都是二叉排序树。 从定义可知，按中序遍历二叉排序树会得到一个按关键字值递增排序的序列。 BST的查找与折半查找类似，算法思想是，当BST二叉排序树非空时，先将给定值和根结点的关键字进行比较，若相等，则查找成功；若小于根结点的关键字值，则查找根结点的左子树；若大于根结点的关键字值，则查找根结点的右子树。 BST的插入算法思想是，根据BST的特点，新插入的结点作为叶子结点，并且在查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子。 BST的删除算法思想是，在BST中删除任意一个结点时，都必须保证删除后的二叉树仍然是二叉排序树。分以下几种情况，假设被删除结点为P，其双亲结点为f。 （1）如果p为叶子结点，则直接删除该结点；如果P为根结点，则删除后二叉排序树变为空树。 （2）如果P只有左子树或只有右子树，可直接将p的左子树或右子树代替p，变为f的子树。 （3）如果p既有左子树又有右子树，根据二叉排序树的特点，可用p的中序下的前驱结点的值（或其中序下的后继结点的值）代替P的值，同时删除其中序下的前驱结点（或其中序下的后继结点），而P的中序前驱无右子树（或P的中序后继无左子树），则转为（2）。另外，还可直接将P的右子树代替P，同时将P的左子树变为P右子树中序第一个结点的左孩子，也可直接将P的左子树代替P，同时将P的右子树变为P左子树中序最后一个结点的右孩子。

编辑推荐

《21世纪高等学校规划教材•计算机科学与技术:算法分析与设计:数据结构实践》既可作为计算机学科各专业学生的辅助教材，也可作为广大工程技术人员和自学考试人员的参考书。

用户评论 (总计3条)

•   没有c++编程经验， 看得一知半解
•   和学习教材配套
•   这本书其实蛮一般的，总是感觉作者的思路有点乱。