c - K&R第6-6节查表: Overwriting when hashvalues are the same

Question

我无法理解这一点。

首先我想指出，当我从输入命令行声明这一点时:

#define Please 100
#define routine 120

因为“Please”和“routine”具有相同的哈希值。我的程序覆盖了哈希表值，从我的输入控制台输入“请”将得到 120 的值。我如何解决覆盖问题，或者它只是本书的一部分？

其次，这部分

struct nlist *lookup (char *s)
{
struct nlist *np;
for (np = hashtab[hash(s)]; np != NULL; np = np->next)
    return np;
return NULL;
}

特别是在for循环语句中。我的问题是 for 循环如何重复多次？因为我看到的只是每个 hashtab[hash(s)] 值的一个实例。

无论如何，这是完整的代码。您可以使用 gcc 运行它。 Undef() 工作得很好。

#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>
#include <string.h>
//#include <vld.h>
#define MAXWORD 100

struct nlist {
    struct nlist *next;
    char *name;
    char *defn;
};

void error(int, char *);
int getca(void); // getch()
void getdef(void);
int getword(char *, int);
struct nlist *install(char *, char *);
struct nlist *lookup(char *);
void skipblanks(void);
void undef(char *);
void ungetca(int); // ungetch()
void ungets(const char *);

#define HASHSIZE 101
unsigned hash(char *);
static struct nlist *hashtab[HASHSIZE];
char *strdupli (char *); //strdup() function

int main(void)
{
char w[MAXWORD];
struct nlist *p;

while (getword(w, MAXWORD) != EOF)
    if (strcmp(w, "#") == 0) /* beginning of direct */
        getdef();
    else if (!isalpha(w[0]))
        printf("%s", w);    /* cannot be defined */
    else if ((p = lookup(w)) == NULL)
        printf("%s", w);   /* not defined */
    else
        ungets(p->defn); /* push definition */
return 0;
}

void ungets(const char *s)
{
size_t i = strlen(s);
while(i > 0)
    ungetca(s[--i]);
}

void getdef(void)
{
    int i;
    char def[MAXWORD], dir[MAXWORD], name[MAXWORD];
skipblanks();
if (!isalpha(getword(dir, MAXWORD)))
    error (dir[0],
    "getdef: expecting a directive after #");
else if (strcmp(dir, "define") == 0) {
    skipblanks();
    if (!isalpha(getword(name, MAXWORD)))
        error(name[0],
        "getdef: non-alpha - name expected");
    else {
        skipblanks();
        for(i = 0; i < MAXWORD - 1; i++)
            if((def[i] = getca()) == EOF ||
                                    def[i] == '\n')
                break;  /*end of definition*/
        def[i] = '\0';
        if(i <= 0)      /* no definition */
            error('\n', "getdef: incomplete define");
        else            /* install definition */
            install (name, def);
    }
} else if (strcmp(dir, "undef") == 0) {
    skipblanks();
    if(!isalpha(getword(name, MAXWORD)))
        error(name[0], "getdef: non-alpha in undef");
    else
        undef(name);
} else
    error(dir[0],
    "getdef: expecting a directive after #");
}



struct nlist *install(char *name, char *defn)
{
struct nlist *np;
unsigned hashval;
if ((np = lookup(name)) == NULL) { /* not found */
    np = (struct nlist *) malloc(sizeof(*np));
    if (np == NULL || (np->name = strdupli(name)) == NULL)
        return NULL;
    hashval = hash(name);
    np->next = hashtab[hashval];
    hashtab[hashval] = np;
} else {/* already there */
    free((void *) np->defn); /*free previous defn */
}
if ((np->defn = strdupli(defn)) == NULL)
    return NULL;
return np;
 }

void undef(char *s)
{
int h;
struct nlist *prev, *np;

prev = NULL;
h = hash(s);
for(np = hashtab[h]; np != NULL; np = np->next) {
    if(strcmp(s, np->name)==0)
        break;
    prev = np;
}
if (np != NULL) {
    if (prev == NULL)
        hashtab[h] = np->next;
    else
        prev->next = np->next;
    free((void *) np->name);
    free((void *) np->defn);
    free((void *) np);
}
}

unsigned hash(char *s)
{
unsigned hashval;
for (hashval = 0; *s != '\0'; s++)
    hashval = *s + 31 * hashval;
return hashval % HASHSIZE;
}

struct nlist *lookup (char *s)
{
struct nlist *np;
for (np = hashtab[hash(s)]; np != NULL; np = np->next)
    return np;
return NULL;
}

int getword(char *word, int lim)
{
    int c, getca(void);
    void ungetca(int);
    char *w = word;

    while(isspace(c = getca()))
        ;
    if(c != EOF)
        *w++ = c;
    if(!isalpha(c)) {
        *w = '\0';
    return c;
}
    for( ; --lim > 0; w++)
        if(!isalnum(*w = getca())) {
            ungetca(*w);
            break;
        }
    *w = '\0';
    return word[0];
}

void error(int c, char *s)
{
    printf("error: %s\n", s);
        while(c != EOF && c != '\n')
    c = getca();
}

void skipblanks (void)
{
    int c;
while ((c = getca()) == ' ' || c == '\t')
;
ungetca(c);
}

void strcopy (char *, const char *);
char *strdupli (char *s) /* make a duplicate of s */
{
    char *p;
    p = (char *) malloc (strlen(s) + 1);
    if (p != NULL)
        strcopy(p, s);
    return p;
}

void strcopy (char *s, const char *t)
{
        while ((*s++ = *t++) != '\0')
        ;
}

#define BUFSIZE 100
char buf[BUFSIZE]; /* buffer for ungetch */
int bufp = 0; /* next free position in buf */
int getca(void) /* get a (possibly pushed-back) character */
{
    return (bufp > 0) ? buf[--bufp] : getchar();
}

void ungetca(int c) /* push character back on input */
{
    if (bufp >= BUFSIZE)
       printf("ungetch: too many characters\n");
    else
    buf[bufp++] = c;
}

Answer 1

这是一个示例，假设其他所有内容都与 K&R 的示例相同:

定义一个打印哈希表的函数:

void printTable(struct nlist* ptable[])
{
    for (int i=0; i<HASHSIZE; i++)
        if (ptable[i] != NULL)
        {
            printf("Hash table index %d content: \n", i);
            int j = 0;
            struct nlist *plist;
            for (plist = ptable[i]; plist != NULL; plist = plist->next)
                printf("\tList nr %d: name: '%s', defn: '%s'\n", j++, plist->name, plist->defn);
        }
}

插入两个冲突的定义:

install("Please", "bla");
install("routine", "blabla");

并打印结果:

printTable(hashtab);

给予:

Hash table index 90 content: 
    List nr 0: name: 'routine', defn: 'blabla'
    List nr 1: name: 'Please', defn: 'bla'