《数据结构C 版》期末相关复习课件PPT.ppt

数据结构;;1.1 数据结构的兴起和发展 ; 数据结构随着程序设计的发展而发展;1.2 数据结构的研究对象;数据结构从逻辑上分为四类： ⑴ 集合：数据元素之间就是 “属于同一个集合” ； ⑵ 线性结构：数据元素之间 存在着一对一的线性关系；;数据结构从逻辑上分为四类： ⑴ 集合：数据元素之间就是 “属于同一个集合” ； ⑵ 线性结构：数据元素之间 存在着一对一的线性关系； ⑶ 树结构：数据元素之间存在 着一对多的层次关系；;数据结构从逻辑上分为四类： ⑴ 集合：数据元素之间就是 “属于同一个集合” ； ⑵ 线性结构：数据元素之间 存在着一对一的线性关系； ⑶ 树结构：数据元素之间存在 着一对多的层次关系； ⑷ 图结构：数据元素之间存在 着多对多的任意关系。;通常有两种存储结构： 1. 顺序存储结构：用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置来表示。;通常有两种存储结构： 1. 顺序存储结构：用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置来表示。 2. 链接存储结构：用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系用指针来表示 。;逻辑结构和存储结构之间的关系;1.3 数据结构的基本概念（小结）; 欧几里德算法 ;算法的描述方法——自然语言 ;① 输入m 和n； ② 求m除以n的余数r； ③ 若r等于0，则n为最大公约数，算法结束；否则执行第④步； ④ 将n的值放在m中，将r的值放在n中； ⑤ 重新执行第②步。;优点：流程直观 缺点：缺少严密性、灵活性 使用方法：描述简单算法 注意事项：注意抽象层次 ;N;优点：能由计算机执行 缺点：抽象性差，对语言要求高 使用方法：算法需要验证 注意事项：将算法写成子函数 ;#include iostream.h int CommonFactor(int m, int n) { int r=m % n; while (r!=0) { m=n; n=r; r=m % n; } return n; } void main( ) { coutCommonFactor(63, 54)endl; };伪代码（Pseudocode）：介于自然语言和程序设计语言之间的方法，它采用某一程序设计语言的基本语法，操作指令??以结合自然语言来设计。 优点：表达能力强，抽象性强，容易理解 使用方法：7 ± 2; 1. r = m % n; 2. 循环直到 r 等于0 2.1 m = n; 2.2 n = r; 2.3 r = m % n; 3. 输出 n ;;算法分析;算法的时间复杂度分析;问题规模：输入量的多少。 基本语句：是执行次数与整个算法的执行次数成正比的操作指令。;定义 若存在两个正的常数c和n0，对于任意n≥n0，都有T(n)≤c×f(n)，则称T(n)=O(f(n));定理：若A(n)=amnm+am-1nm-1+?+a1n+a0是一个m次多项式，则A(n)=O(nm)。;例1-5 ++x; 例1-6 for (i=1; i=n; ++i) ++x; 例1-7 for (i=1; i=n; ++i) for (j=1; j=n; ++j) ++x; 例1-8 for (i=1; i=n; ++i) for (j=1; j=i-1; ++j) ++x; ;例1-9 for (i=1; i=n; ++i) for (j=1; j=n; ++j) { c[i][j]=0; for (k=1; k=n; ++k) c[i][j]+=a[i][k]*b[k][j]; } 例1-10 for (i=1; i=n; i=2*i) ++x;;最好情况、最坏情况、平均情况;最好情况：出现概率较大时分析 最差情况：实时系统 平均情况：已知输入数据是如何分布的， 通常假设等概率分布;本章小结——知识结构图;;线性表：简称表，是n（n