bachzart's Blog
0%

ZJU_DS_01-基本概念

Posted on Edited on In ,

此篇系列博文是博主自己在 MOOC 上自学浙江大学数据结构课程时的笔记，每一讲都有对应的笔记，对应一篇博文。虽然之前上课时就做好了笔记，但对很多知识点的理解比较浅显，现在回过头来整理，希望会有所启发。另外，自学之路难免会有错误，欢迎看到文章的同学不吝赐教。另外，题解代码在 Github 上的地址：201909_MOOC_DS_ChenYue


What is Data Structure

何谓数据结构？按照姥姥的讲解，没有特定的数据结构的定义。不过，通过课上姥姥举的一些例子，可以得出：数据结构就是数据对象在计算机中的组织方式。
具体而言，数据对象包含：

  1. 逻辑结构：第一次学数据结构的人可能会对这个概念有点懵，如果已经掌握了一门程序设计语言，并且具备了一定的水平的话，理解起来还是比较容易的。这里举个例子，比如律诗的逻辑结构就是：首联、颔联、颈联和尾联。
  2. 物理存储结构：可以暂时理解为硬盘之类的存储器的结构。

当然，也可以使用抽象数据类型（Abstract Data Type）来描述数据结构，包括：

  1. 数据对象集：简而言之就是由数据组成的集合。
  2. 数据集合相关联的操作集：处理这些数据对象的操作方法。

其中，抽象的含义是：描述数据类型的方法不依赖于具体实现，与存放数据的机器无关，与数据存储的物理结构无关，与实现操作的算法和编程语言均无关。

抽象数据类型其实就是面向对象程序设计语言中的“类（Class）”的含义。要注意，数据对象必定与一系列加在上面的操作是相关联。也就是说，单独存在的数据对象或操作集是无法被称之为数据结构的。而在数据结构中，完成相关操作集所用的方法就是算法（Algorithm）。

其实，数据结构本身就是一个逻辑的概念。

What is Algorithm

算法包含以下几个要素：

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

Measure for Algorithm

时间复杂度（$S(n)$）：根据算法写成的程序在执行时耗费时间的长度。这个长度往往也与输入数据的规模有关。时间复杂度过高的低效算法可能导致我们有生之年都等不到运行结果。

空间复杂度（$T(n)$）：根据算法写成的程序在执行时占用存储单元的长度。这个长度往往与输入数据的规模有关。空间复杂度过高的算法可能导致内存超限，造成程序的非正常中断。

在分析一般算法的效率时，我们经常关注下面两种复杂度：

  1. 最坏情况复杂度（worst）
  2. 平均复杂度（average）

Complexity Expression

复杂度的渐进表示法：
$ T(n) = O(f(n)) $表示存在常数$C>0$，$n_0$使得当$n ≥ n_0$时，有$T(n) ≤ C * f(n)$；

$ T(n) = Ω(g(n)) $表示存在常数$C>0$，$n_0$使得当$n ≥ n_0$时，有$T(n) ≥ C * g(n)$；

$ T(n) = θ(h(n)) $表示同时有$ T(n)=O(h(n)) $和$ T(n)=Ω(h(n)) $；

过大的上界和下界对于分析算法的“好”和“坏”，没有意义，所以一般取值是我们能找到的、最大和最小的那个上界和下界。

当问题的规模为$n$时，不同量级的时间复杂度的关系为：
$log n < n < n*log n < n^2 < n^3 < 2^n < n!$

Complexity Analysis

对算法进行复杂度的分析是衡量一个算法“好”与“坏”的基本方法，关于这方面有以下一些窍门：

  • 若两段算法分别有复杂度$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) \times T_2(n) = O(f_1(n) \times f_2(n))$
  • 若$T(n)$是关于$n$的$k$阶多项式，那么$T(n) = θ(n^k)$
  • 一个for循环的时间复杂度等于循环次数乘以循环体代码的复杂度
  • if-else结构的复杂度取决于if的条件判断复杂度和两个分支部分的复杂度，总体复杂度取三者中最大

