文档介绍：该【数据结构与算法ppt课件 】是由【落意心冢】上传分享，文档一共【47】页，该文档可以免费在线阅读，需要了解更多关于【数据结构与算法ppt课件 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。数据结构与算法ppt课件
POWERPOINT
1
所谓算法是指解题方案的准确而完整的描述。
1、算法的基本特征
>可行性:算法原则上能够精确地执行,甚至人们只用笔和纸做有限次运算即可完成。
>确定性:算法的每一步都必须有确切的定义
>有穷性:一个算法必须在执行有穷步后结束,即算法必须能够终止
>拥有足够的情报:我们要使算法有效就必须拥有足够的情报
2、算法的基本要素
>数据对象的运算和操作
(+、-、*、/)
(&、||、!)
(>、<、=、#)
(赋值、输入、输出)
>算法的控制结构
一个算法一般都可以用顺序、选择、循环三种基本控制结构组合而成。
3、算法设计基本方法
列举法:指针对待解决的问题,列举所有可能的情况,并用问题中给定的条件来检验。
归纳法:特殊——一般的抽象过程
递推:从已知初始条件出发,逐次推出所要求的各中间结构和最后结果
递归:将复杂的问题逐层分解,最后归结为一个简单的问题,再沿原分解的逆过程逐步进行综合。分为直接递归和间接递归
减半递推技术:把规模较大较复杂的问题,分成几个规模较小较简单的问题
回溯法:通过对问题的分析,找出一个解决问题的线索,多次试探,若成功,则得出解,若失败,则回退,换别的路线再进行试探
算法的复杂度主要包括时间复杂度和空间复杂度。两者之间没有必然的联系。
1、算法的时间复杂度
指执行算法所需要的计算工作量。
工作量可以用算法在执行过程中所需基本运算的执行次数来度量。其中基本运算次数是问题规模的函数,即
算法的工作量=f(n)。
>平均性态
>最坏情况复杂性
注意:算法程序执行的具体时间受使用计算机、程序设计语言以及算法实现过程中的许多细节的影响。而算法的时间复杂度与此无关
2、算法的空间复杂度
指执行这个算法所需要的内存空间,包含:
>算法程序所占的空间
>输入的初始数据所占的空间
>算法执行过程中所需要的额外空间
数据结构作为计算机的一门学科,主要研究以下三个方面的问题:
(1)数据的逻辑结构
(2)数据的存储结构(物理结构)
(3)对各种数据结构进行的运算
数据结构学科的研究目的:提高数据处理的效率。主要包括
1、数据的处理速度
2、尽量节省在数据处理过程中所占用的计算机存储空间
数据处理:是指对数据集合中的各元素以各种形式进行运算。包括插入、删除、查找、更改等运算,也包括对数据元素进行分析。
数据元素:在数据处理领域中,每一个需要处理的对象都可以抽象为数据元素。
数据结构:是指反映数据元素之间关系的数据元素集合的表示。数据元素之间的任何关系都可以用前后件关系来描述。
1、数据的逻辑结构
所谓逻辑结构实际上就是指数据元素之间的前后件关系。其中前后件关系是指它们的逻辑关系,而与他们在计算机中的存储位置无关。它包含两个要素:
数据元素的集合,通常记为D;
数据元素之间的关系(前后件关系),通常记为R。
形式表示如下:
B=(D,R)其中B表示数据结构
线性表的顺序存储结构有以下两个基本特点:
(1)线性表中所有元素所占的存储空间是连续的;
(2)线性表中各数据元素在存储空间中是按逻辑顺序依 次存放的。
逻辑上相邻的结点,物理位置上也相邻
在程序设计语言中,通常定义一个一维数组来表示线性表的顺序存储空间,该一维数组的长度通常要定义得比线性表的实际长度大一些,以便对线性表进行各种运算,特别是插入运算。
线性表的主要操作有:
(1)插入、(2)删除、(3)查找、(4)排序、(5)分解、(6)合并、(7)复制、(8)逆转。