Verknüpfte Liste- find_node_data

Question

Ich habe bereits über das gleiche Thema gepostet. Ich bin selbstlernende Datenstrukturen mit MIT Open Courseware. Ich mache die 6.S096-Einführung in C/C++ Kurs und versuche die vierte Aufgabe.

Es basiert auf binäre Suchbäume und ich habe es versucht. Ich wollte die Werte für das Debugging drucken, aber jedes Mal verschiedene Ausführungen erhalten.

Einmal wird der Zyklus nicht abgeschlossen und das andere Mal geht es in die Unendlichkeit. Der Debugging-Block bezieht sich auch auf die andere Funktion (find_node_data) Ich muss vervollständigen. Wenn ich also herausfinden kann, was hier falsch ist, kann ich die find_node_data einfach fertigstellen. Ich habe ein paar Dinge kommentiert, um zu sehen, ob es irgendetwas betrifft. Was mache ich falsch?

#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

Um die node_data Sie verwenden können Rekursion finden Sie den Knoten zu finden.

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); 
    } 
} 

Und dann die Daten für den Knoten z. erhalten die Daten für Knoten mit node_id 42:

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

Volles Programm unten (? Ich kann seine Richtigkeit nicht garantieren, aber vielleicht können Sie)

#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; 
} 

-Test

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 

Sie können Verwenden Sie auch Jonathan Lefflers verbesserte Rekursion, um den Knoten zu finden:

Beide Funktionen geben die korrekten Werte wie im zweiten Test zurück.

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; 
} 

-Test 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