前回
今回
前回は、関数ポインタを内包した構造体Helloを二分探索木で管理しました。それに伴って、f関数,structHelloAllocate関数、in_struct関数、in_struct_at_delete関数を追加しました。また、treeWalk関数内を変更しました。
今回は、構造体Hello内の関数ポインタuを並列実行します。それに伴って、walkNodeWhile関数、thread1関数を追加しました。
walkNodeWhile関数では、pthreadを使ってthread1関数を並列実行しています。
参考ページ
サメベース. SAMEBASE
【[C言語]二分探索木から要素を削除する関数の実装[コード付]】
参考文献
改訂第4版 C言語によるはじめてのアルゴリズム入門 2017年11月25日
河西朝雄 著
準備
console
clang ーlpthread -lm sample.c -o sample
./sample
もしくはオンラインコンパイラを使用します。
オンラインコンパイラ
Cコンパイラを使用します。
ソースコード
sample.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <pthread.h>
#include <errno.h>
typedef struct Hello{
long i;
struct Hello* (*u)(struct Hello*);
}Hello;
typedef struct Hello* (*fupo)(struct Hello*);
Hello* f(Hello* v){
printf("Hello.%ld. \n",v->i);
return v;
}
typedef struct Node {
long i;
char key[12];
long type;
void *data;
struct Node* left;
struct Node* right;
} Node;
Node* treeAllocate(){
return (Node*)malloc(sizeof(Node));
}
Hello* structHelloAllocate(){
return (Hello*)malloc(sizeof(Hello));
}
Node* in_struct(Node *new_node,long insert_data, char *key,long type, void *data){
new_node->i = insert_data;
strcpy(new_node->key,key);
new_node->type=type;
new_node->data=data;
new_node->left = NULL;
new_node->right = NULL;
return new_node;
}
Node* in_struct_at_delete(Node *root,Node *temp){
root->i = temp->i;
strcpy(root->key,temp->key);
root->type=temp->type;
root->data=temp->data;
return root;
}
Node* insertNode(Node* pNode, long insert_data, char *key,long type, void *data) {
if (pNode == NULL) {
Node* new_node = treeAllocate();
in_struct(new_node,insert_data,key,type,data);
return new_node;
}
if (insert_data < pNode->i) {
pNode->left = insertNode(pNode->left, insert_data,key,type,data);
} else if (insert_data > pNode->i) {
pNode->right = insertNode(pNode->right, insert_data,key,type,data);
}
return pNode;
}
Node* findMin(Node* node) {
Node* current = node;
while (current && current->left != NULL)
current = current->left;
return current;
}
Node* deleteNode(Node* root, long key) {
if (root == NULL)
return root;
if (key < root->i)
root->left = deleteNode(root->left, key);
else if (key > root->i)
root->right = deleteNode(root->right, key);
else {
if (root->left == NULL) {
Node* temp = root->right;
free(root);
return temp;
}
else if (root->right == NULL) {
Node* temp = root->left;
free(root);
return temp;
}
Node* temp = findMin(root->right);
in_struct_at_delete(root,temp);
root->right = deleteNode(root->right, temp->i);
}
return root;
}
Node* searchNode(Node* pNode, long search_data) {
if (pNode == NULL || pNode->i == search_data) {
return pNode;
}
if (search_data < pNode->i) {
return searchNode(pNode->left, search_data);
} else {
return searchNode(pNode->right, search_data);
}
}
Node* searchNodeForKey(Node *q,char *key){
Node *p=q;
if(p!=NULL){
if(strcmp(p->key,key)==0){
return p;
}
p=searchNodeForKey(p->left,key);
if(p!=NULL){
return p;
}
else{
p=q;
}
p=searchNodeForKey(p->right,key);
if(p!=NULL){
return p;
}
else{
return NULL;
}
}
else{
return NULL;
}
return q;
}
void walkNode(Node* root) {
if (root == NULL) {
return;
}else {
walkNode(root->left);
walkNode(root->right);
printf("%ld,", root->i);
printf("%s \n", root->key);
if(root->type==0){
printf("%ld \n", ((Hello*)root->data)->i);
((Hello*)root->data)->u((Hello*)root->data);
}
}
return;
}
void * thread1(void *pNode){
Node *root=(Node*)pNode;
printf("%ld,", root->i);
printf("%s \n", root->key);
if(root->type==0){
printf("%ld \n", ((Hello*)root->data)->i);
((Hello*)root->data)->u((Hello*)root->data);
}
pthread_exit((void*)root);
return (void*)root;
}
void walkNodeWhile(Node* root) {
int rc;
pthread_attr_t attr;
pthread_t thid;
rc = pthread_attr_init(&attr);
if (rc == -1) {
perror("error in pthread_attr_init");
exit(1);
}
if (root == NULL) {
return;
}else {
rc = pthread_create(&thid, &attr, thread1, root);
if (rc == -1) {
perror("error in pthread_create");
exit(2);
}
walkNodeWhile(root->left);
walkNodeWhile(root->right);
void *s=NULL;
if (pthread_join(thid, &s) != 0) {
perror("pthread_create() error\n");
exit(3);
}
}
return;
}
int main(void){
Hello lo[10];
long i=0;
for(i=0;i<10;i++){
lo[i].i=i;
lo[i].u=f;
}
long type=0;
Node* root = NULL;
root = insertNode(root, 7,"Cho", type, (void*) &lo[0]);
root = insertNode(root, 2,"Chie", type, (void*) &lo[1]);
root = insertNode(root, 1,"Chroe", type, (void*) &lo[2]);
root = insertNode(root, 0,"Mike", type, (void*) &lo[3]);
root = insertNode(root, 5,"Michel", type, (void*)&lo[4]);
root = insertNode(root, 3,"Rooter", type, (void*)&lo[5]);
root = insertNode(root, 4,"Yuki", type, (void*) &lo[6]);
root = insertNode(root, 6,"Ayaka", type, (void*) &lo[7]);
root = insertNode(root, 8,"Aki", type, (void*) &lo[8]);
root = insertNode(root, 9,"Yuji", type, (void*) &lo[9]);
printf("\npre＿order: ");
walkNode(root);
root = deleteNode(root, 2);
printf("\npre＿order: ");
walkNode(root);
printf("%ld\n",root->i);
root = deleteNode(root, 7);
printf("1\n");
walkNode(root);
printf("1\n");
Node* find_node=NULL;
printf("1\n");
find_node=searchNodeForKey(root,"Ayataka");
if(find_node!=NULL){
printf("%ld,%s\n",find_node->i,find_node->key);
}else{
printf("Not Found.\n");
}
find_node=searchNodeForKey(root,"Mike");
if(find_node!=NULL){
printf("%ld,%s\n",find_node->i,find_node->key);
}else{
printf("Not Found.\n");
}
walkNodeWhile(root);
return 0;
}
実行結果
console1
pre＿order: 0,Mike
3
Hello.3.
1,Chroe
2
Hello.2.
4,Yuki
6
Hello.6.
3,Rooter
5
Hello.5.
6,Ayaka
7
Hello.7.
5,Michel
4
Hello.4.
2,Chie
1
Hello.1.
9,Yuji
9
Hello.9.
8,Aki
8
Hello.8.
7,Cho
0
Hello.0.
pre＿order: 0,Mike
3
Hello.3.
1,Chroe
2
Hello.2.
4,Yuki
6
Hello.6.
6,Ayaka
7
Hello.7.
5,Michel
4
Hello.4.
3,Rooter
5
Hello.5.
9,Yuji
9
Hello.9.
8,Aki
8
Hello.8.
7,Cho
0
Hello.0.
7
1
0,Mike
3
Hello.3.
1,Chroe
2
Hello.2.
4,Yuki
6
Hello.6.
6,Ayaka
7
Hello.7.
5,Michel
4
Hello.4.
3,Rooter
5
Hello.5.
9,Yuji
9
Hello.9.
8,Aki
8
Hello.8.
1
1
Not Found.
0,Mike
8,Aki
0,8
Mike
3
3,Rooter
Hello.3.
5
Hello.5.
1,Chroe
2
Hello.2.
Hello.8.
5,Michel
4
Hello.4.
4,Yuki
6
Hello.6.
6,Ayaka
7
Hello.7.
9,Yuji
9
Hello.9.