数据结构

出版时间：2009-4  出版社：科学出版社  作者：郑泳，方风波 主编  页数：248  

前言

　　“数据结构”是计算机及相关专业的一门重要的专业基础课，也是一门必修的核心课程。其课程教学要求是，学会分析研究计算机加工的数据对象的特性，以便在实际应用中选择适当的数据结构、存储结构和相应的算法，初步掌握算法的时间与空间性能的分析技巧，进行复杂程序设计的训练。　　本书是为高职高专计算机及相关专业编写的教材，选材基本上覆盖了数据结构的主要内容。本书注重培养读者的实际操作能力，侧重于应用，力求内容与应用实例相结合；在介绍基本理论时，尽量做到浅显易懂，不过分追求知识的系统性和完整性；对于一些过于难懂的理论尽量省略；对各种数据结构问题多以实例来讲解，叙述上通俗易懂，可使读者加深对基本概念的理解，且有利于提高读者分析问题和解决问题的能力。　　为了把高职高专学校培养技能型人才的目标落到实处，针对“数据结构”的技术性与综合性较突出的特点，我们为每章编写了相应的实验上机指导及实训项目指导。对教学内容中的每一种数据结构，其各种操作即实验，要求学生必须高质量完成；而对解决实际问题中的操作属于技能训练即实训项目，要求学生根据算法思想完成实现，达到技能训练的目的。本书中的实训项目有4个，涉及线性表、栈、串、树、图、排序、查找等数据结构的实际应用，由于课堂时间有限，读者可以根据自身的实际掌握情况，在课余选做。　　本书使用标准的C语言作为算法描述工具，主要考虑的是：.C语言基本上是各校教学计划中的基础语言，以C语言描述数据结构，在理解和掌握数据结构内容的同时，有利于进一步提高软件设计的能力。同时，目前各种考试，如计算机等级考试，特别是高职专升本及自学考试，均要求学生具有C语言和数据结构的基础。　　全书共分9章；第1章引人数据结构与算法的一些基本概念与术语，并对算法描述及算法分析作了简要说明；第2－5章由浅人深地介绍了线性结构中的线性表、栈、队列、数组及字符串的基本定义、算法和应用；第6、7章介绍了非线性结构的树、二叉树和图；第8、9章介绍了在实际应用中使用非常广泛的查找和排序的基本算法，并进行了简单的时间、空间性能分析。每章配有相当数量的例题和习题，便于读者巩固所学知识。本书配有电子课件等教学资源，下载网址：WWW.abook.cn。本书配套电子课件曾在2008年湖北省教师电教作品大赛评选活动中，荣获网络课程类二等奖；在全国第二届实践教学竞赛中，荣获多媒体课件类三等奖；在“第三届全国高等学校计算机课件评比”中荣获三等奖。

内容概要

本书介绍了各种常用的数据结构及其操作，包括线性表、栈和队列、串、数组、树、图、查找和排序等。全书使用标准的C语言作为算法描述工具。    本书内容通俗易懂，侧重于应用，力求内容与应用实例相结合，并附有上机实验和实训指导，有利于提高读者分析问题和解决问题的能力。    本书可以作为高职高专院校计算机相关专业的教材，也可以作为专升本、自学考试的辅导教材。

书籍目录

前言第1章  概论  1.1  基本概念和术语    1.1.1  逻辑结构    1.1.2  存储结构  1.2  算法的描述与分析    1.2.1  算法描述    1.2.2  算法分析    1.2.3  时间复杂度    1.2.4  空间复杂度  本章小结  习题第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.4  单向循环链表  2.5  双向循环链表    2.5.1  双向链表    2.5.2  双向循环链表  本章小结  习题第3章  栈和队列  3.1  栈    3.1.1  栈的定义与基本运算    3.1.2　顺序栈    3.1.3　链栈　3.2　队列    3.2.1　队列的定义及基本运算    3.2.2　顺序队列    3.2.3　链队列　3.3　栈和队列的应用    3.3.1　栈的应用    3.3.2　队列的应用　本章小结　习题第4章　串　4.1　串及其运算    4.1.1　串的基本概念    4.1.2　串的基本运算　4.2　串的存储结构    4.2.1　串的顺序存储    4.2.2　串的链式存储　4.3　串运算的实现　4.4　串的模式匹配运算    4.4.1　有回溯的模式匹配算法（BF算法）    4.4.2　无回溯的模式匹配算法（KMP算法）　本章小结　习题第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　广义表的存储　本章小结　习题第6章  树第7章  图第8章  排序第9章  查找附录参考文献

章节摘录

　　图是一种网状数据结构，属于多对多的非线性结构，图中的每个结点可以有多个直接前趋和直接后继。图的存储包括存储图中顶点的信息和边的信息两个方面。这两个部分既可以分开单独存储，也可以用结构体形式一起存储。图的存储结构有邻接矩阵、邻接表等。　　图的遍历包含深度优先搜索遍历和广度优先搜索遍历。对于用邻接矩阵结构存储的图，从某个给定的顶点出发的图的遍历得到的访问顶点次序是唯一的，而对于邻接表结构存储的图从某个给定的顶点出发的图的遍历得到的访问顶点次序随建立邻接表的不同而可能不同。　　一个连通图的生成树含有该图的全部n个顶点和其中n－1条边（不构成回路），其中权值之和最小的生成树称为最小生成树。求最小生成树有两种不同的方法，一种是普里姆算法；另一种是克鲁斯卡尔算法。如果所采用的方法不同，得到的最小生成树中边的次序也可能不同，但最小生成树的权值之和相同。　　求图的最短路径有两种算法，其一是单源点的最短路径，用迪杰斯特拉算法来实现；其二是所有顶点对的最短路径，用弗洛伊德算法来实现。