第一章 数据结构2.pptVIP

教学要求 本课程进度安排 基本数据结构和算法 算法的五个重要特性 算法：解题方案的准确而完整的描述 基本特征 （1）有穷性：算法必须在执行有穷步之后结束，每一步都可在有穷时间内完成。 （2）确定性：对相同的输入只能得出相同的输出。 （3）可行性：算法所描述的操作都是可实现的。 （4）输入：0个或多个输入。 （5）输出：1个或多个输出。 备注：4和5指拥有足够的情报。 算法设计的要求 （1）正确性：算法应当满足具体问题的需求； （2）可读性：可读性好的算法有助人们于对算法的理解； （3）健壮性：当输入非法数据时，算法也能适当地做出反应或进行处理，而不会产生莫名其妙的输出结果； （4）效率与低存贮量：效率指的是算法执行的时间，解决同一问题，执行时间短的算法效率高。存储量指算法执行过程中所需要的最大存储空间。 算法基本要素 一个算法通常由两个基本要素所组成： 1.对数据对象的运算和操作 2.算法的控制结构 基本运算和操作分为四类： 1.算术运算 2.逻辑运算 3.关系运算 4.数据传输 算法的控制结构： 顺序 选择 循环 指令系统：计算机系统 执行 所有指令 集合 算法的时间复杂度是指 A) 执行算法程序所需要的时间 B) 算法程序的长度 C) 算法执行过程中所需要的基本运算次数 D) 算法程序中的指令条数 算法的空间复杂度是指 A) 算法程序的长度 B) 算法程序中的指令条数 C) 算法程序所占的存储空间 D) 执行过程中所需要的存储空间 在计算机中，算法是指 A) 加工方法 B) 解题方案的准确而完整的描述 C) 排序方法 D) 查询方法 算法分析的目的是 A) 找出数据结构的合理性 B) 找出算法中输入和输出之间的关系 C) 分析算法的易懂性和可靠性 D) 分析算法的效率以求改进 算法的工作量大小和实现算法所需的存储单元多少分别称为算法的 【1】 。 算法的基本特征是可行性、确定性、 【2】 和拥有足够的情报。 数据结构 特点： l 每个学生的信息占据一行，所有学生的信息按学号顺序依次排列构成一张表格； l 表中每个学生的信息依据学号的大小存在着一种前后关系，这就是我们所说的线性结构； l 对它的操作通常是插入某个学生的信息，删除某个学生的信息，更新某个学生的信息，按条件检索某个学生的信息等等。 应用举例2——输出n个对象的全排列 输出n个对象的全排列可以使用下图1-1所示的形式描述。 特点： l 在求解过程中，所处理的数据之间具有层次关系，这是我们所说的树形结构； l 对它的操作有：建立树形结构，输出最低层结点内容等等。 应用举例3——制定教学计划 在制定教学计划时，需要考虑各门课程的开设顺序。有些课程需要先导课程，有些课程则不需要，而有些课程又是其他课程的先导课程。比如，计算机专业课程的开设情况如下表1-2所示： 特点 l 课程之间的先后关系用图结构描述； l 通过实施创建图结构，按要求将图结构中的顶点进行线性排序。 结论： 数据结构主要研究以下三个方面的问题： 数据的逻辑结构 数据的存储结构 对各种数据结构进行的运算 注意： 讨论以上问题主要目的是为了提高数据处理的效率，提高效率包括两个方面： 一是提高数据处理的速度 二是节省在数据处理过程中所占用的计算机存储空间 逻辑结构 1.数据的逻辑结构分为线性结构和非线性结构两大类。 (1)线性结构:包括数组、链表、 栈、队列、优先级队列等; 线性结构的基本特征 存在唯一的“第一个”数据元素； 存在唯一的“最后一个”数据元素； 除第一个外，每个数据元素均有且只有一个直接前驱元素； 除最后一个外，每个数据元素均有且只有一个直接后继元素。 (2)非线性结构:包括树、图等. 存 储 结 构 存储结构概念：数据的逻辑结构在计算机存储空间中的存放形式 常见存储结构： (1)顺序存储结构：特点是借助于数据元素的相对存储位置来表示数据元素之间的逻辑结构. 即逻辑上相邻,物理上也相邻. (2)链式存储结构：特点是借助于指示数据元素地址的指针表示数据元素之间的逻辑结构。 (3)索引存储结构: 例题讲解 数据处理的最小单位是 A) 数据 B) 数据元素 C) 数据项 D) 数据结构 数据结构中，与所使用的计算机无关的是数据的 A) 存储结构 B) 物理结构 C) 逻辑结构 D) 物理和存储结构 下列叙述中，错误的是