学习指导+练习题.doc

数据结构学习指导 目 录 第1章 概述 5 讲课提要 5 学习指导 5 习题1 8 习题1参考答案 11 第2章 线性表 12 讲课提要 12 学习指导 13 习题2 17 习题2参考答案 21 第3章 串 28 讲课提要 28 学习指导 28 习题3 30 习题3参考答案 32 第4章 数组和广义表 34 讲课提要 34 学习指导 34 习题4 38 习题4参考答案 41 第5章 树 42 讲课提要 42 学习指导 43 习题5 52 习题5参考答案 56 第6章 图 62 讲课提要 62 学习指导 63 习题6 71 习题6参考答案 76 第7章 查找 82 讲课提要 82 学习指导 82 习题7 90 习题7参考答案 92 第8章 内部排序 95 讲课提要 95 学习指导 96 习题8 104 习题8参考答案 107 第1章 概述 讲课提要 【主要内容】 1．数据结构的研究目的和研究内容 2．数据结构中的几个重要概念和术语 3．算法设计的基本要求以及算法复杂度的分析和计算方法 【教学目标】 1．了解数据结构的研究目的和研究内容 2．掌握数据结构中的重要概念和术语 3．掌握算法设计的基本要求以及算法复杂度的分析和计算方法 【所需课时】 2次课。 [第一次课] 1．数据结构的研究目的和研究内容 2．数据结构中的重要概念和术语 [第二次课] 3．算法设计的基本要求以及算法复杂度的分析和计算方法 学习指导 1．概念和术语 数据：是能输入到计算机中并能被计算机程序处理的符号的总称。 数据元素：是数据的基本单位，它在计算机处理和程序设计中通常作为一个整体进行考虑和处理。一个数据元素可由若干数据项组成。 数据对象：是具有相同特征的数据元素的集合，是数据的一个子集。 数据结构：是数据元素的组织形式，或数据元素相互之间存在一种或多种特定关系的集合。 数据的逻辑结构：是指数据结构中数据元素之间的逻辑关系。 数据的存储结构：是数据的逻辑结构在计算机内存中的存储方式，又称物理结构。 数据类型：是一组具有相同性质的操作对象以及该组操作对象上的运算方法的集合。 抽象数据类型：是指一个数学模型以及在该模型上定义的一套运算规则的集合。 算法：建立在数据结构基础上的，为解决问题而采取的步骤和方法。 2．逻辑结构的四种基本形态 根据数据元素之间关系的不同特征，通常有下列四类基本结构： （1）集合：结构中的数据元素间除了“同属于一个集合”的关系外，别无其它关系。 （2）线性结构：结构中的数据元素之间存在一个对一个的关系。 （3）树型结构：结构中的数据元素之间存在一个对多个的关系。 （4）图型结构或网状结构：结构中的数据元素之间存在多个对多个的关系。 3．数据存储结构的基本组织方式 数据存储结构有顺序和链式两种方式。 （1）顺序存储结构的特点：要借助数据元素在存储器中的相应位置来体现数据元素相互间的逻辑关系，常用高级编程语言中的“一维数组”来描述或实现。 （2）链式存储结构的特点：通过表示数据元素存储地址的指针来表示数据元素之间的逻辑关系，通常用链表来实现。 在顺序存储结构的基础上，又可延伸变化出另外两种存储结构，即索引存储和散列存储。 （1）索引存储就是在数据文件的基础上增加了一个索引表文件。通过索引表建立索引，可以把一个顺序表分成几个顺序子表，其目的是在查询时提高查找效率，避免盲目查找。 （2）散列存储就是通过数据元素与存储地址之间建立起某种映射关系，使每个数据元素与每一个存储地址之间尽量达到一一对应的目的。这样，查找时同样可大大提高效率。 4．数据结构的研究内容 数据结构的核心研究内容包括三个方面：数据的逻辑结构、存储结构以及相应的基本操作运算的定义和实现。 5．算法的五个重要特征 （1）有穷性：一个算法必须保证在执行有限步骤之后结束，而不是无限的。 （2）确定性：算法中每一条指令必须有明确的含义，而不能是模棱两可的。 （3）可行性：每一个操作步骤都必须在有限的时间内完成。 （4）输入：一个算法可以有一个或多个输入，也可以没有输入。 （5）输出：一个算法可以有一个或多个输出。没有输出的算法是没有实际意义的。 6．算法的评价标准 （1）正确性。 （2）易读性。 （3）高效性。 （4）可维护性。 7．算法分析的目的 算法分析主要是指分析算法的效率。算法效率的度量主要从两个方面：算法的运行时间和算法所需的存储空间。分析的目的是通过考察算法的时间和空间效率，以求改进算法或对不同的算法进行比较。一般情况下，鉴于运算空间（内存）较为充足，所以把算法的时间复杂度分析作为重点。 8．算法的时间复杂度分析 （1）算法运算时间的度量的两种方法：事后统计的方法和事前分析估算的方法。 （2）算法运行时间的分析规则 通常把一个程序的运行时间定义为一个T