今度は衝突した場合に連結リストで対処するのではなく再ハッシュ値を求めてそこに要素を配置する方法。ここでは再ハッシュの手順を以下のようにする。 h1(x) = (h(x) + k) mod B ※Bは要素の個数例 キー ハッシュ値 a 1 b 5 c 8 d 5 e 6 f 6 上記の要素を配置…

ここから探索の勉強 チェイン法はキーのハッシュを添字として配列に追加していくのだけど、キーの衝突(同じハッシュ値)が起きた場合に、配列要素のnextポインタに同じハッシュ値を持つ要素をつなぐ方法。 例：配列の要素が連結リストになっている 添字 一つ…

リストの最後は循環リスト その名のとおり循環します。最後の要素の次が先頭要素になります。 このリストも必ず空き要素headが一つ存在する。 #include <stdio.h> #include <stdlib.h> typedef struct CELL { struct CELL *next; int value; } Cell; Cell *head; /* 循環リスト</stdlib.h></stdio.h>…

次は双方向リストのプログラム 次の要素を示すnext変数の他に前の要素をしめすprev変数も構造体に追加している。 あとは先頭要素としてheadをグローバル変数として宣言して初期化時に next、prevそれぞれ自分のアドレスを代入する。headは今回はポインタでは…

続いて連結リストのCプログラムを書いてみる 要素は構造体で表現していてそのなかのnext変数が次の要素のポインタになっている。 追加、削除ではそれぞれ指定された要素をnextポインタを利用して探す。 連結リストの先頭要素を示すグローバル変数を*rootとし…

アルゴリズムとデータ構造の勉強を始める。 勉強中のC言語を使えばどちらも上達できると思う。 教科書にしているのはこの本。定本 Cプログラマのためのアルゴリズムとデータ構造 (SOFTBANK BOOKS)作者: 近藤嘉雪出版社/メーカー: ソフトバンククリエイティブ…

サンプル(多次元配列) #include <stdio.h> #define Number(arr) ((int)(sizeof(arr)/sizeof(arr[0]))) /* UTF-8の漢字は３バイト */ char a[][20] = { "無印良品", "無印良品物語", "無印健康良品"}; char *b[] = { "無印良品", "無印良品物語", "無印健康良品", NULL</stdio.h>…

サンプル1（ポインタ演算） #include <stdio.h> int main(void) { int hoge; int *hoge_p; hoge_p = &hoge; printf("hoge_p...%p\n", hoge_p); /* hoge_pに１を加算する */ hoge_p++; printf("hoge_p...%p\n", hoge_p); /* hoge_pに３を加算して表示 */ printf("hoge_</stdio.h>…

C言語ポインタの整理 サンプル1(ポインタと配列） #include <stdio.h> int main(void) { char abc[] = "abc"; char *p = abc; int i; printf("addr of abc : %p : %s\n", abc, abc); printf("p=%p : &p=%p : %s\n", p, &p, p); for (i=0; *p; ++p, ++i) { printf(" p </stdio.h>…

externについて整理する externが着いた変数は、変数の型は認識されるが変数のための領域はメモリ上に確保されない。他のコンパイル単位で確保されているはずの領域を共有する。他のコンパイル単位にある関数もexternを付けてプロトタイプ宣言することで呼び…

動的記憶領域のまとめ 解放した領域にまだ文字列が残る場合の例 #include <stdio.h> #include <string.h> #include <stdlib.h> char *stralloc(const char *str) { char *mem; mem = malloc(strlen(str) + 1); if (mem != NULL) { strcpy(mem, str); } return mem; } int main(void) { cha</stdlib.h></string.h></stdio.h>…