数据结构

出版时间:2011-6  出版社:机械工业出版社  作者:殷人昆  页数:307  

内容概要

  《数据结构:c语言描述》是根据2007年教育部颁发的《高等学校计算机科学与技术专业公共核心知识体系与课程》规范和2010年修订的《全国硕士研究生入学统一考试计算机专业基础综合考试大纲》编写的数据结构课程教材。全书共分7章:第1章介绍数据结构的地位和主要知识点,数据结构和算法的基本概念,算法分析的简单方法,以及用c语言编程的要点;第2~7章对应考试大纲的6个知识单元,包括线性表,栈、队列和数组,树与二叉树,图,查找,排序。本书融入了作者三十多年的教学经验和考试辅导体会,合理安排相关知识点,对学生容易忽略的地方和隐含在所讨论问题之后的内容给出适当的提示。  《数据结构:c语言描述》既可作为普通高校计算机科学与技术及相关专业本科生学习数据结构课程的教材,也可作为计算机专业考研的辅导教材或其他专业计算机考试的复习教材,还可作为计算机系统开发人员的学习资料。

作者简介

殷人昆,清华大学计算机系教授,中国科学院研究生院工程教育部兼职教授。1985年赴日本东京理科大学做访问学者,研究方向为软件工程过程的质量管理和软件产品的质量评价。主要负责清华大学计算机系“数据结构”、“软件工程”的本科课程教学工作和“软件工程技术与设计”、“软件项目管理”的研究生课程教学工作。主讲的“数据结构”课程被评为清华大学精品课程。曾与人合作或单独编写教材十余本。曾在核心刊物和专业会议发表论文多篇。

书籍目录

