课程地址:https://www.icourse163.org/course/ZJU-93001
笔记中图片均来自此mooc中讲义。

这周开始了浙大陈越老师的数据结构课程,听了一周,感觉讲的很清晰,现在总结一下。

Part1:回顾

1. 什么是数据结构

简单来说,就是数据对象在计算机中的组织方式,分为逻辑机构和物理存储结构,而数据对象必定和一些操作相关,这些操作就是算法。
这里老师还提到抽象数据类型的概念,就是定义一个数据对象集和其操作集,而不管其具体的实现。举个例子,大家都知道矩阵,也知道它的运算,那么矩阵可以看成一个抽象数据类型,在计算机中具体由python还是C来定义这些细节就不是抽象数据类型关心的了。
抽象的好处在与处理问题的时候只需要关注问题本身,而不用关注底层的实现。

2. 什么是算法

算法的其实就是解决问题的方法,设计算法的时候要考虑时间复杂度和空间复杂度。时间复杂度一般就是考虑最坏情况以及渐进表示,因为最坏情况方便计算,而且算法只需要考虑当数据量大的情形,所以只需要考虑渐进表示。

3. 应用实例

这部分也是这周的作业,虽然不算很难,但是本菜鸡还是折腾了很久。本周的例子是最大子列,PTA上有两题和此相关,第三题二分法查找算法比较简单,就不列出了。

Part2:作业

#include <stdio.h>

int MaxSubseqSum(int A[],int N);

int main(){
	//获取数组的长度 
	int a;
	scanf("%d",&a);
	
	//将数组存入数组
	int b[a];
	int i;
	for (i=0;i<a;i++){
		scanf("%d",&b[i]);
	}
	
	int sum;
	sum=MaxSubseqSum(b,a);
	
	printf("%d",sum);

}
int MaxSubseqSum(int A[],int N){
	int sum=0;
	int maxsum=0;
	int i;
	for (i=0;i<N;i++){
		sum+=A[i];
		if (sum<0){
			sum=0;
		}else if(sum>maxsum){
			maxsum=sum;
		}
	}
	return maxsum;
} 
  • 作业2
#include <stdio.h>

int MaxSubseqSum(int A[],int N);

int main(){
	//获取数组的长度 
	int a;
	scanf("%d",&a);
	
	//判断是否全为0,如果全为负数,则输出0 
	int flag=1; 
	
	//将数组存入数组
	int b[a];
	int i;
	for (i=0;i<a;i++){
		scanf("%d",&b[i]);
	}
	
	int sum=0;
	int maxsum=0;
	int x=0;
	int y=0;
	int z=0;
	
	for (i=0;i<a;i++){
		if (b[i]>=0){
			//如果有非负数,flag变为0 
			flag*=0;
		}
		sum+=b[i];
		if(sum>maxsum){
			maxsum=sum;
			x=z;
			y=i;
		}else if (sum<0){
			sum=0;
			z=i+1;
		}
	}
	if (maxsum<=0){
		if (flag){
			printf("%d %d %d",0,b[0],b[a-1]);
		}
		else{
			//flag为1表示存在非负数,而此时maxsum<=0,所以表示全为0 
			printf("%d %d %d",maxsum,0,0);
		}
	}else{
		printf("%d %d %d",maxsum,b[x],b[y]);
	}
	return 0;
}

以上就是这周的课程内容,虽然写这篇文章花了很久,写的也不大好,但是感觉理了一遍之后收获还是很大的,希望自己可以坚持下去。