注：本文使用的网课资源为中国大学MOOC
https://www.icourse163.org/course/ZJU-93001
什么是数据结构
举例1：如何在书架上摆放图书
新书怎么插入？
如何找到某本指定的书？
结论：解决问题方法的效率与数据的组织方式有关
举例2：写程序实现一个函数printN，使得传入一个正整数N的参数后，能顺序打印从1到N的全部正整数。
#include <stdio.h>
void PrintN1(int N);
void PrintN2(int N);
int main()
{
int N;
scanf("%d", &N);
PrintN1(N);
//PrintN2(N);
return 0;
}
// 循环实现
void PrintN1(int N)
{
int i;
for (i=1; i<=N; i++){
printf("%d
", i);
}
return;
}
// 递归实现
void PrintN2(int N)
{
if (N){
PrintN2(N-1);
printf("%d
", N);
}
return;
}
结论：解决问题方法的效率，跟空间的利用率有关
举例3：写程序计算给定多项式在给定点x处的值。
[f(x) = a_0+a_1x+...+a_{n-1}x^{n-1}+a_nx^n
]
#include <stdio.h>
#include <time.h>
#include <math.h>
#include <windows.h>
//windows.h里定义了关于创建窗口，消息循环等函数
clock_t start, end;
/* clock_t 是 clock()函数返回的变量类型*/
double duration;
/* 被测函数运行时间，以秒为单位*/
#define MAXN 101 /* 多项式最大项数，即多项式次数+1*/
#define MAXK 1e5 /* 被测函数最大重复调用次数*/
//函数声明
double f1(int n, double a[], double x);
double f2(int n, double a[], double x);
void run(double (*f)(int n, double *, double), double a[], int func_n);
//给出多项式在定点处的值
int main()
{
int i;
double a[MAXN]; /* 存储多项式的系数 */
a[0] = 1;
for (i = 1; i < MAXN; i++)
a[i] = (double)(1.0 / i);
run(f1, a, 1);
run(f2, a, 2);
system("pause"); //程序暂停，显示按下任意键继续
return 0;
}
// 直接计算版
double f1(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 f2(int n, double a[], double x)
{
int i;
double p = a[0];
for (i = n; i > 0; i--)
p = a[i - 1] + x * p;
return p;
}
//double (*f)(int n, double *, double)
//这是声明 f 是函数指针，函数返回void，
//该函数有3个形式参数，形式参数是int,double型的指针和double型的变量
void run(double (*f)(int n, double *, double), double a[], int func_n)
{
int i;
start = clock();
for (i = 0; i < MAXK; i++)
f(MAXN - 1, a, 1.1);
end = clock();
duration = ((double)(end - start)) / CLK_TCK;
printf("ticks%d = %f
", func_n, (double)(end - start));
printf("duration%d = %6.2e
", func_n, duration);
}
结论：解决问题方法的效率，跟算法的巧妙程度有关
数据结构是数据对象在计算机中的组织方式，包括逻辑结构和物理存储结构。数据对象博定与一系列加在其上的操作相关联，而完成这些操作所用的方法就是算法。 抽象数据类型:只描述数据对象集和相关操作集“是什么”，并不涉及“如何做到”的问题。
举例4：“矩阵的抽象数据类型定义”。
- 类型名称：矩阵(Matrix)
- 数据对象集：由MxN个三元组<a,i,j>构成，其中a是矩阵元素的值，i是元素所在的行号，j是元素所在的列号。
- 操作集：
Matrix Create(int M, int N); //返回一个MxN的空矩阵
int GetMaxRow(Matrix A); //返回矩阵A的总行数
int GetMaxCol(Matrix A); //返回矩阵A的总列数
ElementType GetEntry(Matrix A, int i, int y); //返回矩阵A的第i行，第j列的元素
Matrix Add(Matrix A, Matrix B);//如果A和B的行，列数一致，则返回矩阵C=A+B，否则返回错误标志
Matrix Multiply(Matrix A, Matrix B);// 如果A和B的行，列数一致，则返回矩阵C=AB，否则返回错误标志
什么是算法
- 一个有限的指令集
- 接受一些输入(有些情况下不需要输入)
- 产生输出
- 一定在有限步骤之后终止
- 每条指令都必须：1.有明确的目标，不可以有歧义；2.在计算机可处理的范围内；3.描述应不依赖于任何一种计算机语言以及具体的实现手段。
什么是好的算法
空间复杂度S(n)：程序在执行时占用存储单元的长度。
时间复杂度T(n):程序在执行时耗费时间的长度。
举例：递归形式的printN函数之所以效率不高，是因为大量的函数调用占用的存储单元多，从而导致空间复杂度过高。
复杂度的渐进表示法
[egin{aligned}
T(n) &= O(f(n))表示存在常数C>0,n_0>0使得当n>n_0时有T(n) <= C*f(n)\
T(n) &= Omega(g(n))表示存在常数C>0,n_0>0使得当n>n_0时有T(n) >= C*g(n)\
T(n) &= Theta(h(n))表示同时有T(n) = O(h(n))和T(n) = Omega(h(n))
end{aligned}
]
复杂度分析小窍门
若两段算法分别有复杂度(T_1(n)=O(f_1(n)))和(T_2(n)=O(f_2(n)))，则
- (T_1(n)+T_2(n) = max(O(f_1(n)), O(f_2(n))))
- (T_1(n)*T_2(n) = O(f_1(n))* O(f_2(n)))
若T(n)是关于n的k阶多项式，那么(T(n) = Theta(n^k))
一个for循环的时间复杂度等于循环次数乘以循环体代码的复杂度
if-else结构的复杂度取决于if的条件判断复杂度和两个分支部分的复杂度，总体复杂度取三者中最大。
应用实例：最大子列和问题
给定N个整数的序列(A_1,A_2,...,A_N)，求函数(f(i,j)=max(0,displaystylesum_{k=i}^jA_k))的最大值。
算法1：直接循环计算
此时算法复杂度为(O(N^2))
int MaxSubseqSum1(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;
}
算法2：分而治之
把一个大的序列分为两个小的序列，再把小的序列分为更小的两个序列，…，直到每个小序列只有一个数。在每个小序列中，会得到：
- 左边最大子列和（正数即本身，负数即0）；
- 右边最大子列和；
- 横跨划分边界的最大子列和；
（比如对于只有 1 | 2 两个数的子列，其左边最大子列和为 1 ，右边最大子列和为 2，而横跨划分边界的最大子列和为 1+2），此时此时三者中最大的值就是该小序列的"最大子列和"。
此时算法时间复杂度(T(n)=2T(frac{T}{2}+c*n, T(1)=O(1)),即(T(n)=O(nlogn))
注：本程序摘自https://github.com/callmePicacho/Data-Structres
/*返回三者中的最大值*/
int Max3(int a, int b, int c)
{
int tempMax;
if (a > b)
tempMax = a;
else
tempMax = b；
if (tempMax < c)
tempMax = c;
return tempMax;
}
/* 分治*/
int DivideAndConquer(int a[],int left,int right)
{
/*递归结束条件：子列只有一个数字*/
// 当该数为正数时，最大子列和为其本身
// 当该数为负数时，最大子列和为 0
if(left == right)
{
if(0 < a[left])
return a[left];
return 0;
}
/* 分别递归找到左右最大子列和*/
int mid = (left+right)/2;
int MaxLeftSum = DivideAndConquer(a,left,mid);
int MaxRightSum = DivideAndConquer(a,mid+1,right);
/* 再分别找左右跨界最大子列和*/
int MaxLeftBorderSum = 0;
int LeftBorderSum = 0;
for(int i=mid; i>=left; i--)
{
//应该从边界出发向左边找
LeftBorderSum += a[i];
if(MaxLeftBorderSum < LeftBorderSum)
MaxLeftBorderSum = LeftBorderSum;
}
int MaxRightBorderSum = 0;
int RightBorderSum = 0;
for(int i=mid+1; i<=right; i++)
{
// 从边界出发向右边找
RightBorderSum += a[i];
if (MaxRightBorderSum < RightBorderSum)
MaxRightBorderSum = RightBorderSum;
}
/*最后返回分解的左边最大子列和，右边最大子列和，和跨界最大子列和三者中最大的数*/
return Max3(MaxLeftSum,MaxRightSum,MaxRightBorderSum+MaxLeftBorderSum);
}
// 分冶法求最大值主函数
int MaxSubseqSum2(int A[], int N)
{
return DivideAndConquer(A,0,N-1);
}
算法3：在线处理(动态规划)
每输入一个数据就进行即时处理,只关心它当前的大小。当临时和加上当前值为负时，它对之后子列和肯定没有帮助（甚至只会让之后的和更小），此时抛弃这段临时和并将它置0.此时算法复杂度为(O(n))。
int MaxSubseqSum3( 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; //发现更大和则更新当前结果
if( ThisSum < 0) //如果当前子列和为负
ThisSum = 0; //则不可能使后面的部分和增大，抛弃之
}
return MaxSum;
}