补拙·启源

符号表

符号表在概念上与字典类似，它在称为键的标识与一个关联值（一般有更大、更复杂的结构）之间形成映射。

散列表

散列将键映射到整型，然后使用这些整型快速指明键在数组中的位置。将键转化为在一个固定范围内查找整数的函数称为散列函数。对应特定键的散列函数值称为散列值。使用这种方法的符号表称为散列表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

#ifndef _symtab_h
#define _symtab_h

char undefined_object[] = "UNDEFINED";
//extern char undefined_object[];
#define UNDEFINED ((void *) undefined_object)

typedef char *string;

typedef struct symtabCDT *symtabADT;

typedef void (* symtabFnT)(string key, void *value, void *clientData);

symtabADT NewSymbolTable(void);
void FreeSymbolTable(symtabADT table);

void Enter(symtabADT table, string key, void *value);
void *Lookup(symtabADT table, string key);

void MapSymbolTable(symtabFnT fn, symtabADT table, void *clientData);
#endif

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

#include <stdlib.h>
#include <string.h>
#include "symtab.h"

#define NBuckets 101

typedef struct cellT{
    string key;
    void *value;
    struct cellT *link;
} cellT;

struct symtabCDT{
    cellT *buckets[NBuckets];
};

static void FreeBucketChain(cellT *cp);
static cellT *FindCell(cellT *cp, string key);
static int Hash(string key, int nBuckets);

symtabADT NewSymbolTable(void){
    symtabADT table;
    int i;

    table = malloc(sizeof (*table));
    for(i=0; i<NBuckets; i++){
        table->buckets[i] = NULL;
    }

    return (table);
}
void FreeSymbolTable(symtabADT table){
    int i;

    for(i=0; i<NBuckets; i++){
        FreeBucketChain(table->buckets[i]);
    }
    free(table);
}

void Enter(symtabADT table, string key, void *value){
    int bucket;
    cellT *cp;
    string newkey;

    bucket = Hash(key, NBuckets);
    cp = FindCell(table->buckets[bucket], key);
    if(cp == NULL){
        newkey = malloc(strlen(key)+1);
        strcpy(newkey, key);
        cp = malloc(sizeof (cellT *));
        cp->key = newkey;
        cp->link = table->buckets[bucket];
        table->buckets[bucket] = cp->link;
    }
    cp->value = value;
}
void *Lookup(symtabADT table, string key){
    int bucket;
    cellT *cp;
    bucket = Hash(key, NBuckets);
    cp = FindCell(table->buckets[bucket], key);
    if(cp == NULL){
        return (UNDEFINED);
    }
    return (cp->value);
}

void MapSymbolTable(symtabFnT fn, symtabADT table, void *clientData){
    int i;
    cellT *cp;

    for(i=0; i<NBuckets; i++){
        for(cp=table->buckets[i]; cp!=NULL; cp=cp->link){
            fn(cp->key, cp->value, clientData);
        }
    }
}

static void FreeBucketChain(cellT *cp){
    cellT *next;
    while(cp != NULL){
        next = cp->link;
        free(cp->key);
        free(cp->value);
        free(cp);
        cp = next;
    }
}

static cellT *FindCell(cellT *cp, string key){
    while(cp!=NULL && strcmp(cp->key, key)!=0){
        cp = cp->link;
    }
    return (cp);
}

#define Multiplier -1664117991L
static int Hash(string key, int nBuckets){
    int i;
    unsigned long hashcode;

    hashcode = 0;
    for(i=0; key[i]!='\0'; i++){
        hashcode = hashcode * Multiplier + key[i];
    }
    return (hashcode % nBuckets);
}

迭代器

迭代器允许客户遍历集合中的值，例如符号表中的键。让NewIterator完成关键的工作，建立其内部结构，使得迭代器包含表中所有键的一个完整列表，具有如下优点：

  1. 能够建立一个完整列表的迭代器实现起来比较简单；
  2. 建立一个列表可以减少为了按照逻辑顺序处理值的必要消耗；
  3. 客户代码中的循环体能够改变迭代器所进行操作的ADT的内容。
