c - 在递归函数中只调用一次函数

Question

每次调用函数 getInRange 时，l 的指针值都会发生变化。

我想初始化一个新的链表，但是当函数 getInRange 执行时它的值发生变化当我在 getInRange 的参数中使用 LinkedList 时，你有什么解决方案吗？它运行良好，但我必须找到另一个解决方案！

该函数在 BST.c 中

谢谢！！！

1-LinkedList.h

2-LinkedList.c

3-BinarySearchTree.h

4-BST.c

* ========================================================================= *
 * LinkedList interface:
 * Note that contrary to the Binary Search Tree, the linked list structure
 * is not opaque so that you can manipulate it directly.
 * ========================================================================= */

#ifndef _LINKED_LIST_H_
#define _LINKED_LIST_H_

#include <stddef.h>
#include <stdbool.h>


typedef struct llnode_t {
    const void* value;
    struct llnode_t* next;

} LLNode;

typedef struct linkedlist_t LinkedList;

/* ------------------------------------------------------------------------- *
 * Creates an empty LinkedList
 *
 * The LinkeedList must later be deleted by calling freeLinkedList().
 *
 * RETURN
 * linkedList    A pointer to the LinkedList, or NULL in case of error
 *
 * ------------------------------------------------------------------------- */

LinkedList* newLinkedList(void);


/* ------------------------------------------------------------------------- *
 * Frees the allocated memory of the given LinkedList.
 *
 * PARAMETERS
 * ll           A valid pointer to a LinkedList object
 * freeContent  Whether to free the content as well.
 *
 * NOTE
 * The const qualifier will be exceptionally discarded if freeContent == true
 * to allow the deletion of the content.
 * ------------------------------------------------------------------------- */

void freeLinkedList(LinkedList* ll, bool freeContent);

/* ------------------------------------------------------------------------- *
 * Counts the number of elements stored in the given LinkedList.
 *
 * PARAMETERS
 * ll           A valid pointer to a LinkedList object
 *
 * RETURN
 * nb           The amount of elements stored in linked list
 * ------------------------------------------------------------------------- */

size_t sizeOfLinkedList(const LinkedList* ll);


/* ------------------------------------------------------------------------- *
 * Inserts a new element in the linked list.
 *
 * PARAMETERS
 * ll           A valid pointer to a LinkedList object
 * value        The value to store
 *
 * RETURN
 * res          A boolean equal to true if the new element was successfully
 *              inserted, false otherwise (error)
 * ------------------------------------------------------------------------- */

LinkedList * insertInLinkedList(LinkedList* ll, const void* value);


/* ------------------------------------------------------------------------- *
 * Return a new linked list containing (the pointer to) the element of the
 * original linked list for which the keepIt predicate is true.
 *
 * PARAMETERS
 * ll           A valid pointer to a LinkedList object
 * keepIt       A predicate operating on the values of the linked list
 *
 * RETURN
 * filtered     A (possibly empty) linked list or NULL in case of error
 *
 * USAGE (example for strings)
 * bool startByH(const void* string)
 * {
 *     const char* string_ = string;
 *     return string_[0] == 'h';
 * }
 * ...
 * LinkedList* filtered = filterLinkedList(ll, &startByH);
 * ------------------------------------------------------------------------- */

LinkedList* filterLinkedList(LinkedList* ll,  bool keepIt_fn_t(const void*));



#endif // !_LINKED_LIST_H_


/* ========================================================================= *
 * LinkedList definition
 * ========================================================================= */

#include <stdio.h>
#include <stddef.h>
#include <stdlib.h>
#include "LinkedList.h"


struct linkedlist_t {
  size_t size;
  LLNode* head;
  LLNode* last;
  int (*sameAs)(const void*, const void*); /* fonction de comparaison qui doit retourner 1 si elle considère
                          que deux valeurs sont similaires */
  int (*display)(const void *);// fonction qui affiche la valeur pointée par value
  void (*destroy)(void *);     // fonction qui libère la mémoire pointée par value
};

LinkedList* newLinkedList(void)
{
    LinkedList* ll = malloc(sizeof(LinkedList));
    if (!ll)
        return NULL;
    ll->head = NULL;
    ll->last = NULL;
    ll->size = 0;
    return ll;
}



void freeLinkedList(LinkedList* ll, bool freeContent)
{
    // Free LLNodes
    LLNode* node = ll->head;
    LLNode* prev = NULL;
    while(node != NULL)
    {
        prev = node;
        node = node->next;
        if(freeContent)
            free((void*)prev->value); // Discard const qualifier
        free(prev);
    }
    // Free LinkedList sentinel
    free(ll);
}


size_t sizeOfLinkedList(const LinkedList* ll)
{
    return ll->size;
}


