数据结构和算法

字符串匹配算法（二）——Rabin-Karp算法

Rabin-Karp设计了一个巧妙的hash算法。用到的数学公式为：t(s+1) = (d(t(s)-T[s+1]h)+T[s+m+1]) mod q
t(s+1)为目标字符串的子字符串T[s+1,s+m+1]的哈希值，因为用到了上一次的结果t(s)，所以可以节省计算时间。

首先计算pattern字符串的hash值，然后在从目标字符串的开头，计算相同长度字符串的hash值。若hash值相同，则表示匹配，若不同，则向右移动一位，计算新的hash值。整个过程，与暴力的字符串匹配算法很相似，但由于计算hash值时，可以利用上一次的hash值，从而使新的hash值只需要加上新字母的计算，并减去上一次的第一个字母的计算，即可。

Rabin-Karp算法的预处理时间为O(m)，最坏情况下该算法的匹配时间为O((n-m+1)m)。但是平均运行时间还是比较好的。

用C语言实现如下：

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
#include <stdio.h>
#include <math.h>

int mod = 0x7fffffff;
const int d = 128;

int rabin_karp(char *T, char *P, int n, int m)
{
    if (n < m) return -2;
    int h = pow(d, m-1);
    int p = 0;
    int t = 0;
    int i, j;
    for (i=0; i<m; i++) {
        p = (d*p + P[i]) % mod;
        t = (d*t + T[i]) % mod;
    }
    for (j=0; j<=n-m; j++) {
        if (p == t) {
            return j;
        }
        if (j < n-m) {
            t = (d*(t - h*T[j]) + T[j+m]) % mod;
        }
    }
    return -1;
}

int main(int argc, char *argv[])
{
    char t[] = "BBC ABCDAB ABCDABCDABDE";
    char p[] = "ABCDABD";
    int len1 = sizeof(t) - 1;
    int len2 = sizeof(p) - 1;
    int index = rabin_karp(t, p, len1, len2);
    printf("index: %d\n", index);
    return 0;
    return 0;
}

现在结合上面的公式和代码再进行讲解一下。
d表示字母表的字母个数，上面的代码只接受ascii值为0~127的字符。如果采用小写英文字母来做字母表的话，那么d就是26。
h等于d^(m-1) % q。其实模q运算应该是可有可无的，加入q应该是为了避免数据溢出。但是加入模q后，由ts == p mod q不能说明ts == p，不过ts != p mod q则可以肯定ts != p。所以q最好选择比较大的质数，并且选取的q要满足使dq的值在一个计算机字长内。如果使用的是动态的编程语言的话就不用担心数据溢出，因此就不用进行模q运算。

数据结构和算法

字符串匹配算法（一）——朴素算法

写python代码写习惯了，再来用C代码处理字符串感觉很痛苦。在python中有find、index等函数可以进行字符串匹配，而用C语言就只能自己写了。

朴素算法思路比较简单，就是将源字符串与目标字符串挨个进行比较，看看在目标字符串中是否包含了源字符串。该算法的匹配时间为O((n-m+1)m)。

C语言实现如下：

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
#include <stdio.h>

int native_matcher(char *t, char *p, int len1, int len2)
{
    int i, j, idx;
    idx = 0;
    for (i=0; i<len1; i++) {
        for (j=0; j<len2; j++) {
            if (p[j] != t[j+i]) {
                break;
            }
        }
        if (j == len2) {
            return i;
        }
    }
    return -1;
}

int main(int argc, char *argv[])
{
    char t[] = "BBC ABCDAB ABCDABCDABDE";
    char p[] = "ABCDABD";
    int len1 = sizeof(t) - 1;
    int len2 = sizeof(p) - 1;
    int index = native_matcher(t, p, len1, len2);
    printf("index: %d\n", index);
    return 0;
}
数据结构和算法

常用的排序算法（八）——桶排序

桶排序算法对待排数列有一定的要求。数据长度必须一样，并且符合均匀分布。

