数据结构-引言.pptVIP

数据结构;教材;资料下载（临时）;成绩组成;第一章 引言;什么是数据结构;数据的逻辑结构;集合结构;数据结构的操作;数据结构的存储实现;基本的存储方式;关系的存储;第一章 引言;算法分析;算法的质量评价;算法效率分析;算法分析;程序的运行时间 ;有效算法的重要性;有效时间中能够处理的数据量;有效算法的重要性;时间复杂度;算法分析;算法运算量的计算;实例;算法一 int max1(int array, int size, int d) {int max=0, i; for (i=0; i size ; ++i) array[i] *= d; for (i=0; i size ; ++i) if (array[i] max) max = array[i]; return max; };运算量的计算;找出运算量的函数;算法分析;渐进表示法;渐进表示法;大O表示法实例;F(N)的选择;典型的增长率;算法按时间复杂度分类;算法分析;大O表示法的计算;大O表示法的定理;大O表示法的计算规则;规则3：循环语句的执行时间是循环控制行和循环体执行时间的总和。循环控制一般是一个简单的条件判断，因此循环语句的执行时间是循环体的运行时间乘循环次数。 规则4：嵌套循环语句，对外层循环的每个循环周期，内存循环都要执行它的所有循环周期，因此，可用求积定理计算整个循环的时间复杂度，即最内层循环体的运行时间乘所有循环的循环次数。例语句： for (i=0; in; i++) for (j=0; jn; j++) k++; 的时间复杂性为O(n2);连续语句：利用求和定理把这些语句的时间复杂性相加。例程序段： for (i=0; in; i++) a[i]=0; for (i=0; in; i++) for (j=0; jn; j++) a[i]= i+j; 有两个连续的循环组成。第一个循环的时间复杂度为O（n），第二个循环的时间复杂度为O（n2）。根据求和定理，整段程序的的时间复杂性为O(n2);大O的简化计算;算法分析;典型实例--最大连续子序列问题;解法一 – 穷举法;int maxSubsequenceSum(int a[], int size, int start, int end) { int maxSum = 0; for (int i = 0; i size; i++ ) for( int j = i; j size; j++ ) { int thisSum = 0; for( int k = i; k = j; k++ ) thisSum += a[ k ]; if( thisSum maxSum ) { maxSum = thisSum; start = i; end = j; } } return maxSum; };时间复杂度分析;方法二 --- O(n2)的算法;int maxSubsequenceSum(int a[], int size, int start, int end) { int maxSum = 0; for( int i = 0; i size; i++ ) { int thisSum = 0; for( int j = i; j size; j++ ) { thisSum += a[j]; if( thisSum maxSum ) { maxSum = thisSum; start = i; end = j; } } } return maxSum; } ;算法三 – O(N);算法三 – O(N);int maxSubsequenceSum(int a[], int size, int start, int end) { int maxSum = 0, thisSum = 0, startTmp = 0