K&R 习题6-3

**

K&R 习题6-3

**

• 编写一个交叉引用程序，打印文档中所有单词的列表，并且每个单词还有一个列表，记录出现过该单词的行号。对the、and等非实义单词不予考虑。

测速数据：Our current preoccupation with zombies and vampires is easy to explain. They’re two sides of the same coin, addressing our fascination with sex, death and food. They’re both undead, they both feed on us, they both pass on some kind of plague and they can both be killed with specialist techniques – a stake through the heart or a disembraining. But they seem to have become polarised. Vampires are the undead of choice for girls, and zombies for boys. Vampires are cool, aloof, beautiful, brooding creatures of the night. Typical moody teenage boys, basically. Zombies are dumb, brutal, ugly and mindlessly violent. Which makes them also like typical teenage boys, I suppose.
测速结果：

#include <locale.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXLINE 1024
#define MAXNUM 300
#define TRUE 1
#define FALSE 0

struct tnode
{
    char *word;
    int line[MAXNUM];
    int row[MAXNUM];
    int count;
    struct tnode *left;
    struct tnode *right;
}; /*二叉树节点*/

struct tnode *talloc(void);                                       /*在内存中分配一个二叉树节点*/
char *strcop(char *);                                             /*在内存中分配字符串，并将变量名拷贝进去，赋值给链表中的 char *v */
struct tnode *addtree(struct tnode *, char *, int line, int row); /*增加二叉树节点*/
void treeprint(struct tnode *);                                   /*打印二叉树*/
struct tnode *root[52];                                           /*字母表数组 按首字母小写然后大写排列，如aAbBcC...*/
void word_analysis(char *, char *, int);                          /*单词拆分并加入二叉树*/
int isword(char *);                                               /*判断是否为一个字母组成的单词，并且不是非实义单词，符合条件返回TRUE，否则返回FALSE*/

int main()
{
    static char buffer[MAXLINE] = {0};
    int line = 0;
    int i;

    char *delims = " \t\n\r\a\f\v!\"%^&*()_=+{}[]\\|/,.<>:;#~?";
    setlocale(LC_ALL, "");
    for (i = 0; i < 52; i++)
        root[i] = NULL;
    while ((line++ < MAXLINE) && (getline(buffer, MAXLINE) != EOF))
    {
        word_analysis(buffer, delims, line);
    }
    wprintf(L"单词                          行号                列号    \n");
    for (i = 0; i < 52; i++)
        treeprint(root[i]);
}

int getline(char s[], int lim)
{
    int c, i;
    i = 0;
    while (--lim > 0 && (c = getchar()) != EOF && c != '\n')
        s[i++] = c;
    if (c == '\n')
        s[i++] = c;
    s[i] = '\0';
    return c;
}

void word_analysis(char *buff, char *delims, int line)
{
    char *ptr_start, *ptr_end;
    int found, row, k, n, c, len;
    char word[100];
    ptr_start = ptr_end = buff;
    len = strlen(delims);
    row = 0;
    while (((*ptr_end) != EOF) && ((*ptr_end) != '\n'))
    {
        k = found = 0;
        while ((k < len) && (found == 0))
        {
            if ((*ptr_end) == delims[k++])
            {
                n = 0;
                while (ptr_start < ptr_end)
                {
                    word[n++] = *(ptr_start++);
                }
                ptr_start = ptr_end + 1;
                word[n] = '\0';
                found = 1;
                row++;
                if (isword(word))
                {
                    c = word[0];
                    if (c >= 'a' && c <= 'z')
                    {
                        c = c - 'a';
                        c *= 2;
                    }
                    else if (c >= 'A' && c <= 'Z')
                    {
                        c = c - 'A';
                        c = c * 2 + 1;
                    }
                    root[c] = addtree(root[c], word, line, row);
                }
                break;
            }
        }
        ptr_end++;
    }
}

int isword(char *word)
{
    char *list[] =
        {
            "a",
            "an",
            "and",
            "be",
            "but",
            "by",
            "he",
            "I",
            "is",
            "it",
            "off",
            "on",
            "she",
            "so",
            "the",
            "they",
            "you"};
    char c, *pword = word;
    size_t n = sizeof(list) / sizeof(list[0]);
    int i = n;
    if ((*word) == '\0')
        return FALSE;
    while ((c = *(pword++)) != '\0')
    {
        if (c >= 'a' && c <= 'z')
            ;
        else if (c >= 'A' && c <= 'Z')
            ;
        else
            return FALSE;
    }
    while (--i >= 0)
    {
        if ((strcmp(list[i], word)) == 0)
            return FALSE;
    }
    return TRUE;
}

struct tnode *addtree(struct tnode *p, char *w, int line, int row)
{
    int cound, i;
    if (p == NULL)
    {
        p = talloc();
        p->word = strcop(w);
        p->count = 1;
        p->line[0] = line;
        p->row[0] = row;
        p->left = p->right = NULL;
    }
    else if ((cound = strcmp(w, p->word)) == 0)
    {
        p->count++;
        i = p->count - 1;
        p->line[i] = line;
        p->row[i] = row;
    }
    else if (cound < 0)
        p->left = addtree(p->left, w, line, row);
    else
        p->right = addtree(p->right, w, line, row);
    return p;
}

void treeprint(struct tnode *p)
{
    int i = 0;
    if (p != NULL)
    {
        treeprint(p->left);
        printf("%-20s          ", p->word);
        for (; i < p->count; i++)
            printf("        Line[%-3d]    Row[%-3d]", p->line[i], p->row[i]);
        printf("\n");
        treeprint(p->right);
    }
}

struct tnode *talloc()
{
    return (struct tnode *)malloc(sizeof(struct tnode));
}

char *strcop(char *s)
{
    char *p;
    p = (char *)malloc(strlen(s) + 1);
    if (p != NULL)
        strcpy(p, s);
    return p;
}