4.1-4.3算法与数据结构.ppt

第4章 算法与数据结构;算法与数据结构;算法与数据结构;算法历史小知识;4.1算法及其表示;算法五大特征;算法的表示;; Insertion-Sort(A) 1 for j = 1 to n-1 2 key = A[j] 3 i = j-1 4 while i = 0 and A[i] key 5 A[i+1] = A[i] 6 i = i - 1 7 A[i+1] = key;算法的分析与评价;算法的复杂性;时间复杂度表示;问题规模与时间复杂度的关系 ;算法与建模;4.2 常用算法结构分析;常用算法及举例;递归法 基本思想;递归法之计算 3！;递归法之Tower of Hanoi;;;;; void Towers (int n, char Source, char Target, char Interm) { if (n==1) printf(“From %c to %c\n”, Source,Target); else { Towers(n-1, Source, Interm, Target); Towers(1, Source, Target, Interm); Towers(n-1, Interm, Target, Source); } };贪心法 基本思想;贪心算法之0/1背包问题;迭代法;分治法;回溯法;回溯法之八皇后问题 ;动态规划法（ dynamic programming ）;动态规划法之拦截导弹;分支界限法branch-and-bound ;4.3数据结构及表示;DS是带有结构特征的数据元素的集合以及作用于其上的函数与运算。 DS三要素：数据的逻辑结构+存储结构+数据运算。 数据结构是以数据为加工对象，研究数据组织方式和相关操作方法的学问。 也可以说：DS是指相互之间存在一种或多种特定关系的数据元素所组成的集合。怎样去组织一批特定的数据。;根据数据元素之间的逻辑关系 线性结构数据元素间呈 现一对一的关系； 非线性结构则呈现一对多的或多对多的关系。;常用数据结构;;非线性结构表示;数据结构二元组表示（二）;二元组表示举例;数据的逻辑结构;数据的存储结构;数组逻辑结构与存储结构比较;顺序存储结构;链式存储结构;索引存储结构;散列存储结构;逻辑结构和存储结构的关系;数据操作/运算;数据结构-求解算法的关系; 算法最关心的是对数据的运算，如数据的基本运算和方法。 数据结构最关心的是数据的表示，如逻辑结构、存储结构。;小结