桶排序的基本思想就是先创建一个含n个元素的数组，即就是创建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
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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
const int N = 20;
const int M = 10;

struct chain
{
    int key;
    struct chain *next;
};

void init_bucket(struct chain a[], int n)
{
    int i = 0;
    for(; i < n; i++)
    {
        a[i].key = i * 10;
        a[i].next = NULL;
    }
}

int * generate(int a[], int n)
{
    int i;
    for(i = 0; i < n; i++)
    {
        a[i] = 0;
    }
    time_t t;
    srand((unsigned)time(&t));

    for(i = 0; i < n; i++)
    {
        a[i] = rand() % 100;
    }
    return a;
}


void print_array(int *a, int n)
{
    int i = 0;
    while(i < n)
    {
        printf("%4d", a[i]);
        i++;
    }
    printf("\n");
}

void print_bucket(struct chain a[], int n)
{
    int i = 0;
    for(; i < n; i++)
    {
        printf("%4d", a[i].key);
    }
    printf("\n");
}


void insertChain(struct chain node, struct chain *newNode)
{
    if(node.next == NULL)
    {
        node.next = newNode;
    }
    else
    {
        struct chain *p = node.next;
        struct chain *q = p;
        while(p->key < newNode->key)
        {

            q = p;
            p = p->next;
        }
        newNode->next = q->next;
        q->next = newNode;

    }
}

void print_keys(struct chain a[], int n)
{
    int i = 0;
    for(; i < n; i++)
    {
        if(a[i].next != NULL)
        {
            struct chain *p = a[i].next;
            while(p->next != NULL)
            {
                printf("%4d", p->key);
                p = p->next;
            }
            printf("%4d", p->key);
        }
    }
}

void insert_bucket(struct chain a[], int *keys, int n)
{
    int i = 0;
    for(; i < n; i++)
    {
        struct chain *newNode = (struct chain *)malloc(sizeof(struct chain));
        newNode->key = keys[i];
        newNode->next = NULL;

        struct chain *node = &a[keys[i] / 10];

        if(node->next == NULL)
        {
            node->next = newNode;
        }
        else
        {
            struct chain *p = node->next;
            struct chain *q = p;
            while((p->key <= newNode->key) && (p->next != NULL))
            {

                q = p;
                p = p->next;
            }
            newNode->next = q->next;
            q->next = newNode;
        }
    }
}

int main()
{
    struct chain heads[M];
    init_bucket(heads, M);
    printf("bucket: ");
    print_bucket(heads, M);

    int keys[N];
    generate(keys,N);
    printf("numbers:");
    print_array(keys, N);

    insert_bucket(heads, keys, N);
    printf("ordered:");
    print_keys(heads, M);
    printf("\n");
    return 0;
}
数据结构和算法

常用的排序算法（七）——希尔排序

希尔排序又称缩小增量排序。它是插入排序的一种改进版。

它的基本思想是：先将整个待排序列分割成若干子序列分别进行直接插入排序，待整个序列基本有序时再进行一次直接插入排序。

例如对于数列A={49, 38, 65, 97, 76, 13, 27, 49, 55, 04}，首先将数列分成五个子序列{A0, A5}, {A1, A6}, {A2,A7}, {A3,A8}, {A4,A9}，分别对它们进行直接插入排序。于是第1趟希尔排序之后数列为：{ 13 27 49 55 4 49 38 65 97 76 }。然后再将该数列分成两个子数列{A0,A2,A4,A6,A8}， {A1,A3,A5,A7,A9}，于是第3趟希尔排序之后数列为：{ 4 27 13 49 38 55 49 65 97 76 }。最后再进行一次插入排序即可。

用C语言实现如下：

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
#include <stdio.h>

void print_list(int *ar, int n)
{
    int i;
    printf("[ ");
    for (i=0; i<n; i++) {
        printf("%d ", ar[i]);
    }
    printf("]\n");

}