平时在做到一些题目的时候会遇到要分析时间复杂度的习题，可以从上述的角度入手。不过一般而言，第四条用的要多一些。

Demo Code

example 2

题目：写程序实现一个函数 PrintN ，使得传入一个正整数为 N 的参数后，能顺序打印从 1 到 N 的全部正整数。

学过一门程序设计语言的同学，应该不会觉得有困难，因为直接利用循环从 1 数到 N 即可完成这个需求。但是，可能会有部分同学会对递归不熟悉，好在老师也给出了代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <stdio.h>
void PrintN(int n) {
	// method 1: use loop
	for(int i = 1; i <= n; i++) {
		printf("%d\n", i);
	}
}

/*
void PrintN(int n) {
	// method 2: use recursion
	if(n) {
		PrintN(n - 1);
		printf("%d\n", n);
	}
}
*/

int main() {
	int N;
	scanf("%d", &N);
	PrintN( N );
	return 0;
}

example 3

题目：写程序计算给定多项式在给定点 x 处的值。

处理这个题有两种方法，所以可以顺便比较一下两种方法运行的时间长短。由于计算机的运行速度较快，仅运行一次无法看出差异，所以需要多执行几次。计算时间需要借助 C 语言的库函数，而这些库函数的声明在time.h这个头文件中。由于姥姥又给出了代码，又可以偷懒了~
下面给出代码：

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
54
55
56
57
58
59
60
#include <stdio.h>
#include <time.h>
#include <math.h>
clock_t start, stop;
double duration;
#define MAXN 10
#define MAXK 1e7
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[n];
	for(i = n; i > 0; i--) {
		p = a[i - 1] + x * p;
	}
	return p;
} 

int main() {
	int i;
	double a[MAXN];
	for(i = 0; i < MAXN; i++) a[i] = (double)i;
	
	start = clock();
	for(i = 0; i < MAXK; i++) {
		f1(MAXN - 1, a, 1.1);
	}
	stop = clock();
	duration = ((double)(stop - start)) / CLK_TCK;
	printf("ticks1 = %f\n", (double)(stop - start));
	printf("duration1 = %6.2e\n", duration);
	
	start = clock();
	for(i = 0; i < MAXK; i++) {
		f2(MAXN - 1, a, 1.1);
	}
	stop = clock();
	duration = ((double)(stop - start)) / CLK_TCK;
	printf("ticks2 = %f\n", (double)(stop - start));
	printf("duration2 = %6.2e\n", duration);
	
	return 0;
}

/*
result:

ticks1 = 1969.000000
duration1 = 1.97e+000
ticks2 = 284.000000
duration2 = 2.84e-001

*/

从上面代码的结果可以看出，采用不同计算方法的代码运行时间竟然相差了几乎 7 倍！

Maximum Subsequence Sum

题目：最大子列和问题

最大子列和的问题是很经典的动态规划（DP, dynamic programming）问题，这是博主后来查阅资料了解到的。既然姥姥将这道题当作例题放在第一讲，应该也有她的道理，何况她还介绍了这么多不用动规思路的解题方法呢。从题目出发，我们可以大致得到这道题的答题代码框架：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <stdio.h>
int MaxSubseqsum(int a[], int k) {

}

int main(int argc, char const *argv[]) {
	int i, K;
	scanf("%d", &K);
	int arr[K];
	for(i=0; i<K; i++) {
		scanf("%d", &arr[i]);
	}
	printf("%d\n", MaxSubseqsum(arr, K));
	return 0;
}

下面来看看各种不同的解法：

directly calculating easy version

直接暴力求解的思路较为直观，利用三重循环，将每一个数构成的序列全部枚举一遍，如果符合条件且满足最大，就更新结果。循环结束后，得到最后结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int MaxSubseqsum(int a[], int N) {
	int ThisSum, MaxSum = 0;
	int i, j, k;
	for(i=0; i<N; i++) {
		for(j=i; j<N; j++) {
			ThisSum = 0;
			for(k=i; k<=j; k++) {
				ThisSum += a[k];
			}
			if(ThisSum > MaxSum) MaxSum = ThisSum;
		}
	}
	return MaxSum;
}

