Python.use(better, follow=”K&R”) # for novice 《記事一覧》 改訂♪2008/09/25《承前》

最初に、項目をひとつも含まない場合から始めます。ただし、以下の単体テストでは、その動作を確認するために、K&R と違って hashsize=5 に設定しています。>>> p = Htable() >>> p Htable([None, None, None, None, None])生成したハッシュ表 Htable() が保…

《関連記事》__str__ K&R には、ハッシュ表を出力する事例はありません。そこで、名前/置換テキストを括弧で括ったリストとして表示させます。class Nlist: def __repr__(self): s = "" e = self while e: s += "%r: %r, "%(e.name, e.defn) e = e.next retu…

Python.use(better, follow=”K&R”) # for novice 《記事一覧》 改訂♪2008/09/25《承前》

----------------------------------------------K&R, p.144 >>---- struct nlist { /* table entry: */ struct nlist *next; /* next entry in chain */ char *name; /* defined name */ char *defn: /* replacement text */ };#define HASHSIZE 101 static…

----------------------------------------------K&R, p.145 >>---- /* install: put (name, defn) in hashtab */ struct nlist *install(char *name, char *defn) { struct nlist *np; unsigned hashval; if )((np = lookup(name))( == NULL) { /* not foun…

----------------------------------------------K&R, p.145 >>---- /* lookup: look for s in hashtable */ struct nlist *lookup(char *s) { struct nlist *np; for (np = hashtab[hash(s)]; np != NULL; np = np->next) if (strcmp(s, np->name) == 0) re…

----------------------------------------------K&R, p.144 >>---- /* hash: form hash value for string s */ unsigned hash(char *s) { unsigned hashval; for (hashval = 0; *s != '\0'; s++) hashval = *s + 31 * hashval; return hashval % HASHSIZE; …

K&R; 6.6 Table Lookup では、自己参照的構造体となる連結リストを要素に持つハッシュ表〔hash table〕を使った事例が紹介されています。 【K&R, p.144】"An array element points to the beginning of a linked list of blocks describing names that have …

Python.use(better, follow=”K&R”) # for novice 《記事一覧》 改訂♪2008/09/23《承前》

こんな症状を抱えているなら (@.@) ・配列の添字に数値以外を使いたい ・配列の中に任意のオブジェクトを混在させたい 【効能】添字を指定したり、要素を格納するときに、自由度が高まる 【副作用】辞書のないプログラミングなんて… 《ひよ子のきもち♪2007/1…

K&R で紹介された二分木を再構成して、組み込み型 dict と同等に扱えるようにすると、利用者定義のクラスと組み込み型との間に「シームレス」な関係を維持できます。 今回は、K&R で紹介されたハッシュ探索を使って、組み込み型 dict と同等の機能を実現しま…

K&R で紹介されたハッシュ表〔hash table〕は、言語処理系の記号表を管理するのに便利な機能を提供します。一様なハッシュ関数が得られるなら、ハッシュ値を添字とする配列の要素を参照して、二分木より高速なアクセスが可能です。辞書 dict は、配列にはな…

Python.use(better, follow=”K&R”) # for novice 《記事一覧》 ハッシュ表と辞書 《著》本間りす、森こねこ 《監修》小泉ひよ子とタマゴ倶楽部改訂♪2008/09/23Ｃ言語のバイブルとされる K&R では、ハッシュ探索を使った事例を紹介しています。Python の世界…