数据结构系统与解答

《数据结构系统与解答》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构学习指导主编孙凌李丹副主编王桂芝周琳高大利-62-前言本书是与教材《数据结构》配套的教学辅导书，共分8章，顺序与《数据结构》教材前8章的顺序一致。内容包括各章的讲课提要、学习指导、习题及参考答案。编者根据多年的教学积累，对各章的知识要点进行归纳和总结，精心编写了近一百道例题和近四百道练习题，覆盖了本课程的全部教学内容。本书不仅可供学生进行学习辅导，也可供教师教学参考。通过阅读本书，将有助于学生加深对基础理论知识的理解，更可以通过大量的练习培养学生实际应用的能力。特别要提醒的是，本书每章练习均配有参考答案，希望读者合理使用参考答案，尽量不

2、要在解题之前先看答案，以免干扰自己的思考过程。对于每个算法设计题来说，解题方法往往有许多种，参考答案中给出的不一定是最好的。本书第1章、第3章和第4章由周琳编写；第2章由王桂芝编写；第5章由李丹编写；第6章由高大利编写；第7章和第8章由孙凌编写。李丹负责统编全稿。本书在编写过程中力求概念清晰，表述正确，通俗易懂，便于自学。由于时间仓促，且作者水平有限，书中可能会有一些错误，恳请读者批评指正。作者2005年7月-62-目录第1章概述5讲课提要5学习指导5习题18习题1参考答案11第2章线性表12讲课提要12学习指导13习题217习题2参考答案21

3、第3章串28讲课提要28学习指导28习题330习题3参考答案32第4章数组和广义表34讲课提要34学习指导34习题438习题4参考答案41第5章树42讲课提要42学习指导43习题552习题5参考答案56第6章图62讲课提要62学习指导63习题671习题6参考答案76第7章查找82讲课提要82学习指导82习题790习题7参考答案92第8章内部排序95-62-讲课提要95学习指导96习题8104习题8参考答案107-62-第1章概述讲课提要【主要内容】1．数据结构的研究目的和研究内容2．数据结构中的几个重要概念和术语3．算法设计的基本要求以及算法复

4、杂度的分析和计算方法【教学目标】1．了解数据结构的研究目的和研究内容2．掌握数据结构中的重要概念和术语3．掌握算法设计的基本要求以及算法复杂度的分析和计算方法【所需课时】2次课。[第一次课]1．数据结构的研究目的和研究内容2．数据结构中的重要概念和术语[第二次课]3．算法设计的基本要求以及算法复杂度的分析和计算方法学习指导1．概念和术语数据：是能输入到计算机中并能被计算机程序处理的符号的总称。数据元素：是数据的基本单位，它在计算机处理和程序设计中通常作为一个整体进行考虑和处理。一个数据元素可由若干数据项组成。数据对象：是具有相同特征的数据元素的

5、集合，是数据的一个子集。数据结构：是数据元素的组织形式，或数据元素相互之间存在一种或多种特定关系的集合。数据的逻辑结构：是指数据结构中数据元素之间的逻辑关系。数据的存储结构：是数据的逻辑结构在计算机内存中的存储方式，又称物理结构。数据类型：是一组具有相同性质的操作对象以及该组操作对象上的运算方法的集合。抽象数据类型：是指一个数学模型以及在该模型上定义的一套运算规则的集合。算法：建立在数据结构基础上的，为解决问题而采取的步骤和方法。-62-2．逻辑结构的四种基本形态根据数据元素之间关系的不同特征，通常有下列四类基本结构：（1）集合：结构中的数据元

6、素间除了“同属于一个集合”的关系外，别无其它关系。（2）线性结构：结构中的数据元素之间存在一个对一个的关系。（3）树型结构：结构中的数据元素之间存在一个对多个的关系。（4）图型结构或网状结构：结构中的数据元素之间存在多个对多个的关系。3．数据存储结构的基本组织方式数据存储结构有顺序和链式两种方式。（1）顺序存储结构的特点：要借助数据元素在存储器中的相应位置来体现数据元素相互间的逻辑关系，常用高级编程语言中的“一维数组”来描述或实现。（2）链式存储结构的特点：通过表示数据元素存储地址的指针来表示数据元素之间的逻辑关系，通常用链表来实现。在顺序存储

7、结构的基础上，又可延伸变化出另外两种存储结构，即索引存储和散列存储。（1）索引存储就是在数据文件的基础上增加了一个索引表文件。通过索引表建立索引，可以把一个顺序表分成几个顺序子表，其目的是在查询时提高查找效率，避免盲目查找。（2）散列存储就是通过数据元素与存储地址之间建立起某种映射关系，使每个数据元素与每一个存储地址之间尽量达到一一对应的目的。这样，查找时同样可大大提高效率。4．数据结构的研究内容数据结构的核心研究内容包括三个方面：数据的逻辑结构、存储结构以及相应的基本操作运算的定义和实现。5．算法的五个重要特征（1）有穷性：一个算法必须保证在

8、执行有限步骤之后结束，而不是无限的。（2）确定性：算法中每一条指令必须有明确的含义，而不能是模棱两可的。（3）可行性：每一个操作步骤都必须在有限的时间