directly calculating advanced version

继续按照暴力求解的思路进行计算，可以发现：对于相同的 i ，不同的 j ，只要在 j - 1 次循环的基础上累加 1 项即可，而不需要再从 1 一直加到 i。这样的话，就可以节省一层for循环的运行时间了，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
int MaxSubseqsum(int a[], int N) {
	int ThisSum, MaxSum = 0;
	int i, j;
	for(i=0; i<N; i++) {
		ThisSum = 0;
		for(j=i; j<N; j++) {
			ThisSum += a[j];
			if(ThisSum > MaxSum) MaxSum = ThisSum;
		}
	}
	return MaxSum;
}

divide and conquer

这道题还可以采用分治法来解决，不过不是那么容易理解，但根本在于要把握此法中边界的概念，并且要注意最终结果是 3 种情况下的最大值。

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
int MaxSubseqsum(int a[], int N) {
	/*use same interface*/
	return DivideAndConquer(a, 0, N-1);
}
int DivideAndConquer(int a[], int left, int right) {
	int MaxLeftSum, MaxRightSum;	/*save the result of left and right subsequence */
	int MaxLeftBorderSum, MaxRightBorderSum;	/*save the result of each subsequence*/
	int LeftBorderSum, RightBorderSum;
	int center, i;

	if(left == right) {
		if(a[left] > 0) return a[left];
		else return 0;
	}
	/*divide*/
	center = (left + right) / 2;
	
	/*use recursion to get the result*/
	MaxLeftSum = DivideAndConquer(a, left, center);
	MaxRightSum = DivideAndConquer(a, center+1, right);
	
	/*get the result of left subsequence*/
	MaxLeftBorderSum = 0, LeftBorderSum = 0;
	for(i=center; i>=left; i--) {
		LeftBorderSum += a[i];
		if(LeftBorderSum > MaxLeftBorderSum)	MaxLeftBorderSum = LeftBorderSum;
	}
	
	/*get the result of right subsequence*/
	MaxRightBorderSum = 0, RightBorderSum = 0;
	for(i=center+1; i<=right; i++) {
		RightBorderSum += a[i];
		if(RightBorderSum > MaxRightBorderSum)	MaxRightBorderSum = RightBorderSum;
	}

	return Max3(MaxLeftSum, MaxRightSum, MaxLeftBorderSum + MaxRightBorderSum);
}

int Max3(int a, int b, int c)
{
	return a>b?a>c?a:c:b>c?b:c;
}

online processing

比起上面的几种方法，在线处理就简单粗暴了许多，一趟循环下来就完事了，但不是那么好理解，最好根据测试样例手动模拟一遍。此法之所以快的原因在于，一旦出现了序列出现了负数，负数并不能使结果变大，反而使结果变小了。那么这种情况就不是符合条件的结果了，直接舍弃，这样就不用做多余的计算了，这和“剪枝”有点相似。而所谓“在线”，意思是指每输入一个数据就进行即时处理，在任何一个地方中止输入，算法都能正确给出当前的解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int MaxSubseqsum(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;
		} else if(ThisSum < 0) {
			ThisSum = 0;
		}
	}
	return MaxSum;
}

Homework

此课程的作业题目全部都放在 PTA 的习题集内，按照姥姥给的邀请码就可以进入题目集做题啦。

01-1 最大子列和问题