void shell_sort(int *ar, int n)
{
    int d, i, j, tmp;
    d = n / 2;
    while (d >= 1) {
        for (i=d; i<n; i++) {
            tmp = ar[i];
            j = i - d;
            while (j >= 0 && tmp < ar[j]) {
                ar[j+d] = ar[j];
                j -= d;
            }
            ar[j+d] = tmp;
        }
        d = d / 2;
        print_list(ar, n);
    }
}

int main(int argc, char *argv[])
{
    int a[] = {49, 38, 65, 97, 76, 13, 27, 49, 55, 04};
    int len=sizeof(a)/sizeof(int);
    printf("begin: ");
    print_list(a, len);
    shell_sort(a, len);
    printf("end ");
    print_list(a, len);
    return 0;
}

希尔排序演示图片：

数据结构和算法

常用的排序算法（六）——快速排序

快速排序也是分治算法的一种应用。它的基本操作是根据某种方法（可以是随机的，也可以是最左边，或者是中间的）选择一个元素作为中枢值。这个元素将数组分为两个子数组，小于或等于中枢值的元素都移到左边，大于或等于中枢值的元素都移到右边。然后每个子数组再递归地排序。

快速排序的平均时间复杂度为O(nlogn)，最好时为O(nlogn)，最坏时为O(n*n)。

用C语言实现如下：

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
#include <stdio.h>

void print_list(int *ar, int n)
{
    int i;
    printf("[ ");
    for (i=0; i<n; i++) {
        printf("%d ", ar[i]);
    }
    printf("]\n");

}

int partition(int *ar, int left, int right)
{
    int x, i, j;
    int tmp;

    x = ar[right];
    i = left;
    for (j=left; j<right; j++) {
        if (ar[j] <= x) {
            tmp = ar[j];
            ar[j] = ar[i];
            ar[i] = tmp;
            i++;
        }
    }
    tmp = ar[i];
    ar[i] = ar[right];
    ar[right] = tmp;
    return i;
}

void quick_sort(int *ar, int left, int right)
{
    int index;
    if (left < right) {
        index = partition(ar, left, right);
        quick_sort(ar, left, index-1);
        quick_sort(ar, index, right);
    }
}

int main(int argc, char *argv[])
{
    int a[] = {15, 9, 8, 1, 4, 11, 7, 12, 13, 16, 5, 3, 16, 2, 10, 14};
    int len=sizeof(a)/sizeof(int);
    printf("begin: ");
    print_list(a, len);
    quick_sort(a, 0, len-1);
    printf("end ");
    print_list(a, len);
    return 0;
}

这个例子是选择最右边的元素作为中枢值。

快速排序演示图片：

数据结构和算法

常用的排序算法（五）——堆排序

堆排序的时间复杂度为O(nlogn)。

首先简单介绍一下堆，一个堆其实就是一个近似的完全二叉树，它具有以下两个性质：
外形性质：如果深度k-1存在2**(k-1)个节点，那么深度k(k>0)上存在叶子节点。另外，在一个部分填充的深度级上，节点是“ 从左到右”添加的。

堆的性质：树中每一个节点的值都大于或者等于任意一个子节点的值。

堆只是一个抽象的数据结构，在内存可以使用数组来表示的。第0个值为根节点。对于第i个节点，其左子节点为2i+1，右子节点为2i+2。

例如，对于数列[ 5 3 16 2 10 14 ]，将其构造一个堆则为：

1
2
3
4
5
    16
   /   \
  10    14
 / \    /
2   3  5

然后这个堆对应的数组为[ 16 10 14 2 3 5 ]，最后就是对这个堆进行排序。

代码如下：

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
#include <stdio.h>