LinkedList * insertInLinkedList(LinkedList* ll, const void* value)
{
    LLNode* node = malloc(sizeof(LLNode));
    if(!node)
        return ll;
    // Initialisation
    node->next = NULL;
    node->value = value;
    // Adding the node to the list
    if(!ll->last)
    {
        // First element in the list
        ll->last = node;
        ll->head = node;
    } else {
        //At least one element in the list
        ll->last->next = node;
        ll->last = node;
    }
    // In both cases, increment size
    ll->size++;
    return ll;
}

LinkedList* filterLinkedList(LinkedList* ll,  bool keepIt_fn_t(const void*))
{
    LinkedList* filtered = newLinkedList();
    if (!filtered)
        return NULL;
    LLNode* curr = ll->head;
    bool error = false;
    while(!error && curr != NULL)
    {
        if(keepIt_fn_t(curr->value))
            error = error  || !insertInLinkedList(filtered, curr->value);
        curr = curr->next;
    }
    if(error)
    {
        freeLinkedList(filtered, false);
        return NULL;
    }
    return filtered;
}


int displayLinkedList(LinkedList* ll)
{
  unsigned long nb = sizeOfLinkedList(ll);
  printf("Number of elements: %lu\n", nb);
  LLNode* node = ll->head;
  while(node != NULL)
    {
      if (ll->display) ll->display(node->value);
      else printf("%d\n", (int*)(node->value));
      node = node->next;
    }
  return 0;
}


LinkedList * smart(int a, int b)
{
    LinkedList *l = newLinkedList();
    if (a == 0 || b == 0) {
        return insertInLinkedList(l, NULL);
        
        
    }
    else 
    {
        insertInLinkedList(l,a);
        smart(a-1,b-1);

    }
}

/*int main(void)
{
    LinkedList * l = newLinkedList();


    l = smart(12,5);

    displayLinkedList(l);
}*/


/* ========================================================================= *
 * BinarySearchTree interface
 * ========================================================================= */

#ifndef _BINARY_SEARCH_TREE_H_
#define _BINARY_SEARCH_TREE_H_

#include <stddef.h>
#include <stdbool.h>
#include "LinkedList.h"



/* Opaque Structure */
typedef struct tree_t BinarySearchTree;

BinarySearchTree* insert(BinarySearchTree*p, const void* key);

/* ------------------------------------------------------------------------- *
 * Creates an empty BinarySearchTree (or BST).
 *
 * The BST must later be deleted by calling freeBinarySearchTree().
 *
 * ARGUMENT
 * comparison_fn_t      A comparison function
 *
 * RETURN
 * bst                  A pointer to the BinarySearchTree, or NULL in case of
 *                      error
 *
 * COMPARISON FUNCTION
 * comparison_fn_t(a, b) < 0    <=> a < b
 * comparison_fn_t(a, b) = 0    <=> a == b
 * comparison_fn_t(a, b) > 0    <=> a > b
 *
 * USAGE (example for doubles: http://www.gnu.org/software/libc/manual/html_node/Comparison-Functions.html)
 * int compare_doubles(const void* a, const void* b)
 * {
 *     const double* a_ = (const double*)a;
 *     const double* b_ = (const double*)b;
 *     return (*a_ > *b_) - (*a_ < *b_)
 * }
 * ...
 * BinarySearchTree bst = newBST(&compare_doubles);
 * ------------------------------------------------------------------------- */

BinarySearchTree* newBST(int comparison_fn_t(const void *, const void *));

/* ------------------------------------------------------------------------- *
 * Frees the allocated memory of the given BinarySearchTree.
 *
 * PARAMETERS
 * bst          A valid pointer to a BinarySearchTree object
 * freeContent  Whether to free the content as well.
 *
 * NOTE
 * The const qualifier will be exceptionally discarded if freeContent == true
 * to allow the deletion of the content.
 * ------------------------------------------------------------------------- */

void freeBST(BinarySearchTree* bst);

/* ------------------------------------------------------------------------- *
 * Counts the number of elements/nodes stored in the given BinarySearchTree.
 *
 * PARAMETERS
 * bst          A valid pointer to a BinarySearchTree object
 *
 * RETURN
 * nb           The amount of elements stored in bst
 * ------------------------------------------------------------------------- */

size_t sizeOfBST(const BinarySearchTree* bst);



/* ------------------------------------------------------------------------- *
 * Inserts a new key-value pair in the provided BinarySearchTree. This
 * specific implementation of the BST must handle duplicate keys.
 *
 * PARAMETERS
 * bst          A valid pointer to a BinarySearchTree object
 * key          The key of the new element or of the element to update
 * value        The value to store
 *
 * RETURN
 * res          A boolean equal to true if the new element was successfully
 *              inserted, false otherwise
 * ------------------------------------------------------------------------- */

