“西电社书目”祝您及您的家人健康快乐好运相随
数据结构是学习程序设计的核心课程,可以培养学生的程序设计、逻辑思维和分析问题的能力,进而提高其使用计算机解决问题的能力。
作者在多年讲授数据结构课程的基础上,结合教学实际对教材的形式进行了设计,主要体现在以下几个方面:
(1)突出基础性的内容,侧重工程实践,能够抓住数据结构的核心概念,有利于为学生学习算法打下较为扎实的基础。同时,算法的描述简明扼要,避免过于形式化的描述,注重算法的设计与程序的实现。
(2)遵循认知规律,在内容的讲解上注意条理性和连贯性。由于数据结构具有概念性强、算法抽象、不易掌握等特点,因此部分学生学习起来感到较为困难。鉴于此,本书一方面根据认知规律,从基本概念出发,抓住数据的实质以及算法的基本思想,由浅入深地讲解算法的设计;另一方面注意把握理论的深度,同时追求应用的广度,给出了较为丰富的例题,希望能够达到举一反三的目的。
(3)算法描述方式多样,注重逻辑思维能力的培养。学好数据结构,需要有较强的逻辑思维能力。在讲述算法的过程中,本书注意思维的引导,首先根据具体的问题,讲清楚问题求解的基本思路和基本方法,然后展现问题的求解过程,采用“图示理解→伪代码描述算法→C语言描述算法”的三级模式,给出分析问题和解决问题的过程。
(4)分析各部分内容的重点和难点,有针对性地加以处理。全书各章节中含有大量的插图和表格,有利于直观地描述有关的概念、算法等内容。算法的模块化有利于将一个复杂问题分解为一些简单的问题,达到降低问题复杂程度的效果。
(5)注意知识的应用,激发学习兴趣。从第2章到第7章,每章的最后都给出了应用举例。我们希望通过这种形式开阔学生的思维,提高学生的学习兴趣,对数据结构算法的应用起到一定的启发作用。
(6)拓宽知识面,了解与数据结构相关的一些前沿知识。第10章的内容涉及并行数据结构及应用。现在的计算机都有多个CPU核,软件开发人员必须掌握的关键技能之一就是设计并行数据结构,特别是如何在多线程环境中设计并行数据结构。
本书采用类C语言作为数据的存储结构和算法的描述语言,并且尽可能与C语言接近,方便将算法转换为能够上机执行的C程序(所谓类C语言就是不必过于严格地遵循C语言的语法规则,重点在于对算法的描述);
对于比较复杂的算法,同时给出伪代码和类C语言两种描述方式,以提高算法的可理解性;
对于应用举例中的问题,只是用伪代码描述解决问题的方法,类C语言的描述留给学生去完成,目的是锻炼学生的算法设计能力。
本书各章的习题概念性强,覆盖面广,内容全面,具有典型性和代表性,对于加深理解所学知识会起到较大的帮助作用,有利于提高算法的分析和设计能力。
此外,本书所有数据元素的逻辑序号均从1开始,数组下标均从0开始,所有例外均是为了简化算法,且作了说明。例如,顺序查找算法中数组0元素用作监视哨,排序算法中数组0元素用作暂存单元。
向上滑动阅览
目录
第一部分
第1章数据结构概述..................................2
1.1数据结构的基本概念...............................2
1.1.1为什么要学习数据结构....................2
1.1.2什么是数据结构................................3
1.1.3数据的逻辑结构................................4
1.1.4数据的存储结构................................5
1.2算法...........................................................6
1.2.1算法的定义与性质............................6
1.2.2描述算法的工具................................6
1.2.3对算法的评价标准............................8
习题1...............................................................11
第2章线性表..............................................13
2.1线性表的逻辑结构.................................13
2.1.1线性表的定义..................................13
2.1.2线性表的基本运算..........................13
2.2线性表的顺序存储结构.........................15
2.2.1线性表的顺序存储——顺序表......15
2.2.2线性表的基本运算在
顺序表上的实现..............................16
2.2.3顺序表的应用实例..........................20
2.3线性表的链式存储结构.........................23
2.3.1单链表..............................................23
2.3.2循环链表..........................................31
2.3.3双向链表..........................................32
2.4顺序表与链表的比较.............................35
2.5线性表的应用举例.................................35
2.5.1顺序表的应用——大整数的
表示及求和......................................35
2.5.2单链表的应用——一元多项式的
表示及运算......................................37
习题2...............................................................39
第3章栈和队列..........................................47
3.1栈.............................................................47
3.1.1栈的定义及基本运算......................47
3.1.2栈的顺序存储结构和
基本运算的实现..............................49
3.1.3栈的链式存储结构和
基本运算的实现..............................53
3.1.4顺序栈和链栈的比较......................55
3.2队列.........................................................56
3.2.1队列的定义及基本运算..................56
3.2.2队列的顺序存储结构和
基本运算的实现..............................56
3.2.3队列的链式存储结构和
基本运算的实现..............................59
3.3栈和队列的应用举例.............................63
3.3.1栈的应用——表达式求值..............63
3.3.2队列的应用——货运列车
车厢重排..........................................69
习题3...............................................................70
第4章串........................................................75
4.1串的概念及基本运算.............................75
4.1.1串的定义..........................................75
4.1.2串的基本运算..................................76
4.2串的顺序存储结构及基本
运算的实现..............................................77
4.2.1串的顺序存储结构..........................77
4.2.2顺序串基本运算的实现..................78
4.3串的链式存储结构.................................80
4.4串的模式匹配算法.................................82
4.4.1简单的模式匹配算法......................82
4.4.2改进的模式匹配算法......................84
4.5串的应用举例.........................................87
4.5.1文本编辑程序..................................87
4.5.2建立词索引表..................................88
习题4...............................................................92
第5章数组和广义表................................95
5.1数组.........................................................95
5.1.1数组的基本概念..............................95
5.1.2数组的存储结构..............................96
5.2特殊矩阵的压缩存储.............................97
5.2.1三角矩阵..........................................97
5.2.2对称矩阵..........................................98
5.2.3对角矩阵..........................................98
5.3稀疏矩阵的压缩存储.............................99
5.3.1稀疏矩阵的三元组表存储..............99
5.3.2稀疏矩阵的十字链表存储............
5.4广义表...................................................
5.4.1广义表的概念及基本运算............
5.4.2广义表的存储结构........................
5.5数组的应用举例...................................
5.5.1数组的应用举例——构造n阶
魔方阵............................................
5.5.2在矩阵中找出所有鞍点................
习题5.............................................................
第6章树和二叉树...................................
6.1树的基本概念.......................................
6.1.1树的定义和表示............................
6.1.2树的基本术语................................
6.2二叉树...................................................
6.2.1二叉树的定义................................
6.2.2二叉树的性质................................
6.2.3二叉树的存储结构........................
6.3二叉树的遍历.......................................
6.3.1深度优先遍历................................
6.3.2广度优先遍历................................
6.3.3从遍历序列恢复二叉树................
6.3.4二叉树遍历算法的应用................
6.4线索二叉树...........................................
6.4.1线索二叉树的存储结构................
6.4.2线索二叉树的基本操作................
6.5树和森林...............................................
6.5.1树的存储结构................................
6.5.2树、森林与二叉树的转换............
6.6哈夫曼树及其应用...............................
6.6.1最优二叉树....................................
6.6.2哈夫曼树的构造............................
6.7树的应用举例.......................................
6.7.1哈夫曼编码和译码........................
6.7.2八枚硬币问题................................
习题6.............................................................
第7章图......................................................
7.1图的基本概念.......................................
7.2图的存储结构.......................................
7.2.1邻接矩阵........................................
7.2.2邻接表............................................
7.3图的遍历...............................................
7.3.1深度优先搜索遍历........................
7.3.2广度优先搜索遍历........................
7.4生成树和最小生成树...........................
7.4.1生成树和生成森林........................
7.4.2最小生成树....................................
7.4.3构造最小生成树的Prim算法......
7.4.4构造最小生成树的
Kruskal算法..................................
7.5最短路径...............................................
7.5.1从某个源点到其他各顶点的
最短路径........................................
7.5.2每一对顶点之间的最短路径........
7.6拓扑排序...............................................
7.7关键路径...............................................
7.7.1AOE网概述..................................
7.7.2关键路径的确定方法....................
7.8图的应用举例.......................................
7.8.1七桥问题........................................
7.8.2七巧板涂色....................................
7.8.3确定图的中心顶点问题................
习题7.............................................................
第二部分
第8章查找.................................................
8.1查找概述...............................................
8.1.1查找的基本概念............................
8.1.2查找算法的性能............................
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.4.4散列表的插入、查找和
删除操作........................................
8.4.5散列表的性能分析........................
8.4.6闭散列表与开散列表的比较........
习题8.............................................................
第9章排序.................................................
9.1排序的基本概念...................................
9.2插入排序...............................................
9.2.1直接插入排序................................
9.2.2希尔排序........................................
9.3交换排序...............................................
9.3.1起泡排序........................................
9.3.2快速排序........................................
9.4选择排序...............................................
9.4.1直接选择排序................................
9.4.2堆排序............................................
9.5归并排序...............................................
9.6基数排序...............................................
9.6.1多关键字排序的概念....................
9.6.2基数排序的过程及链式
基数排序算法................................
9.7各种内部排序算法的比较和选择.......
习题9.............................................................
第三部分
第10章并行数据结构及应用..............
10.1并行计算系统概述.............................
10.1.1并行处理器..................................
10.1.2并行编程框架..............................
10.1.3并行计算的性能度量..................
10.1.4并行计算的应用..........................
10.2图形处理器.........................................
10.2.1GPU硬件架构............................
10.2.2CUDA..........................................
10.2.3OpenCL........................................
10.3基于GPU的并行算法.......................
10.3.1并行矩阵矢量点积......................
10.3.2并行矩阵乘法..............................
习题10...........................................................
参考文献.........
相关图书
本科电子信息类《数据结构实用教程(C语言版)》
《脑洞大开——数据结构另类攻略》
《数据结构》
《最优控制理论与数值算法》
《像素级图像融合算法与应用》