初めに
練習に二分探索木を使った、連想配列を作りました。
keyがstd::stringでdataがlongです。
ソース
main.cpp
#include <cstdio>
#include <cmath>
#include <cstring>
#include <iostream>
#include <vector>
#include <fstream>
#include <string>
#include <sstream>
class tree2
{
public:
struct one_tree
{
std::string name;
long data;
one_tree *R_next; // 大きい
one_tree *L_next; // 小さい
};
one_tree *tree_data;
one_tree *Get_one_tree()
{
one_tree *temp = new one_tree;
temp->data = 0L;
temp->name = "";
temp->R_next = temp->L_next = NULL;
return temp;
};
tree2()
{
tree_data = NULL;
}
one_tree *search(one_tree *tree_data2, std::string name)
{
if (tree_data2 == NULL)
{
return NULL;
}
else
{
int temp = strcmp(tree_data2->name.c_str(), name.c_str());
if (temp == 0)
{
return tree_data2;
}
else if (temp > 0)
{
return search(tree_data2->L_next, name);
}
else if (temp < 0)
{
return search(tree_data2->R_next, name);
}
}
}
one_tree *search(std::string name)
{
if (tree_data == NULL)
{
return NULL;
}
else
{
int temp = strcmp(tree_data->name.c_str(), name.c_str());
if (temp == 0)
{
return tree_data;
}
else if (temp > 0)
{
return search(tree_data->L_next, name);
}
else if (temp < 0)
{
return search(tree_data->R_next, name);
}
}
}
// 検索関数
one_tree **search2(one_tree **tree_data3, one_tree *tree_data2, std::string name)
{
if (tree_data2 == NULL)
{
return tree_data3;
}
else
{
int temp = strcmp(tree_data2->name.c_str(), name.c_str());
if (temp > 0)
{
return search2(&(tree_data2->L_next), tree_data2->L_next, name);
}
else if (temp < 0)
{
return search2(&(tree_data2->R_next), tree_data2->R_next, name);
}
}
}
one_tree **search2(std::string name)
{
if (tree_data == NULL)
{
return &tree_data;
}
else
{
int temp = strcmp(tree_data->name.c_str(), name.c_str());
if (temp > 0)
{
return search2(&(tree_data->L_next), tree_data->L_next, name);
}
else if (temp < 0)
{
return search2(&(tree_data->R_next), tree_data->R_next, name);
}
}
}
// 追加用検索関数
void add(std::string name, long data)
{
if (search(name) == NULL)
{
one_tree **temp = search2(name);
*temp = Get_one_tree();
(*temp)->name = name;
(*temp)->data = data;
}
}
// 追加
void Dprint(one_tree *tree_data2)
{
if (tree_data2 == NULL)
return;
std::cout << tree_data2->name << "," << tree_data2->data << std::endl;
Dprint(tree_data2->R_next);
Dprint(tree_data2->L_next);
}
void Dprint()
{
if (tree_data == NULL)
return;
std::cout << tree_data->name << "," << tree_data->data << std::endl;
Dprint(tree_data->R_next);
Dprint(tree_data->L_next);
}
// デバッグ用
void all_delete(one_tree *tree_data2)
{
if (tree_data2 == NULL)
return;
delete tree_data2;
all_delete(tree_data2->R_next);
all_delete(tree_data2->L_next);
};
void all_delete()
{
if (tree_data == NULL)
return;
delete tree_data;
all_delete(tree_data->R_next);
all_delete(tree_data->L_next);
};
// メモリー開放
~tree2()
{
all_delete();
}
};
使い方
main.cpp
//main.cppの続き
int main(){
tree2 a;
a.add("key",100);
a.add("key2",130);
std::cout << a.search("key")->data << std::endl;//100
}