01绪论

1.1定义

数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。

逻辑结构(面向问题)：集合结构、线性结构、树形结构、图形结构
物理结构(面向计算机)：顺序存储结构、链式存储结构

1.2抽象数据类型

数据类型–数据对象集和数据集合相关联的操作集；
抽象–描述数据类型的方法不依赖于具体实现。
（面向对象中的类）

例1.1：“矩阵”的抽象数据类型定义
类型名称：矩阵（Matrix）
数据对象集：一个M×N的矩阵A_M×N = (a_ij)（i = 1,…,M; j = 1,…,N）由M×N个三元组<a,i,j>构成，其中a是矩阵元素的值，i是所在行，j是所在列。
操作集：对于任意矩阵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 ) : 返回矩阵第i行第j列元素；
Matrix Add( Matrix A, Matrix B ) : 如果A和B的行列数一致，返回矩阵C=A+B，否则返回错误标志；
Matrix Multiply( Matrix A, Matrix B ) : 如果A的列数等于B的行数，返回C=AB，否则返回错误标志；

1.3算法

算法：一个有限指令集，接受一些输入(有些情况下不需要输入)，产生输出，一定在有限步骤之后终止，每一条指令必须有充分明确的目标，不可以有歧义，并且在计算机能处理的范围之内，描述不依赖于任何一种计算机语言及具体的实现手段。

空间复杂度S(n)：占用存储单元的长度；
时间复杂度T(n)：耗费时间的长度；

最坏情况复杂度T_worst(n) >= 平均复杂度T_avg(n);

例1.2：分析二分查找的复杂度
查找算法中的“二分法”是这样定义的：
给定N个从小到大排好序的整数序列List[]，以及某待查找整数X，我们的目标是找到X在List中的下标。即若有List[i]=X，则返回i；否则返回-1表示没有找到。
二分法是先找到序列的中点List[M]，与X进行比较，若相等则返回中点下标；否则，若List[M]>X，则在左边的子系列中查找X；若List[M]<X，则在右边的子系列中查找X。
试写出算法的伪码描述，并分析最坏、最好情况下的时间、空间复杂度。

伪码描述：

int BINARY_SEARCH(int n, int a, int x)
int left,right
while left <= right
	mid = (left + right) / 2
	case
	A_middle < searchnum : left = middle + 1
	A_middle > searchnum : right = middle - 1
	A_middle = searchnum : return middle
return -1

复杂度分析：T_worst(n) = O(log₂n)，T_best(n)=O(1)，S_worst(n)=S_best(n)=O(1)

1.4复杂度量级对比

复杂度的计算：
(1).两段算法复杂度分别为T₁(n)=O(f₁(n))，T₂(n)=O(f₂(n))，则T₁(n)+T₂(n)=max(O(f₁(n)),O(f₂(n)))；T₁(n)×T₂(n)=O(f₁(n)×f₂(n))；
(2).T(n)是n的k阶多项式，T(n)=O(n^k)；
(3).for循环时间复杂度为循环次数乘循环体复杂度；if-else结构的复杂度取条件判断复杂度及分支部分复杂度三者中的最大值。

例1.3：最大子列和

1.暴力解法O(N²)；2.分而治之O(NlogN)；3.在线处理O(N)。

//方法一：暴力解题法，时间复杂度O(N^2)
//int max_subseq_sum1(int n, int a[]) {
//	int ThisSum, MaxSum = 0;
//	for (int i = 0; i < n; i++) {
//		ThisSum = 0;
//		for (int j = i; j < n; j++) {
//			ThisSum += a[j];
//			if (ThisSum > MaxSum) {
//				MaxSum = ThisSum;
//			}
//		}
//	}
//	return MaxSum;
//}

//方法二：分而治之，时间复杂度O(NlogN)
int Max3(int a, int b, int c) {
	int Max2, Max3;
	Max2 = a > b ? a : b;
	Max3 = Max2 > c ? Max2 : c;
	return Max3;
}

int DivideAndConquer(int a[], int left, int right) {
	int MaxLeftSum, MaxRightSum;  //存放左右子问题的解
	int MaxLeftBorderSum, MaxRightBorderSum; //存放左右跨分界的解
	int LeftBorderSum, RightBorderSum; 
	
	if (left == right) {
		if (a[left] > 0) return a[left];  //递归的终止条件，子列只有一个数字
		else return 0;
	}

	//分
	int Border = (left + right) / 2;

	MaxLeftSum = DivideAndConquer(a, left, Border);
	MaxRightSum = DivideAndConquer(a, Border+1, right);

	//求跨分界线的最大子列和
	MaxLeftBorderSum = 0;
	MaxRightBorderSum = 0;
	LeftBorderSum = 0;
	RightBorderSum = 0;
	for (int i = Border; i >= left; i--) {
		LeftBorderSum += a[i];
		if (LeftBorderSum > MaxLeftBorderSum)
			MaxLeftBorderSum = LeftBorderSum;
	}
	for (int i = Border+1; i <= right; i++) {
		RightBorderSum += a[i];
		if (RightBorderSum > MaxRightBorderSum)
			MaxRightBorderSum = RightBorderSum;
	}

	//返回最大值
	return Max3(MaxLeftSum, MaxRightSum, MaxLeftBorderSum+ MaxRightBorderSum);
}

int max_subseq_sum2(int n, int a[]) {
	return DivideAndConquer(a, 0, n - 1);
}

//方法三：在线处理,时间复杂度O(N)
//int max_subseq_sum3(int n, int a[]) {
//	int ThisSum, MaxSum = 0;
//	ThisSum = 0;
//	for (int i = 0; i < n; i++) {
//		ThisSum += a[i];
//		if (ThisSum > MaxSum) {
//			MaxSum = ThisSum;
//		}
//		else if (ThisSum < 0) {
//			ThisSum = 0;
//		}
//	}
//	return MaxSum;
//}


int main(int argc, char *argv[]) {

	int a[] = { 4,-3,5,-2,-1,2,6,-2 };
	int n = sizeof(a) / sizeof(a[0]);

	int max_sum = max_subseq_sum2(n, a);
	cout << max_sum << endl;

	system("pause");
	return 0;
}