数据结构（一）基本概念

什么是数据结构

抽象数据类型（ADT）

Abstract Data Type

（1）数据类型

  • 数据对象集
  • 数据集合相关联的操作集

（2）抽象

描述数据类型的方法不依赖于具体实现

  • 与存放数据的机器无关
  • 与数据存储的物理结构无关
  • 与实现操作的算法和编程语言无关

只描述数据对象集和相关操作集“是什么”，并不涉及“如何做到”

（3）例子

数据名称：矩阵

数据对象集：一个M*N的矩阵由M*N个三元组<a, i, j>组成，a是值，i、j为行列值

操作集：

int GetMaxRow(Matrix A)：返回矩阵的行数

int GetMaxColumn(Matrix A)：返回矩阵的列数

无关怎么存储的矩阵、如何实现的操作，只关心这个东西是什么，有哪些操作可以做

什么是算法

（1）定义

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

（2）算法好坏衡量

一般由时间复杂度和空间复杂度来衡量

假设数据规模为n

1
2
3
4
5
6
7
void printN(int N) {
    if (N) {
        printN(N - 1);
        printf("%d\n", N); 
    }
    return;
}

以上函数空间复杂度随N的变化而变化

1
2
3
4
5
6
7
8
double f(int n, double a[], double x) {
    int i;
    double p = a[0];
    for (int i = 1; i <= n; i++) {
        p += (a[i] * pow(x, i));
    }
    return p;
}

以上函数共执行(1 + 2 + … + n) = (n^2 + n) / 2次乘法，即时间复杂度

1
2
3
4
5
6
7
8
double f(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;
}

以上函数只执行n次乘法，时间复杂度更低

在分析一般算法的效率时，一般关心两种复杂度：最坏情况复杂度、平均复杂度

（3）渐进复杂度

渐进复杂度

以上为渐进复杂度，从上到下依次为上界、平均、下界

最大子序列和问题

给定一个N个整数的序列{A1, A2,…, AN}，求该序列连续子序列的和的最大值

算法1

暴力循环求解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int MaxSubSeqSum1(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;
}

时间复杂度O(n^3)

算法2

暴力循环求解优化

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

时间复杂度O(n^2)

算法3

分治法

最大子序列和分治法

nlogn的时间复杂度

算法4

贪心的思想

最大子序列和在线处理

题1：最大子序列和（一）

最大子序列和问题（一）

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 <bits/stdc++.h>

using namespace std;

int main() {
    int k;
    cin >> k;
    vector<int> a(k);
    for (int i = 0; i < k; i++) {
        cin >> a[i];
    }
    int cur = 0;
    int ans = 0;
    for (int i = 0; i < k; i++) {
        cur += a[i];
        if (cur > ans) {
            ans = cur;
        }
        if (cur < 0) {
            cur = 0;
        }
    }
    cout << ans;
}

题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
#include <bits/stdc++.h>

using namespace std;

int main() {
    int k;
    cin >> k;
    vector<int> a(k);
    int cnt = 0;
    for (int i = 0; i < k; i++) {
        cin >> a[i];
        if (a[i] < 0) {
            cnt++;
        }
    }
    if (cnt == k) {
        cout << 0 << " " << a[0] << " " << a[k-1] << endl;
        return 0;
    }
    int cur = 0;
    int ans = -1;
    int ansL = 0;
    int ansLen = 0;
    int l = 0;
    for (int i = 0; i < k; i++) {
        cur += a[i];
        if (cur > ans) {
            ans = cur;
            ansL = l;
            ansLen = i - ansL + 1;
        }
        if (cur < 0) {
            cur = 0;
            l = i + 1;
        }
    }
    
    cout << ans << " " << a[ansL] << " " << a[ansL+ansLen-1] << endl;
    
}

题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
43
44
45
46
47
48
49
50
51
#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;
}

/* 你的代码将被嵌在这里 */
/* 如下 */

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