desperately need help with avl tree

This is a discussion on desperately need help with avl tree within the C Programming forums, part of the General Programming Boards category; i am required to create an avl tree that will store the lyrics of songs read in from a file. ...

  1. #1
    Registered User
    Join Date
    Oct 2009
    Posts
    1

    desperately need help with avl tree

    i am required to create an avl tree that will store the lyrics of songs read in from a file.
    i am then required to implement a function that will let the user enter a word query. the function is to search the avl tree and display the songs that the word is in, and the position(word number it is in the song)
    for some reason, some of the words are missing. i tried entering the first word in the song, but it doesnt exist in the tree.

    my insert function is as follow
    Code:
    AvlTree Insert( ElementType X, AvlTree T )
    {
      int i;
      struct Song *song, *prev;
      if( T == NULL )
      {
        /* Create and return a one-node tree */
        T = malloc( sizeof( struct AvlNode ) );
        if( T == NULL )
        {
          printf("Error allocating space");
          exit(EXIT_FAILURE);
        }
        else
        {
          T->Element = X;
          T->Height = 0;
          T->Left = T->Right = NULL;
        }
      }
      else
      {
        if( strcmp(X->string,T->Element->string)<0 )
        {
          T->Left = Insert( X, T->Left );
          if( Height( T->Left ) - Height( T->Right ) == 2 )
          {
            if( strcmp(X->string, T->Left->Element->string)<0 )
              T = SingleRotateWithLeft( T );
            else
              T = DoubleRotateWithLeft( T );
          }
        }
        else
        {
          if( strcmp(X->string,T->Element->string)>0 )
          {
            T->Right = Insert( X, T->Right );
            if( Height( T->Right ) - Height( T->Left ) == 2 )
            {
              if( strcmp(X->string, T->Right->Element->string)>0 )
                T = SingleRotateWithRight( T );
              else
                T = DoubleRotateWithRight( T );
            }
          }
          /*else if word is already in list*/
          if(strcmp(X->string,T->Element->string)==0)
          {
            song = T->Element->firstSong;
            while(song!=NULL && song->Number!=X->firstSong->Number)
            {
              prev=song;
              song=song->nextSong;
            }
            if(song == NULL)
            {
              prev->nextSong = X->firstSong;
            }
            else if(song->Number == X->firstSong->Number)
            {
              for(i=1;i<100;i++)
              {
                if(song->Position[i]==-1)
                {
                  song->Position[i]=X->firstSong->Position[0];
                  break;
                }
              }
            }
          }
        }
      }
      T->Height = Max( Height( T->Left ), Height( T->Right ) ) + 1;
       return T;
    }
    when i call the funtion, is just have
    Avltree T;
    while(blah blah)
    T = insert(word,T);

  2. #2
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    If T is not a pointer to a pointer, you cannot actually make it point to anything new. That is to say:
    Code:
    foo *p;
    ...
    bar( p ); /* p will not retain its new memory if we did something like... */
    ...
    void bar( foo *p )
    {
        p = malloc( sizeof *p ); /* won't actually do anything useful once this function returns... */
    }
    To make a variable retain a value change through a function call, you need a pointer to that type. Thus:
    Code:
    foo *p;
    ...
    bar( &p );
    ...
    void bar( foo **p )
    {
        *p = malloc( sizeof **p );
    }
    That's my at-a-glance guess as to what your problem is.


    Quzah.
    Hope is the first step on the road to disappointment.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Binary Tree Search
    By C++Newbie in forum C++ Programming
    Replies: 7
    Last Post: 04-05-2011, 01:17 AM
  2. Interpreter.c
    By moussa in forum C Programming
    Replies: 4
    Last Post: 05-28-2008, 05:59 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21