C/C++教程

【数据结构C++】01绪论

本文主要是介绍【数据结构C++】01绪论,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

01绪论

1.1定义

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

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

1.2抽象数据类型

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

例1.1:“矩阵”的抽象数据类型定义
类型名称:矩阵(Matrix)
数据对象集:一个M×N的矩阵AM×N = (aij)(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):耗费时间的长度;

最坏情况复杂度Tworst(n) >= 平均复杂度Tavg(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

复杂度分析:Tworst(n) = O(log2n),Tbest(n)=O(1),Sworst(n)=Sbest(n)=O(1)

1.4复杂度量级对比不同复杂度增长

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

例1.3:最大子列和

1.暴力解法O(N2);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;
}

这篇关于【数据结构C++】01绪论的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!