[小学教育]数据结构 第一章 绪论.ppt

各章介绍 抽象出数学模型→设计算法→选择计算机语言→编出程序→测试→最终解答。 例1 书目自动检索系统 例3 人机对奕问题 例4：田径赛的时间安排问题 例6：多叉路口交通灯管理问题 求解非数值计算的问题： 主要考虑的是设计出合适的数据结构及相应的算法。 即：首先要考虑对相关的各种信息如何表示、组织和存储？ 因此，可以认为： 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科。 数据的逻辑结构与存储结构密切相关 算法设计 逻辑结构 算法实现 存储结构 关系的映像方法：表示?x, y?的方法 ? 常见函数的时间复杂度按数量递增排列及增长率。 常数阶O(1) 对数阶O(log2n) 线性阶O(n) 线性对数阶O(nlog2n) 平方阶O(n2) 立方阶O(n3) …… k次方阶O(nk) 指数阶O(2n) 如何估算 算法的时间复杂度？ 算法 = 控制结构 + 原操作 （固有数据类型的操作） 算法的执行时间 = 原操作(i)的执行次数×原操作(i)的执行时间 算法的执行时间 与 原操作执行次数之和 成正比 从算法中选取一种对于所研究的问题来说是 基本操作 的原操作，以该基本操作在算法中重复执行的次数（语句的频度）作为算法运行时间的衡量准则。 原操作 例如： (a){++x;s=0;} 语句频度为1，T(n)=O(1) (b)for(i=1;i=n;++i) {++x;s+=x;} 语句频度为n，T(n)=O(n) (c)for(j=1;j=n;++j) for(k=1;k=n;++k) {++x;s+=x;} 语句频度为n2，T(n)=O(n2) void mult(int a[], int b[], int c[] ) { // 以二维数组存储矩阵元素，c 为 a 和 b 的乘积 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]; } //for } //mult 基本操作: 乘法操作 时间复杂度: O(n3) 例1： 两个矩阵相乘 由于是一个三重循环， 每个循环从1到n， 则总次数为: n×n×n= n3 时间复杂度为T(n)= O(n3) 基本操作: 乘法操作 时间复杂度: O(n3) 例2： 选择排序 　　从记录的无序子序列中“选择”关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。 198 213 229 213* 191 180 0 1 2 3 4 5 198 213* i = 0 229 213 191 213 191 180 229 180 213* 229 198 i = 1 i = 2 180 191 213* 213 198 初始 最小者 180 交换198,180 最小者 191 交换213,191 最小者 198 交换229,198 直接选择排序的过程 最小者 213* 无交换 229 213* 0 1 2 3 4 5 213* i = 4 213 191 180 229 213* 229 198 结果 i = 3 180 191 213 198 最小者 213 无交换 213 198 191 180 各趟排序后的结果 void select_sort(int a[], int n) { // 将 a 中整数序列重新排列成自小至大有序的整数序列。 } // select_sort 基本操作: 比较(数据元素)操作 时间复杂度: O(n2) j = i; // 选择第 i 个最小元素 for ( k = i+1; k n; ++k ) if (a[k] a[j] ) j = k; for ( i = 0; i n-1; ++i ) { if ( j != i ) a[j] ←→ a[i] } 有的情况下， 算法中基本操作重复执行的次数 还随问题的输入数