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

アルゴリズムとデータ構造２.１ - (2008/01/31 (木) 21:47:25) の編集履歴(バックアップ)

---

すみません、前のが見難かったので、こちらに見やすいのをあげときます。
直前でごめんなさい。
今回、置き換えできるのは３．１の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");
}
}