算法复习笔记

发表于 | | 热度: ℃
字数统计: 5.9k 字 | 阅读时长 ≈ 25 分钟

顺序表的静态定义

1
2
3
4
5
6
7
8
9
10
11
12
13
// 第一种，定义一个数组
int Sqlist[100];

// 第二种，定义一个宏来描述大小
#define List_size 100
int Sqlist[List_size];

// 第三种，定义一个结构体
#define List_size 100
typedef struct{
    int elem[List_size];
    int len; // 描述实际长度
}Sqlist;

顺序表动态定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 利用指针
#define List_size 100
typedef struct{
    int *elem;
    int len; // 描述实际长度
    int listsize; //当前分配空间大小
}Sqlist;

int InitSqlist(Sqlist *L){
    L->elem = (int*)malloc(List_size * sizeof(int));
    if(L->elem == NULL){
        exit(EXIT_FAILURE);
    }
    L->len = 0;
    L->listsize = List_size;
    return 1;
}

顺序表插入操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 在第i个位置插入e
int listInsert_Sq(Sqlist &L, int i, int e){
    // 插入位置合理
    if(i<1 || i>L.len+1) return 0;
    // 出现上溢
    if(L.len >= L.listsize){
        newbase = (int*)realloc(L.elem, (L.listsize + ListIncerament) * sizeof(int));
        if (newbase == NULL) exit(OVERFLOW);
        L.elem = newbase;
        L.listsize = L.listsize + ListIncerament;
    }
    for(int j = L.len; j>=i; j--) L.elem[j] = L.elem[j-1];
    L.elem[i-1] = e;
    L.len++;
    return 1;
}

顺序表的删除操作

1
2
3
4
5
6
7
// 删除第i个元素
int listDelete_Sq(Sqlist &L, int i){
    if(i<1 || i> L.len) return 0;
    for(int j = i; j<L.len; j++) L.elem[j-1] = L.elem[j];
    L.len--;
    return 1;
}

顺序表优缺点

  • 优点：随机存取
  • 缺点：空间利用率低；静态的不可扩充；动态的反复扩充开销大；插入删除需要移动大量元素；
  • 适用于输入数据大小已知，无需太多动态操作的应用

单链表的定义

1
2
3
4
5
6
struct Node{
    int data;
    struct Node *next;
};
typedef struct Node *Link;
Link head;

有头节点的单链表插入算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 在第i个位置插入元素e
int listInsert(Link &L, int i, int e){
    Link p = L;
    int j = 0;
    while(p!= NULL && j < i-1){
        p = p->next;
        j++;
    }
    if(p == NULL || j>i-1) return 0;
    struct Node s;
    s = (Link)malloc(sizeof(Node));
    if(s == NULL) exit(OVERFLOW);
    s->data = e;
    s->next = p->next;
    p->next = s;
    return 1;
}