这道题被姥姥当成了应用实例进行讲解，可以直接使用姥姥给的代码，稍加修改一下就可以直接 AC 了。不过，根据这道题给定的一些条件，需要对一些数据做一些处理。这里，我们偷下懒，直接使用在线处理思路的代码进行解题，代码如下：

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
#include <stdio.h>
#define maxk 100005
int array[maxk] = {0};
int f(int array[], int N) {
	int ThisSum = 0, MaxSum = 0;
	int i;
	for(i = 0; i < N; i++) {
		ThisSum += array[i];
		if(ThisSum > MaxSum) MaxSum = ThisSum;
		else if(ThisSum < 0) ThisSum = 0;
	}
	return MaxSum;
}
int main() {
	int k, i;
	scanf("%d", &k);
	for(i = 0; i < k ; i++) {
		scanf("%d", &array[i]);
	}
	printf("%d", f(array, k));
	return 0;
}

/*
samples:
in:
6
-2 11 -4 13 -5 -2 
out:
20

*/

01-2 Maximum Subsequence Sum

这道题是上面题目的升级版，要求给出最佳结果的左端点和右端点的下标。需要注意的是这道题目的输出要求比较多，要当心一点。此题还是利用在线处理的思路进行求解，代码如下：

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
#include <stdio.h>
#include <stdbool.h>
#define maxk 100005
int array[maxk] = {0};
int main() {
	int k, i;
	scanf("%d", &k);
	bool flag = false;
	for(i = 1; i <= k; i++) {
		scanf("%d", array + i);
		if(array[i] >= 0) flag = true;
	}
	if(!flag) {
		printf("0 %d %d\n", array[1], array[k]);	// all the numbers are negative
	} else {
		int left = 1, right = k, temp_left = 1;
		int ThisSum = 0, MaxSum = -1;	// MaxSum need to be initialized as a negative number
		for(i = 1; i <= k; i++) {
			ThisSum += array[i];
			if(ThisSum > MaxSum) {	// update max value, the left index and right index
				MaxSum = ThisSum;
				left = temp_left;
				right = i;
			} else if(ThisSum < 0) {
				ThisSum = 0;
				temp_left = i + 1;
			}
		}
		printf("%d %d %d\n", MaxSum, array[left], array[right]);
	}
	return 0;
}

01-3 二分查找

这道题目介绍的算法算是十分基础入门的算法了，对于学过一门程序设计语言的同学来说，要解决应该不会有什么困难。不过，可能会有部分同学会对 PTA 上此类题目的做题方法有所疑惑。其实，这种函数题就是让你写个函数，然后系统会自动的将你提交的这段函数代码嵌入到题目的代码之中运行，继而判断结果是否正确。要注意这类题目对函数接口和一些关键词的定义，不要搞错了。笔者做这类题目时，都是直接把所有代码全部拷贝下来，然后把缺失的代码全部按照题意写出来，然后再单独的提交题目要求的那个函数代码，代码如下：

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 10
#define NotFound 0
typedef int ElementType;

typedef int Position;
typedef struct LNode *List;
struct LNode {
    ElementType Data[MAXSIZE];
    Position Last; /* 保存线性表中最后一个元素的位置 */
};

List ReadInput(); /* 裁判实现，细节不表。元素从下标1开始存储 */
Position BinarySearch( List L, ElementType X );

int main() {
    List L;
    ElementType X;
    Position P;

    L = ReadInput();
    scanf("%d", &X);
    P = BinarySearch( L, X );
    printf("%d\n", P);

    return 0;
}

List ReadInput() {
	List L = (List)malloc(sizeof(struct LNode));
	int n, t, i;
	scanf("%d", &n);
	for(i = 1; i <= n; i++) {
		scanf("%d", &L->Data[i]);
	}
	L->Last = i;
	return L;
}

Position BinarySearch( List L, ElementType X ) {
	int left = 1, right = L->Last, mid, flag = 0;
	while(left <= right) {
		mid = (left + right) / 2;
		if(L->Data[mid] == X) {
			flag = 1;
			break;
		} else if(L->Data[mid] < X) left = mid + 1;
		else right = mid - 1;
	}
	if(flag) return mid;
	else return NotFound;
}

/*
some samples:
in:
5
12 31 55 89 101
31
out:
2

in:
3
26 78 233
31
out:
0

in:
4
26 78 88 233
88
out:
3

in:
4
26 78 88 233
78
out:
2
*/