新编数据结构案例教程(C/C++语言)-微课版

（1）结构清晰，内容全面，文字描述简洁明了，可读性强，由浅入深地归纳总结每种数据结构的算法设计方法。
（2）图文并茂，全书使用150余幅图描述数据结构概念、算法的基本思想、算法的执行过程。
（3）强调数据结构中3种逻辑结构和2种存储表示。全书强调3种逻辑结构，即线性结构、树结构、图结构，每一种结构都采用2种存储方式，即顺序存储和链式存储,但必须注意每一种逻辑结构应结合其特点选择合适的存储表示。

 

本书在主要介绍数据的逻辑结构、数据的存储结构、数据的运算等基本知识的基础上,从抽象数据类型的角度,讨论各种基本类型的数据结构及相关应用。
全书共分5篇： 第1篇(第1章)为绪论篇,着重介绍数据结构的相关概念和算法的基础知识；第2篇(第2~5章)为线性结构篇,着重讨论线性结构的概念和基本运算的算法实现,介绍了一般的线性结构和特殊的线性结构在不同存储结构之下的基本操作和应用； 第3篇(第6章)为树形结构篇,着重介绍基本的树形结构——二叉树在不同存储结构之下如何实现基本操作和应用； 第4篇(第7章)为图形结构篇,介绍图形结构在不同存储结构之下的基本操作和应用； 第5篇(第8~10章)为数据运算篇,首先介绍数据的查找和排序基本运算的算法实现,接着介绍常见的查找和排序方法,分析并对比它们的算法效率，*后介绍数据结构的基础知识在程序设计竞赛中的应用。全书提供了大量应用实例,每种算法都采用C/C 语言进行描述,帮助读者理解基础理论。
本书叙述清楚，便于教学和读者自学,适合作为高等院校计算机专业及信息相关专业的教材,也可作为计算机应用技术人员的参考书。

目录

第1篇绪论篇

第1章绪论

1．1什么是数据结构

1．1．1数据结构的产生与发展

1．1．2数据结构的基本概念

1．1．3逻辑结构的种类

1．1．4数据的存储结构

1．2抽象数据

1．2．1数据类型

1．2．2抽象数据类型的表示与实现

1．3算法及其性能分析

1．3．1算法

1．3．2算法设计的目标

1．3．3算法的时间复杂度度量

1．3．4算法的空间复杂度度量

1．4STL概述

1．4．1STL的发展和特点

1．4．2C 标准库和STL

1．4．3数据结构和STL的关系

1．5综合案例

1．5．1哥德巴赫猜想问题

1．5．2连续整数问题

本章小结

第2篇线性结构篇

第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．3．3双链表

2．3．4循环链表

2．3．5STL与链表

2．4综合案例

2．4．1一元多项式的表示及相加运算

2．4．2魔法师发牌问题

2．4．3约瑟夫问题

本章小结

第3章栈与队列

3．1栈

3．1．1栈的概述

3．1．2栈的顺序存储结构

3．1．3栈的链式存储结构

3．2栈综合案例

3．2．1进制转换

3．2．2表达式求值

3．2．3检验表达式中的括号匹配情况

3．2．4栈与递归问题

3．3队列

3．3．1队列的定义和抽象数据类型

3．3．2队列的顺序存储

3．3．3队列的链式存储

3．3．4优先级队列

3．4STL中的栈与队列

3．4．1STL中的栈

3．4．2STL中的队列

3．4．3STL中的优先队列的使用方法

3．5队列综合案例

3．5．1打印杨辉三角形

3．5．2报数问题

3．5．3舞伴问题

本章小结

第4章串

4．1串的基本概念和抽象数据类型

4．1．1串的基本概念

4．1．2串的抽象数据类型

4．2串的存储结构

4．2．1串的顺序存储结构——顺序串

4．2．2串的链式存储结构——链串

4．3串的模式匹配

4．3．1串的古典匹配算法

