第8章算法与数据结构基础-new-讲授

《第8章算法与数据结构基础-new-讲授》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、8.1算法基础第8章算法与数据结构8.1.1算法基本概念8.1算法基础1.算法的定义8.1.1算法基本概念算法（algorithm）是指对特定问题求解步骤准确8.1.2算法的效率与存储量评价而完整的描述，它是指令序列的有限集合，其中每一条指令表示一个或多个操作。用计算机解决具体问题的时候，需要以下几个步骤：具体问题数学模型算法描述编程测试得到答案区分算法和程序。8.1算法基础8.1算法基础8.1.1算法基本概念8.1.1算法基本概念2.算法的基本特征3.算法的基本要素ò有穷性ò组成算法的各条指令，即对数据的运算和操作。ò可行性ò各条指令的组

2、织形式，表现为各种控制结构。ò确定性ò有零个或多个输入ò有一个或多个输出8.1算法基础8.1算法基础8.1.1算法基本概念8.1.1算法基本概念3.算法的基本要素4.算法的表示例：任意输入一个数，若大于0，输出‘YES’，否则ò图形工具：流程图、N-S图、PAD图等。输出‘NO’。ò表格工具伪代码描述：ò语言工具输入一个数x;if(x>0)输出‘YES’;else输出‘NO’;18.1算法基础8.1算法基础8.1.1算法基本概念8.1.1算法基本概念5.算法的设计5.算法的设计要制定一个算法，一般要经过设计、确认、分一个好的算法要达到以下目

3、标：析、编码、检查、调试、计时等阶段。ò正确性常用的设计策略有：ò可读性ò列举法ò归纳法ò递推法ò健壮性ò递归法ò减半递推技术ò回溯法ò效率与低存储量要求8.1算法基础8.1算法基础8.1.2算法的效率和存储量评价8.1.2算法的效率和存储量评价ò为何对算法的效率进行分析？ò算法分析可分两个阶段进行，即事前估算和事后统计，通常采用事前估算的方法，评测出来的结果就?是所谓的“算法复杂度”。?ò算法复杂度可以分为时间复杂度和空间复杂度。?8.1算法基础8.1算法基础8.1.2算法的效率和存储量评价8.1.2算法的效率和存储量评价1.算法的时间复

4、杂度1.算法的时间复杂度计算机执行某一程序所需时间的因素：ò算法的时间复杂度还跟问题的输入数据有关，所以ò依据的算法采用何种策略算法的时间复杂度可以用两种形式表达：ò问题的规模*平均时间复杂度ò书写程序的语言*最坏情况时间复杂度ò编译程序所产生的机器代码的质量ò机器执行指令速度28.1算法基础第8章算法与数据结构8.1.2算法的效率和存储量评价2.算法的空间复杂度8.2数据结构基础类似于算法的时间复杂度，可以用算法的空间复8.2.1数据结构的基本概念杂度作为算法所需存储空间的度量。8.2.2线性表及其存储结构跟存储程序的指令、常数、变量和输

5、入数据的8.2.3栈及其存储结构空间大小有关外，还跟存储一些为实现计算所需信8.2.4队列及其存储结构息的辅助空间的大小有关。8.2.5树和二叉树除特别指明外，均按最坏情况分析。8.2.6查找8.2.7排序8.2数据结构基础8.2数据结构基础8.2.1数据结构的基本概念8.2.1数据结构的基本概念ò数据(Data):是对信息的一种符号表示。在计算机1.数据结构的研究内容科学中指所有能输入到计算机中并被计算机程序处ò数据的逻辑结构理的符号的总称。ò数据的存储结构ò数据元素(DataElement):是数据的基本单位，在ò数据结构的运算计算机程

6、序中通常作为一个整体进行考虑和处理。ò数据结构(DataStructure)：是相互之间具有一种或多种关联的数据元素的集合。8.2数据结构基础8.2数据结构基础8.2.1数据结构的基本概念8.2.1数据结构的基本概念1.数据结构的研究内容1.数据结构的研究内容ò数据的逻辑结构ò数据的逻辑结构数据的逻辑结构是用来描述数据元素在逻辑上的数据元素之间的前后位置关系称为前后件关关联关系的。它是数据的组织形式，与数据在计算系，也称为直接前驱和直接后继关系。机内的存储方式无关。数据的逻辑结构描述了两个方面的信息：常用的数据的逻辑结构有：集合、线性结构、

7、*描述数据元素的信息；树状结构、图状结构等。*描述数据元素之间的前后件关系的信息。38.2数据结构基础8.2数据结构基础8.2.1数据结构的基本概念8.2.1数据结构的基本概念1.数据结构的研究内容1.数据结构的研究内容ò数据的存储结构ò数据结构的运算数据的逻辑结构在计算机存储器中的存储方式数据结构的运算一般包括：插入、删除、查找、就是数据的存储结构（也称数据的物理结构）。分类、合并、分解、复制、修改等。基本的存储结构有：顺序存储结构、链式存储结构、索引存储结构、散列存储结构。8.2数据结构基础8.2数据结构基础8.2.1数据结构的基本概念

8、8.2.1数据结构的基本概念2.数据结构的表示2.数据结构的表示ò二元关系表示法ò二元关系表示法ò图形表示法形式：B=（D,R）其中，B表示数据结构，D表示数据元素的集合，R表示