BinarySearchTree* insertInBST(BinarySearchTree* bst, const void* key, const void* value);



/* ------------------------------------------------------------------------- *
 * Return the value associated to that key, if any
 *
 * PARAMETERS
 * bst          A valid pointer to a BinarySearchTree object
 * key          The key to look for
 *
 * RETURN
 * res          One of the value corresping to that key. Or NULL if the key
 *              is not present in the BST
 * ------------------------------------------------------------------------- */

const void* searchBST(BinarySearchTree* bst, const void* key);

/* ------------------------------------------------------------------------- *
 * Finds a set of elements in the provided BinarySearchTree whose the keys
 * are included in a range [key1, key2] and returns their values. The values
 * are sorted in the increasing order of the keys.
 *
 * PARAMETERS
 * bst          A valid pointer to a BinarySearchTree object
 * keyMin       Lower bound of the range (inclusive)
 * keyMax       Upper bound of the range (inclusive)
 *
 * RETURN
 * ll           A linkedList containing the element in the given range, or
 *              NULL in case of allocation error.
 *
 * NOTES
 * The linkedList must be freed but not its content
 * If no elements are in the range, the function returns an empty linked-list
 * ------------------------------------------------------------------------- */
LinkedList * getInRange(const BinarySearchTree* bst, void * keyMin, void * keyMax);


#endif // !_BINARY_SEARCH_TREE_H_

#include <stddef.h>
#include <stdlib.h>
#include <stdio.h>
#include "BinarySearchTree.h"
#include "LinkedList.h"

#define COUNT 10 

// Program to print binary tree in 2D 
#include<stdio.h> 
#include<malloc.h> 
  
// A binary tree node 
struct tree_t{
    const void *data;
    int count;
    const void *key;
    struct tree_t* lchild;
    struct tree_t* rchild;
};
struct Node 
{ 
    int data; 
    struct Node* left, *right; 
}; 
  
// Helper function to allocates a new node 
BinarySearchTree* newNode(int data) 
{ 
    BinarySearchTree* node = malloc(sizeof(struct tree_t)); 
    node->data = data; 
    node->lchild = node->rchild = NULL; 
    return node; 
} 
  
// Function to print binary tree in 2D 
// It does reverse inorder traversal 
void print2DUtil(BinarySearchTree *root, int space) 
{ 
    // Base case 
    if (root == NULL) 
        return; 
  
    // Increase distance between levels 
    space += COUNT; 
  
    // Process right child first 
    print2DUtil(root->rchild, space); 
  
    // Print current node after space 
    // count 
    printf("\n"); 
    for (int i = COUNT; i < space; i++) 
        printf(" "); 
    printf("%d\n", root->key); 
  
    // Process left child 
    print2DUtil(root->lchild, space); 
} 
  
// Wrapper over print2DUtil() 
void print2D(BinarySearchTree* root) 
{ 
   // Pass initial space count as 0 
   print2DUtil(root, 0); 
} 
  
// Driver program to test above functions 


int compare_doubles(const void* a, const void* b)
{
    const double* a_ = (const double*)a;
    const double* b_ = (const double*)b;
    return (*a_ > *b_) - (*a_ < *b_);
}





BinarySearchTree* newBST(int comparison_fn_t(const void *, const void *)){
    BinarySearchTree *t = NULL;
    
    t = (struct tree_t *)malloc(sizeof(struct tree_t));
    t->data = NULL;
    t->key = NULL;
    t->lchild = t->rchild = NULL;
    return t;
    
    

}

void freeBST(BinarySearchTree* bst){
        if (bst == NULL)
        {
            return;
        }
        freeBST(bst->lchild);
        freeBST(bst->rchild);
        free(bst);
        
}



size_t sizeOfBST(const BinarySearchTree* bst){
    if (bst == NULL)
    {
        return 0;
    }
    return 1 + sizeOfBST(bst->lchild) + sizeOfBST(bst->rchild);

}

BinarySearchTree* insertInBST(BinarySearchTree* bst, const void* key, const void* value){
    BinarySearchTree *t = NULL;

    

    if (bst == NULL)
    {
        t = (struct tree_t *)malloc(sizeof(struct tree_t));
        t->key = key;
        t->data = value;
        t->lchild = t->rchild = NULL;
        return t;
    }
    /*if (key == bst->key)
        bst->key = insertInLinkedList(bst->data, value);*/
    
    if (key < bst->key)
        bst->lchild = insertInBST(bst->lchild, key, value);
    else if (key >= bst->key)
        bst->rchild = insertInBST(bst->rchild, key, value );

    return bst;
 
}

