数据结构基础教程 (2010 年度畅销榜NO.20710 )

本书系统地介绍了各种常用的数据结构及排序、查找的各种算法，阐述了各种数据结构的逻辑结构、存储结构及其基本运算。各数据结构类型和基本运算，首先用类C代码描述，然后用可编译运行的C语言代码实现，并给出了详细的注释。全书既注重原理又强调实践，配有大量的图表和习题，概念讲解清楚、逻辑性强、可读性好。本书的特点在于，首次尝试在基础课程中介绍计算机科学发展史知识，采用脚注的形式使学生了解计算机科学史知识和数据结构课程与其他课程之间的关系；附有大量以“思考”形式出现的问题，以便在恰当的时机引导学生思考，启发思维；以学生为主体精心设计了数据结构课程的实践教学内容。
本书可作为高等院校非计算机专业教材或高职、高专院校计算机专业教材，也可作为成人教育(面授或函授)的教材，还可为参加全国计算机软件水平程序员等级考试提供参考，亦可供广大从事计算机应用的科技人员参考。

第1章绪论
1.1数据结构基本概念
1.1.1数据结构实例
1.1.2数据结构概念
1.2算法分析基本概念
1.2.1算法
1.2.2算法效率分析
1.2.3算法效率评价
习题1
第2章线性表
2.1概念和运算
2.1.1线性表概念
2.1.2线性表基本运算
2.2顺序存储结构
2.2.1顺序表
2.2.2顺序表基本运算
2.3链式存储结构
2.3.1线性链表
2.3.2线性链表基本运算
2.4线性表应用
2.5基本运算实现
2.5.1顺序表基本运算实现
2.5.2链表基本运算实现
上机实习线性表
习题2
第3章栈
3.1概念和运算
3.1.1栈概念
3.1.2栈基本运算
3.2存储和实现
3.2.1顺序栈
3.2.2链栈
3.3栈应用
3.3.1数制转换
3；3.2表达式求值
3.3.3栈和递归
3.4栈基本运算实现
3.4.1顺序栈基本运算实现
3.4.2链栈基本运算实现
上机实习栈
习题3
第4章队列
4.1概念和基本运算
4.1.1队列概念
4.1.2队列基本运算
4.2顺序存储结构和运算
4.3循环队列
4.4链队列
4.5队列应用
4.6队列基本运算实现
4.6.1循环队列运算实现
4.6.2链队列运算实现
上机实习队列
习题4
第5章线性结构推广
5.1串
5.1.1定义
5.1.2基本运算
5.1.3定长顺序存储
5.1.4模式匹配
5.1.5链式存储结构
5.2数组
5.2.1定义和存储
5.2.2矩阵压缩存储
5.3广义表
5.3.1定义
5.3.2存储—
5.4串的基本运算实现
上机实习串
习题5
第6章树
6.1树的概念和基本运算
6.1.1定义
6.1.2基本术语
6.1.3基本运算
6.2树的存储
6.3二叉树的概念和性质
6.3.1概念和基本运算
6.3.2性质
6.3.3存储
6.4二叉树遍历
6.5线索二叉树
6.6树和二叉树
6.6.1树与二叉树的转换
6.6.2叉树与森林的转换
6.7哈夫曼树及其应用
6.8二叉树基本运算
6.9二叉树基本运算实现
上机实习二叉树
习题6
第7章图
7.1概念和基本运算
7.1.1图的概念
7.1.2图的基本运算
7.2图存储
7.2.1数组表示法
7.2.2邻接表
7.3图遍历
7.3.1连通图的深度优先搜索遍历
7.3.2广度优先搜索
7.4最小生成树
7.4.1Prim算法
7.4.2Kruskal算法
7.5单源点最短路径
7.6图的基本运算实现
上机实习图
习题7
第8章排序
8.1排序基本概念
8.2插入类排序
8.2.1直接插入排序
8.2.2折半插入排序
8.2.3希尔排序
8.3交换类排序
8.3.1冒泡排序
8.3.2快速排序
8.4选择类排序
8.4.1简单选择排序
8.4.2树型选择排序
8.4.3堆排序
8.5归并排序
8.6各种排序方法的综合比较
8.7外部排序
8.8各类排序算法的综合实现
上机实习排序
习题8
第9章查找
9.1基本概念
9.2静态查找表
9.2.1顺序查找法
9.2.2折半查找法
9.2.3分块查找法
9.3动态查找表
9.4哈希表
9.4.1基本概念
9.4.2哈希函数构造方法
9.4.3冲突处理方法
9.4.4哈希表查找
9.5查找表实现
上机实习查找表
习题9
参考文献

