@guoxs
2015-10-18T17:14:45.000000Z
字数 4347
阅读 2945
数据结构与算法
数据对象在计算机中的组织方式
数据对象必定与一系列加在其上的操作相关联
完成这些操作所用的方法就是算法
抽象数据类型(Abstract Data Type)
数据类型
抽象:描述数据类型的方法不依赖于具体实现
只描述数据对象集和相关操作集“是什么”,并不涉及
“如何做到”的问题
类型名称:矩阵(Matrix)
数据对象集:一个M×N的矩阵
操作集:对于任意矩阵A、B、C属于Matrix,以及整数i、j、M、N
Matrix Create( int M, int N )
:返回一个M×N的空矩阵;int GetMaxRow( Matrix A )
:返回矩阵A的总行数;int GetMaxCol( Matrix A )
:返回矩阵A的总列数;ElementType GetEntry( Matrix A, int i, int j )
:返回矩阵A的第i行、第j列的元素;Matrix Add( Matrix A, Matrix B )
:如果A和B的行、列数一致,则返回矩阵C=A+B,否则返回错误标志;Matrix Multiply( Matrix A, Matrix B )
:如果A的列数等于B的行数,则返回矩阵C=AB,否则返回错误标志;抽象在于:
矩阵中a类型不确定,二维数组?一位数组?十字链表?
运算的规则未确定,先按行加?先按列加?什么语言?
算法(Algorithm)
每一条指令必须
算法的伪码描述
void SelectionSort ( int List[], int N ){
/* 将N个整数List[0]...List[N-1]进行非递减排序*/
for ( i = 0; i < N; i ++ ) {
MinPosition = ScanForMin( List, i, N–1 );
/* 从List[i]到List[N–1]中找最小元,并将其位置赋给MinPosition */
Swap( List[i], List[MinPosition] );
/* 将未排序部分的最小元换到有序部分的最后位置*/
}
}
抽象性在于:
List到底是数组还是链表(虽然看上去很像数组)?
Swap用函数还是用宏去实现?
什么是好的算法?
空间复杂度S(n) —— 根据算法写成的程序在执行时
时间复杂度T(n) —— 根据算法写成的程序在执行时
在有生之年都等不到运行结果。
在分析一般算法的效率时,一般关注下面两种复杂度:
复杂度的渐进表示法
常见算法复杂度函数排序:
复杂度分析小窍门
若两段算法分别有复杂度
若T(n)是关于n的k阶多项式,那么
一个for
循环的时间复杂度等于循环次数乘以循环体代码的复杂度
if-else
结构的复杂度取决于if
的条件判断复杂度和两个分枝部分的复杂度,总体复杂度取三者中最大
例1:写程序实现一个函数PrintN,使得传入一个正整数为N的参数后,能顺序打印从1到N的全部正整数
循环实现:
void PrintN ( int N ){
int i;
for ( i=1; i<=N; i++ ){
printf(“%d\n”, i );
}
return;
}
递归实现:
void PrintN ( int N ){
if ( N ){
PrintN( N – 1 );
printf(“%d\n”, N );
}
return;
}
递归实现简单,代码简洁,但是有一个致命的问题,那就是空间占用太大。当N很大时,需要花费很大的内存来存储中间变量,易导致计算机崩溃!
例2:
写程序计算给定多项式在给定点x处的值:
double f( int n, double a[], double x ){
int i;
double p = a[0];
for ( i=1; i<=n; i++ ){
p += (a[i] * pow(x, i));
}
return p;
}
另一种更优算法:
double f( int n, double a[], double x ){
int i;
double p = a[n];
for ( i=n; i>0; i-- ){
p = a[i-1] + x*p;
}
return p;
}
clock()
:捕捉从程序开始运行到clock()
被调用时所耗费的时间。这个时间单位是clock tick
,即“时钟打点”。
常数CLK_TCK
(或CLOCKS_PER_SEC
):机器时钟每秒所走的时钟打点数。每台机器该值不一样。
用clock()
函数比较两个算法所花的时间:
#include <stdio.h>
#include <time.h>
clock_t start, stop;
/* clock_t是clock()函数返回的变量类型*/
double duration;
/* 记录被测函数运行时间,以秒为单位*/
int main (){
/* 不在测试范围内的准备工作写在clock()调用之前*/
start = clock();/* 开始计时*/
MyFunction();/* 把被测函数加在这里*/
stop = clock();/* 停止计时*/
duration = ((double)(stop - start))/CLK_TCK;
/* 计算运行时间*/
/* 其他不在测试范围的处理写在后面,例如输出duration的值*/
return 0;
}
解决问题方法的效率
给定N个整数的序列
算法1:
int MaxSubseqSum1( int A[], int N ){
int ThisSum, MaxSum = 0;
int i, j, k;
for( i = 0; i < N; i++ ) { /* i是子列左端位置*/
for( j = i; j < N; j++ ) { /* j是子列右端位置*/
ThisSum = 0; /* ThisSum是从A[i]到A[j]的子列和*/
for( k = i; k <= j; k++ )
ThisSum += A[k];
if( ThisSum > MaxSum ) /* 如果刚得到的这个子列和更大*/
MaxSum = ThisSum; /* 则更新结果*/
} /* j循环结束*/
} /* i循环结束*/
return MaxSum;
}
算法2:
int MaxSubseqSum2( int A[], int N ){
int ThisSum, MaxSum = 0;
int i, j;
for( i = 0; i < N; i++ ) { /* i是子列左端位置*/
ThisSum = 0; /* ThisSum是从A[i]到A[j]的子列和*/
for( j = i; j < N; j++ ) { /* j是子列右端位置*/
ThisSum += A[j];
/*对于相同的i,不同的j,只要在j-1次循环的基础上累加1项即可*/
if( ThisSum > MaxSum ) /* 如果刚得到的这个子列和更大*/
MaxSum = ThisSum; /* 则更新结果*/
} /* j循环结束*/
} /* i循环结束*/
return MaxSum;
}
算法3:分而治之
算法4:在线处理
int MaxSubseqSum4( int A[], int N ){
int ThisSum, MaxSum;
int i;
ThisSum = MaxSum = 0;
for( i = 0; i < N; i++ ) {
ThisSum += A[i]; /* 向右累加*/
if( ThisSum > MaxSum )
MaxSum = ThisSum; /* 发现更大和则更新当前结果*/
else if( ThisSum < 0 ) /* 如果当前子列和为负*/
ThisSum = 0; /* 则不可能使后面的部分和增大,抛弃之*/
}
return MaxSum;
}
“在线”的意思是指每输入一个数据就进行即时处理,在任何一个地方中止输入,算法都能正确给出当前的解。