数据结构:C语言描述

“数据结构”是计算机科学及相关学科的一门核心专业基础课，该门课程在计算机科学及相关学科的课程体系中处于承上启下的核心地位，它一方面扩展和深化了在“离散数学”“程序设计语言”等课程学到的基本技术和方法，另一方面为进一步学习其他专业课，如“算法设计与分析”“计算方法”“操作系统”“编译原理”“软件工程”等奠定坚实的理论与实践基础。此外，数据结构中所研究的常见数据组织和存储形式及经典算法还是所有计算机软件开发人员必须掌握的技术。正是由于“数据结构”课程的重要作用，目前绝大多数高校研究生招生专业课考试中都将“数据结构”列入必考科目，许多IT企业的面试和笔试也都广泛地涉及对数据结构相关知识的考查。

本书共分为9章，内容基本覆盖了大多数高校的“数据结构”课程教学大纲和考研大纲。第1章为绪论，介绍了数据结构中的基本概念和常用术语；第2章到第7章详细地介绍了常用的线性数据结构和非线性结构，其中包括线性表、栈和队列、串、数组和广义表、树和二叉树以及图；第8章和第9章分别介绍了数据处理中经常需要使用的经典查找和排序算法。目录中标记“*”的部分是选学内容。本书中涉及的所有算法均采用C语言描述，并在VC   6.0下全部进行了调试和运行。读者应在学习教材中的算法之前，提前复习一下C语言中的指针、函数、结构体、动态内存分配和预定义等内容。

本书的主要特点如下：

1. 内容选择及组织合理，涵盖了“数据结构”课程的核心知识和主要算法。教材编写主要针对计算机及相关专业本科及大中专在校学生，面向数据结构的初学者，既适用于高校学生的教学，又适用于技术人员的自学。

2. 编写深入浅出，内容详略得当，重点突出，难易适中，着重对学生学习中常见的问题和难点进行详细讲解，有效减少学生学习该课程的困难。本书配备了丰富的习题，便于学生的课下复习和巩固。

3. 全部算法均采用标准C语言进行描述，程序风格简洁易懂，注释详细，算法分析充分，便于学生的学习理解及上机实践，可帮助学生培养良好的程序设计风格，掌握进行复杂程序设计的技能。

4. 各部分内容均配套应用实例进行讲解，使读者可以深入理解数据结构中的经典算法，并将其应用于解决实际问题。 

教材的编者均为具有“数据结构”及相关课程一线教学经验长达二十年以上的高校教师，对课程内容和授课对象特点十分熟悉，对知识体系中的重点和难点问题把握得当，内容讲解深入浅出，算法描述清晰易懂，理论知识和应用实例紧密结合。教材中每部分内容都配备有对应的程序实例和课后上机实验题目，能够有效增强学生对经典算法的理解和运用能力。教材的第1章到第4章由西安理工大学计算机学院雷西玲老师编写；第5、6、8、9章由西安理工大学计算机学院李晔老师编写；第7章由西安理工大学自动化学院孙旭霞老师编写。

本书的出版获得西安理工大学教材立项的支持，西安理工大学计算机学院的院领导及教学专家对于本书的编写给予了热情的帮助和指导，西安理工大学计算机学院的罗作民老师对本书的章节设置和内容选择提出了宝贵的意见，在此一并表示衷心的感谢。

本书既可作为普通高等学校计算机科学及相关学科本科及专科学生“数据结构”课程的教材使用，也可作为考研学生、软件水平考试人员和计算机程序员的参考读物。

由于编者水平有限，书中难免存在疏漏之处，敬请读者批评指正。

编　者

2019年10月

 

“数据结构”是计算机科学及相关学科的一门核心专业基础课，主要讨论各种数据结构在计算机中的存储表示及算法实现，是一门集技术性、理论性和实践性于一体的课程。本书综合了诸多院校的课程教学大纲以及*2018年考研大纲中《计算机学科专业基础综合考试大纲》进行编写，书中所有算法描述均采用标准C语言。教材内容安排合理，难易程度适中，讲解深入浅出。每部分内容都配备有对应的程序实例和丰富的习题，可有效增强读者对经典算法的理解和运用能力。全书共9章，内容包括绪论、线性表、栈和队列、串、数组和广义表、树和二叉树、图、查找、排序。

本书主要面向本科及大中专计算机及相关专业的在校学生和具有C语言程序设计基础的数据结构自学者，既可作为高校数据结构课程的教材，又可供从事软件设计和开发的技术人员参考。

李晔，西安理工大学计算机科学与工程学院，副教授，姓名：李晔  年龄:    43  职称职务： 副教授   ；博士

工作院校(系)：西安理工大学计算机科学与工程学院

讲授课程：C语言、数据结构、软件工程等

主要研究项目及领域：计算机应用技术

作者简介：本科、硕士及博士所学专业均为计算机相

关专业，有二十多年从事计算机课程一线教学的经验，

长期主讲数据结构课程。