1
2
3
4
5
6
7
8
9
10
11
12
13
14

#ifndef _iterator_h
#define _iterator_h

#include<stdlib.h>
#include"symtab.h"

typedef enum{false, true} bool;

typedef struct iteratorCDT *iteratorADT;

iteratorADT NewIterator(symtabADT table);
bool StepIterator(iteratorADT iterator, string *key);
void FreeIterator(iteratorADT iterator);
#endif

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

#include<string.h>
#include"iterator.h"

typedef struct cellT{
    string key;
    struct cellT *link;
} cellT;

struct iteratorCDT{
    cellT *start;
};

static void InsertKey(string key, void *value, void *clientData);

iteratorADT NewIterator(symtabADT table){
    iteratorADT iterator;

    iterator = malloc(sizeof (iteratorADT));
    iterator->start = NULL;
    MapSymbolTable(InsertKey, table, iterator);

    return (iterator);
}

bool StepIterator(iteratorADT iterator, string *key){
    cellT *cp;
    cp = iterator->start;
    if(cp == NULL){
        return (false);
    }
    *key = cp->key;
    iterator->start = cp->link;
    free(cp);
    return (true);
}

void FreeIterator(iteratorADT iterator){
    cellT *cp;
    while((cp=iterator->start) != NULL){
        iterator->start = cp->link;
        free(cp);
    }
    free(iterator);
}

static void InsertKey(string key, void *value, void *clientData){
    iteratorADT iterator;
    cellT *prev, *next, *cp;

    iterator = (iteratorADT)clientData;
    prev = NULL;
    next = iterator->start;

    while(next!=NULL && strcmp(key, next->key)>0){
        prev = next;
        next = next->link;
    }

    cp = malloc(sizeof (cellT));
    cp->key = key;
    cp->link = next;

    if(prev == NULL){
        iterator->start = cp;
    }
    else{
        prev->link = cp;
    }
}

命令分派表

将一个命令名称转换为对应操作的过程称为命令分派（command dispatching）。相比跳跃链表，使用符号表实现命令分派有如下优点：

  1. 分派操作更加高效；
  2. 程序结构更易读懂；
  3. 命令表可以更加容易的扩展。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

#include<stdio.h>
#include<string.h>

typedef char *string;

static void ExecuteCommand(string cmd){
    if(strcmp(cmd, "clear") == 0){
        ClearCmd();
    }
    else if(strcmp(cmd, "run") == 0){
        RumCmd();
    }
    else if(strcmp(cmd, "help") == 0){
        HelpCmd();
    }
    else if(strcmp(cmd, "quit") == 0){
        QuitCmd();
    }
    else{
        printf("Undefined command: %s\n", cmd);
    }
}

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

#include<stdlib.h>
#include<stdio.h>
#include"symtab.h"

typedef void (*commandFnT)(void);

// 函数指针和void *类型不兼容
typedef struct{
    commandFnT fn;
} *commandEntryT;

static void InitCommandTable(void);
static void DefineCommand(string cmd, commandFnT fn);
static void ExecuteCommand(string cmd);

static symtabADT commandTable;

static void InitCommandTable(void){
    commandTable = NewSymbolTable();
    DefineCommand("clear", ClearCmd);
    DefineCommand("run", RunCmd);
    DefineCommand("help", HelpCmd);
    DefineCommand("quit", QuitCmd);
}

static void DefineCommand(string cmd, commandFnT fn){
    commandEntryT entry;

    entry = malloc(sizeof (commandEntryT));
    entry->fn = fn;
    Enter(commandTable, cmd, entry);
}

static void ExecuteCommand(string cmd){
    commandEntryT entry;
    entry = Lookup(commandTable, cmd);
    if(entry == UNDEFINED){
        printf("Undefined command: %s\n", cmd);
        return;
    }
    entry->fn();
}