本章的重点是了解数据结构的逻辑结构存储结构数据的运算三方面的概念及相互关系难点是算法复杂度的分析方法
需要达到 <识记> 层次的基本概念和术语有数据数据元素数据项数据结构特别是数据结构的逻辑结构存储结构及数据运算的含义及其相互关系数据结构的两大类逻辑结构和四种常用的存储表示方法
需要达到 <领会> 层次的内容有算法算法的时间复杂度和空间复杂度最坏的和平均时间复杂度等概念算法描述和算法分析的方法对一般的算法要能分析出时间复杂度
对于基本概念仔细看书就能够理解这里简单提一下
数据就是指能够被计算机识别存储和加工处理的信息的载体
数据元素是数据的基本单位有时一个数据元素可以由若干个数据项组成数据项是具有独立含义的最小标识单位如整数这个集合中这个数就可称是一个数据元素又比如在一个数据库(关系式数据库)中一个记录可称为一个数据元素而这个元素中的某一字段就是一个数据项
数据结构的定义虽然没有标准但是它包括以下三方面内容 逻辑结构存储结构和对数据的操作 这一段比较重要我用自己的语言来说明一下大家看看是不是这样
比如一个 表 ( 数据库 )我们就称它为一个数据结构它由很多 记录 ( 数据元素 )组成每个元素又包括很多 字段 ( 数据项 )组成那么这张表的逻辑结构是怎么样的呢? 我们分析数据结构都是从 结点 (其实也就是元素记录顶点虽然在各种情况下所用名字不同但说的是同一个东东)之间的关系来分析的对于这个表中的任一个记录(结点)它只有一个 直接前趋 只有一个 直接后继 (前趋后继就是前相邻后相邻的意思)整个表只有一个 开始结点 和一个 终端结点 那我们知道了这些关系就能明白这个表的逻辑结构了
而 存储结构 则是指用 计算机语言 如何表示结点之间的这种关系如上面的表在计算机语言中描述为连续存放在一片内存单元中还是随机的存放在内存中再用指针把它们链接在一起这两种表示法就成为两种不同的存储结构( 注意在本课程里我们只在高级语言的层次上讨论存储结构 )
第三个概念就是对 数据的运算 比如一张表格我们需要进行查找增加修改删除记录等工作而怎么样才能进行这样的操作呢? 这也就是数据的运算它不仅仅是加减乘除这些算术运算了在数据结构中这些运算常常涉及算法问题
弄清了以上三个问题就可以弄清数据结构这个概念
通常我们就将数据的 逻辑结构 简称为 数据结构 数据的逻辑结构分两大类 线性结构 和 非线性结构 (这两个很容易理解)
数据的存储方法有四种 顺序存储方法 链接存储方法 索引存储方法和散列存储方法
下一个是 难点 问题就是算法的描述和分析主要是 算法复杂度 的分析方法及其运用
首先了解一下几个概念一个是 时间复杂度 一个是 渐近时间复杂度 前者是某个算法的时间耗费它是该算法所求解问题 规模 n的函数而后者是指当问题规模趋向无穷大时该算法 时间复杂度的数量级
当我们评价一个算法的时间性能时主要标准就是 算法的渐近时间复杂度 因此 在算法分析时往往对两者不予区分经常是将渐近时间复杂度T(n)=O(f(n)简称为时间复杂度其中的f(n)一般是算法中频度最大的语句频度
此外算法中语句的频度 不仅与问题规模有关还与输入实例中各元素的取值相关 但是我们总是考虑在最坏的情况下的时间复杂度以保证算法的运行时间不会比它更长
常见的时间复杂度按数量级递增排列依次为 常数阶O() 对数阶O(logn) 线性阶O(n) 线性对数阶O(nlogn) 平方阶O(n^)立方阶O(n^) k次方阶O(n^k) 指数阶O(^n)
时间复杂度的分析计算请看书本上的例子然后我们通过做练习加以领会和巩固
数 据 结 构 习 题 一
简述下列概念数据数据元素数据类型数据结构逻辑结构存储结构线性结构非线性结构
◆ 数据 指能够被计算机识别存储和加工处理的信息载体
◆ 数据元素 就是数据的基本单位在某些情况下数据元素也称为元素结点顶点记录数据元素有时可以由若干 数据项 组成
◆ 数据类型 是一个值的集合以及在这些值上定义的一组操作的总称
◆ 数据结构 指的是数据之间的相互关系即数据的组织形式一般包括三个方面的内容:数据的 逻辑结构 存储结构 和 数据的运算
◆ 逻辑结构 指各数据元素之间的逻辑关系
◆ 存储结构 就是数据的逻辑结构用计算机语言的实现
◆ 线性结构 数据逻辑结构中的一类它的特征是若结构为非空集则该结构有且只有一个 开始结点 和一个 终端结点 并且所有结点都最多只有一个 直接前趋 和一个 直接后继 线性表就是一个典型的线性结构
◆ 非线性结构 数据逻辑结构中的另一大类它的逻辑特征是一个结点可能有多个直接前趋和直接后继
试举一个数据结构的例子叙述其逻辑结构存储结构运算三个方面的内容
◆ 例如有一张学生成绩表记录了一个班的学生各门课的成绩按学生的姓名为一行记成的表这个表就是一个数据结构每个记录(有姓名学号成绩等字段)就是一个结点对于整个表来说只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录)其他的结点则各有一个也只有一个直接前趋和直接后继(它的前面和后面均有且只有一个记录)这几个关系就确定了这个表的逻辑结构
那么我们怎样把这个表中的数据存储到计算机里呢? 用高级语言如何表示各结点之间的关系呢? 是用一片连续的内存单元来存放这些记录(如用数组表示)还是随机存放各结点数据再用指针进行链接呢? 这就是存储结构的问题我们都是从高级语言的层次来讨论这个问题的(所以各位赶快学C语言吧)
最后我们有了这个表(数据结构)肯定要用它那么就是要对这张表中的记录进行查询修改删除等操作对这个表可以进行哪些操作以及如何实现这些操作就是数据的运算问题了
常用的存储表示方法有哪几种?
常用的存储表示方法有四种:
◆ 顺序存储方法 它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里结点间的逻辑关系由存储单元的邻接关系来体现由此得到的存储表示称为 顺序存储结构
◆ 链接存储方法 它不要求逻辑上相邻的结点在物理位置上亦相邻结点间的逻辑关系是由附加的指针字段表示的由此得到的存储表示称为 链式存储结构
◆ 索引存储方法 除建立存储结点信息外还建立附加的索引表来标识结点的地址
◆ 散列存储方法 就是根据结点的关键字直接计算出该结点的存储地址
设三个函数fgh分别为 f(n)=n^+n^+ g(n)=n^+n^ h(n)=n^+nlgn 请判断下列关系是否成立
() f(n)=O(g(n))
() g(n)=O(f(n))
() h(n)=O(n^)
() h(n)=O(nlgn)
◆ ()成立
◇ 这里我们复习一下渐近时间复杂度的表示法 T(n)=O(f(n)) 这里的O是数学符号它的严格定义是 若T(n)和f(n)是定义在正整数集合上的两个函数则T(n)=O(f(n))表示存在正的常数C和 n 使得当n≥ n 时都满足≤T(n)≤C·f(n) 用容易理解的话说就是 这两个函数当整型自变量n趋向于无穷大时两者的比值是一个不等于的常数 这么一来就好计算了吧第()题中两个函数的最高次项都是n^因此当n→∞时两个函数的比值是一个常数所以这个关系式是成立的
◆ ()成立
◆ ()成立
◆ ()不成立
设有两个算法在同一机器上运行其执行时间分别为n^和^n要使前者快于后者n至少要多大?
◆
◇ 最简单最笨的办法就是拿自然数去代呗假定n取为则前者的值是后者的值是小于前者那我们就加个用代入得前者为后者为已经比前者大但相差不多那我们再减个用代入得前者为后者为又比前者小了所以结果得出来就是n至少要是
设n为正整数利用大O记号将下列程序段的执行时间表示为n的函数
() i=; k=
while(i
{ k=k+*i;i++;
} ◆ T(n)=n
∴ T(n)=O(n)
◇ 这个函数是按线性阶递增的
() i=; k=;
do{
k=k+*i; i++;
}
while(i<> ◆ T(n)=n
∴ T(n)=O(n)
◇ 这也是线性阶递增的
() i=; j=;
while(i+j<=n)
{
if (i
else i++;
} ◆ T(n)=n/
∴ T(n)=O(n)
◇ 虽然时间函数是n/但其数量级仍是按线性阶递增的
() x=n; // n>
while (x>=(y+)*(y+))
y++; ◆ T(n)=n /
∴ T(n)=O(n / )
◇ 最坏的情况是y=那么循环的次数是n / 次这是一个按平方根阶递增的函数
() x=; y=;
while(y>)
if(x>)
{x=x;y;}
else x++; ◆ T(n)=O()
◇ 这个程序看起<
