下面咕咕咕了,看这个:数据结构(王道考研复习笔记)
基本概念
什么是数据结构
试一下在机器上运行的结果
source:
递归的空间占用大
source:1.11.c
bug:
CLK_TCK问题
运行结果:
source:1.12.c
什么是算法
1
2
3
4
5
6void PrintN(int N){
if(N){
PrintN(N-1);
printf("%d\n",N);
}
}
1 | double f1(int n,double a[],double x) |
f1复杂度
f2复杂度
最大子列问题
1 | int MaxSubseqSum1( int A[], int N ) |
1 | int MaxSubseqSum2( int A[], int N ) |
分而治之算法
$T(N)=2T(N/2)+C*N$
$T(1)=O(1)$
在线处理算法1
2
3
4
5
6
7
8
9
10
11
12
13int 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;
}
线性结构
线性表及其实现
引子-多项式表示:
方法1:顺序存储结构直接表示
$f(x)=4x^5-3x^2+1$