第1章　绪论 1

1.1　什么是数据结构 1

1.2　数据结构的概念及有关术语 1

1.3　算法和算法分析 5

习题 7

第2章　线性表 9

2.1　线性表的定义 9

2.2　线性表的基本运算 9

2.3　顺序存储结构线性表 10

2.3.1　线性表的顺序存储结构 10

2.3.2　顺序存储结构线性表的基本运算 11

2.3.3　顺序存储结构线性表的应用 15

2.4　链式存储结构线性表 20

2.4.1　单链表 20

2.4.2　循环链表 28

2.4.3　双向链表 29

2.4.4　静态链表 30

2.4.5　链式存储结构线性表的应用 31

2.5　小结 38

习题 38

第3章　栈和队列 42

3.1　栈 42

3.1.1　栈的定义及基本运算 42

3.1.2　顺序存储结构栈的基本运算 42

3.1.3　链式存储结构栈的基本运算 45

3.1.4　栈的应用实例 47

3.1.5　栈与递归 48

3.2　队列 50

3.2.1　队列的定义及基本运算 50

3.2.2　顺序存储结构队列的基本运算 50

3.2.3　链式存储结构队列的基本运算 53

3.2.4　队列的应用 55

3.3　小结 57

习题 58

第4章　串 61

4.1　串的概念及基本运算 61

4.1.1　串的基本概念 61

4.1.2　串的基本运算 62

4.2　顺序存储结构串的运算 63

4.2.1　串的定长顺序存储结构 63

4.2.2　定长顺序存储结构串的基本运算 64

4.3　串的堆分配存储结构及其运算 66

4.3.1　串的堆分配存储结构 66

4.3.2　堆分配存储结构串的运算 66

4.4　串的链式存储结构及基本运算 68

4.4.1　串的链式存储结构 68

4.4.2　链串的基本运算 69

4.5　串的模式匹配 70

4.5.1　简单模式匹配算法——BF算法 70

4.5.2　无回溯的模式匹配算法——KMP算法 72

*4.5.3　next函数的改进 77

4.6　小结 79

习题 79

第5章　数组和广义表 81

5.1　数组 81

5.1.1　数组的定义及逻辑结构 81

5.1.2　数组的存储结构 83

5.1.3　特殊矩阵的压缩存储 84

5.1.4　数组应用举例 88

5.2　广义表 91

5.2.1　广义表的定义 91

5.2.2　广义表的存储结构 93

5.2.3　广义表基本操作实现 94

5.2.4　广义表应用举例 97

5.3　小结 98

习题 99

第6章　树和二叉树 102

6.1　树的定义及有关术语 102

6.1.1　树的定义 102

6.1.2　常用术语 102

6.2　二叉树 103

6.2.1　二叉树的定义 103

6.2.2　二叉树的性质 105

6.2.3　二叉树的存储结构 105

6.2.4　二叉树的遍历 107

6.2.5　线索二叉树 113

6.2.6　哈夫曼树 117

6.3　树和森林 122

6.3.1　树的存储结构 122

6.3.2　树或森林与二叉树的转换 124

6.3.3　树和森林的遍历 125

6.4　小结 126

习题 126

第7章　图 130

7.1　图的定义及有关术语 130

7.2　图的存储结构 134

7.2.1　邻接矩阵 134

7.2.2　邻接表 137

7.2.3　十字链表 139

*7.2.4　邻接多重表 141

7.3　图的遍历 143

7.3.1　深度优先搜索 143

7.3.2　广度优先搜索 145

7.3.3　图的连通性 148

7.4　小生成树 150

7.4.1　普里姆算法 150

7.4.2　克鲁斯卡尔算法 153

7.5　有向无环图及其应用 156

7.5.1　拓扑排序 156

7.5.2　关键路径 161

7.6　短路径 166

7.6.1　单源短路径 166

7.6.2　每一对顶点之间的短路径 169

7.7　图的应用实例 172

7.8　小结 174

习题 175

第8章　查找 180

8.1  查找的有关概念 180

8.2　线性表的查找 181

8.2.1　顺序查找 181

8.2.2　二分查找 182

8.2.3　分块查找 184

8.3　树表的查找 185

8.3.1　二叉排序树 185

8.3.2　平衡二叉树 190

8.3.3　B-树 193

8.3.4　B 树 196

8.4　哈希查找 197

8.4.1　哈希表的概念及哈希函数的构造 197

8.4.2　哈希表的建立 199

8.4.3　冲突的处理方法 199

8.4.4　哈希查找的实现 201

8.5　小结 202

习题 203

第9章　排序 206

9.1　排序的有关概念 206

9.2　插入排序 207

9.2.1　直接插入排序 207

9.2.2　折半插入排序 208

9.2.3　希尔排序 209

9.3　交换排序 211

9.3.1　冒泡排序 211

9.3.2　快速排序 212

9.4　选择排序 214

9.4.1　简单选择排序 214

9.4.2　堆排序 216