4．3．2串的KMP算法

4．4综合案例

4．4．1文本编辑

4．4．2建立词索引表

本章小结

第5章数组和广义表

5．1数组的定义及抽象数据类型

5．1．1数组的定义

5．1．2数组的抽象数据类型

5．2数组的顺序存储与寻址

5．2．1以行序为主序

5．2．2以列序为主序

5．3特殊矩阵及其压缩存储

5．3．1对称矩阵

5．3．2下(上)三角矩阵

5．3．3对角矩阵

5．4稀疏矩阵

5．4．1稀疏矩阵的三元组表示

5．4．2稀疏矩阵的十字链表表示

5．5广义表

5．5．1广义表的定义

5．5．2广义表的存储结构

5．5．3广义表的运算

5．6综合案例

5．6．1大整数相乘

5．6．2荷兰国旗问题

本章小结

第3篇树形结构篇

第6章树和二叉树

6．1树

6．1．1树的定义

6．1．2树的术语

6．1．3树的基本性质

6．1．4树的抽象数据类型

6．2二叉树

6．2．1二叉树的定义

6．2．2二叉树的性质

6．2．3二叉树的抽象数据类型

6．2．4二叉树的存储结构

6．3二叉树的基本操作

6．3．1中序遍历

6．3．2先序遍历

6．3．3后序遍历

6．3．4层次遍历

6．3．5二叉树遍历的应用

6．3．6二叉树遍历的非递归实现

6．4线索二叉树

6．4．1线索二叉树的概念

6．4．2线索化二叉树

6．4．3遍历线索二叉树

6．5树与森林

6．5．1树的存储结构

6．5．2森林与二叉树的转换

6．5．3树的遍历与森林的遍历

6．6哈夫曼树及其应用

6．6．1哈夫曼树的基本概念

6．6．2哈夫曼树构造算法

6．6．3哈夫曼编码

6．7STL中实现树结构

6．7．1STL中的vector

6．7．2STL中的map

6．8综合案例——学校建模问题

本章小结

第4篇图形结构篇

第7章图

7．1图的概念

7．1．1图的定义和术语

7．1．2图的抽象数据类型

7．2图的存储表示

7．2．1邻接矩阵

7．2．2邻接表

7．2．3十字链表

7．3图的遍历与连通性

7．3．1深度优先遍历

7．3．2广度优先遍历

7．3．3连通分量

7．4最小生成树

7．4．1普里姆算法

7．4．2克鲁斯卡尔算法

7．5最短路径

7．5．1单源最短路径

7．5．2全源最短路径

7．6活动网络

7．6．1用顶点表示活动的AOV网络

7．6．2AOE图与关键路径

7．7综合案例

7．7．1道路修建问题

7．7．2回家路线问题

7．7．3棍子还原问题

本章小结

第5篇数据运算篇

第8章查找

8．1查找的基本概念

8．2静态表的查找

8．2．1顺序查找

8．2．2折半查找

8．2．3斐波那契查找

8．2．4分块查找

8．3动态查找表

8．3．1二叉排序树

8．3．2平衡二叉树

8．3．3B-树

8．3．4B 树

8．4哈希表查找

8．4．1哈希表的基本概念

8．4．2哈希函数构造方法

8．4．3哈希冲突解决方法

8．4．4哈希表上的查找分析

8．5STL中的查找

8．6综合案例——拼写检查问题

本章小结

第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.4.3堆排序

9.5二路归并排序

9.6基数排序

9.7内部排序方法的比较

9.8STL中的排序

9.9综合案例——比赛排名问题

本章小结

第10章ACM经典案例

10.1递归算法

10.1.1三柱汉诺塔问题

10.1.2传染病问题

10.1.3N皇后问题

10.2DFS与BFS问题

10.2.1DFS之迷宫难题

10.2.2BFS之管道和指针游戏

本章小结

附录A全国计算机专业数据结构考研大纲

参考文献

前言

