文档介绍：!" 世纪高等学校应用型教材
数据结构(! 语言版)
胡学钢# 主# 编#
高等教育出版社
书
内容提要
为满足不同专业和教学层次对数据结构课程的要求,本书从数据结构的核心内容和实际需要出发,以简明
的方式介绍了数据结构的基本知识。全书共! 章,主要内容包括:概论、线性表、栈、队列、数组、树、图、查找、排
序和文件等。每章后都配有习题。
本书语言精炼,例题丰富,内容由浅入深,简明易懂,可作为本科非计算机专业、成人以及高职高专计算机相
关专业的教材或参考书。
本书的配套电子教案可从高等教育出版社网站下载,网址为"##$:% % &&&’"($’()*’+, 或"##$:% % +-’"($’+./’
+,。此外,本书还配有实验指导和习题解答可供读者学习参考。
前! ! 言
在计算机及应用专业及相关专业的课程中,数据结构是重要的专业基础课程,是提高软件设
计水平以及学习后续课程所必需的基础。课程中介绍了软件设计中常见的线性表、串、栈和队
列、数组、树和二叉树、图、文件等数据结构及其在计算机内存中的存储结构和各种操作的实现,
介绍了软件设计中常用的排序和查找方法,并讨论有关运算的性能。通过对这些内容的学习,将
使学生能熟练地掌握各种常用结构的特性和各种运算的实现方法及其性能,并能在实际应用中
根据具体问题的要求设计出合理的数据结构和运算。
由于该课程中的许多内容较抽象,并缺乏有效的实验条件,使学习数据结构课程的难度较
大。
为此,本书尽量以通俗易懂的语言方式介绍有关知识,并给出了必要的例题及其分析,以帮
助读者理解知识点并掌握学习方法,易于激发读者的学习兴趣,可收到良好的学习效果。每章后
都给出了习题,有助于读者及时巩固所学的知识。
第" 章介绍了数据结构课程的研究内容、特点以及一些所需的基础知识和学习方法,有助于
整个课程的学习。
第# 章介绍了线性表和串的逻辑结构和运算,重点讨论了顺序表和链表结构及其基本运算
实现,并给出了大量例题及分析讲解。
第$ 章介绍了栈、队列和数组这三种结构的逻辑结构和运算,顺序栈、链栈、顺序( 循环)队
列和链队列及其基本运算实现,介绍了数组的有关内容。
第% 章介绍了树和森林的逻辑结构、存储结构和运算,介绍了二叉树的概念、性质、存储结
构,重点讨论了二叉树的遍历运算方法及其应用,讨论了线索二叉树的概念、应用及相关算法,并
给出了相应的例题及分析,另外还介绍了哈夫曼树的有关知识及其应用。
第& 章介绍了图的有关概念,介绍了两种常用的存储结构,重点讨论了两种遍历算法的方法
和应用,最后以通俗的语言介绍了最小生成树、拓扑排序和最短路径等几个图的应用问题及求解
算法。
第’章所介绍的查找是软件设计中常用的基本运算,本章讨论了在顺序表、树表和散列表等
几种表结构上的查找方法及其性能。
第( 章重点讨论了各种排序的方法、算法及其性能分析。
第) 章对关于文件方面的基本知识作了简要介绍。
本书由胡学钢主编。其中,第" 章、第% 章和第& 章由胡学钢编写,第# 章和第) 章由范宝
德编写,第$ 章由张晶编写,第’章由阙夏编写,第( 章由周红鹃编写。全书由胡学钢最后统稿。
由于受水平及时间所限,书中如存在不足之处,恳请读者指正。
胡学钢! ! !
#**$ 年"# 月于合肥工大
!! "
#! ! $
% " & ’
数据结构是计算机专业重要的专业基础课程,直接关系到后续课程的学
的提高。本章首先通过实例来说明《数据结构》课程在软件设计中的作用以及在计算机专业课
程中的地位,然后介绍与整个课程有关的概念、术语、算法及其描述语言和算法分析等。
!" !# !"#$%&’()
数据结构这门课程在计算机专业中有什么作用?下面从应用计算机解决实际问题的过程来
谈谈本课程在软件设计中的作用。
!" !" !# 用计算机解决实际问题的过程
在用计算机解决实际问题时,一般要经过几个步骤:首先,对具体问题抽象出数学模型,然后
针对数学模型设计出求解算法,最后编出程序上机调试,直至得到最终的解答。数值计算问题的
数学模型一般可由数学方程或数学公式来描述。但是,对非数值计算问题,如图书资料的检索、
职工档案管理、博弈游戏等问题,它们的数学模型无法用数学方程或数学公式来描述。在这类问
题的处理对象中的各分量不再是单纯的数值型数据,更多的是字符、字符串及其他用编码表示的
信息。因此,首要的问题是把处理对象中的各种信息按照其逻辑特性组织起来,再存储到计算机
中。然后设计出求解算法,并编写出相应的程序。下面简述各环节的有关内容。
建立模型:一般情况下