出版者的话 编委会 丛书序言 前言 教学安排建议 第1章 绪论1 1.1 数据结构的概念及分类1 1.1.1 为什么要学习数据结构1 1.1.2 与数据结构相关的基本术语2 1.1.3 数据结构的分类4 1.1.4 数据结构的存储结构6 1.1.5 定义在数据结构上的操作6 1.2 使用c语言描述数据结构6 1.2.1 数据类型7 1.2.2 算法的控制结构7 1.2.3 算法的函数结构8 1.2.4 动态存储分配10 1.2.5 逻辑和关系运算的约定11 1.2.6 输入与输出11 1.3 算法和算法设计12 1.3.1 算法的定义和特性12 1.3.2 算法的设计步骤12 1.3.3 算法设计的基本方法13 1.4 算法分析与度量16 1.4.1 算法的评价标准16 1.4.2 算法的时间和空间复杂度度量16 1.4.3 算法的渐近分析19 小结21 习题21 第2章 线性表23 2.1 线性表的定义及操作23 2.1.1 线性表的定义和特点23 2.1.2 线性表的主要操作24 2.2 顺序表25 2.2.1 顺序表的定义和特点25 2.2.2 顺序表的结构定义25 2.2.3 顺序表主要操作的实现26 2.2.4 顺序表主要操作的性能分析28 2.2.5 顺序表的应用举例29 2.3 单链表30 2.3.1 单链表的定义和特点30 2.3.2 单链表的结构定义31 2.3.3 单链表中的插入与删除31 2.3.4 带头结点的单链表33 2.3.5 单链表主要操作的性能分析35 2.3.6 单链表的顺序访问与尾递归36 2.3.7 单链表的应用举例38 2.4 顺序表与线性链表的比较40 2.5 线性链表的其他变形41 2.5.1 循环链表41 2.5.2 双向链表44 2.5.3 静态链表46 2.6 线性表的应用:字符串47 2.6.1 字符串的概念47 2.6.2 字符串的初始化和赋值48 2.6.3 c语言中有关字符串的库函数48 2.6.4 自定义字符串的存储表示50 2.7 单链表的应用:一元多项式及其运算53 2.7.1 一元多项式的表示53 2.7.2 多项式的结构定义54 2.7.3 多项式的加法55 2.7.4 多项式的乘法56 小结58 习题58 第3章 栈、队列和数组61 3.1 栈61 3.1.1 栈的概念61 3.1.2 顺序栈62 3.1.3 链式栈66 3.1.4 栈的混洗68 3.2 队列69 3.2.1 队列的概念69 3.2.2 循环队列70 3.2.3 链式队列73 3.3 栈的应用75 3.3.1 数制转换75 3.3.2 括号匹配75 3.3.3 表达式的计算与优先级处理76 3.3.4 栈与递归的实现80 3.4 队列的应用83 3.4.1 打印杨辉三角形与逐行处理83 3.4.2 电路布线与两点间的最短路径84 3.5 数组86 3.5.1 一维数组86 3.5.2 多维数组87 3.5.3 数组的应用举例89 3.6 在算法设计中使用递归89 3.6.1 汉诺塔问题与分治法90 3.6.2 迷宫问题与回溯法92 3.6.3 计算组合数与动态规划95 3.7 特殊矩阵96 3.7.1 对称矩阵的压缩存储96 3.7.2 三对角线矩阵的压缩存储97 3.7.3 稀疏矩阵的压缩存储98 3.8 双端队列100 3.8.1 双端队列的概念100 3.8.2 双端队列的主要操作101 3.8.3 双端队列的顺序存储表示101 3.8.4 双端队列的链接存储表示103 小结103 习题104 第4章 树与二叉树108 4.1 树的基本概念108 4.1.1 树的定义和术语108 4.1.2 树的基本操作110 4.2 二叉树111 4.2.1 二叉树的概念111 4.2.2 二叉树的性质112 4.2.3 二叉树的主要操作113 4.3 二叉树的存储表示114 4.3.1 二叉树的顺序存储表示114 4.3.2 二叉树的链表存储表示115 4.4 二叉树的遍历116 4.4.1 二叉树遍历的递归算法116 4.4.2 递归遍历算法的应用举例117 4.4.3 二叉树遍历的非递归算法120 4.4.4 非递归遍历算法的应用举例123 4.4.5 二叉树的计数125 4.5 线索二叉树127 4.5.1 线索二叉树的概念127 4.5.2 线索二叉树的种类128 4.5.3 中序线索二叉树的建立和遍历129 4.5.4 前序与后序线索二叉树131 4.6 树与森林132 4.6.1 树的存储表示132 4.6.2 森林与二叉树的转换134 4.6.3 树与森林的深度优先遍历135 4.6.4 树与森林的广度优先遍历137 4.6.5 树遍历算法的应用举例138 4.7 二叉树的应用:二叉排序树138 4.7.1 二叉排序树的概念138 4.7.2 二叉排序树的查找139 4.7.3 二叉排序树的插入140 4.7.4 二叉排序树的删除141 4.7.5 二叉排序树的性能分析142 4.8 二叉树的应用:平衡二叉树144 4.8.1 平衡二叉树的概念144 4.8.2 平衡化旋转144 4.8.3 平衡二叉树的插入146 4.8.4 平衡二叉树的删除147 4.8.5 平衡二叉树的性能分析149 4.9 二叉树的应用:huffman树150 4.9.1 带权路径长度的概念150 4.9.2 huffman树与huffman算法151 4.9.3 huffman树的应用:最优判定树153 4.9.4 huffman树的应用:huffman编码154 4.10 二叉树的应用:堆155 4.10.1 小根堆和大根堆155 4.10.2 堆的建立156 4.10.3 堆的插入158 4.10.4 堆的删除158 4.11 树的应用:八皇后问题与树的剪枝159 4.11.1 八皇后问题的提出159 4.11.2 八皇后问题的状态树160 4.11.3 八皇后问题算法161 小结162 习题162 第5章 图168 5.1 图的基本概念168 5.1.1 与图有关的概念168 5.1.2 图的基本操作170 5.2 图的存储结构171 5.2.1 图的邻接矩阵表示171 5.2.2 图的邻接表表示175 5.2.3 邻接矩阵表示与邻接表表示 的比较178 5.2.4 图的邻接多重表表示179 5.3 图的遍历180 5.3.1 深度优先搜索181 5.3.2 广度优先搜索182 5.3.3 连通分量183 5.3.4 重连通图184 5.3.5 欧拉回路与一笔画问题186 5.3.6 有向图的强连通分量187 5.4 最小生成树188 5.4.1 最小生成树求解和贪婪法188 5.4.2 kruskal算法190 5.4.3 prim算法193 5.5 最短路径194 5.5.1 非负权重的单源最短路径194 5.5.2 所有顶点之间的最短路径197 5.5.3 无权重的最短路径199 5.6 用顶点表示活动的网络(aov网络)200 5.7 用边表示活动的网络(aoe网络)204 小结207 习题208 第6章 查找212 6.1 查找的基本概念与性能分析212 6.1.1 查找的概念212 6.1.2 查找算法的性能分析213 6.2 顺序查找法213 6.2.1 顺序表上的顺序查找算法213 6.2.2 线性链表上的顺序查找算法216 6.3 折半查找法216 6.3.1 一般的折半查找法216 6.3.2 拟最优查找树:折半查找的 改进方法219 6.3.3 斐波那契查找:折半查找的 变形222 6.3.4 插值查找:折半查找的变形223 6.4 b树224 6.4.1 索引顺序表与分块查找224 6.4.2 多级索引结构与m叉查找树225 6.4.3 b树的概念226 6.4.4 b树上的查找227 6.4.5 b树上的插入228 6.4.6 b树上的删除229 6.4.7 b+树231 6.5 散列表及其查找233 6.5.1 散列的概念233 6.5.2 常见的散列函数234 6.5.3 解决冲突的开地址法236 6.5.4 解决冲突的链地址法242 6.5.5 散列法分析244 小结245 习题245 第7章 排序250 7.1 排序的概念与算法性能250 7.1.1 排序的概念250 7.1.2 排序算法的性能251 7.1.3 数据表和静态链表的结构定义251 7.2 几种简单的排序方法253 7.2.1 直接插入排序253 7.2.2 基于链表的直接插入排序254 7.2.3 折半插入排序255 7.2.4 起泡排序256 7.2.5 简单选择排序258 7.3 希尔排序259 7.3.1 希尔排序的设计思路259 7.3.2 希尔排序的算法实现260 7.4 快速排序261 7.4.1 快速排序的设计思路261 7.4.2 快速排序的算法描述262 7.4.3 快速排序的算法分析262 7.4.4 快速排序的改进算法263 7.5 堆排序264 7.5.1 大根堆264 7.5.2 堆排序的算法265 7.5.3 堆排序的算法分析267 7.6 归并排序267 7.6.1 两路归并267 7.6.2 递归的归并排序算法268 7.6.3 迭代的归并排序算法269 7.6.4 基于链表的归并排序算法271 7.7 基数排序272 7.7.1 基数排序的概念272 7.7.2 msd基数排序273 7.7.3 lsd基数排序274 7.8 内排序算法的分析与比较276 7.8.1 排序方法的下界276 7.8.2 各种内排序方法的比较279 7.8.3 链表排序结果的重排280 小结282 习题283 附录一 2009~2011年全国考研计算机学科联考专业基础综合考试数据结构部分试题解析288 附录二 大作业要求及样例303 参考文献308

