ヨタの日々

_ 午前

0700 起床 || 走る

0830 プリキュア

1030 おひる

_ 午後

1200 NetBSDほげ

1600 散歩

アジサイ

_ 夜

1900 寝る

2100 飯

2200 探索ほげ

_ ふぁぼったー

50 fav (>'A`)>

_ [アルゴリズム][ディジタル探索]アルゴリズム辞典 - ディジタル探索 (C実装)

/* -------------------------------------------------------------------------
 *  アルゴリズム辞典
 *  島内剛一 野下浩平 伏見正則 有沢誠 浜田穂積
 *
 *  ディジタル探索 pp. 522-523
 * ---------------------------------------------------------------------- */


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

typedef struct node
{
  char key;
  struct node* right;
  struct node* left;
} node;

static node head = { 0x0, NULL, NULL };
static char mask[9] = { 0x00, 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80 };

// 探索
node* search ( char key )
{
    node* np;
    int idx;
    idx = 0;
    np = head.left;
    // キーの idx 行が 1(0) ならば右(左)へ
    while( np != NULL && key != np->key )
    {
      np = ( key & mask[ ++idx ] ) ? np->right : np->left;
    }

    return np;
}


// 挿入
void insert( char key )
{
  node *np, *father = &head;
  int idx;

  // ステップ1 キーの探索
  idx = 0;
  np = father->left;
  while( np != NULL && key != np->key )
  {
    father = np;
    np = ( key & mask[ ++idx ] ) ? np->right : np->left;
  }

  // ステップ2 キー挿入
  if( np != NULL )
    printf( "%c はすでにある\n", key );
  else
  {
    // 新しい節を作り
    np = calloc( 1, sizeof( node ));

    // キーを置き親とつなぐ
    np->key = key;
    np->right = np->left = NULL;

    if( key & mask[ idx ] )
      father->right = np;
    else
      father->left = np;
  }

  return;

}


// 削除
void delete ( char key )
{
  node *np, *father = &head, *x;
  int idx;

  // ステップ1 キーの探索
  idx = 0;
  np = head.left;
  while( np != NULL && key != np->key )
  {
    father = np;
    np = ( key & mask[ ++idx ] ) ? np->right : np->left;
  }


  // ステップ2 キー削除
  if( np == NULL )
  {
    printf( "%c はない\n", key );
    return;
  }

  // np の子孫中の葉を探す
  x = np;
  while( x->left != NULL || x->right != NULL )
  {
    father = x;
    idx++;
    x = ( x->left == NULL ) ? x->right : x->left;
  }

  // 葉のキーを np に置き、葉を切り離す
  np->key = x->key;
  if( x->key & mask[ idx ] )
    father->right = NULL;
  else
    father->left = NULL;

  return;
}


int main( int ac, char** av )
{
  node *np;

  insert( 'a' );
  insert( 'b' );
  insert( 'c' );
  insert( 'd' );

  np = search( 'a' );
  if( np != NULL )
    printf( "key hit: %c\n", np->key );


  np = search( 'a' );
  if( np != NULL )
    printf( "key hit: %c\n", np->key );

  np = search( 'b' );
  if( np != NULL )
    printf( "key hit: %c\n", np->key );

  delete( 'b' );
  printf( "delete key: %c\n", 'b' );

  np = search( 'a' );
  if( np != NULL )
    printf( "key hit: %c\n", np->key );

  np = search( 'b' );
  if( np != NULL )
    printf( "key hit: %c\n", np->key );

  delete( 'a' );
  printf( "delete key: %c\n", 'a' );

  np = search( 'a' );
  if( np != NULL )
    printf( "key hit: %c\n", np->key );

  return;
}

% ./a.exe
key hit: a
key hit: a
key hit: b
delete key: b
key hit: a
delete key: a

4320027094

_ [アルゴリズム][ディジタル探索]アルゴリズム辞典 - ディジタル探索 (ruby実装)

# アルゴリズム辞典
# 島内剛一 野下浩平 伏見正則 有沢誠 浜田穂積
#
# ディジタル探索 pp. 522-523

require 'pp'

class Node
  attr_accessor :key, :left, :right

  def initialize(key, left, right)
    @key = key
    @left = left
    @right = right
  end
end

class DigitalSearch
  def initialize()
    @head = Node.new(0, nil, nil)
    @mask = [0x00, 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80]
  end

  # 探索
  def search(key)
    idx = 0
    np = @head.left

    while np != nil && key != np.key
      # キーの idx 桁が 1(0) ならば右(左)へ
      idx += 1
      np = (key[0] & @mask[idx] != 0) ? np.right : np.left
    end

    return np

  end

  # 挿入
  def insert(key)
    father = @head
    idx = 0

    # ステップ1 キーの探索
    np = father.left
    while np != nil && key != np.key
      father = np
      idx += 1
      np = (key[0] & @mask[idx] != 0) ? np.right : np.left
    end

    # ステップ2 キー挿入
    if np != nil
      puts "#{key} はすでにある"
    else
      # 新しい節を作り
      np = Node.new(key, nil, nil)
      # キーを置き親とつなぐ
      if key[0] & @mask[idx] != 0
        father.right = np
      else
        father.left = np
      end
    end

  end

  # 削除
  def delete(key)

    # ステップ1 キーの探索
    idx = 0
    np = @head.left
    while np != nil && key != np.key
      father = np
      idx += 1
      np = (key[0] & @mask[idx] != 0) ? np.right : np.left
    end


    # ステップ2 キー削除
    if np == nil
      puts "#{key} はない"
      return
    end

    # np の子孫中の葉を探す
    x = np
    while x.left != nil || x.right != nil
      father = x
      idx += 1
      x = x.left == nil ? x.right : x.left
    end

    # 葉のキーを np に置き、葉を切り離す
    np.key = x.key
    if x.key[0] & @mask[idx] != 0
      father.right = nil
    else
      father.left = nil
    end
  end
end


def main()
  digi = DigitalSearch.new()
  digi.insert('a')
  digi.insert('b')
  digi.insert('c')
  digi.insert('d')

  np = digi.search('a')
  if np != nil
    puts "key hit: #{np.key}"
  end

  np = digi.search('a')
  if np != nil
    puts "key hit: #{np.key}"
  end

  np = digi.search('b')
  if np != nil
    puts "key hit: #{np.key}"
  end

  np = digi.search('c')
  if np != nil
    puts "key hit: #{np.key}"
  end

  np = digi.search('d')
  if np != nil
    puts "key hit: #{np.key}"
  end

  digi.delete('b')
  puts "delete key: b"

  np = digi.search('a')
  if np != nil
    puts "key hit: #{np.key}"
  end

  np = digi.search('b')
  if np != nil
    puts "key hit: #{np.key}"
  end

  digi.delete('a');
  puts "delete key: a"

  np = digi.search('a')
  if np != nil
    puts "key hit: #{np.key}"
  end

end


main()

% ruby digi.rb
key hit: a
key hit: a
key hit: b
key hit: c
key hit: d
delete key: b
key hit: a
delete key: a

if 0 がなぜ真になるのだ！ と 30 分くらい悩んで ruby だということを思い出した。

制御構造

Ruby では false または nil だけが偽で、それ以外は 0 や空文字列も含め全て真です。

4320027094