void print_list(int *ar, int n)
{
    int i;
    printf("[ ");
    for (i=0; i<n; i++) {
        printf("%d ", ar[i]);
    }
    printf("]\n");

}
static void heapify(int *ar, int idx, int max)
{
    int left = 2*idx + 1;
    int right = 2*idx +2;
    int largest;

    // 计算A[idx], A[left], A[right]中最大的一个
    if (left < max && ar[left] > ar[idx]) {
        largest = left;
    } else {
        largest = idx;
    }

    if (right < max && ar[right] > ar[largest]) {
        largest = right;
    }

    // 如果最大的不是父节点，那么交换并递归执行
    if (largest != idx) {
        int tmp;
        tmp = ar[idx];
        ar[idx] = ar[largest];
        ar[largest] = tmp;

        heapify(ar, largest, max);
    }
}

static void buildHeap(int *ar, int n)
{
    int i;
    for (i=n/2-1; i>=0; i--) {
        heapify(ar, i, n);
    }
}

void heap_sort(int *ar, int n)
{
    int i;
    int tmp;
    buildHeap(ar, n);
    printf("build:");
    for (i=n-1; i>=1; i--) {
        tmp = ar[0];
        ar[0] = ar[i];
        ar[i] = tmp;

        heapify(ar, 0, i);
    }
}

int main(int argc, char *argv[])
{
    int a[] = {5, 3, 16, 2, 10, 14};
    int len=sizeof(a)/sizeof(int);
    printf("begin: ");
    print_list(a, len);
    heap_sort(a, len);
    printf("end ");
    print_list(a, len);
    return 0;
}

堆排序演示图片：

数据结构和算法

常用的排序算法（四）——选择排序

选择排序的时间复杂度为O(n*n)。

其基本操作是每一次从待排序的数列中先出最大（或最小）的一个元素，然后把它顺序的放在已排好序的数列的最后。

例如：
一个数列初始状态为：[ 5 3 16 2 10 14 ]
第一次排序后为： [ 5 3 14 2 10 ] 16
第二次排序后为： [ 5 3 10 2 ] 14 16
第三次排序后为： [ 5 3 2 ] 10 14 16
第四次排序后为： [ 2 3 ] 5 10 14 16
第五次排序后为： [ 2 ] 3 5 10 14 16
排序完成之后为： [ 2 3 5 10 14 16 ]

代码如下：

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
#include <stdio.h>

void print_list(int *ar, int n)
{
    int i;
    printf("[ ");
    for (i=0; i<n; i++) {
        printf("%d ", ar[i]);
    }
    printf("]\n");

}

int select_max(int *ar, int left, int right)
{
    int max = left;
    int i = left;
    while (++i <= right) {
        if (ar[i]  > ar[max]) {
            max = i;
        }
    }
    return max;
}

void selection_sort(int *ar, int n)
{
    int i, max, tmp;
    for (i=n-1; i>=1; i--) {
        max = select_max(ar, 0, i);
        if (max != i) {
            tmp = ar[i];
            ar[i] = ar[max];
            ar[max] = tmp;
        }
    }

}

int main(int argc, char *argv[])
{
    int a[] = {5, 3, 16, 2, 10, 14};
    int len=sizeof(a)/sizeof(int);
    printf("begin: ");
    print_list(a, len);
    selection_sort(a, len);
    printf("end ");
    print_list(a, len);
    return 0;
}

选择排序演示图片：

数据结构和算法

常用的排序算法（三）——归并排序

归并排序的最好、最坏和平均时间复杂度都是O(nlogn)。它是分治算法的一种典型应用。

它是基本操作就是将待排序的数列分为多个有序子数列，然后再将这些子数列合并为有序的数列。

这种排序方法经常用于将多个有序的数据文件合并在一个有序的数据文件。

用C语言实现如下：

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
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

int len;
void print_list(int *list, int n)
{

    int i;
    printf("[ ");
    for (i=0; i<n; i++) {
        printf("%d ", list[i]);
    }
    printf("]\n");
}

