“数据结构”是高等院校计算机及其相关专业的重要课程,也是计算机软件开发及应用人员必备的专业基础。本书首先介绍数据结构与算法的基础知识,然后系统地论述线性表、栈、队列、数组、串、树和二叉树、图等基本数据结构,并讨论了常用的查找和排序技术。
       本书语言与选材精练、层次清晰、深入浅出。各章节所涉及的数据结构与算法均给出了C语言描述，并附有大量的经典习题。
       本书适合作为高等院校计算机类和电子信息类专业数据结构课程的教材,也可供从事计算机软件开发及应用的工程技术人员阅读和参考，还可作为研究生入学考试的复习参考书。

       党的二十大报告指出：“教育是国之大计、党之大计。培养什么人、怎样培养人、为谁培养人是教育的根本问题。育人的根本在于立德。全面贯彻党的教育方针，落实立德树人根本任务，培养德智体美劳全面发展的社会主义建设者和接班人。”随着人工智能（artificial intelligence,AI）技术的发展，AI人才紧缺，信息技术相关课程成为AI技术人才培养的主战场。
      “数据结构”是电子信息类和计算机类专业重要的专业基础课程与核心课程之一。全国硕士研究生入学统一考试计算机科学与技术学科全国联考的考试科目“计算机学科专业基础综合”涵盖四门课程，“数据结构”作为重要的一门，其所占比例和分值均较高。“数据结构”课程主要是学习基本数据结构及其应用、检索和排序算法的各种实现方法与分析比较。在“数据结构”课程教学中，对数据结构本质和各种算法思想的掌握与理解并不依赖描述工具。
       为适应我国AI技术人才培养的需求，进一步提高计算机及相关专业“数据结构”课程的教学质量，编者根据多年教学经验，结合高等教育普及化的趋势，编写了本书。
       本书分为3篇：第1篇为基础理论，重点介绍几种基本数据结构、检索和排序的理论基础；第2篇是经典试题，并给出了试题的详尽解析；第3篇给出了较为详细的基础实验指导。附录A给出了北京科技大学天津学院“数据结构与算法”课程设计的任务书，以方便教师开展课程实验教学，帮助学生掌握数据结构知识，提高算法设计和实践能力。
       本书具有以下特色：
     （1）对数据结构的基本概念、基本理论的阐述注重科学性和严谨性。对各种基本算法描述尽量详细，叙述清楚。对许多算法给出了详尽的图示，帮助读者理解算法的思路，以便读者更好地掌握理论知识，提高抽象思维的能力。
     （2）注重实用。对于数据结构和算法的描述，采用了大多数读者较熟悉的C语言进行描述，每个算法都用C语言的函数形式给出。
     （3）选取多层次经典试题。试题设计严谨，考查知识点全面而深入。题目语言表达准确，逻辑清晰，无歧义；难度适中，区分度高，能准确反映不同水平学生的能力。
       本书由顾玲芳主编，李亚红、张永拓、赵成参编。具体编写分工如下：第1篇的第1~5章由顾玲芳编写，第6章由李亚红编写，第7章由张永拓编写；第2篇的第1~5章由顾玲芳编写，第6章由李亚红编写，第7章由张永拓编写；第3篇及附录A由赵成编写。全书由顾玲芳统稿。在本书写作过程中，编者得到了数据结构课程组老师的指导和帮助，在此，向他们表示衷心的感谢。
       由于编者水平有限，加上时间仓促，书中难免有疏漏及欠妥之处，恳请同行专家及广大读者批评指正。编者的电子邮箱是jellyku@qq.com。



      编者
  2025年1月

第1篇基础理论
第1章绪论2
1.1数据结构概述2
1.1.1数据结构的相关概念3
1.1.2数据结构的三要素3
1.1.3抽象数据类型6
1.2算法和算法评价6
1.2.1算法概念与特性6
1.2.2算法的描述6
1.2.3算法的评价7
第2章线性表及其存储8
2.1线性表的概念8
2.2线性表的顺序存储9
2.3线性表的链式存储13
2.3.1单链表13
2.3.2其他链表17
第3章特殊线性表19
3.1栈及其存储20
3.1.1栈的定义20
3.1.2顺序栈20
3.1.3链栈23
3.2队列及其存储24
3.2.1队列的定义24
3.2.2顺序队列25
3.2.3循环队列27
3.2.4链队29
3.3数组及其存储31
3.3.1数组的定义31
3.3.2数组的存储31
3.4矩阵的存储32
3.4.1特殊矩阵的压缩存储33
3.4.2稀疏矩阵的存储37
3.5广义表39
3.5.1广义表的定义39
3.5.2广义表的存储40
3.6串41
3.6.1串的定义41
3.6.2串的存储结构41
3.6.3串的模式匹配42
第4章树和二叉树47
4.1树48
4.1.1树的相关概念48
4.1.2树的存储49
4.1.3树的遍历50
4.2二叉树的概念与性质50
4.2.1二叉树的基本概念50
4.2.2二叉树的性质51
4.3二叉树的存储与遍历51
4.3.1二叉树的存储51
4.3.2二叉树的遍历52
4.4二叉树的线索化及与树的转换57
4.4.1线索二叉树58
4.4.2二叉树与树的转换60
4.5二叉树的应用62
4.5.1二叉排序树62
4.5.2平衡二叉树66
4.5.3哈夫曼树71
第5章图74
5.1图及其存储75
5.1.1图概述75
5.1.2图的存储77
5.2图的遍历80
5.2.1深度优先遍历80
5.2.2广度优先遍历81
5.3图的最小生成树83
5.3.1普里姆算法83
5.3.2克鲁斯卡尔算法86
5.4有向无环图及其应用89
5.4.1拓扑排序89
5.4.2关键路径91
5.5最短路径问题94
5.5.1单源最短路径95
5.5.2任意顶点对的最短路径97
第6章查找99
6.1线性表的基本概念100
6.2线性表的查找1006.2.1顺序查找100
6.2.2二分查找102
6.2.3分块查找105
6.3散列查找107
6.3.1散列存储107
6.3.2构造散列函数107
6.3.3冲突处理108
6.3.4查找分析108
第7章排序112
7.1排序的基本概念112
7.2插入排序113
7.2.1直接插入排序113
7.2.2希尔排序115
7.3交换排序116
7.3.1冒泡排序116
7.3.2快速排序118
7.4选择排序120
7.4.1直接选择排序120
7.4.2堆排序121
7.5归并排序126
7.6基数排序127
7.7排序算法总结131

