「アルゴリズムとデータ構造２.１」の編集履歴（バックアップ）一覧はこちら

「アルゴリズムとデータ構造２.１」(2008/11/04 (火) 16:43:32) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

すみません、前のが見難かったので、こちらに見やすいのをあげときます。
直前でごめんなさい。如月
今回、置き換えできるのは３．１のaのみです。

課題３．１
//
//  3.3節  ２分探索木
//
//    ２分探索木による探索の例
//    図3.G, 図3.H, 図3.I, 図3.J, 問題3.2, 問題3.3
// 
//  Copyright (C) 2007 Akira Utsumi. All rights reserved 
//

#include <stdio.h>

struct node {
  int  element;
  struct node *left, *right;
};

struct node *search(int x, struct node *p);
struct node *delete(int x, struct node *p);
struct node *delete_root(struct node *p);
struct node *insert(int x, struct node *p);
struct node *min(struct node *p);
void inorder(struct node *p);
void print_tree(int n, struct node *p);

main()
{
  int x;
  char c[2];
  struct node *init = NULL, *p;

  while(1){     /* 無限ループ: 抜け出すには Ctrl+C を入力 */
    printf("Insert(i)/Delete(d)/Search(s)/Min(m)/Traverse(t)/Quit(q)? ");
    scanf("%1s", c);
    if(c[0] == 'i'){
      printf("挿入するデータ(整数)は? ");
      scanf("%d",&x);
      init = insert(x,init);
      print_tree(0,init);
    } else if(c[0] == 'd'){
      printf("削除するデータ(整数)は? ");
      scanf("%d",&x);
      init = delete(x,init);
      print_tree(0,init);
    } else if(c[0] == 's'){
      printf("探索するデータ(整数)は? ");
      scanf("%d",&x);
      p = search(x,init);
      if(p == NULL){
	printf("データ %d は存在しません!\n",x);
      } else {
	printf("データ %d は存在します\n",x);
	if(p->left != NULL) printf("左の子はデータ %d です\n",p->left->element);
	if(p->right != NULL) printf("右の子はデータ %d です\n",p->right->element);
      }
    } else if(c[0] == 'm'){
      p = min(init);
      if(p == NULL){
	printf("2分探索木が空です!\n");
      } else {
	printf("最小値は %d です\n",p->element);
      }
    } else if(c[0] == 't'){
      inorder(init);
      printf("\n");
    } else if(c[0] == 'q'){
      exit(0);
    } else {
      printf("入力エラーです!\n");
    }
  }
}

struct node *search(int x, struct node *p)
/* 2分探索木 p で x をキーに持つレコードを探し，見つかった場合には    */
/* そのレコードへのポインタを，見つからなかった場合には NULL を返す． */
/* 構造体 struct node は，図 2.M の定義を用いる．                   */
{
  struct node *q;

  q = p;
  while(q != NULL){
    if(q->element == x)  return q;
    if(q->element < x) q = q->right;
    else q = q->left;
  }
  return q;
}

struct node *delete(int x, struct node *p)
/* ２分探索木の根へのポインタ p と削除すべきキー x を受け取り，x を持つノードを */
/* 削除した後の２分探索木の根のポインタを返す． */
{
  struct node *q, **r;

  q = p; r = &p;        /* q は探索しているレコードへのポインタ */
  while(q != NULL){     /* r は q の指しているレコードの親レコードのメンバ (left or right) へのポインタ */
    if(q->element == x){
      *r = delete_root(q);   /* q が指すレコードを根とする部分木から, そのレコードを削除した */
                             /* 新たな２分探索木へのポインタを r の指しているポインタへ代入  */
      if(p == q) return *r;  /* ２分探索木の根を削除した場合 */
      else return p;
    }
    if(q->element < x){   
      r = &(q->right);
      q = q->right;
    }
    else{
      r = &(q->left);
      q = q->left;
    }
  }
  printf("データ %d は見つかりませんでした!\n",x);
  return p;
}

struct node *delete_root(struct node *p)
/* ２分探索木の根へのポインタ p を受け取り，その根を削除して再構成した */
/* 新しい２分探索木の根へのポインタを返す．(再帰を用いない方法) */
{
  struct node *q, **r;

  if(p->left == NULL && p->right == NULL){  /* p の指すノードが葉の場合 */
    free(p);                                /* p を削除して NULL を返す */
    return NULL;
  }
  if(p->left == NULL){   /* p の指すノードの子が一つの場合 */
    q = p->right;        /* その子ノードへのポインタを返す */
    free(p);
    return q;
  }
  if(p->right == NULL){  
    q = p->left;         
    free(p);
    return q;
  }
  q = p->right;         /* p の指すノードの子が二つの場合 */
  r = &(p->right);      
  while(q->left != NULL){  /* 右部分木で最小のキーを持つノードを見つける */
    r = &(q->left);        /* q はそのノードへのポインタ */
    q = q->left;           /* r は q の指すノードの親レコードのメンバへのポインタ */
  }
  p->element = q->element; /* q が指す最小要素ノードを p の指す根へ移す */
  *r = q->right;           /* 最小キーを持っていたノードを根とする部分木から */
  free(q);                 /* そのレコードを削除する */
  return p;
}

struct node *insert(int x, struct node *p)
/* 挿入すべきデータ x と２分探索木の根へのポインタ p を受け取り，*/
/* x を挿入した後の２分探索木の根のアドレスを返す.               */
/* すでにデータ x が存在する場合は, その旨を出力して何もしない.  */
{
  struct node *q=p,*r;
  int a;
  
  while(q != NULL){  
    r = q; a = x - q->element;
    if(a > 0) q = q->right; 
    else if(a < 0) q = q->left;
    else {
      printf("データ %d はすでに存在します!\n",x);
      return p;
    }
  } 
  q = (struct node *)malloc(sizeof(struct node));
  q->element = x;
  q->left = q->right = NULL;
  if(r == NULL) return q;
  else if(a > 0) r->right = q;
  else r->left = q;
  return p;
}