一、 为什么要写本书
随着信息处理技术和计算机技术的飞速发展,计算机在各个学科和领域得到了广泛的应用,而随着计算机处理的数据量迅速增大,数据类型随之增多,结构复杂的数据和数据关系的处理是我们必须面对的问题,由此设计一个结构好、效率高的软件,就必须分析并设计出好的数据结构,以便优质地处理数据的存储、数据传输和输出处理等操作。
“数据结构”作为计算机专业的一门核心基础课程,是计算机程序设计的重要理论和技术基础。通过本课程的学习,学生不仅可掌握各种组织方式下数据的存储、运算,而且还能使学生熟悉程序设计的基础方法,提高利用数据结构和算法解决实际问题的能力。
二、 内容特色
本书有如下特色。
（1） 结构清晰、内容全面、文字描述简单明了、可读性强。
（2） 图文并茂,全书使用150余幅图描述数据结构概念、算法的基本思想、算法的执行过程。
（3） 强调数据结构中的3种逻辑结构和2种存储表示。
全书强调3种逻辑结构,即线性结构、树形结构、图形结构,对每一种结构都采用2种存储方式（即顺序存储和链式存储）表示,但必须注意每一种逻辑结构要结合其特点选择合适的存储方式表示。
（4） 由浅入深归纳总结每种数据结构的算法设计方法。
例如，利用创建单链表的算法,可以帮助实现链表的逆置、拆分、合并、排序等操作,利用二叉树的遍历算法,可以帮助实现查找结点、计算结点数量、计算二叉树高度、构造二叉树等。同样，图的很多算法都是基于遍历算法的。如果读者掌握了基本算法的设计方法,设计相关问题就容易多了。
三、 结构安排
本书共分5篇10章,具体内容如下。
第1篇即第1章，为绪论篇。
第1章为绪论,主要介绍数据结构的基本概念、数据的存储表示和算法的时间复杂度等内容。
第2篇即第2~5章，为线性结构篇。
第2章为线性表（线性表是最基本的数据结构）,主要介绍了线性表的概念、线性表的抽象数据类型、线性表的两种存储结构(顺序表和链表)和常见的基本算法设计,并通过示例深入理解线性表的应用。
第3章为栈与队列,是操作受限制的线性表,主要介绍栈的概念、栈的抽象数据类型、栈的两种存储结构(顺序栈和链栈)和基本运算算法设计、栈的应用算法设计； 队列的概念、队列的抽象数据类型、队列的两种存储结构(顺序队列和链队列)和各种基本运算算法设计、队列的应用算法设计。
第4章为串,是特殊的线性表,主要介绍了串的概念、串的存储结构、串的几种基本运算算法设计和串的模式匹配算法设计。
第5章为数组和广义表,主要介绍了数组的概念、数组按行和按列两种存储方式实现、几种特殊矩阵的压缩存储方式、稀疏矩阵压缩存储及转置算法设计； 广义表的概念、广义表的存储结构及相关算法设计。
第3篇即第6章，为树形结构篇。
第6章为树和二叉树,主要介绍树的概念及逻辑表示、树的性质、树的存储结构； 介绍二叉树的概念、二叉树的性质、二叉树的基本运算算法设计、二叉树的遍历运算算法设计(非递归方式和递归方式)、线索二叉树的概念和构造、哈夫曼树的概念和构造、哈夫曼编码构造等。
第4篇即第7章，为图形结构篇。
第7章为图,主要介绍图的基本概念和逻辑表示、图的存储结构、图的基本运算算法设计、图的遍历算法(DFS和BFS)及相关应用,尤其是工程上常用的最小生成树、最短路径算法、AOV网及AOE网的基本算法等。
第5篇即第8~10章，为数据运算篇。
第8章为查找,主要介绍查找的概念、查找效率的度量标准。本章分为静态表的查找、动态查找表和哈希表查找,分析并对比各种查找方法的查找效率。
第9章为排序,主要介绍排序的概念、排序效率的度量标准，插入排序、交换排序、选择排序、归并排序、基数排序的算法设计,并对各排序算法的时间复杂度和空间复杂度进行分析和比较。
第10章为ACM经典案例,主要介绍以数据结构理论知识为基础的深化应用,探讨如何综合应用数据结构基础知识参与程序设计竞赛,增强学生的竞技精神。
本书的第1、2章由周丽平编写,第3、5、6、7、8、10由薛晓亚编写,第4章由马金霞编写,第9章由陈延波编写。全书由薛晓亚统稿。

