problem in sorting and searching

This is a discussion on problem in sorting and searching within the C++ Programming forums, part of the General Programming Boards category; Code: #include <iostream> #include <string> struct node { node* one; node* zero; char value; int amount; node (char x) { ...

  1. #1
    Just because ygfperson's Avatar
    Join Date
    Jan 2002
    Posts
    2,493

    problem in sorting and searching

    Code:
    #include <iostream>
    #include <string>
    
    struct node {
     node* one;
     node* zero;
     char value;
     int amount;
     node (char x) {
       one=NULL;
       zero=NULL;
       value=x;
       amount=1;
     }
     void add() {
      amount++;
     }
    };
    
    class huffman_tree {
    public:
    node *node_list[100];
    int list_size;
     int search(char x) {
       for (int i=0;i<list_size;i++) {
         if (node_list[i]->value==x) { return i;}
          }
     }
    
     void add(char x) {
      int temp;
      if (temp=search(x)) {
        node_list[temp]->add();
        return;
      }
      node_list[list_size]=new node(x);
      list_size++;
      node_list[list_size]=NULL;
     }
     huffman_tree() {
       list_size=0;
       node_list[0]=NULL;
     }
    
    
    
     void sort() {  bubblesort(); }
     void bubblesort()  {
       node* temp;
       int n=list_size;
       for (int i=0;i<n-1;++i)
        for (int j=1;j<n-i;++j)
         if (node_list[j-1]->value > node_list[j]->value) {
           temp=node_list[j];
           node_list[j]=node_list[j-1];
           node_list[j-1]=temp;
    
         }
     }
    
    };
    
    int main()
    {
    huffman_tree tree;
    
    
    string temp="hello";
    char letter;
    while (temp.length()) {
     letter=temp.at(0);
     temp.erase(0,1);
     tree.add(letter);
    }
    tree.sort();
    for (int i=0;i<tree.list_size;i++)
    
    }
    this is the complete code. node is a struct which contains a value, an ascii character, and an amount, the number of times this character appears. huffman_tree is a class which will receive incoming letters, sort 'em, and later on do all the compression work.
    this code works when i comment out the "if (search(x))..." block. right now it comes up with a segmentation error on the second letter.
    here's what i think's happening: (note: i put some cout statements to aid in debugging, then took them out when i posted the code)
    a string is created. i pull the letters off the beginning of the string until there are none left, and store each letter in char letter. each letter is sent to tree->add().
    tree->search() is supposed to return a non-zero if this letter was already added. in that event amount is supposed to increase by one on the letter to represent 2 of that letter. search isn't doing it's job. search() tests each node value and compares it to the given char. if yes, then it returns the position of the note. else it returns 0...

    i think i found the problem. so just answer this: at the end of a function is return 0; implied, or does it just return some random number?
    Last edited by ygfperson; 04-16-2002 at 06:37 PM.

  2. #2
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    This is the problem, like you said:
    Code:
    int search(char x) {
       for (int i=0;i<list_size;i++) {
         if (node_list[i]->value==x) { return i;}
       }
      // marker
     }
    This is all well and good unless list_size is less than or equal to 0, in which case the method returns a garbage value which the program later chokes on. The same thing will happen if you try to search for a value that isn't in the list.

    -Prelude
    My best code is written with the delete key.

  3. #3
    Just because ygfperson's Avatar
    Join Date
    Jan 2002
    Posts
    2,493
    it works when i add return 0 after the if condition. another problem (less serious):
    i change temp(the test string) to some wacky string like "gggkehyhhl". a for loop and a cout statement at the end of main() show the values of all the nodes. a string like "hello" outputs to the screen:
    ehlo
    the letters sorted alphabetically, each one used only once. (btw, the sort() function is a bubble sort, works fine. not gonna do any heavy sorting with it, so it should suffice)
    the wacky string above outputs:
    eggghkly
    the letter g is failed to be recognized, so it gets its own node each time it appears. for some reason, this affects only the first letter in the string. in "hello" h appeared only once so it didn't have problems.

    anyone see the problem?

  4. #4
    Just because ygfperson's Avatar
    Join Date
    Jan 2002
    Posts
    2,493
    nm, saw the problem. apparently when i return the index of the node the first letter is a zero, and it mistakes it for a "nothing found" message.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. *Help*in sorting and searching algorithm
    By yuentong in forum C++ Programming
    Replies: 1
    Last Post: 03-07-2009, 09:43 AM
  2. Doxygen failing
    By Elysia in forum A Brief History of Cprogramming.com
    Replies: 19
    Last Post: 04-16-2008, 01:24 PM
  3. hashing & searching
    By Micko in forum C++ Programming
    Replies: 9
    Last Post: 03-16-2004, 05:20 AM
  4. understanding searching and sorting
    By volk in forum C++ Programming
    Replies: 3
    Last Post: 04-30-2003, 09:44 AM
  5. sorting and searching
    By rattex33 in forum C Programming
    Replies: 2
    Last Post: 10-23-2002, 04:11 AM

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