struct node *min(struct node *p)
/* ２分探索木の根へのポインタ p を受け取り，  */
/* 最小値(整数)を持つノードへのポインタを返す */
{
  if(p == NULL) return p;
  while(p->left != NULL){
    p = p->left;
  }
  return p;
}

void inorder(struct node *p)
/* ２分探索木の根へのポインタ p を受け取り，*/
/* 中順に木をなぞって出力する */
{
  if(p != NULL){
    inorder(p->left);
    printf("%d ",p->element);
    inorder(p->right);
  }  
}

void print_tree(int n, struct node *p)
/* 根を最左に, 左の子が上, 右の子が下になるように 2分木を表示する */
{
  int i;

  if(p != NULL){
    print_tree(n+1, p->right);
    for(i=0;i<n;i++) printf("     ");
    printf("%3d\n",p->element);
    print_tree(n+1, p->left);
  }
}

課題３．２
//
//  3.5節  ハッシュ
//
//    外部ハッシュ法による探索の例 
//    図3.O, 図3.P, 図3.Q, 問題3.7 
// 
//  Copyright (C) 2007 Akira Utsumi. All rights reserved 
//

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

#define W  6

struct cell {
  char name[W+1];
  struct cell  *next;
};

int B;  /* ハッシュ表のサイズ */

struct cell *search(char x[], struct cell *A[]);
void insert(char x[], struct cell *A[]);
void delete(char x[], struct cell *A[]);
int h(char x[]);
void print_hash(struct cell *A[]);

main()
{
  int i;
  char c[2], x[W+1];
  struct cell *A[100];

  printf("ハッシュ表のサイズ B = ");
  scanf("%d",&B);
  for(i=0;i<B;i++) A[i] = NULL;
  for(i=0;i<=W;i++) x[i] = '\0';
  while(1){
    printf("Insert(i)/Delete(d)/Search(s)/Quit(q)? ");
    scanf("%1s", c);
    if(c[0] == 'i'){
      printf("挿入するデータ(文字列)は? ");
      scanf("%s",x);
      insert(x,A);
      print_hash(A);
    } else if(c[0] == 'd'){
      printf("削除するデータ(文字列)は? ");
      scanf("%s",x);
      delete(x,A);
      print_hash(A);
    } else if(c[0] == 's'){
      printf("探索するデータ(文字列)は? ");
      scanf("%s",x);
      if(search(x,A) == NULL) printf("文字列 %s はハッシュ表に存在しません!\n", x);
      else printf("文字列 %s はすでにハッシュ表に存在します.\n",x);
    } else if(c[0] == 'q'){
      exit(0);
    } else {
      printf("入力エラーです!\n");
    }
  }
}

struct cell *search(char x[], struct cell *A[])
/* ハッシュ表 A に文字列 x があるかどうかを判定し，存在する場合にはそのセル */
/* へのポインタを返す．*/
{
  struct cell *p;

  p = A[h(x)]; /* x のハッシュ値を計算して，バケットへのポインタを p に代入 */
  while(p != NULL){
    if(strcmp(p->name,x) == 0) /* x が見つかった */
      return p;
    p = p->next;
  }
  return NULL;  /* x が見つからなかった */
}

void insert(char x[], struct cell *A[])
/*  ハッシュ表 A へ文字列 x を挿入  */
/*  すでに x が存在する場合には挿入せず,その旨を表示する */
{
  struct cell *p,*q,*r;

  p = (struct cell *)malloc(sizeof(struct cell));
  q = A[h(x)];
  if(q == NULL) A[h(x)]=p;
  else{
  	while(q != NULL){
  	  if(strcmp(q->name,x)==0){
	    printf("文字列 %s はすでにハッシュ表に存在するので, 挿入しません.\n",x);
	    return;
      }
  	  else {r=q; q=q->next;}
  	}
  	r->next=p;
  }
  strcpy(p->name,x);
  p->next=NULL;
}

void delete(char x[], struct cell *A[])
/*  ハッシュ表 A から文字列 x を削除  */
/*  x が存在しない場合には, その旨を表示する */
{
  struct cell *q, *r;

  q=A[h(x)];                        
  r=NULL;
  while(q != NULL) 
    {
     if(strcmp(q->name, x)==0)   
       {
        if(r==NULL) A[h(x)]=q->next; 
        else r->next=q->next;
        free(q); return;              
       }
     r=q; q=q->next;
    }
  printf("文字列 %s はハッシュ表に存在しないので, 削除できません.\n", x);
}

int h(char x[])
/* 文字列 x を受け取り，式(2.9)を用いてそのハッシュ値を計算する関数 */
{
  int i, hash = 0;

  for(i=0;i<W && x[i]!='\0';i++) hash = hash + (int)x[i];
  hash = hash % B;
  return hash;
}

void print_hash(struct cell *A[])
{
  int i;
  struct cell *p;

  for(i=0;i<B;i++){
    p = A[i];
    if(p != NULL) printf("%3d: ",i);
    else continue;
    while(p != NULL){
      printf("%s ",p->name);
      p = p->next;
    }
    printf("\n");
  }
}

すみません、前のが見難かったので、こちらに見やすいのをあげときます。
直前でごめんなさい。如月
今回、置き換えできるのは３．１のaのみです。

課題３．１
//
//  3.3節  ２分探索木
//
//    ２分探索木による探索の例
//    図3.G, 図3.H, 図3.I, 図3.J, 問題3.2, 問題3.3
// 
//  Copyright (C) 2007 Akira Utsumi. All rights reserved 
//