void merge(int *a, int p, int q, int r)
{
    int n1 = q - p + 1;
    int n2 = r - q;
    int *L = (int *)malloc((n1+1) * sizeof(int));
    int *R = (int *)malloc((n2+1) * sizeof(int));
    int i, j, k;
    
    for (i=0; i<n1; i++) {
        L[i] = a[p+i];
    }
    for (j=0; j<n2; j++) {
        R[j] = a[q+j+1];
    }
    // 设置"哨兵牌"
    L[i] = INT_MAX;
    R[j] = INT_MAX;

    i = j = 0;
    for (k=p; k<=r; k++) {
        if (L[i] <= R[j]) {
            a[k] = L[i];
            i++;
        } else {
            a[k] = R[j];
            j++;
        }
    }
    free(L);
    free(R);
    print_list(a, len);
}

void merge_sort(int *a, int p, int r)
{
    if (p < r) {
        int q = (p + r) / 2;
        merge_sort(a, p, q);
        merge_sort(a, q+1, r);
        merge(a, p, q, r);
    }
}

int main(int argc, char *argv[])
{
    int a[] = {3, 41, 52, 26, 38, 57, 9, 49};
    //int a[] = {5, 2, 4, 7, 1, 3, 2, 6};
    len = sizeof(a) / sizeof(int);
    merge_sort(a, 0, len-1);
    return 0;
}

各位可以尝试把它改进一下，去掉哨兵牌。

归并排序演示图片：

数据结构和算法

常用的排序算法（二）——插入排序

插入排序的平均时间复杂度为O(nn)，最好的情况下为O(n)，最坏情况为O(nn)。

其基本机理与我们平时打牌时整理手中的牌的做法差不多。把小的牌插到左边，大的牌往右边移。

用C语言实现如下：

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
#include <stdio.h>

void print_list(int *list, int n)
{

int i;
printf("[ ");
for (i=0; i<n; i++) {
printf("%d ", list[i]);
}
printf("]\n");
}

void insertion_sort(int *base, int len)
{

int i, j, n;
int value;
for (j=1; j<len; j++) {
i = j - 1;
value = base[j];
while (i>=0 && base[i] > value) {
base[i+1] = base[i];
i--;
}
base[i+1] = value;
printf("step %d:", j);
print_list(base, len);
}
}

int main(int argc, char *argv[])
{
int a[] = {5, 2, 4, 6, 1, 3};
int len = sizeof(a) / sizeof(int);
insertion_sort(a, len);
return 0;
}
数据结构和算法

常用的排序算法（一）——冒泡排序

前言：

自从毕业了之后就没怎么用到算法，以致于之前学的都忘得差不多了。最近决定抽空再把算法重新学习一下，虽然平时也用不上。
这次学习我是把算法导论、算法技术手册和数据结构(严蔚敏)这三本书混合着看。


正文：

冒泡排序的时间复杂度为O(n*n)，它的原理比较简单。基本思路就是从第1个元素开始，依次的把该元素与后一个元素进行比较，如果比后一个元素大则交换它们的位置；每1次全部比较完成之后，最大的那个元素就放在了最后。重复之前的操作，直到所有元素都排好序。

用C语言实现如下：

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
#include <stdio.h>

void print_list(int *ar, int n)
{
    int i;
    printf("[ ");
    for (i=0; i<n; i++) {
        printf("%d ", ar[i]);
    }
    printf("]\n");

}

void bubble_sort(int *ar, int n)
{
    int i, j;
    int tmp;
    for (i=0; i<n-1; i++) {
        for (j=0; j<n-1; j++) {
            if (ar[j] > ar[j+1]) {
                tmp = ar[j];
                ar[j] = ar[j+1];
                ar[j+1] = tmp;
            }
        }
    }
}

int main(int argc, char *argv[])
{
    int a[] = {5, 3, 16, 2, 10, 14};
    int len=sizeof(a)/sizeof(int);
    printf("begin: ");
    print_list(a, len);
    bubble_sort(a, len);
    printf("end: ");
    print_list(a, len);
    return 0;
}

冒泡排序演示图片：