9.5　归并排序 219

9.6　基数排序 221

9.7　多关键字排序 223

9.8　小结 224

习题 225

参考文献 229

“数据结构”是计算机科学及相关学科的一门核心专业基础课，主要讨论各种数据结构在计算机中的存储表示及算法实现，是一门集技术性、理论性和实践性于一体的课程。本书综合了诸多院校的课程教学大纲以及*2018年考研大纲中《计算机学科专业基础综合考试大纲》进行编写，书中所有算法描述均采用标准C语言。教材内容安排合理，难易程度适中，讲解深入浅出。每部分内容都配备有对应的程序实例和丰富的习题，可有效增强读者对经典算法的理解和运用能力。全书共9章，内容包括绪论、线性表、栈和队列、串、数组和广义表、树和二叉树、图、查找、排序。

本书主要面向本科及大中专计算机及相关专业的在校学生和具有C语言程序设计基础的数据结构自学者，既可作为高校数据结构课程的教材，又可供从事软件设计和开发的技术人员参考。

李晔，西安理工大学计算机科学与工程学院，副教授，姓名：李晔  年龄:    43  职称职务： 副教授   ；博士

工作院校(系)：西安理工大学计算机科学与工程学院

讲授课程：C语言、数据结构、软件工程等

主要研究项目及领域：计算机应用技术

作者简介：本科、硕士及博士所学专业均为计算机相

关专业，有二十多年从事计算机课程一线教学的经验，

长期主讲数据结构课程。

数据结构是计算机科学及相关学科的一门核心专业基础课，该门课程在计算机科学及相关学科的课程体系中处于承上启下的核心地位，它一方面扩展和深化了在离散数学、程序设计语言等课程学到的基本技术和方法，另一方面为进一步学习其他专业课，如算法设计与分析、计算方法、操作系统、编译原理、软件工程等奠定坚实的理论与实践基础。此外，数据结构中所研究的常见数据组织和存储形式及经典算法还是所有计算机软件开发人员必须掌握的技术。正是由于数据结构课程的重要作用，目前绝大多数高校研究生招生专业课考试中都将数据结构列入必考科目，许多IT企业的面试和笔试也都广泛地涉及对数据结构相关知识的考查。

本书共分为9章，内容基本覆盖了大多数高校的数据结构课程教学大纲和考研大纲。第1章为绪论，介绍了数据结构中的基本概念和常用术语；第2章到第7章详细地介绍了常用的线性数据结构和非线性结构，其中包括：线性表、栈和队列、串、数组和广义表、树和二叉树以及图；第8章和第9章分别介绍了数据处理中经常需要使用的经典查找和排序算法。本书中涉及的所有算法均采用C语言描述，并在VC  6.0下全部进行了调试和运行。读者应在学习教材中的算法之前，提前复习一下C语言中的指针、函数、结构体、动态内存分配和预定义等内容。

教材的编者均为数据结构及相关课程一线教学经验长达二十年以上的高校教师，对课程内容和授课对象特点十分熟悉，对知识体系中的重点和难点问题把握得当，内容讲解深入浅出，算法描述清晰易懂，理论知识和应用实例紧密结合。教材中每部分内容都配备有对应的程序实例和课后上机实验题目，能够有效增强学生对经典算法的理解和运用能力。教材的第1章到第4章由西安理工大学计算机学院雷西玲老师编写；第5、6、8、9章由西安理工大学计算机学院李晔老师编写；第7章由西安理工大学自动化学院孙旭霞老师编写。

本书所具备的主要特点如下：

1. 内容选择及组织合理，涵盖了数据结构课程的核心知识和主要算法。教材编写主要针对计算机及相关专业本科及大中专在校学生，面向《数据结构》的初学者，既适用于高校学生的教学，又适用于技术人员的自学。

2. 教材编写深入浅出，内容详略得当，重点突出，难易适中，着重对学生学习中常见的问题和难点进行详细讲解，有效减少学生学习该课程的困难。教材配备了丰富的习题，便于学生的课下复习和巩固。

3. 本书全部算法均采用标准C语言进行描述，程序风格简洁易懂，注释详细，算法分析充分，便于学生的学习理解及上机实践，可帮助学生培养良好的程序设计风格，掌握进行复杂程序设计的技能。

4. 各部分内容均配套应用实例进行讲解，使读者可以深入理解数据结构中的经典算法，并将其应用在实际问题的解决中。 

本书的出版获得西安理工大学教材立项的支持，西安理工大学计算机学院的院领导及教学专家对于本书的编写给予了热情的帮助和指导，西安理工大学计算机学院的罗作民老师对教材的章节设置和内容选择提出了宝贵的意见，在此一并表示衷心的感谢。

本书既可作为普通高等学校计算机科学及相关学科本科及专科学生数据结构课程的教材使用，也可作为考研学生、软件水平考试人员和计算机编程者的参考文献。

由于编者水平有限，书中难免存在错误和疏漏之处，敬请读者批评指正。