第一章 数据结构 概论.ppt

1、第一章 绪论,基本概念 算法,绪论,数据结构是专业核心课 讨论描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现 数据结构+算法,数据结构,具有特定关系的数据元素集合 即数据的组织形式，包括三个方面 数据元素之间的逻辑关系数据的逻辑结构 数据元素在计算机存储器中是如何存储的数据的物理结构（存储结构） 数据的运算,数据结构,数据元素 是数据的基本单位 又称：记录、元素、顶点等 包含若干个数据项,数据结构,数据的逻辑结构 简称为数据结构 分为线性与非线性结构 线性结构：有且仅有一个开始结点和一个终端结点，并且所有结点最多只有一个直接前趋和一个直接后继。,数据结构,常见的四

2、种数据结构,数据结构,数据的物理结构 顺序存储 结点间的逻辑关系由存储单元的邻接关系来体现 通常借助数组来描述 主要实现线性的数据结构 链接存储 非顺序的 通常借助指针来描述,数据结构,算法与算法分析,算法 Algorithm 对问题求解过程的一种描述 重要特性 有穷性、确定性、可行性、输入、输出,算法与算法分析,有穷性 对于任意一组合法的输入值，在执行有穷步骤之后一定能结束。 确定性 算法的每一步骤都具有确定的含义，不会出现二义性。 可行性 算法的每一步都必须是可行的，也就是说，每一步都能够通过执行有限次数完成。 输入 作为算法加工对象的量值，通常体现为算法中的一组变量。但有些算法的字面上可

3、以没有输入，实际上已被嵌入算法之中。 输出 它是一组与输入有确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能。,算法与算法分析,算法设计的要求 正确性 可读性 健壮性 效率高和存储量低,算法与算法分析,算法效率的度量 事后统计方法 通过设计好的测试程序和数据，利用计算机计时器对不同算法编制的程序的运行时间进行比较，从而确定算法效率的高低 事前分析估算方法 在计算机程序编制前，依据统计方法对算法进行估算,算法与算法分析,事前分析估算方法 一个用高级程序语言编写的程序在计算机上运行时所消耗的时间取决于下列因素： 算法采用的策略、方法 编译产生的代码质量 问题的输入规模 机

4、器执行指令的速度,算法与算法分析,第1条是算法好坏的根本 第2条由软件来支持 第4条要看硬件性能。 抛开这些与计算机硬件、软件有关的因素，一个程序的运行时间，依赖于所解决问题的规模大小及采用的“策略”。,算法与算法分析,算法的时间复杂度 算法的时间量度 记为T(n)=O(f(n)，如： T(n)=O(n2) 常用数量级的形式来表示 n 表示问题规模，当n逐渐增大时T(n)的极限情况 f（n）是问题规模n的某个函数 常见的：O(n)，O(1)，O(n2),算法与算法分析,计算方法 求出语句总的执行次数表达式 用常数1取代运行时间中的所有加法常数 在修改后的运行次数函数中，只保留最高阶项 如果最高

5、阶项存在且不是1，则去除与这个项相乘的常数,算法与算法分析,例 计算下面求累加和程序段的时间复杂性 sum=0； （1次） for(i=1;i=n;i+) （n次 ） for(j=1;j=n;j+) （n2次 ） sum+； （n2次 ） 解：T(n)=2n2+n+1 =O(n2),算法与算法分析,分析下列算法的时间复杂性 1） sum=0; for (i=1;i=n;i+) sum=sum+i; O(n) 2） i=1; while(i=n) i=i*10； O(lgn),算法与算法分析,算法的空时复杂度 算法所需的存储空间实现 记为：S(n)= O(f(n) n为问题的规模 f(n)为语句关于n所占存储空间的函数,算法与算法分析,小结 基本概念 算法 例题 数据结构按逻辑结构可分为两大类，它们分别是线性结构与（