无头节点的单链表插入算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int listInsert(Link &L, int i, int e){
    if(i == 1){
        struct Node s;
        s = (Link)malloc(sizeof(Node));
        s->data = e;
        s->next = L;
        L = s;
    }else{
        Link p = L;
        int j = 1;
        while(p != NULL && j<i-1){
            p = p->next;
            j++;
        }
        if(p == NULL || j>i-1) return 0;
        struct Node s;
        s = (Link)malloc(sizeof(Node));
        s->data = e;
        s->next = p->next;
        p->next = s;
    }
    return 1;

头插法

1
2
3
4
s = (Link)malloc(sizeof(Node));
scanf(&s->data);
s->next = L->next;
L->next = s;

尾插法

1
2
3
4
p->next = (Link)malloc(sizeof(Node));
p = p->next;
scanf(&p->data);
p->next = NULL;

双向链表定义

1
2
3
4
5
6
7
8
9
10
struct Node{
    int data;
    struct Node *next;
    struct Node *prev;
};
typedef struct Node *Link;
typedef struct{
    Link head, tail;
    int len;
}DLinkList;

顺序栈的定义

1
2
3
4
5
6
7
8
struct stack{
    int *base;
    int stack_size;
    int min_stack;
    int max_stack;
    int top;
};
typedef struct stack Stack;

初始化栈

1
2
3
4
5
6
7
8
9
10
11
12
13
Stack *CreateStack(int how_many){
    Stack *pstk;
    assert(how_many>0);
    pstk = (Stack*)malloc(sizeof(Stack));
    if(pstk == NULL) return(NULL);
    pstk->stack_size = how_many;
    pstk->base = (int*)malloc(how_many * sizeof(int));
    if(pstk->base == NULL) return(NULL);
    pstk->min_stack = 0;
    pstk->max_stack = how_many-1;
    pstk->top = -1;
    return(pstk);
}

销毁栈

1
2
3
4
5
void DestroyStack(Stack *this_stack){
    this_stack->top = -1;
    free(this_stack->base);
    this_stack->base = NULL;
}

随机访问栈元素

1
2
3
4
5
6
// which_elem 表示待查元素与栈顶的间隔
int* viewElem(Stack *this_stack, int which_elem){
    if(this_stack->top == -1) return(NULL);
    if(this_stack->top - whick_elem < 0 ) return(NULL);
    return(&(this_stack->base[this_stack->top-which_elem]));
}

入栈

1
2
3
4
5
6
7
int pushElem(Stack *this_stack, int *to_push){
    // 判断栈满
    if(this_stack->top == this_stack->max_stack) return(0);
    this_stack->top += 1;
    memmove(&(this_stack->base[this_stack->top]), to_push, sizeof(int));
    return(1);
}

出栈

1
2
3
4
5
6
7
int popElem(Stack *this_stack, int *dest){
    // 判断栈空
    if(this_stack->top == -1) return(0);
    memmove(dest, &(this_stack->base[this_stack->top]), sizeof(int));
    this_stack->top -= 1;
    return(1);
}

推荐适用顺序栈

  • 实现简单
  • 栈的受限操作正好屏蔽了顺序表的弱势：插入和删除都是在同一端进行的

栈、队列对比

  • 栈：栈顶（top）允许插入和删除的一端；栈底（base/bottom）表头端
  • 队列：队头（front）允许删除的一端；队尾（rear）允许插入的一端

队列的应用：操作系统的作业排队

顺序队列定义

1
2
3
4
5
6
7
#define Max_QSize 100
typedef struct{
    int *base;
    int front;
    int rear;
} queue_struct;
queue_struct SqQueue;

顺序对列的入队出队以及队空队满

  • 入队：若未满，Q.rear++
  • 出队：若未空，Q.front++
  • 队空：Q.front == Q.rear
  • 队满：Q.rear == Max_QSize
  • 问题是存在假上溢

构建循环队列，解决假上溢的问题

  • 入队：若未满，Q.rear = (Q.rear+1)% Max_QSize
  • 出队：若不空，Q.front = (Q.front+1)% Max_QSize
  • 队空：Q.rear == Q.front
  • 队满：Q.rear == Q.front
  • 问题是对空队满判断一样
  • 解决：少一个元素空间，堆满改为：(Q.rear+1)% Max_QSize == Q.front

链队列

  • 队头用链表的头指针表示
  • 队尾用链表的尾指针表示
  • 无队满问题
  • 队空：Q.rear == Q.front

Hash表定义

  • 用动态定义的顺序表来定义hash表
1
2
3
4
5
6
7
#define Table_Size 100
struct HashTable_struct{
    int *elem;
    int len;
    int tableSize;
};
typedef struct HashTable_struct hash_table;

冲突处理办法

  • 线性再散列
  • 非线性再散列
  • 外部拉链法
  • 线性再散列的缺点是1.不能删除表中元素，解决办法是把用过的槽标记为无效2.当表被填满时性能显著下降
  • 再散列法的优点是1容易进行动态编码2负载因子较低且不太可能删除元素时速度快，负载因子大于0.5时不建议使用
  • 外部拉链法可以容纳的元素取决于内存的大小，而再散列法取决于表的大小
  • 外部拉链法平均查找时间 = 链表长度/2 + 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
25
26
27
// 确定在有序整数序列x中，整数t第一次出现的位置
int binarySearch(int t){
    int l,u,m;
    l = 0;
    u = n-1;
    for(;;){
        if(l>u) return -1;
        m = (l+u)/2;
        if(x[m] < t) l = m+1;
        else if(x[m] == t) return m;
        else u = m-1;
    }
}

// 优化1
int binarySearch1(int t){
    int l,u,m;
    l = 0;
    u = n-1;
    while(l<=u){
        m = (l+u)/2;
        if(x[m]<t) l = m+1;
        else if(x[m] == t) return m;
        else u = m-1;
    }
    return -1;
}

代码调优通用法则

  • 利用等价的代数表达式，比如模运算的优化
  • 利用宏替换函数，但有时会起反作用
  • 利用哨兵合并测试条件
  • 展开循环
  • 高速缓存需经常处理的数据
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 整数取模
// 优化前
k = (j + r) % n;

// 优化后
k = j + r;
while(k > n)
    k -= n;
    
// 利用宏
// 优化前
float max(float a, float b){
    return a>b?a:b;
}

// 优化后
#define max(a,b) ((a)>(b)?(a):(b));

朴素的模式匹配算法

  • 时间复杂度：设n为主串长度，m为子串长度，O((n-m+1)*m)
  • 最好情况：O(m)
  • 平均情况：每次匹配不成功都是在子串的首字符处，O(m+n)
  • 最坏情况：O((n-m+1)*m)
  • 缺点是需要回溯

KMP算法

  • 近似时间复杂度为O(m+n), O(n)为比较的时间，O(m)为计算next数组的时间
  • 目标串中不存在回溯
  • 目标串中每个字符会比较1～2次
  • 字符串的下标是从1开始
  • 仅当模式串与目标串存在许多部分匹配时，KMP才比朴素模式匹配有优势
  • 若每一次不匹配都发生在第一个字符，KMP会退化为朴素模式匹配

BM算法

  • 从右往左
  • 坏字符：子串从右开始标，第一个为0，每种字符只标一次，大小为到最右的距离，其他为整个子串长度
  • 好后缀：子串从右开始标，第一个为1，完整的好后缀从右往左找重复的，不完整的好后缀从头往后找重复的，大小等于好后缀长度加上到重复的距离
  • 通常模式串越长，BM算法越快，因为每一次失败的匹配，BM都能够使用这些信息来排除尽可能多的无法匹配的位置

二叉树的性质

  • 第i层最多 $2^{i-1}$ 个节点
  • 深度为k的二叉树最多 $2^{k+1}-1$个节点
  • $n_0 = n_2 + 1$

二叉树顺序存储定义

1
2
3
4
5
6
7
8
9
10
// 定义1
#define MAX_TREE_SIZE 100
ElemType SqBiTree[MAX_TREE_SIZE];

// 定义2
#define MAX_TREE_SIZE 100
typedef struct{
    ElemType elem[MAX_TREE_SIZE+1];
    int len;
}SqBiTree;

二叉链表定义

1
2
3
4
typedef struct{
    ElemType data;
    struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

二叉排序树

  • 中序遍历二叉排序树，可以得到一个关键字的有序序列
  • 删除操作：用中序遍历的直接后继或直接前驱进行替换
  • 构造二叉排序树的形状依赖于数据项，且依赖于它们加载的顺序
  • 为解决二叉排序树的失衡问题，提出了AVL树，红黑树，伸展树

AVL树

  • 发生失衡时，找到不平衡的最小子树根结点开始调节

红黑树

  • 2-3-4树 插入时，遇到4节点就要分

伸展树

  • 优点：最近使用过的数据比未使用的数据更快被访问
  • 查找：若n在树t上，则以n为根结点进行重排；若n不在树t上，则将查找n的过程中第一个非空叶子节点作为根结点进行重排；最后判断根结点与n是否相同
  • 插入：根据重排后的根结点与待插入的n之间的关系，决定n插入的位置
  • 删除：重排后，待删除的n位于根节点处，删除n后，若左孩子非空，则用中序遍历的前驱代替n，若左孩子为空，则用右孩子代替
  • 自底向上：待访问节点c，父节点p，祖父节点g
    • 若c无祖父，直接在cp之间旋转
    • 若cpg之间为LL或RR的关系，则pg先旋转，然后pc旋转
    • 若cpg之间为LR或RL的关系，则cp先旋转，然后cg旋转

B树/B+树

  • 如何快速检索内存中的数据
    • 二叉排序树，hash表，二分查找
  • 如何快速检索磁盘上的海量数据
    • 减少磁盘IO次数和提高内存检索效率
  • B和B+区别
    • B+的叶子节点包含了全部关键字信息以及指向这些关键字的指针，叶子节点本身也以关键字大小自小而大顺序连接
    • 所有非终端节点可以看做索引部分，节点中含有其子树最大或最小的关键字
  • B+树的特点
    • B+树不是树
    • 两部分组成
      • 索引块，指针指向块号
      • 数据块，指针指向记录地址
  • B+树的查找
    • 顺序查找（横向）
    • 随机查找（纵向）
  • B+树的查询效率是常数，B+树的查询效率对于某建成的树是固定的，而B树是与键在树中的位置有关的
  • 应用场景：磁盘上海量数据的检索

Trie树

  • 特性：
    • 1 根节点不含字符，根节点外每个节点含有一个字符
    • 2 从根节点到某一节点路径上经过的字符连接起来为该节点对应的字符串
    • 3 每个节点的子节点都不相同
1
2
3
4
5
6
7
8
// Trie的定义
const int kind = 26
typedef struct Treenode{
    int count;
    bool isColored;
    TrieNode *next[kind];
}TrieNode;
TrieNode *root;
  • 典型应用：用于统计和排序大量的字符串，所以经常被搜索引擎用于文本词频统计
  • 查找某个字符串操作的复杂度为O(N),其中N为字符串长度，空间换时间
  • 优点：利用字符串的公共前缀来节省存储空间，最大限度减少无谓的比较，查询效率比hash高
  • 中文字典树：Trie树的每个子节点用hash存储

排序

  • 通常排序算法都设计为用于数组，非常适合链表的排序方法有：插入排序和快排
  • 内部排序：把待排的所有记录都加载进内存，然后对内存中的这些记录进行排序
  • 外部排序：待排序的记录无法一次性加载到内存中，因此每次加载部分记录，并进行内部排序
  • 基于比较的排序算法：平均复杂度≥O(NlogN)
    • 交换：冒泡，快排
    • 选择：简单选择，堆排序
    • 插入：直接插入，折半插入，希尔排序
  • 基于某种映射的排序，平均时间复杂度为线性级别：桶排序，基数排序

冒泡

  • 连续扫描待排序的记录
  • 每趟扫描都把最大的记录移动到序列的尾部
  • 若某趟扫描没有任何交换，则表明是有序的了
  • 时间复杂度：平均：O($N^2$),最坏：O($N^2$),最好：O(N)
  • 空间复杂度：交换时需要一个辅助空间temp，所以是O(1)
  • 基于数组的冒泡排序的基本操作是比较和交换
  • 优点是：简单，容易实现；对几乎有序的记录排序的时间开销为O(N)
  • 由相邻的记录进行交换，所有是稳定的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 外层循环控制执行的趟数，内层循环控制在一趟中相邻记录间的比较和交换
void BubbleSort(Element **Array, int N, CompFunc Compare){
    int limit;
    for(limit = N-1; limit>0; limit--){
        int j, swapped;
        swapped = 0;
        for(j = 0; j<limit; j++){
            if(Compare(Array[j], Array[j+1])>0){
                Element *temp;
                temp = Array[j];
                Array[j] = Array[j+1];
                Array[j+1] = temp;
                swapped = 1
            }
        }
        if(!swapped)
            break;
    }
}

简单选择排序

  • 连续扫描序列A，不断从待排记录中选出最小的记录放到已排序记录序列的后面，直到n个记录全部插入到已排序序列中
  • 不稳定的：比如3，3，3**，2，在第一遍过后就会变为2，3，3**
  • 对于长度是N的数组，选择排序需要大约N2/2次比较和N次交换
  • 总的来说时间复杂度是T(N) = O($N^2$)
  • 空间复杂度是：交换时需要辅助空间temp，O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 外循环用于控制排序的次数，内循环用于查找待排记录中关键字最小的记录
void SelectSort(Element **Array, int N, CompFunc Compare){
    int i, j, cnt;
    for(i = 0; i<N-1; i++){
        Element *temp;
        temp = Array[i];
        cnt = i;
        for(j = i+1; i<N; j++ ){
            if(Compare(temp, Array[j])>0){
                temp = Array[j];
                cnt = j;
            }
        }
        if(cnt != i){
            Array[cnt] = Array[i];
            Array[i] = temp;
        }
    }
}

直接插入排序

  • 逐个处理待排序的记录，将每个记录与前面已经排好的记录序列进行比较，并将其插入到合适的位置
  • 对于已经排序好的序列，从后往前进行扫描
  • 空间复杂度：只需要一个temp，所以O(1)
  • 稳定性：稳定
  • 时间复杂度：外循环始终n-1次，最好情况即为初始是正序的，时间复杂度为：O(n),最坏情况为逆序序列，时间复杂度为O($N^2$),平均情况为O($N^2$)
  • 越接近于有序，该算法效率越高
  • 基于数组的操作：比较和半交换(移位)
  • 优点：对几乎有序的时间开销为O(n);可以用于优化快排
  • 改进：折半插入排序，直接插入排序的查找插入位置采用折半查找的方法实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void InsertSort(Element **Array, int N, CompFunc Compare){
    int step;
    for(step = 1; step<N; step++){
        int i;
        Element *temp;
        temp = Array[step];
        for(i = step-1; i>=0; i--){
            if(Compare(Array[i], temp)>0){
                Array[i+1] = Array[i]];
            }
            else
                break;
        }
        Array[i+1] = temp;
    }
}

希尔排序

  • 直接插入的改进版
  • 直接插入排序的问题：每次扫描序列，智能确定一个目标的合法位置
  • 思想：先分割成若干小组，分别在组内进行直接插入排序，待基本有序后，再对全体进行一次直接插入排序，每个组内记录间隔h，h稳定递减，h最后一个取值为1
  • 改进的出发点是：直接插入排序对几乎有序的记录排序时间开销为O(N)
  • 时间复杂度为：O($n^{1.25}$)
  • 不稳定
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void ShellSort(Element **Array, int N, CompFunc Compare){
    int step, h;
    for(h = 1; h<= N/9; h = 3*h+1)
        ; // h = 1,4,13,40...
    for(;h>0;h/=3){     //h = ...,40,13,4,1
        for(step = h; step<N; step++){
            int i;
            Element *temp;
            temp = Array[step];
            for(i = step-h; i>0; i-=h){
                if(Compare(temp, Array[i])<0){
                    Array[i+h] = Array[i]
                }
                else
                    break;
            }
            Array[i+h] = temp;
        }
    }
}

快速排序

  • 分治法:将待排数组分成两个小部分,分别进行递归快排
  • 思想:
    • 若待排的数组中只有一个元素,则退出
    • 否则选择一个元素作为基准
    • 将待排的数组按该元素划分成两个数组A1和A2,其中A1中的元素都小于等于该元素,A2中的元素都大于等于该元素
    • 对A1进行快排
    • 对A2进行快排
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 算法实现1
// 单向划分 & 将数组的首元素作为基准
// 性能分析:对于随机数组:T(n) = O(nlogn),栈深度:O(logn)
// 因为每层递归都执行了O(n)次比较,总计O(logn)次递归
// 对于非随机数组:不管是相同的元素还是升降序的,T(n2)
void qsort1(int l, int u){
    int i,m;
    if(l>=u)
        return;
    m = l;  // m表示存放小于基准元素的子数组A1的最末元素的下标,A1采用尾插法来添加新的元素
    for(i = l+1; i<=u; i++){
        if(x[i]<x[l]){
            swap(++m, i);
        }
    }
    swap(l, m);
    qsort1(l, m-1);
    qsort1(m+1, u);
}
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
// 算法实现2
// 双向划分 & 将数组首元素作为基准
// i右移过小元素,遇到大元素时停止
// j左移过大元素,遇到小元素时停止
// 若i,j不交叉,则交换两下标对应的元素
// 性能分析:对于随机顺序的数组:T(n) = O(nlogn),栈深度:O(logn)
// 对于非随机的数组:若果是相同的元素:T(n) = O(nlogn);如果是升降序的:T(n)=O(n2)
void qsort3(int l, int u){
    int i, j;
    DType t;
    if(l >= u)
        return;
    t = x[l];
    i = l;
    j = u+1;
    for(;;){
        do i++;while(i<=u && x[i]<t);
        do j--;while(x[j]>t); // 这里不使用等号是怕遇到所有元素都相同时,时间复杂度降到O(n2)
        if(i>j) break;
        swap(i, j);
    }
    swap(l, j);
    qsort3(l, j-1);
    qsort3(j+1, u);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 双向划分 & 将随机元素作为基准
// 优点是对于小的子数组,可采用插入排序的方法
void qsort4(int l , int u){
    int i, j;
    DType t, temp;
    if(u-l < cutoff)
        return;
    swap(l, randint(l,u));
    t = x[l];
    i = l;
    j = u+1;
    for(;;){
        do i++; while(i<=u && x[i]<t);
        do j--; while(x[j]>t);
        if(i>j) break;
        temp = x[i];
        x[i] = x[j];
        x[j] = temp;
    }
    swap(l, j);
    qsort4(l, j-1);
    qsort4(j+1, u);
}
  • 其他改进提速方法
    • 改进栈利用率,大的子数组改用迭代循环,小的子数组仍递归快排
    • 利用static,减少栈空间需求
    • 不使用显式的数组索引,改用等价的指针,以保证快排的稳定性
  • 总结
    • 系统自带的sort函数能满足需求,则不需要编写代码
    • 元素个数较少时,可以考虑直接插入排序
    • 元素个数较大时,可以考虑编码实现的快排

堆排序

  • 不存在最坏情况
  • T= O(nlogn)
  • 和希尔排序一样,是良好的通用排序算法
  • siftup(n) 在堆的尾部插入新元素后,需要重新获取堆的性质
  • siftdown(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
25
26
27
28
29
30
31
32
33
34
void hsort1(){
    int i;
    x--;
    for(i = 2; i<=n; i++)
        siftup(i);
    for(i = n; i>=2; i--){
        swap(1, i);
        siftdown1(1, i-1);
    }
    x++;
}
void siftup(int u){
    int i, p;
    i = u;
    for(;;){
        if(i == 1) break;
        p = i/2;
        if(x[p]>=x[i]) break;
        swap(p, i);
        i = p;
    }
}
void siftdown1(int l, int u){
    int i,c;
    i = l;
    for(;;){
        c = 2 * i;
        if(c>u) break;
        if(c+1 <= u && x[c+1]>x[c]) c++;
        if(x[i]>x[c]) break;
        swap(i,c);
        i =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
int main(){
    int i, ch,n=0,maxi,maxlen=-1;
    // a[n]为后缀数组,c[n]为字符数组
    while((ch = getchar())!= EOF){
        a[n] =  &c[n];
        c[n++] = ch;
    }
    c[n] = 0;
    // 按字符重新排序
    qsort(a,n,sizeof(char*),pstrcmp);
    // 统计最长重复子串
    for(i=0;i<n-1;i++)
        if(comlen(a[i], a[i+1])>maxlen){
            maxlen = comlen(a[i], a[i+1]);
            maxi = i;
        }
    printf("%.*s\n", maxlen, a[maxi]);
    return 0;
}
int pstrcmp(char **p, char **q){
    return strcmp(*p, *q);
}
int comlen(char *p, char *q){
    int i=0;
    while(*p && (*p++ == *q++))
        i++;
    return i;
}

海量数据的处理

统计

  • 双层桶划分+Trie树/hash表/红黑树
    • 将大文件划分成若干个小文件,利用hash技术
    • 对每个小文件进行词频统计
    • 合并各个小文件的结果
  • 云计算架构
  • 线性结构+直接排序法
    • 顺序表存储,归并排序进行排序,拍完再遍历统计词频
    • 理论上排序的时间复杂度是O(nlogn),遍历的时间复杂度是O(n),所以总体的是时间复杂度是O(nlogn)
    • 实际上每个 单词不止I/O一次,I/O属于耗时操作,所以实际上的时间复杂度远比理论上的大
  • 总结:
    • 如果海量数据无法一次性在内存中处理,可以划分成多个可以在内存中处理的数据区域
    • 再用Trie树/hash表统计

排序

  • 顺序表+直接排序法
    • 先外部排序,比如归并排序,时间复杂度O(nlogn)
    • 对排序完的进行遍历,统计次数,O(n)
    • 总体的时间复杂度就是O(nlogn)
  • 利用hash表
    • key为字串,value为出现次数
    • 时间复杂度为:O(n * 每个槽上的线性表平均长度)
    • 相比较上一个,不仅仅时间复杂度优化,而且只要IO一次,更好
  • 找出TOP10:可采用内部排序,局部淘汰,堆

关于重复项的处理

  • 分而治之+基于hash表的查找
    • 分别遍历a,b,求hash,分到若干个小文件中
    • 对每个小文件,将a中的数据存储到hash中,遍历b中每个数据,查询是否在hash中
  • 若允许有一定的错误率,可采用bloom filter
    • 是位图法的扩展
    • k个hash函数,每个字符串与k个bit对应,k越大,冲突的概率就越小
    • 存在查询结果的误判,但是节省了存储开销
    • 无需处理碰撞
    • $k=(ln2)*(m/n)$ 时的错误率是最小的,其中n为元素个数,m为位数组的大小,m的单位是bit,n的单位是个数,通常单个元素的长度都是狠多bit的,所以bloom filter是可以节省空间的
    • 在错误率不大于E的情况下,$m /geq nlog_2(1/E)log_2e = nlog_2(1/E)*1.44$
    • 缺点:不可逆,无法恢复表示的数据,因为hash表不可逆;不能删除元素
-------------本文结束 感谢您的阅读-------------