const void* searchBST(BinarySearchTree* bst, const void* key){


    if (bst == NULL)
    {
        /*printf("element %d not found\n", *((int *)(&key)));*/
        return NULL;
    }
    else if (bst->key == key){
            //printf("element %d found his! data is %d \n", *((int *)(&key)), *((int *)(&bst->data)));
            searchBST(bst->rchild, key);
            return bst->key;
            
            
    }
    else if (bst->key > key)
        searchBST(bst->lchild, key);
    else if (bst->key < key)
        searchBST(bst->rchild, key);   

}

LinkedList * getInRange(const BinarySearchTree* bst, void * keyMin, void * keyMax){

    LinkedList * l = newLinkedList();

    
    if (bst == NULL){
        return NULL;
    }
    if (bst->key >= keyMin && bst->key <= keyMax){
        printf("%d\n",(bst->key));
        l = insertInLinkedList(l, bst->key);
        printf("%p\n", l); 
    }  
    if (bst->key > keyMin){
        getInRange(bst->lchild, keyMin, keyMax);
    }
    if (bst->key < keyMax ){
        getInRange(bst->rchild, keyMin, keyMax);
        
    }
    return l;
}

BinarySearchTree* insert(BinarySearchTree*p, const void* key)
{
    BinarySearchTree *t = NULL;
    if (p == NULL)
    {
        t = (struct tree_t *)malloc(sizeof(struct tree_t));
        t->data = key;
        t->lchild = t->rchild = NULL;
        return t;
    }
    if (key < p->data)
        p->lchild = insert(p->lchild, key);
    else if (key > p->data)
        p->rchild = insert(p->rchild, key);

    return p;
}

void afficher_data(BinarySearchTree *p)
{
    if(p == NULL)
    {
        printf("_");
    }
    else{
        printf("[");
        afficher_data(p->lchild);
        printf(",%d,", *((int *)(&p->data)));
        afficher_data(p->rchild);
        printf("]");
    }
}

void afficher_keys(BinarySearchTree *p)
{
    if(p == NULL)
    {
        printf("_");
    }
    else{
        printf("[");
        afficher_keys(p->lchild);
        printf(",%d,", *((int *)(&p->key)));
        afficher_keys(p->rchild);
        printf("]");
    }
}

void show_data(BinarySearchTree *p)
{
    if(p){
    show_data(p->lchild);
    printf("%d\n###data",*((int *)(&p->data)));
    show_data(p->rchild);
    }
    
}

void show_key(BinarySearchTree *p)
{
    if(p){
    show_key(p->lchild);
    printf("%d\n###keys",*((int *)(&p->key)));
    show_key(p->rchild);
    }
    
}




int main()
{
    BinarySearchTree *root = NULL;
    
    

    root = insertInBST(root, (void *)10, (void *)1);
    insertInBST(root,  (void *)20,(void *) 100);
    insertInBST(root,  (void *)30, (void *)2);
    insertInBST(root,  (void *)40, (void *)2);
    insertInBST(root,  (void *)32,(void *) 2);
    insertInBST(root,  (void *)33,(void *) 1000);
    insertInBST(root, (void *) 65,(void *) 1000);
    insertInBST(root,  (void *)2,(void *) 100);
    insertInBST(root,  (void *)1,(void *) 100);
    insertInBST(root,  (void *)100,(void *) 100);
    insertInBST(root,  (void *)570,(void *) 100);
    insertInBST(root,  (void *)540,(void *) 100);
    insertInBST(root,  (void *)490,(void *) 100);
    
    
    
    LinkedList * ll = newLinkedList();
    ll = getInRange(root, 10, 50);
/*    printf("%p\n",ll);
    ll = insertInLinkedList(ll, 15);
     printf("%p\n",ll);
    ll = insertInLinkedList(ll, 20);
     printf("%p\n",ll);
    ll = insertInLinkedList(ll, 25);

    printf("%p\n",ll);*/

    displayLinkedList(ll);
    //displayLinkedList(ll);
    //displayLinkedList(ll);

    




    printf("\n");
    printf("%ld\n",sizeOfBST(root));    





    /*struct Node *root   = newNode(1); 
    root->left   = newNode(2); 
    root->right  = newNode(3); 
  
    root->left->left  = newNode(4); 
    root->left->right = newNode(5); 
    root->right->left  = newNode(6); 
    root->right->right = newNode(7); 
  
    root->left->left->left  = newNode(8); 
    root->left->left->right  = newNode(9); 
    root->left->right->left  = newNode(10); 
    root->left->right->right  = newNode(11); 
    root->right->left->left  = newNode(12); 
    root->right->left->right  = newNode(13); 
    root->right->right->left  = newNode(14); 
    root->right->right->right  = newNode(15);  */
      
    /*print2D(root);*/


    freeBST(root);
   

}

标签： c