数据结构与算法.

第8章数据结构与算法本章主要内容一、算法二、数据结构的基本概念三、线性表及顺序结构四、栈和队列五、线性链表六、树与二叉树一、算法1、算法的概念是指对解题方案的准确而完整的描述。通常人们解决问题时，是先研究问题然后设计解决问题的方案；程序设计也一样，开发人员总是先研究程序的算法，再根据算法编写代码。例题：1+2+3+4+5+…+100一、算法2、算法的基本特性有穷性：是指一个算法应包含有限的操作步骤而不能是无限的。确定性：是指算法中的每个步骤都应该是确定的，而不是含混的、模棱两可的。可行性：算法应该有效的执行。输入：是指在执行算法时需要从外界取得必要的信息。输出：算法的目的是求解，“解”就是输出。一个算法可以有一个或多个输出。一、算法3、算法的基本要素一个算法有两个基本要素：(1)是对数据对象的运算和操作。基本的运算和操作有4类：算数运算、逻辑运算、关系运算、数据传输。(2)是算法的控制结构算法中各种操作之间的执行顺序称为算法的控制结构。一个算法不仅取决于它选用的操作，而且还与操作之间执行的顺序有关。一般算法有顺序结构、选择结构和循环结构这3种控制结构。一、算法4、算法设计的基本方法（1）列举法（2）归纳法（3）递推法（4）递归法（5）减半递归法一、算法5、算法的复杂度（1）算法的时间复杂度是指执行算法所需要的计算工作量。工作量：用算法执行的基本运算次数来度量。同一算法的时间复杂度随问题规模的增大而增加。（2）算法的空间复杂度指执行这个算法所需要的内存空间。内存空间包括：算法程序所占空间、输入数据所占的空间、算法执行过程中所需要的额外空间。一、算法（1）在计算机中，算法是指______。A.查询方法B.加工方法C.解题方案的准确而完整的描述D.排序方法6、习题一、算法（2）在下列选项中，哪个不是一个算法一般应该具有的基本特征______。A.确定性B.可行性C.无穷性D.拥有足够的情报一、算法（3）算法的空间复杂度是指______。A.算法在执行过程中所需要的计算机存储空间B.算法所处理的数据量C.算法程序中的语句或指令条数D.算法在执行过程中所需要的临时工作单元数一、算法（4）算法的时间复杂度是指______。A.算法的执行时间B.算法所处理的数据量C.算法程序中的语句或指令条数D.算法在执行过程中所需要的基本运算次数二、数据结构利用计算机进行数据处理时，需要处理的数据元素较多，大量的数据在计算机中怎样存放，才能提高数据处理的效率，节省存储空间，这是数据结构处理的关键问题。数据结构研究内容数据结构的基本概念数据：指能输入到计算机中并被计算机程序处理的符号的总称。如整数、实数、字符、文字、声音、图形、图像等都是数据。数据元素：数据元素是数据的基本单位，它在计算机处理和程序设计中通常作为独立个体考的对象。数据元素一般由一个或多个数据项组成，一个数据元素包含多个数据项时，常称为记录，结点等。数据项也称为域、字段、属性。数据项是数据的最小单位。数据结构：是指相互有关联的数据元素的集合。数据结构是一门研究数据组织、存储和运算的学科。主要目的是：（1）提高处理数据的速度（2）尽量节省在数据处理过程中所占用的存储空间。数据结构包括两方面信息：（1）数据元素信息（2）数据元素之间的前后件关系数据结构的基本概念1、数据的逻辑结构据元素之间所固有的逻辑关系（前后件关系：数据元素之间的最基本关系）数据结构通常有四类基本形式：集合形式，线性结构，树型结构，图形结构或网状结构。数据结构的基本概念1、数据的存储结构定义：数据的逻辑结构在计算机存储空间中的存放方式。（1）为了表示逻辑关系（即前后件关系），存储结构中不仅要存放数据元素信息，还有存放数据元素之间的前后件关系的信息。（2）一种数据的逻辑结构根据需要可以表示为多种存储结构。（3）数据元素在计算机存储空间中的位置关系与他们的逻辑关系不一定相同。（4）程序的执行效率与数据的存储结构有密切相关。数据的存储结构包括:顺序、链式、索引、散列映射等。数据结构的基本概念线性表由一组相同数据类型n(n=0)个元素构成有限序列，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。线性表及其顺序存储结构线性表的基本概念：线性表及其顺序存储结构非空线性表特点：（1）且只有一个根结点a1，它无前件；（2）有且只有一个终端结点an，它无后件；（3）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。在计算机中存放线性表，最简单的方法是采用顺序存储结构，用顺序存储结构来存储的线性表也称顺序表。特点：1）顺序表中所有元素所占的存储空间是连续的。2）顺序表中各数据元素在存储空间中是按逻辑顺序依次存放的。线性表及其顺序存储结构线性表的顺序存储结构：在复杂线性表中，由若干项数据项元素组成的数据元素称为记录，而由多个记录构成的线性表又称为文件。线性表及其顺序存储结构顺序表的运算(1)插入运算(2)删除运算线性表及其顺序存储结构习题：1.数据结构中，与所使用的计算机无关的是数据结构是______。A.存储结构B.物理结构C.逻辑结构D.物理和存储结构线性表及其顺序存储结构2.数据的存储结构是指A）存储在外存中的数据B）数据所占的存储空间量C）数据在计算机中的顺序存储方式D）数据的逻辑结构在计算机中的存储方式线性表及其顺序存储结构3.下列叙述中正确的是______。A.一个逻辑数据结构只能有一种存储结构B.数据的逻辑结构属于线性结构，存储结构属于非线性结构C.一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率D.一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率线性表及其顺序存储结构4.下列叙述中正确的是______。A.程序执行的效率与数据的存储结构密切相关B.程序执行的效率只取决于程序的控制结构C.程序执行的效率只取决于所处理的数据量D.以上三种说法都不对线性表及其顺序存储结构