浙大数据结构Week1

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

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

Part1:回顾

1. 什么是数据结构

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

2. 什么是算法

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

3. 应用实例

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

Part2:作业

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#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;
}

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