リンクされたリスト - find_node_data

Question

私はこれまで同じトピックについて投稿しています。私は、MITオープンコースウェアを使用してデータを自己学習しています。 6.S096-C/C++コースの紹介と4番目の割り当てを試みています。

これは、バイナリ検索ツリーに基づいており、試してみました。私はデバッグのために値を表示したいが、毎回異なる実行を続けた。

1回はサイクルが完了せず、もう1回は無限に進みます。デバッグブロックはまた、他の関数（find_node_data）に関連しています私は完了する必要があります。だからここで何が間違っているのか分かるならば、find_node_dataを簡単に終えることができます。私はそれが何かに影響するかどうかを見るためにいくつかの点をコメントしました。私は間違って何をしていますか？

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

typedef struct node{ 
    int node_id; 
    int data; 
    struct node* left; 
    struct node* right; 
}node; 



///*** DO NOT CHANGE ANY FUNCTION DEFINITIONS ***/// 
// Declare the tree modification functions below... 
node* newNode(int data,int node_id){ 
    node* new_node = (node*) malloc(sizeof(node)); 
    new_node->data = data; 
    new_node->node_id= node_id; 
    new_node->right= new_node->left=NULL; 
    return new_node; 
} 

node* insert_node(node* root, int node_id, int data) { 
    if(root==NULL) 
     return newNode(data,node_id); 
    else{ 
     node* cur; 
     if(node_id<root->node_id){ 
      cur=insert_node(root->left,data,node_id); 
      root->left=cur;     
     } 
     else if(node_id>root->node_id){ 
      cur=insert_node(root->right,data,node_id); 
      root->right=cur; 
     } 
    } 
    return root; 
} 

// Find the node with node_id, and return its data 
/*int find_node_data(node* root, int node_id) { 
    node* current; 
    for(current = root->; current->next!=NULL; 
     current= current->next){ 
    if(current->data == data) return current; 
} 
return NULL; 
} 
*/ 
int main() { 
    /* 
    Insert your test code here. Try inserting nodes then searching for them. 

    When we grade, we will overwrite your main function with our own sequence of 
    insertions and deletions to test your implementation. If you change the 
    argument or return types of the binary tree functions, our grading code 
    won't work! 
    */ 
    int T,data,node_id; 
    printf("Print yo cases"); 
    scanf("%d", &T); 
    node* root = NULL; 
    while(T-->0){ 
     printf("Type yo numnums no. %d:",T); 
     scanf("%d %d",&data,&node_id); 
     root=insert_node(root,data,node_id); 
    } 
    node *lol; 
    node *king; 
    for(lol=root;lol->left!=NULL;lol=lol->left){ 
     //for(king=root;king->right!=NULL;king=king->right){ 
     printf("executed!\n"); 
     printf("%d ",lol->node_id);//,king->node_id); 
     //} 
    }  
    return 0; 
} 

Answer 1

ノードを見つけるために再帰を使用することができますnode_dataを検索します。

node* find_node_data(node *root, int node_id) {  
    if (root == NULL) 
     return NULL; 
    else if (root->node_id == node_id) 
     return root; 
    else { 
     node *left = find_node_data(root->left, node_id); 
     return left? left: find_node_data(root->right, node_id); 
    } 
} 

そして、ノードなどのデータを取得NODE_ID 42とのノードのデータを取得：

printf("node data %d", find_node_data(root, 42)->data); 

全プログラム

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

typedef struct node { 
    int node_id; 
    int data; 
    struct node *left; 
    struct node *right; 
} node; 


///*** DO NOT CHANGE ANY FUNCTION DEFINITIONS ***/// 
// Declare the tree modification functions below... 
node *newNode(int data, int node_id) { 
    node *new_node = (node *) malloc(sizeof(node)); 
    new_node->data = data; 
    new_node->node_id = node_id; 
    new_node->right = new_node->left = NULL; 
    return new_node; 
} 

node *insert_node(node *root, int data, int node_id) { 
    if (root == NULL) 
     return newNode(data, node_id); 
    else { 
     node *cur; 
     if (node_id < root->node_id) { 
      cur = insert_node(root->left, data, node_id); 
      root->left = cur; 
     } 
     else if (node_id > root->node_id) { 
      cur = insert_node(root->right, data, node_id); 
      root->right = cur; 
     } 
    } 
    return root; 
} 

