实用数据结构第一章绪论.pptVIP

数据结构Data Structure 主讲:龚 梦 2012年9月; 学时数：（68h） 教 材：陈元春等，实用数据结构基础，中国铁道出版社，2011 参考书： [1] 严蔚敏等，数据结构(C语言版)，清华大学出版社，2007年4月。￥22 [2] 朱战立，数据结构(JAVA语言描述），清华大学出版社，2005年12月。￥25 [3] 丁宝康等，数据结构自学考试指导，清华大学出版社， 2001年5月。￥23;内 容 安 排;数据结构课程的地位;第1章 数据结构的基本概念;1.1 数据结构基本概念;Q1：什么是数据结构？;术语：数据、数据元素和数据项;Q2：学习数据结构有什么用？;Q3：数据结构涵盖的内容？;解释1： 什么叫数据的逻辑结构？;例：用图形表示下列数据结构，并指出它们是属于线性结构还是非线性结构。;（2） S=(D, R) D={di | 1≤i≤5} R={(di , dj ), ij};解释2：什么叫数据的物理结构？;解释3：什么是数据的运算？;1.2 算法与伪码;程序设计实质＝好算法＋好结构;算法的特性：;1 条列式的步骤 2 流程图 3 伪码 4 程序语句;条列式:以条列式的步骤来描述解决问题的方法。;1.4 程序分析的方法; 利用计算机内记时功能，不同算法的程序可以用一组或多组相同的统计数据区分 缺点： ?必须先运行依据算法编制的程序 ?所得时间统计量依赖于硬件、软件等环境因素，掩盖算法本身的优劣 ; 一个高级语言程序在计算机上运行所消耗的时间取决于： ?依据的算法选用何种策略 ?问题的规模 ?程序语言 ?编译程序产生机器代码质量 ?机器执行指令速度 同一个算法用不同的语言、不同的编译程序、在不同的计算机上运行，效率均不同，———所以使用绝对时间单位衡量算法效率不合适。;讨论：那如何进行事前分析？;1.5 时间复杂度分析;一个特定算法的“运行工作量”的大小，只依赖于问题的规模（通常用整数量n表示）或者说，它是问题规模的函数。 假如，随着问题规模n的增长，算法执行时间的增长率和f(n)的增长率相同，则可记作： T (n) = O(f(n)) 称T (n) 为算法的(渐近)时间复杂度;如何估算算法的时间复杂度？ 算法的执行时间= 原操作(i)的执行次数×原操作(i)执行时间 算法的执行时间 与 原操作执行次数之和成正比 从算法中选取一种基本操作，以该基本操作在算法中重复执行的次数作为算法运行时间的衡量准则。 ;频度(Frequency Count) ：指该语句重复执行的次数 例如 ： {s=0;++x;s=0;} 将x自增看成是基本操作，则语句频度为１，即时间复杂度为Ｏ(1); 如果将s=0也看成是基本操作，则语句频度为２，其时间复杂度仍为O(1)，即常量阶。 例如：for(i=1;i=n;++i) {++x;s+=x;} 语句频度为：2n　其时间复杂度为：O(n) 即时间复杂度为线性阶。;算法的时间复杂度是指算法中所有语句的频度之和， 记为f(n)。 求O的数学定义： ;渐进符号（O）的定义：当且仅当存在一个正的常数 C，使得对所有的 n ? n0 ，有 f(n) ? Cg(n)，则f(n) = O(g(n)) ;时间复杂度T(n)按数量级递增顺序为： ;例如：for(I=1;I=n;++I) 　　　　for(j=1;j=n;++j) {++x;s+=x;} 语句频度为：2n2 　其时间复杂度为：O(n2) 即时间复杂度为平方阶。;语句频度为：;例：分析以下程序段的时间复杂度。;例：两个n阶矩阵的乘法 C = A × B，算法如下： #define MAX 100 void matrixmult(int n,float a[MAX][MAX], float b[MAX][MAX],float c[MAX][MAX]) { int i,j,k; float x; ① for ( i=1; i=n; i++ ) { ② for ( j=1; j=n; j++