Latest algorithm dictionary in C language (written by Haruhiko Okumura / 1991 first edition Gijutsu-Hyoronsha: 206 pages)
Quoted from the reference materials below
Binary tree used for search. Each node has data and two pointers, all the data of the offspring connected by the left pointer left is smaller than itself, and all the data of the offspring connected by the right pointer right is larger than oneself. A binary search tree search starts at the root and follows the left or right pointer, depending on whether the object you are looking for is smaller or larger than the node. A perfectly balanced binary tree can be compared n times to find the desired one from 2 to the n-1 factorial.
postfix.c
//Binary search tree
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//Type declaration of the key used for the search
typedef char keytype[21];
//Binary node node type declaration
typedef struct node {
struct node *left, *right; //Pointers to the left and right child nodes
keytype key; //Search key
} *nodeptr; //Pointer to a node
struct node nil; //Node representing the end of the tree
nodeptr root = &nil; //Pointer to the root
//Insert into a tree(Registration)function
nodeptr insert(keytype insertkey){
int cmp;
nodeptr *p; //Pointer to a node
nodeptr q; //Node entity
strncpy(nil.key,insertkey,sizeof(keytype)); //Copy the argument key to the guard's key
p = &root; //Assign the root pointer to the pointer of the internal variable
//Loop until the keys match
while((cmp = strncmp(insertkey, (*p)->key, sizeof(keytype))) != 0)
{
//If the insert key is less than the key of the node pointed to by the pointer, move to the smaller node on the left
//If the insert key is greater than the key of the node pointed to by the pointer, move to the larger node on the right
if(cmp < 0){
//Move the pointer to the left
p = &((*p)->left);
}
else{
//Move the pointer to the right
p = &((*p)->right);
}
}
//If the key is already registered
if(*p != &nil){
return NULL;
}
//Allocate memory area for node
if((q = malloc(sizeof(*q))) == NULL){
printf("insert:Failed to secure memory area due to insufficient memory.\n");
exit(EXIT_FAILURE);
}
//Copy the node key
strncpy(q->key, insertkey, sizeof(keytype));
q->left = &nil;
q->right = *p;
*p = q;
//Returns the registered node
return q;
}
//Delete function
//Returns 0 if it can be deleted, 1 if it fails
int delete(keytype deletekey){
int cmp;
nodeptr *p, *q;
nodeptr r, s;
strncpy(nil.key, deletekey, sizeof(keytype)); //Guardian
p = &root;
//Loop until the keys match
while((cmp = strncmp(deletekey, (*p)->key, sizeof(keytype))) != 0)
{
//If the insert key is less than the key of the node pointed to by the pointer, move to the smaller node on the left
//If the insert key is greater than the key of the node pointed to by the pointer, move to the larger node on the right
if(cmp < 0){
p = &((*p)->left);
}
else{
p = &((*p)->right);
}
}
//If the key is not found
if(*p == &nil){
return 1;
}
r = *p;
if(r->right == &nil){
*p = r->right;
}else if(r->left == &nil){
*p = r->right;
} else{
q = &(r->left);
while((*q)->right != &nil){
q = &((*q)->right);
}
s = *q;
*q = s->left;
s->left = r->left;
s->right = r->right;
*p = s;
}
//Free up space
free(r);
return 0;
}
//Search function
//If the key is found, it returns a pointer to the node that holds the key
//Returns NULL if not found
nodeptr search(keytype searchkey){
int cmp;
nodeptr p;
strncpy(nil.key, searchkey, sizeof(keytype));
p = root;
while((cmp =strncmp(searchkey, p->key, sizeof(keytype))) != 0){
if(cmp < 0){
p = p->left;
}else{
p = p->right;
}
}
if(p != &nil){
//If found
return p;
}else{
//If not found
return NULL;
}
}
void printtree(nodeptr p){
static int depth = 0;
//Show the node on the left
if((p->left) != &nil){
depth++;
//Recursive call
printtree(p->left);
depth--;
}
//Display the node received as an argument
printf("%*c%s\n", 5*depth, ' ', p->key);
//Show the node on the right
if(p->right != &nil){
depth++;
//Recursive call
printtree(p->right);
depth--;
}
}
int main(void) {
char buf[22];
short count;
printf( "Command Iabc:Insert abc\n"
" Dabc:Remove abc\n"
" Sabc:Search for abc\n");
for(;;){
printf("What is the order?");
//Receive data from standard input for buf size
if(scanf("%21s%*[^\n]", buf) != 1){
break;
}
switch(buf[0]){
//Insert process
case 'I': case'i':
//Insert function
if(insert(&buf[1])){
printf("%21s%*[^\n]:Has registered\n",buf);
}else{
printf("%21s%*[^\n]: Registered\n",buf);
}
break;
//Delete process
case 'D': case 'd':
//Delete function
if(delete(&buf[1])){
printf("%21s%*[^\n]: Not deleted\n",buf);
}else{
printf("%21s%*[^\n]:It has been deleted\n",buf);
}
break;
//Search process
case 'S': case 's':
//Delete function
if(search(&buf[1])){
printf("%21s%*[^\n]: Registered\n",buf);
}else{
printf("%21s%*[^\n]:not registered\n",buf);
}
break;
default:
printf("I can use, D,Only S\n");
break;
}
if(root != &nil){
printf("\n");
printtree(root);
printf("\n");
}
count++;
}
return EXIT_SUCCESS;
}
stdin.txt(Any)
Iabc
Sabc
Dabc
stdout.txt(Any)
Command Iabc:Insert abc
Dabc:Remove abc
Sabc:Search for abc
What is the order? Has registered
abc
What is the order?
Success #stdin #stdout 0s 4368KB
Command Iabc:Insert abc
Dabc:Remove abc
Sabc:Search for abc
What is the order? not registered
What is the order?
Success #stdin #stdout 0s 4516KB
Command Iabc:Insert abc
Dabc:Remove abc
Sabc:Search for abc
What is the order? Not deleted
What is the order?
Recommended Posts