C＃によるアルゴリズムとデータ構造

４．探索
探索とは
（１）目的とする値を持った要素を探し出すこと。
（２）探し出す値の項目をキー（key）と呼ぶ。
（３）探索だけでなく，挿入・削除が必要な場合，
これらの処理のコストも考慮して
アルゴリズムを選択すること。
４．探索
４．１単純線形探索とは
（１）配列は，
要素が順に並んでいるので，
３を探索（探索成功）
0
1
2
3
4
5
目的とするキー値の
要素に出会うまで，
８
４
５
３
２
６
８
４
５
３
２
６
配列添え字を
カウントアップすればよい。
８
４
５
３
２
６
８
４
５
３
２
６
探索成功
探索失敗の場合
７を探索（探索失敗）
（２）探索しようとするキーが
配列に入っているとは
限らないので，
配列添え字の最大値を
監視しておき，
添え字の最大値を超えたら，
探索失敗として
終了させる必要がある。
0
1
2
3
4
5
８
４
５
３
２
６
８
４
５
３
２
６
８
４
５
３
２
６
８
４
５
３
２
６
８
４
５
３
２
６
８
４
５
３
２
６
８
４
５
３
２
６
探索失敗
プログラム表現
［プログラム表現］
private int 探索(int V)
{
for(int i=0; i < myArray.Length; i++)
if(V == myArray[i]) return i;
return -1;
}
ここで，条件の判定が，For文での添え字の判定，
要素の値判定の２箇所にあることに注意。
［はっきりさせるに］
int R = -1;
int i = 0;
while( i < myArray.Length)
｛
if(V == myArray[i]) { R = i; break; }
i++;
}
return R;
判定の回数
したがって，探索失敗のときの判定回数は，
N = myArray.Lengthとして，
２×Ｎ＋１
先頭で成功するときは，先頭の判定だけだから，２回。
今，配列に含まれているＮ個のデータを探索しようとすると，
探索回数は，
２＋４＋６＋・・・＋２Ｎ＝２Ｎ（Ｎ＋１）/２＝Ｎ（Ｎ＋１）
１個当たり，平均して
平均判定回数＝Ｎ（Ｎ＋１）／Ｎ＝Ｎ＋１
となるが，要素数Ｎが大きくなると，
ほぼＮに比例するものと考えても構わない。
［フォーム定義］
Name:textBox1
Name:listBox1
確認用プログラム例
Name:button1
プログラム
private int[] myArray= new int[]{7,3,4,5,1,9,8,6};
private void Form1_Load(object sender, System.EventArgs e)
{
listBox1.Items.Clear();
for(int I = 0;I < myArray.Length; i++)
listBox1.Items.Add(myArray[i].ToString());
}
private int 探索(int V)
{
int R = -1;
for(int i=0; i< myArray.Length; i++)
if(V == myArray[i]) { R = i; break; }
return R;
}
private void button1_Click(object sender, System.EventArgs e)
{
int R = 探索(int.Parse(textBox1.Text));
listBox1.SelectedIndex = R;
if(R < 0) MessageBox.Show ("探索できませんでした");
}
４．２番兵法
３を探索（探索成功）
７を探索（探索失敗）
0
1
2
3
4
5
番兵
0
1
2
3
4
5 番兵
８
４
５
３
２
６
３
８
４
５
３
２
６
３
８
４
５
３
２
６
３
８
４
５
３
２
６
３
８
４
５
３
２
６
３
８
４
５
３
２
６
３
８
４
５
３
２
６
３
８
４
５
３
２
６
３
８
４
５
３
２
６
３
８
４
５
３
２
６
３
８
４
５
３
２
６
３
探索成功
探索失敗
４．３２分探索法
３３を探索（探索成功）
0
1
2
3
4
２
４
８１１１４１５１８２２２４２５３３４２４６５３５３
Left
２
5
6
7
8
9
10
11
12
13
PC
Right
33 > 22 → Left = PC+1
４
14
８１１１４１５１８２２２４２５３３４２４６５３５３
対象外
Left
PC
Right
33 < 42 → Right = PC－1
２
４
８１１１４１５１８２２２４２５３３４２４６５３５３
対象外
Left PC Right
対象外
33 > 25 → Left = PC+1
２
４
８１１１４１５１８２２２４２５３３４２４６５３５３
対象外
対象外
Left PC Right
33 = 33 → 探索成功
不成功の場合
３６を探索（探索不成功）
２
４
８１１１４１５１８２２２４２５３３４２４６５３５３
対象外
対象外
Left PC Right
36 > 33 → Left = PC+1
２
４
８１１１４１５１８２２２４２５３３４２４６５３５３
対象外
対象外
Right Left
LeftとRightが逆転→失敗
３０を探索（探索不成功）
２
４
８１１１４１５１８２２２４２５３３４２４６５３５３
対象外
対象外
Left PC Right
30 < 33 → Right = PC－1
２
４
８１１１４１５１８２２２４２５３３４２４６５３５３
対象外
対象外
Right Left
LeftとRightが逆転→失敗
［フォーム定義］
Name:textBox1
確認用プログラム例
Name:button1
Name:button2
Name:listBox1
Name:label2
プログラム（領域宣言と探索処理）
private int[] myArray= new int[]{4,8,20,28,30,35,40,59,65,75,95};
private int Mode;
private int MP1, MP2, MV;
private int 探索(int V)
{
int p1=0; int p2=myArray.Length-1; int p;
while(p1<=p2)
{
p=(p1+p2)/2;
if (myArray[p]==V) return p;
else if(myArray[p]<V) p1 = p + 1;
else
p2 = p - 1;
}
return -1;
}
プログラム
private void button1_Click(object sender, System.EventArgs e)
{
int R=探索(int.Parse(textBox1.Text));
listBox1.SelectedIndex=R;
if (R<0) MessageBox.Show("探索失敗");
}
private void Form1_Load(object sender, System.EventArgs e)
{
listBox1.Items.Clear();
for(int i=0; i<myArray.Length; i++)
listBox1.Items.Add(myArray[i].ToString());
Mode=0;
}
プログラム（逐次的に観察するための処理）
private void button2_Click(object sender, System.EventArgs e)
{
int p, CV ; string Cmp, R;
if (Mode==0) {
MP1=0; MP2=myArray.Length-1;
MV = int.Parse(textBox1.Text);
Mode=1;
}
p=(MP1 + MP2)/2; CV=myArray[p];
if (CV == MV){ Cmp=" = "; R="検索成功"; Mode=0; }
else {
if(CV < MV){ Cmp=" < "; MP1=p+1;}
else
{ Cmp=" > "; MP2=p-1;}
R=””; if (MP2<MP1) { R=“検索失敗”; Mode=0;}
}
label2.Text=CV.ToString() + Cmp + MV.ToString() + " " + R;
listBox1.SelectedIndex=p;
if(R != "") {
MessageBox.Show("探索がおわりました");
listBox1.SelectedIndex=-1;
}
}
４．４計算量（complexity）
■時間計算量（time complexity）
実行に要する時間の評価
■領域計算量（space complexity）
どのくらいの記憶域が必要かを評価
両者のバランスを考える必要がある。
線形探索の時間計算量
I = 0;
while ( I < N){
if (A[I] == key)
return I;
I++;
}
return -1;
//
//
//
//
//
(1)
(2)
(3)
(4)
(5)
実行回数＝１
実行回数＝平均Ｎ／２
実行回数＝平均Ｎ／２
実行回数＝１
実行回数＝平均Ｎ／２
// (6) 実行回数＝1
実行回数がＮに比例するとき，
Ｏ（Ｎ）
と記述し，「Ｎのオーダ(order)」あるいは
「オーダＮ（Order N)」等という。
オーダは大雑把な計算量
［関係式］
O( f ( N )) + O( g ( N ))＝O( max( f( N ), g( N )))
すなわち，計算量はより大きい方の計算量に支配される。
線形探索の計算量は，
O(1) + O(N) + O(N) + O(1) + O(N) + O(1)
= O(N)
２分探索法の時間計算量
PL=0;
PR=N - 1;
while (PL <= PR){
PC = (PL + PR) / 2
if (A[PC] == key)
return PC;
else if (A[PC] < key)
PL = PC + 1;
else
PR = PC - 1;
}
return -1;
//
//
//
//
//
//
//
//
//
//
( 1)
( 2)
( 3)
( 4)
( 5)
( 6)
( 7)
( 8)
( 9)
(10)
実行回数＝１
実行回数＝１
実行回数＝log N
実行回数＝log N
実行回数＝log N
実行回数＝１
実行回数＝log N
実行回数＝(log N)/2
実行回数＝(log N)/2
実行回数＝(log N)/2
// (11) 実行回数＝1
実行回数＝log N，実行回数＝(log N)/2両者ともにlog Nに
比例する計算回数であるためO(log N)と記述される。
４．５ハッシュ法（hashing）
２分探索法を使うと，効率のよい探索ができるが。。。
ソート済みでなければならない。
そこでソート済み配列へのデータの挿入を考えてみると
４０
挿入
１８１９２７３３４２４７５０６４
移動
１８１９２７３３４０４２４７５０６４
配列をずらす必要がある。
配列をずらして挿入
private void 挿入(int V)
{
int i;
if(maxPointer >= MAXARRAY)
MessageBox.Show("データが入りません");
else
{
bool flag=true; int k = maxPointer;
for(i = 0; i < maxPointer;i++)
{
if(V == myArray[i])
{ flag = false; break;}
else if(V < myArray[i]) { k = i;
break;}
}
if(flag)
{
for(i = maxPointer;i >= k; i--) myArray[i + 1]=myArray[i];
myArray[k] = V; maxPointer++;
}
}
}
ハッシュ法（hashing）とは
ハッシュ法：
配列に格納するキーをもとに，簡単な計算で
格納する位置（配列の添え字）を計算する方法。
■配列の各要素をバケット（bucket）と呼ぶ。
■ハッシュ値を計算する関数を
ハッシュ関数（hashing function）と呼ぶ。
ハッシュ法（hashing）とは
［例］キーの値を１３で割った余りをハッシュ値とする場合
ハッシュ値５６１７３８１１１２
キー値１８１９２７３３４２４７５０６４
配列
－２７－４２－１８１９３３４７－－５０６４
０１２３４５６７８９１０１１１２
ハッシュ値＝格納位置
キーの挿入
キーの挿入
［例］キー値３５（１３の剰余＝９）を挿入
ハッシュ値
挿入前
０１２３４５６７８９１０１１１２
－２７－４２－１８１９３３４７－－５０６４
３５
挿入後
－２７－４２－１８１９３３４７３５－５０６４
キーの衝突
衝突［例］キー値３２（１３の剰余＝６）を挿入
キー値
０１２３４５６７８９１０１１１２
－２７－４２－１８１９３３４７－－５０６４
すでに埋まっている!!
３２
キー衝突の回避
■チェイン法
同一値をもつ要素を線形リストで管理する方法
■オープンアドレス法
空きバケットを見つけるまでハッシュを繰り返す方法
チェイン法
各バケットに，
キー値を持つノードを連結した
リストへのポインタを格納する方法
０
１
２７
２
３
４２
４
５
６
７
８
１８１９３３４７
９１０１１１２
５０６４
チェイン法での挿入
線形リストとして挿入するので
衝突することはない。
０
１
２７
２
３
４２
４
５
６
７
８
１８３２３３４７
１９
削除も線形リストの削除として行われる。
９１０１１１２
５０６４
プログラム
［フォーム定義］
Name:
textBox1
Name:
listBox1
Name:button1
Name:button2
Name:button3
Name:button4
Name:button5
プログラム ①領域宣言とバケット領域の初期化
public struct NumberListData
{
public int Data;
public int Pointer;
}
public const int AREASIZE = 50;
public const int HASHSIZE = 16;
public int ErasePointer;
public static NumberListData[]
NumberList=new NumberListData[AREASIZE];
public int[] Bucket=new int[HASHSIZE];
public void BucketInitialize()
{
for(int i=0;i<Bucket.Length;i++) Bucket[i]=-1;
}
プログラム ②領域管理
public void AreaInitialize()
{
int i;
for(i=0;i<NumberList.Length;i++) NumberList[i].Pointer=i+1;
NumberList[NumberList.Length-1].Pointer=-1;
ErasePointer=0;
}
public int GetArea()
{
if (ErasePointer<0) return -1;
int P=ErasePointer;
ErasePointer=NumberList[ErasePointer].Pointer;
return P;
}
public void FreeArea(int P)
{
NumberList[P].Pointer=ErasePointer;
ErasePointer=P;
}
プログラム ③線形リスト処理
public int replaca(int P, int A)
{
NumberList[P].Data=A; return P; }
public int replacd(int P, int A)
{ NumberList[P].Pointer=A; return A;}
public int car(int P)
{ return NumberList[P].Data;}
public int cdr(int P)
{ return NumberList[P].Pointer;}
public int cons(int A, int B)
{
int P=GetArea(); if(P<0) return -1;
NumberList[P].Data=A; NumberList[P].Pointer=B;
return P;
}
プログラム ④Form1_Load，ポインタ部の表示
private void Form1_Load(object sender, System.EventArgs e)
{
BucketInitialize(); AreaInitialize(); ポインタ部の表示();
}
private void ポインタ部の表示()
{
listBox1.Items.Clear();
listBox1.Items.Add("Erase Pointer=" + ErasePointer.ToString());
listBox1.Items.Add("(ポインタ部のみ)"); int i=ErasePointer;
while(i>=0)
{ i=cdr(i);listBox1.Items.Add(i.ToString());}
}
プログラム ⑤領域管理のテスト
private void button1_Click(object sender, System.EventArgs e)
{
int P=GetArea();
string PS=P.ToString();textBox1.Text=PS;
ポインタ部の表示();
MessageBox.Show (PS);
}
private void button2_Click(object sender, System.EventArgs e)
{
FreeArea(int.Parse(textBox1.Text));
ポインタ部の表示();
}
プログラム ⑥ハッシュ表示
private void ハッシュ表示()
{
string S; int P;
listBox1.Items.Clear();
for(int i=0;i<Bucket.Length;i++)
{
S=i.ToString()+" "; P=Bucket[i];
if(P>=0)
{
while(P>=0)
{
S += " " + car(P).ToString();
P=cdr(P);
}
listBox1.Items.Add(S);
}
else listBox1.Items.Add(S+"(空)");
}
}
プログラム
⑦線形リストでのキー探索，ハッシュ設定
private int SearchKey(int Key, int P)
{
int PP=P;
while(PP>=0)
{
if(car(PP)==Key) return PP;
PP=cdr(PP);
}
return -1;
}
private void ハッシュ設定(int Key, int Mod)
{
int ID = Key % Mod;
if(SearchKey(Key, Bucket[ID])<0) Bucket[ID]=cons(Key, Bucket[ID]);
}
プログラム
⑧button3_Click，ハッシュ探索，button4_Click
private void button3_Click(object sender, System.EventArgs e)
{
int Mod = Bucket.Length;
int Key = int.Parse(textBox1.Text) ;
ハッシュ設定(Key, Mod);
ハッシュ表示();
}
private int ハッシュ探索(int Key, int Mod)
{
int ID = Key % Mod;
return SearchKey(Key, Bucket[ID]);
}
private void button4_Click(object sender, System.EventArgs e)
{
int Mod = Bucket.Length;
int Key = int.Parse(textBox1.Text) ;
int P = ハッシュ探索(Key, Mod);
MessageBox.Show(P.ToString());
}
プログラム
⑨ハッシュ削除，button5_Click
private int ハッシュ削除(int Key, int Mod)
{
int ID = Key % Mod; int Befor = -1; int P = Bucket[ID];
if(P<0) return -1;
while(P >= 0) {
if(car(P) == Key) break;
Befor = P; P = cdr(P);
}
int After = cdr(P); FreeArea(P);
if(Befor < 0) Bucket[ID] = After;
else
replacd(Befor, After);
return After;
}
private void button5_Click(object sender, System.EventArgs e)
{
int Mod = Bucket.Length; int Key = int.Parse(textBox1.Text) ;
int P = ハッシュ削除(Key, Mod);
ハッシュ表示();
}
オープンアドレス法
オープンアドレス法（open addressing）または
クローズドハッシュ法（closed hashing）と呼ばれる。
衝突が発生した際，別のバケットに入れるために
再ハッシュ（rehashing）を行う方法。
キー値
０１２３４５６７８９１０１１１２
－２７－４２－１８１９３３－－－５０６４
３２ → 再ハッシュ
［再ハッシュの方法］
簡単化のためにキー値に１を加えて１３の剰余をとる。
例
０１２３４５６７８９１０１１１２
－２７－４２－１８１９３３－－－５０６４
３２ → 33 mod 13 = 7
－２７－４２－１８１９３３－－－５０６４
３２ → 34 mod 13 =8
－２７－４２－１８１９３３－－－５０６４
３２
削除
削除のときは，削除フラグをバケットに付ける。
ここでは「×」で示す。
０１２３４５６７８９１０１１１２
－２７－４２－ × １９３３－－－５０６４
削除
■１５を探索しようとすると，１５ mod １３＝２
のバケットが空であるので，探索失敗。
要素の探索
■１８を探索しようとすると，１８ mod １３＝５
のパケットが削除済みなので，再ハッシュ，
更に，キー値が異なるので，再ハッシュ，
探索値が入っているので，探索成功。
０１２３４５６７８９１０１１１２
－２７－４２－ × １９１８３４－－５０６４
再ハッシュ再ハッシュ
プログラム例
［文字列のハッシュ値の計算］
（１）文字列内のChar値を加算し，
その合計値の１６の剰余をハッシュ値とする。
ただし，加算の際，１６の剰余をとったものを
加算しても同じ値が得られるので，
剰余を加算する。
（２）バケットサイズは，３２としておく。
（３）削除マークは“\n”とする。
（４）未登録バケットは，“\r”とする。
フォーム
Name:
textBox1
Name:
listBox1
プログラム例
Name:button1
Name:button2
Name:button3
プログラム例 ①データ宣言，ハッシュ登録処理
private const int HASHVALUE=16;
private string[] Bucket = new string[HASHVALUE*2];
private void ハッシュ登録(string Str, int HashMod)
{
int ID=ハッシュ値(Str, HashMod);
while(Bucket[ID]!="\r" && Bucket[ID]!="\n" && ID<Bucket.Length)
{
if(Str==Bucket[ID])
{
MessageBox.Show("同一文字列が登録されています");
return;
}
ID++;
}
if (ID>=Bucket.Length)MessageBox.Show("登録できません");
else
Bucket[ID]=Str;
}
プログラム例 ②ハッシュ探索，ハッシュ削除
private int ハッシュ探索(string Str, int HashMod)
{
int ID=ハッシュ値(Str, HashMod);
while(Bucket[ID]!="\r" && ID<Bucket.Length)
{
if(Str==Bucket[ID])
return ID;
ID++;
}
return -1;
}
private void ハッシュ削除(string Str, int HashMod)
{
int ID = ハッシュ探索(Str , HashMod);
if(ID>=0) Bucket[ID]="\n";
}
プログラム例 ③ハッシュ表示, button1_Click
private void ハッシュ表示()
{
listBox1.Items.Clear();
for(int i=0;i<Bucket.Length;i++)
{
if(Bucket[i]=="\r")
listBox1.Items.Add("----");
else if(Bucket[i]=="\n") listBox1.Items.Add("****");
else
listBox1.Items.Add(Bucket[i]);
}
}
private void button1_Click(object sender, System.EventArgs e)
{
string V = textBox1.Text; ハッシュ登録(V , HASHVALUE);
ハッシュ表示();
}
プログラム例
④ハッシュ値の計算，Form1_Load, button2_Click
private int ハッシュ値(string S, int H)
{
int CH = 0;
for(int i = 0; i < S.Length; i++)
{ CH +=(int) (S[i] % H); CH %= H;
}
return CH;
}
private void Form1_Load(object sender, System.EventArgs e)
{
for(int i=0;i<Bucket.Length;i++) Bucket[i]="\r";
ハッシュ表示();
}
private void button2_Click(object sender, System.EventArgs e)
{
string V = textBox1.Text; int ID = ハッシュ探索(V , HASHVALUE);
listBox1.SelectedIndex = ID;
}
プログラム例
⑤ button3_Click，listBox1_SelectedIndexChanged
private void button3_Click(object sender, System.EventArgs e)
{
string V = textBox1.Text;
ハッシュ削除(V , HASHVALUE);
ハッシュ表示();
}
// listBox1が選択されたら，その文字列をtextBox1に移す。
private void listBox1_SelectedIndexChanged
(object sender, System.EventArgs e)
{
textBox1.Text=listBox1.Text;}

Download Report