第2篇经典试题与解析
第1章绪论133
1.1数据结构经典试题133
一、选择题133
二、综合应用题134
1.2算法经典试题134
一、选择题134
二、综合应用题136
第2章线性表及其存储137
2.1顺序表经典试题137
一、选择题137
二、综合应用题140
2.2链表经典试题141
一、选择题141
二、综合应用题144
第3章特殊线性表147
3.1栈经典试题147
一、选择题147
二、综合应用题150
3.2队列经典试题151
一、选择题151
二、综合应用题155
3.3数组经典试题157
一、选择题157
二、综合应用题158
3.4矩阵经典试题158
一、选择题158
二、综合应用题160
3.5广义表经典试题162
选择题162
3.6串经典试题162
选择题162
第4章树和二叉树165
4.1树经典试题165
一、选择题165
二、综合应用题166
4.2二叉树经典试题168
一、选择题168
二、综合应用题171
4.3二叉树存储与遍历经典试题172
一、选择题172
二、综合应用题173
4.4线索二叉树经典试题175
一、选择题175
二、综合应用题176
4.5二叉树应用经典试题177
一、选择题177
二、综合应用题185
第5章图189
5.1图概念及存储经典试题189
一、选择题189
二、综合应用题192
5.2图的遍历经典试题194
一、选择题194
二、综合应用题1955.3最小生成树经典试题197
一、选择题197
二、综合应用题198
5.4有向无环图经典试题200
一、选择题200
二、综合应用题204
5.5最短路径经典试题207
一、选择题207
二、综合应用题208
第6章查找211
6.1线性表查找经典试题211
一、选择题211
二、综合应用题214
6.2散列查找经典试题215
一、选择题215
二、综合应用题218
第7章排序221
7.1插入排序经典试题221
一、选择题221
二、综合应用题222
7.2交换排序经典试题224
一、选择题224
二、综合应用题226
7.3选择排序经典试题227
一、选择题227
二、综合应用题229
7.4归并排序经典试题230
一、选择题230
二、综合应用题232

第3篇实验指导
实验1基于线性表的学生信息管理237
一、实验目的237
二、实验内容237
三、实验步骤237
实验2基于线性表的大整数运算240
一、实验目的240
二、实验内容240
三、实验步骤240
实验3基于栈的后缀表达式求值243
一、实验目的243
二、实验内容243
三、实验步骤243
实验4基于二叉树的表达式求值245
一、实验目的245
二、实验内容245
三、实验步骤245
实验5基于哈夫曼树的数据压缩算法247
一、实验目的247
二、实验内容247
三、实验步骤247
实验6基于Dijkstra算法的最短路径249
一、实验目的249
二、实验内容249
三、实验步骤249
实验7基于不同方法的检索系统251
一、实验目的251
二、实验内容251
三、实验步骤251附录A课程设计任务书253
一、目的与要求253
二、课程设计任务253
三、课程设计步骤254
四、进度安排255
五、报告要求255
参考文献256

       顾玲芳，北京科技大学天津学院信息工程学院计算机基础课程组组长，副教授，专业方向为软件工程，主要教授计算机基础、C语言、C等课程；曾参与中国冶金教育学会2009年度教育科学研究规划重点课题《网络环境下应用型本科院校知识教学模式和学生在线学习模式研究》；先后发表论文《应用型本科VFP教学中的教学方法研究》、《VFP6.0索引教学经验谈》、《高校非计算机专业计算机基础教学改革之浅见》。

1. 理论扎实，讲解透彻：以 C 语言为描述工具，系统讲解线性表、树、图等核心数据结构知识，算法描述详尽，搭配大量图示辅助理解，严谨阐述基本概念与理论，助力读者掌握数据结构本质与算法思想。
2. 学练结合，助力提升：精选多层次经典试题，知识点覆盖全面，题目设计严谨、难度适中，且解析细致，帮助读者攻克学习难点；同时配备丰富实验指导与课程设计任务书，促进理论知识向实践能力转化。
3. 定位精准，适用广泛：契合人工智能人才培养需求，无论是高校师生开展教学与学习，考研学子复习备考，还是计算机从业者巩固专业基础，都能从本书中汲取养分，夯实数据结构知识体系。