《编程珠玑》第14、15章读书笔记

第14章堆

本章用堆结构解决了两个重要问题：

1. 排序，对n元数组排序，所需时间不超过O(nlogn)，而且只需要额外几个字的额外空间。

2. 优先级队列，堆通过插入新元素和提取最小元素这两种操作来维护元素集合，每个操作所需的时间都为O(nlogn)。

       堆的数据结构实现, 最常见的二叉树表示方法，需要记录和指针。

任何结点的值都小于或等于其孩子的值的完全二叉树为小根堆

任何结点的值都大于或等于其孩子的值的完全二叉树为大根堆

注意：堆使用的是从下标1开始的数组。

两个关键函数

siftup函数重新获得堆性质：通过交换该结点与其父结点，尽可能地将新元素向上筛选。运行时间和log n成正比。

void siftup(n)

    pre n >0 && heap(1,n-1)

    post heap(1,n)

  i=n

  loop

    if i==1

     break

    p=i/2

    if x[p] <= x[i]

     break

   swap(p,i)

    i=p

       siftdown向下筛选时，将顺序不对的元素和比它小的子结点交换。

void siftdown(n)

      pre heap(2,n) && n>=0

     post heap(1,n)

    i=1

    loop

     c=2*i

      if c>n

        break

      if c+1<=n

        if x[c+1]<x[c]

           c++

      if x[i]<=x[c]

        break

     swap(c,i)

      i=c

堆排序

堆有两个比较重要的操作：插入和删除。插入时，我们一般将新插入的元素放在末尾，这时需要做向上调整；删除时一般是删除“根”节点元素，这时需要做向下调整，以确保堆的性质。

所谓优先队列是不同于先进先出的普通队列，而是每次从队列中取出具有最高优先权的元素。根据优先队列这一特点（每次取出最高优先权的元素），我们可以很自然地想到用堆来实现优先队列。

优先级队列提供了一种简单的向量排序算法，优先在优先级队列中依次插入每个元素，然后按序删除它们。

代码如下：

public:

    priQueue(int m) :maxsize(m)

    {

        x = new T[maxsize + 1];

        n = 0;

    }

    void insert(T t)

    {

        int i, p;

        x[++n] = t;

        //自底向上类似siftup函数内容实现优先级序列

        for (i = n ; i > 1 && x[p=i/2] > x[i] ;  i = p)

            swap(p, i);

    }

    //输出队列顶并调整队列结构

    T extramin()

    {

        /*cout << "队列中的数据为：" << endl;

        for (int i = 1; i <= n; i++)

        cout << x[i] << "\t";

        cout << endl;*/

        int i, c;

        T t = x[1];

        x[1] = x[n--];

        //自顶向下调整队列结构

        for (i = 1; (c = 2 * i) <= n; i = c)

        {

            if (c + 1 <= n && x[c + 1] < x[c])

                c++;

            if (x[i] <= x[c])

                break;

            swap(c, i);

        }

        return t;

    }

本章最终总结以下几个原理：

1.       高效性，堆数据结构形状保证了堆中所有节点和根节点之间相差的层数在logn内，由于树是平衡的，所以函数siftup和siftdown的运行效率很高。堆排序通过在同一个实现数组中包含两种抽象结构（堆和元素序列）来避免使用额外的开销；

2.       正确性；循环体执行始终保持不变式为真；形状和顺序性质是另一种不变式；

3.       抽象性，一个好的工程师能够分清某个组件做什么（用户看到的抽象功能）和如何做（黑盒实现）之间的差别；

4.       过程抽象；

5.       抽象数据类型：数据类型做什么是由它的方法和方法的规范给出的，而如何做则是由具体实现决定的；

 第15章字符串

       讨论了一些字符串的经典问题

1.    单词

【问题一】为文档中包含的单词生成一个列表，用标准模板库中的set和strings可以简单实现

int main(int argc, char **argv)

{

    set<string> str;

    set<string>::iterator iter;

    string t;

    while(cin >> t)

    {

        str.insert(t);

    }

    for(iter = str.begin(); iter != str.end(); iter++)

    {

        cout << *iter << endl;

    }

    return 0;

}

while循环读取输入并将每个单词插入集合str（忽略重复的单词），然后for循环迭代整个集合，并按排好的顺序输出单词。

【问题二】对文档中的每个单词出现的次数进行统计，使用模板中的map将整数计数与每个字符串联系起来。

int main(int argc, char **argv)

{

    map<string, int> m;

    map<string, int>::iterator iter;

    string t;

    while(cin >> t)

    {

        m[t]++;

    }

    for(iter = m.begin(); iter != m.end(); iter++)

    {

        cout << iter->first << " " << iter->second << endl;

    }

    return 0;

}

