本书融入编者多年的教学经验和体会,参考国内外流行教材,较全面地组织教材内容,提供大量的经典算法,并适当引入考研典型题例供学生学习,具有很强的实用性、易读性、针对性。本书的体系结构科学合理,可分为11章,分别讲述绪论、线性表、树、图、查找与排序。每章后附有习题,大部分选自近年考研题目,以帮助深入理解相关内容。
更多科学出版社服务,请扫码获取。
“数据结构”课程是计算机类、电子信息类及相关专业的专业基础课。它在整个课程体系中处于承上启下的核心地位:一方面扩展和深化在离散数学、程序设计语言等课程学到的基本技术和方法;另一方面为进一步学习操作系统、编译原理、数据库等专业知识奠定坚实的理论与实践基础。本课程在教给学生数据结构设计和算法设计的同时,培养学生的抽象思维能力、逻辑推理能力和形式化思维方法,增强分析问题、解决问题和总结问题的能力,更重要的是培养专业兴趣,树立创新意识。本教材在内容选取上符合人才培养目标的要求及教学规律和认知规律,在组织编排上体现“先理论、后应用、理论与应用相结合”的原则,并兼顾学科的广度和深度,力求适用面广泛。
全书共11章。第1章综述数据、数据结构和抽象数据类型等基本概念及算法描述与分析方法;第2~9章主要从抽象数据类型的角度分别讨论线性表、栈和队列、串、数组和广义表、树和二叉树、图等基本类型的数据结构及其应用;第10章和第11章讨论查找和排序的各种方法,着重从时间性能、应用场合及使用范围方面进行分析和比较。本书对数据结构众多知识点的来龙去脉做了详细解释和说明;每章后面配有难度各异的习题,并在附录中给出习题的参考答案,供读者理解知识及复习提高之用。全书采用C语言描述数据结构和算法。
从课程性质上讲,“数据结构”是高等院校计算机科学、电子信息科学及相关专业教学计划中的一门专业基础课;其教学要求是学会分析研究计算机加工的数据结构的特性,以便为实际应用涉及的数据选择适当的逻辑结构、存储结构及其相应的算法,并初步掌握算法的时空分析技术。从课程学习上讲,“数据结构”的学习是复杂程序设计的训练过程;其教学目的是着眼于原理与应用的结合,在深化理解和灵活掌握教学内容的基础上,学会把知识用于解决实际问题,书写出符合软件工程规范的文件,编写出结构清晰及正确易读的程序代码。可以说,“数据结构”比“高级程序设计语言”等课程有着更高的要求,它更注重培养分析抽象数据的能力。
本书是编者多年从事该课程教学工作的教学成果,编者都是具有副教授以上职称、有15年以上该课程教学经验的一线教师。本书由任志国担任主编、赵传成、蓝才会、祁建宏、达文姣、岳秋菊、刘君担任副主编。其中的第1章、第2章、第5章、第7章、第8章、第9章由任志国编写,第3章由赵传成编写,第4章由岳秋菊编写,第6章由达文姣编写,第10章由蓝才会编写,第11章由祁建宏编写,所有章节习题部分由刘君编写。在本书的构思与编写过程中,得到了安天庆教授、党建武教授、王治和教授的帮助,在算法的实现与调试以及插图的制作过程中,得到了杨业、史淑娟、宗小兵等研究生的帮助,在此表示感谢。
《数据结构(C语言描述)》:
1.2.3数据的存储结构
数据结构在计算机中的表示(又称为映像)称为数据的物理结构,又称为存储结构。它不同于逻辑结构,是依赖计算机语言的,是具体的。通常,一个数据元素在计算机内用一块连续的存储单元来表示。那么,在计算机中怎样存储表中所有的数据元素呢?数据结构一般用下面四种基本的存储结构来表示数据元素之间的关系。
1.顺序存储结构
该方法把逻辑上相邻的数据元素存储在物理位置也相邻的存储单元里,数据元素之间的逻辑关系由存储单元的邻接关系来体现,由此得到的存储表示称为顺序存储结构。顺序存储结构主要应用于线性结构,非线性结构也可以通过某种线性的方法实现顺序存储。其优点是可以实现随机存取,每个元素占用最少的存储空间,即存储密度大。其缺点是只能使用相邻的一整块存储单元,因此可能产生较多的外部碎片。
2.链式存储结构
该方法不要求逻辑上相邻的数据元素在物理位置上也相邻,数据元素之间的逻辑关系由附加的指针表示,由此得到的存储表示称为链式存储结构。其优点是不会出现碎片现象,可充分利用所有存储单元。其缺点是每个元素因存储指针而占用额外的存储空间,并且只能实现顺序存取。
3.索引存储结构
该方法通常在存储数据元素信息的同时,还建立附加的索引表。索引表由若干索引项组成。索引项的一般形式是:(关键字、地址)。关键字(Key)是能唯一标识一个数据元素的那些数据项。其优点是检索速度快。缺点是增加附加的索引表占用较多的存储空间。在增加和删除数据时要修改索引表,因而花费较多的时间。
4.哈希(散列)存储结构
该方法的基本思想是根据数据元素的关键字直接计算出该数据元素的存储地址。其优点是检索、增加、删除结点的操作都很快。缺点是如果散列函数不好,可能出现数据元素存储地址的冲突,而解决冲突会增加时间和空间开销。
这四种基本存储方法既可以单独使用,也可以组合起来对数据结构进行存储映像。同一逻辑结构采用不同的存储方法,可以得到不同的存储结构;采用不同的存储结构,其数据处理效率往往不同。选择何种存储结构来表示相应的逻辑结构,视具体要求而定,主要考虑运算方便及算法的时空要求。
1.2.4数据的运算
为了有效地处理数据,可将数据按一定的逻辑结构组织起来,并选择适当的存储方法存储数据,然后再对数据进行运算。
数据的运算是定义在数据的逻辑结构之上的,每一种逻辑结构都有一个运算的集合,并指出运算的功能,例如,查找、插入、删除、修改等,这些运算实际上是在数据元素上施加的一系列的抽象操作。所谓抽象操作,是只知道这些操作要求“做什么”,而无须考虑“如何做”,只有在确定了存储结构之后,才考虑如何具体实现这些运算。下面介绍几种常见的数据运算。
……