1997年5月，一台名为“深蓝”的超级计算机将棋盘上的一个兵走到C4位置时，人类有史以来最伟大的国际象棋名家卡斯帕罗夫不得不沮丧地服输，上世纪末的一场人机大战终于以计算机的微弱优势取胜。2003年4月14日人类基因组计划宣告完成，后基因组时代已经到来，各种生物学成果在计算中不断出现。这些成果使得人们再一次认识到计算的重要性。如今，计算技术已广泛地应用到各个领域，后因特网时代已经到来，以信息化带动工业化已成为时代的主题。计算机程序设计是计算技术的重要内容，而数据结构是计算机程序设计的重要理论基础，它不仅是计算机学科的核心课程，而且已成为其他专业的热门选修课。数据结构课程的教学目标是学会分析需要计算机处理的数据对象的特性，以选择适当的数据结构和存储结构，从而选择相应的算法；初步掌握算法性能分析的方法。通过本课程的学习，使学生获得更进一步的程序设计技能训练，提高编程能力。 长久以来，由于数据结构课程自身的抽象性和严密性，以及数据结构开设的时间通常在刚入大学的第二学期，教师大都感觉数据结构课程难教，学生普遍反映数据结构课程难学，学生很难独立完成算法的实现。基于上述问题，我们在编写本教材时充分考虑了学生的知识结构和教师的教学方法。本教材的编写宗旨是，既注重原理又注重实践，既注重抽象思维又注重形象思维，既方便自学又方便教学。本书的编写具有以下特色。 1.首次尝试在计算机专业的核心基础课程中增加计算机科学知识，使学生在学习本教材的过程中，不但能学到专业知识，还能了解计算机科学发展历史的相关知识和数据结构课程与其他课程的联系。对提高学生学习本课程的兴趣，拓宽学生的知识面大有益处。 2.在教材中使用“▲思考”标志，提出问题拓展学生思维。思考不同于习题，习题的作用代替不了思考。因为习题在每个章节之后，一般要等讲完一个章节才会遇到，因此习题对于课堂教学是滞后的。采用提示思考的方式，可以在教学中恰到好处地启发学生的思维。教材使用“▲思考”标志通常有三种情况：一种是提醒学生需要注意的内容，一种是启发学生基于当前知识基础进一步思考的内容，第三种是提示本教材没有讲授的内容，以引导学有余力的学生拓展自身的知识面。 3.以学生为主体设计数据结构课程的实践内容。数据结构课程是计算机专业的一门重要的基础课程，其性质是实践性的。如何引导学生利用所学概念和算法进行实践是这门课程成败的关键，为此我们采取了两个措施：一是注重概念和算法的应用背景，对每种数据结构都有应用实例，有代码实现；二是在基本运算的实现代码中留有要求学生自己实现代码的部分。这就要求学生不但要读懂已经实现的部分代码，还要自己设计代码，最后才能得到一个完整实现的系统。这有利于提高学生对数据结构概念和算法的理解，真正提高学生的编程能力。每章后的上机实习就由这两部分内容组成，本书中提供的实现代码均在VC 6.0中编译通过。 本书介绍了各种最常用的数据结构，阐述了各种数据结构内涵的逻辑关系，讨论了它们在计算机中的存储表示，以及基于这些数据结构的运算和实际的执行算法，并对算法的效率进行了简要的分析和讨论。 全书包含9章内容，第1章介绍了数据结构和算法分析的基本概念；第2章到第5章第1节介绍了线性结构；第5章第2节到第7章介绍了非线性结构，其中有多维数组、广义表、树和图：第8章和第9章分别介绍了排序和查找。为了便于讲授，所有数据类型定义和算法实现首先均用类C语言(或C语言)描述。为了便于学生上机实习，除了留给学生实习的内容外，所有基本运算算法均用C语言实现，学生可以直接编译运行。另外，为了避免C语言中数组的第一个元素的下标是0给学习和讲授带来的不便，本书在没有特别申明的地方均不使用C语言中数组下标为0的元素。 本书可作为本科院校非计算机专业教材或高职、高专计算机专业的教材，讲授60课时左右。本书的每一章末均有上机实习和习题。根据学生的实际情况，每章的上机实习可安排2课时左右，这样总计实验课时约为16个小时。本书还可作为成人教育(面授或函授)的教材，也可为参加全国计算机软件水.平程序员等级考试提供参考，亦可供从事计算机应用的科技人员参考。 本书由文益民整体构思，在3位多年从教计算机专业数据结构课程作者的教学经验基础±，经过多次反复磋商和共同讨论定稿，是这3位作者共同合作的产物。本书经湖南大学计算机与通信学院周学毛副教授详细，审阅，提出了许多宝贵意见。上海交通大学仿脑计算实验室的硕士、博士生们提供了许多有益的建议，作者谨此一并致以诚挚的谢意。 本书的第1、2、4、5和第7章由文益民编写，第3章和第6章由郭杰编写，第8章和第9章由李健编写。全书由文益民；统稿、修改。 由于编著者水平有限，书中疏漏或错误在所难免，殷切期望广大读者批评指正。 文益民郭杰李健 2004年12月