第1节概论.ppt.ppt

单击此处编辑母版标题样式 计算机软件基础 ----------数据结构 第1节 概论 数据结构讲什么？ 几个概念 数据结构讲什么？ ?数据的逻辑结构 ?存储结构 ?以及对数据进行操作的各种算法。 计算机软件基础 ----------数据结构 第1节 概论 数据结构讲什么？ 几个概念 几个概念 数据 数据结构 数据类型 算法 时间复杂度与空间复杂度 数据(data)： 数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中、能被计算机程序识别和处理的符号的集合。 几个概念 数据 数据结构 数据类型 算法 时间复杂度与空间复杂度 数据结构 数据结构是数据存在的形式 包括逻辑结构和物理结构 数据的逻辑结构 逻辑结构就是数据元素之间的逻辑关系 两种结构： 线性结构 非线性结构 数据存储结构 逻辑结构在存储器里的实现 顺序存储方法(静态存储） 链接存储方法（动态存储） 索引存储方法 几个概念 数据 数据结构 数据类型 算法 时间复杂度与空间复杂度 数据类型 数据结构相同的属于同一个数据类型 几个概念 数据 数据结构 数据类型 算法 时间复杂度与空间复杂度 算法 一个有穷的指令集，这些指令为解决某一特定任务规定了一个运算序列。 几个概念 数据 数据结构 数据类型 算法 时间复杂度与空间复杂度 算法的时间复杂度 执行一个算法所花费的时间代价 ?时间代价（最坏、最好和平均情况） ? 最好情况下的时间代价。 ? 在平均情况下的时间代价。 ? 最坏情况下的时间代价，主要采用大  Ｏ表示法来描述。 如何计算时间复杂度？ 一般以程序中循环次数来表示。 如一个程序中最多的循环次数是n，则说其时间复杂度为O（n） 常见的时间复杂度： 常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n2)、立方阶O(n3)、k次方阶O(nk)、指数阶O(2n)。 空间复杂度 执行一个算法所需占用的空间代价 int a[100],sum=0,i=0; …. while(i100) {scanf(“%d”,a[i]) sum+=a[i];i++;} int a,sum=0,i=0; …. while(i100) {sum+=a;scanf(“%d”,a);i++;} 例如，求100个数之和，左边程序用的空间比右边程序要多 线性结构就是n个相同类型数据元素的有限线性序列，通常表示为( a1,a2,…,an )，长度为n， ai称为数据元素 接下来，学习线性结构…… 特点：每个元素最多有一个直接前趋，最多一个直接后继 首元素、尾元素 线性表 栈 队列 线性结构有哪些？ 单击此处编辑母版标题样式