源代码下载

四、 读者对象
 对数据结构课程感兴趣的读者。
 计算机相关专业的本科生、专科生。
 职业技术类院校计算机相关专业本科生、专科生。
五、 致谢
感谢张秀国、高伟林、赵晓庆、田路阳、李冉冉等在本书的资料整理及校对过程中所付出的辛勤劳动。
由于编者的水平和经验有限,加之时间比较仓促,疏漏之处在所难免,敬请读者批评指正。
编者
2019年2月

第5章
数组和广义表

前几章讨论的线性结构中的数据元素都是非结构的原子类型,原子类型的数据元素是不能再分解的。本章讨论的两种数据结构（数组和广义表）与之前讨论的数据结构有所不同,这两种数据结构均可以被看成是线性表在下述含义上的扩展，即表中的数据元素本身也是一个数据结构。
数组是C/C 中常见的数据类型,几乎所有的程序设计语言都把数组类型设定为固有类型。本章以抽象数据类型的形式讨论数组的定义和实现,便于加深对数组类型的理解。
5．1数组的定义及抽象数据类型
5．1．1数组的定义

数组是由多个类型相同的数据元素组成的一个有限序列。在定义上,数组与线性表的形式几乎一致。从逻辑结构上看,数组A是由n(n>1)个相同类型数据元素a1,a2,…,an构成的有限序列,其逻辑表示为
A=(a1,a2,…,an)
其中,ai(1≤i≤n)表示数组A的第i个元素。
一个二维数组可以被看作是一个特殊的一维数组,即每个数组元素都是相同类型的一维数组。以此类推,任何多维数组都可以被看成是一个线性表,且表中的每个数据元素也是一个线性表。多维数组是线性表的推广。
推广到d(d≥3)维数组,不妨把它看作是一个以d-1维数组作为数据元素的线性表； 或者这样理解,它是一种较复杂的线性表结构,由简单的数据结构（即线性表）辗转合成而得。
5．1．2数组的抽象数据类型
抽象数据类型d维数组的定义如下。

ADT Array{

数据对象:

D={aj1,j2,…,jd| ji=1,…,bi,i=l,2,…,d}//第i维的长度为bi

 数据关系:

R={r1,r2,…,rd}

ri={|1≤jk≤bk ,1≤k≤d且k≠i,1≤ji≤bi-1,i=2,…,d}

 基本运算:

Value(A,&e,index1,…,indexd)

初始条件:A是d维数组,e为元素变量,随后是d个下标值。

操作结果:若各下标不超界,则e赋值为所指定的A的元素值,并返回OK。

Assign(&A,e,index1,…,indexn)

初始条件:A是d维数组,e为元素变量,随后是d个下标值。

操作结果:若下标不超界,则将e的值赋给所指定的A的元素,并返回OK。

ADisp(A,b1,b2,…,bd)

初始条件:A是d维数组,随后是d个下标值。

操作结果:输出d维数组A的所有元素值。

} ADT Array

数组一般不进行插入和删除操作。通常，数组被建立以后，元素的个数和元素之间的关系不再发生变化。这个特点使得数组不像线性表那样，可以在表中的任意位置上进行插入和删除元素。数组中常见的操作是： 给定下标读取数组元素的值和修改数组元素的值。因此,除了使用下标,也可以通过计算数组元素的地址实现上述操作。