// Find the node with node_id, and return its data 
/* 
int find_node_data_old(node *root, int node_id) { 
    node *current; 
    for (current = root->; current->next != NULL; 
     current = current->next) { 
     if (current->data == data) return current; 
    } 
    return NULL; 
}*/ 
node* find_node_data(node *root, int node_id) { 

    if (root == NULL) 
     return NULL; 
    else if (root->node_id == node_id) 
     return root; 
    else { 
     node *left = find_node_data(root->left, node_id); 
     return left? left: find_node_data(root->right, node_id); 
    } 
} 
void print(node *np) { 
    if (np) { 
     print(np->left); 
     printf("(%d, %d)", np->node_id, np->data); 
     print(np->right); 
    } 
} 

int main() { 
    /* 
    Insert your test code here. Try inserting nodes then searching for them. 

    When we grade, we will overwrite your main function with our own sequence of 
    insertions and deletions to test your implementation. If you change the 
    argument or return types of the binary tree functions, our grading code 
    won't work! 
    */ 
    int T, data, node_id; 
    printf("Print yo cases"); 
    scanf("%d", &T); 
    node *root = NULL; 
    while (T-- > 0) { 
     printf("Type yo numnums no. %d:", T); 
     scanf("%d %d", &data, &node_id); 
     root = insert_node(root, data, node_id); 
    } 
    node *lol; 
    node *king; 
    for (lol = root; lol->left != NULL; lol = lol->left) { 
     //for(king=root;king->right!=NULL;king=king->right){ 
     printf("executed!\n"); 
     printf("%d ", lol->node_id);//,king->node_id); 
     //} 
    } 
    print(root); 
    printf("\n"); 
    printf("node data %d", find_node_data(root, 42)->data); 
    return 0; 
} 

テスト

Print yo cases3 
Type yo numnums no. 2:22 42 
Type yo numnums no. 1:21 41 
Type yo numnums no. 0:20 40 
executed! 
42 executed! 
41 (40, 20)(41, 21)(42, 22) 
node data 22 

（私はその正しさを保証することはできませんが、多分あなたはできますか？）の下にあなたはありJonathan Lefflerの改良された再帰を使用してノードを見つけることもできます。

node *find_node_data2(node *root, int node_id) { 
    if (root == NULL) 
     return NULL; 
    else if (root->node_id == node_id) 
     return root; 
    else if (root->node_id > node_id) 
     return find_node_data(root->left, node_id); 
    else 
     return find_node_data(root->right, node_id); 
} 

両方の関数は、2番目のテストで見られるように正しい値を返します。

int main() { 
    /* 
    Insert your test code here. Try inserting nodes then searching for them. 

    When we grade, we will overwrite your main function with our own sequence of 
    insertions and deletions to test your implementation. If you change the 
    argument or return types of the binary tree functions, our grading code 
    won't work! 
    */ 
    int T, data, node_id; 
    printf("Print yo cases"); 
    scanf("%d", &T); 
    node *root = NULL; 
    while (T-- > 0) { 
     printf("Type yo numnums no. %d:", T); 
     scanf("%d %d", &data, &node_id); 
     root = insert_node(root, data, node_id); 
    } 
    node *lol; 
    node *king; 
    for (lol = root; lol->left != NULL; lol = lol->left) { 
     //for(king=root;king->right!=NULL;king=king->right){ 
     printf("executed!\n"); 
     printf("%d ", lol->node_id);//,king->node_id); 
     //} 
    } 
    print(root); 
    printf("\n"); 
    printf("node data %d\n", find_node_data(root, 42)->data); 
    printf("node data find_node_data2 %d", find_node_data2(root, 42)->data); 
    return 0; 
} 

テスト2

Print yo cases3 
Type yo numnums no. 2:11 12 
Type yo numnums no. 1:13 14 
Type yo numnums no. 0:20 42 
(12, 11)(14, 13)(42, 20) 
node data 20 
node data find_node_data2 20