此外为减少处理时间，可以选择建立自己的散列表，结构和散列函数如下

typedef struct node *nodeptr;

typedef struct node

{

    char *word; //指向单词的指针

    int count;    //单词出现的频率

    nodeptr next; //指向下一个节点的指针

}node;

散列函数将每个字符串映射为一个小于NHASH的正整数

unsigned int hash(char *p)

{

    unsigned int h = 0;

    for( ; *p != ''; p++)

    {

        h = MULT * h + *p;

    }

    return h % NHASH;

}

int main(void){

for i=[0,NHASH)

bin[i]=NULL;

                 while scanf(“%s”,buf) != EOF;

 incword(buf);

  for i=[0,NHASH)

      for (p=-bin[i];p1=NULL;p=p->next)

print p->word,p->count;

  return 0;

}

主要操作函数是incword，增加原先存在的单词的计数值，若之前没有该单词，则对计数器初始化

void incword(char *s)

{

    nodeptr p;

    int h = hash(s);    //找到与单词对应的箱

    for(p = bin[h]; p != NULL; p = p->next)

    {

        if(strcmp(s, p->word) == 0)

        {

            (p->count)++;

            return;

        }

    }

    p = nmalloc();

    p->count = 1;

    p->word = smalloc(strlen(s) + 1);

    strcpy(p->word, s);

    p->next = bin[h];    //头插法

    bin[h] = p;

}

该散列表比C++标准模板库中的映射快一个数量级，但缺乏平衡树提供的最坏情况性能保证，，也不能支持其他设计顺序的操作。

2.    短语

【问题三】给定一个文本文件作为输入，查找在其中最长的重复子字符串。

直接方法：双重for循环依次比较每个字符串，找到最长重复子字符串。时间复杂度为n²

方法二：采用后缀数组来处理该问题
    使用一个称为“后缀数组”的数据结构，这个结构是一个字符指针数组，记为a。读取输入时，我们对a进行初始化，使得每个元素指向输入字符串中的相应字符：
    while(ch  = getchar() != EOF)
    {
            a[n] = &c[n];
            c[n] = ch;
    }
    c[n] = 0; //空字符是所有字符串结束的标志
    元素a[0]指向整个字符串，下一个元素指向从第二个字符开始的数组后缀，等等。对于输入字符串“banana”，该数组能够表示如下后缀：
                            char *a="banana"
                            a[0]=banana
                            a[1]=anana
                            a[2]=nana
                            a[3]=ana
                            a[4]=na
                            a[5]=a
    如果某个长字符串在数组c中出现了两次，那么它将出现在两个不同的后缀中，因此我们对数组进行排序以寻找相同的后缀。“banana”数组排序为：
                                      a[0]=a
                            a[1]=ana
                            a[2]=anana
                            a[3]=banana
                            a[4]=na
                            a[5]=nana
    然后就可以扫描数组，通过比较相邻元素来找出最长的重复字符串。
    该方法由于排序的存在，时间复杂度为O(nlogn)。

3.    生成随机文本

基于字母：下一个字母设置为前一个字母的随机函数，或者下一个字母设置为前k个字母的随机函数。

基于单词：
    方法一：最笨的方法是随机输出字典中的单词；
    方法二：稍微好点的方法是读取一个文档，对每个单词进行计数，然后根据适当的概率选择下一个输出的单词；
    方法三：如果使用在生成下一个单词时考虑前面几个单词的马尔科夫链，可以得到更加令人感兴趣的文本；
    下面是香农的算法：以构建【字母级别的一阶文本】为例，随机打开一本书并在该页随机选择一个字母记录下来。然后翻到另一页开始读，直到遇到该字母，此时记录喜爱其后面的那个字母。再翻到另外一页搜索上述第二个字母并记录其后面的那个字母。依次类推。对于【字母级别的1阶、2阶文本和单词级别的0阶、1阶文本】，处理过程类似。

int wordncmp(char *p, char* q)

{   

   int n = k;

   for ( ; *p == *q; p++, q++)

   {

        if (*p == 0 && --n == 0)

            return 0;

   }

   return *p - *q;

}

该函数在字符相同时持续扫描两个字符串。每当遇到空字符时，计数器n减1，并找到K个相同的单词后返回相同；当遇到不同的字符时，返回差别。

int sortcmp(char **p, char **q)

{   

   return wordncmp(*p, *q);

}

char *skip(char *p, int n)

{   for ( ; n > 0; p++)

   {

        if (*p == 0)

            n--;

   }    

   return p;

}

小结：本章简单介绍的一些技巧：

字符串的数据结构

散列：速度快且易于实现

平衡树：最坏情况下也具有最好性能