章节摘录

版权页:插图:

编辑推荐

《数据结构:C语言描述》特点:采用“工科”思维,启发学生掌握“化复杂为简单”的方式,从问题入手,通过“问题/子问题”分解,寻找解决方案。对基本知识点讲深讲透,通过多种应用举例,让学生了解不同问题需要采取什么方法来应对。通过大量习题,从不同视点、不同层面训练学生,培养其联想能力,提高其分析问题、解决问题的能力。可配合辅助教材《数据结构习题精析与考研辅导》进行学习该书提供了600多题的参考答案和解析,并就关键点进行点拨,另外,提供了多套模拟题。涵盖2009-2011年计算机学科研究生联考数据结构部分的真题及解析。

图书封面

评论、评分、阅读与下载


    数据结构 PDF格式下载


用户评论 (总计6条)

 
 

  •   这本书比严蔚敏的简洁易懂真的是本好书!建议考研的都买这本啊
  •   我觉得看严蔚敏的就够了。这本其实没啥买的必要
  •   速度快。而且也蛮好的,就是我觉得有些贵~~
  •   送过来的书很脏而且感觉有点不像正版
  •   书而已嘛,只要不是破的就该好评.
  •   也是考研的朋友推荐的,这本书很详细,通俗易懂比严蔚敏的那个好多了,强烈推荐
 

250万本中文图书简介、评论、评分,PDF格式免费下载。 第一图书网 手机版

京ICP备13047387号-7