Computer Science Canada

structs, pointers and linked list
Author:  jin [ Sun Nov 26, 2006 12:35 am ]
Post subject:  structs, pointers and linked list
Hey i am using a struct and forming a linked list when i output it i get the element and then a weird symbol followed by w.

Struct

code:

struct WordListNode
{
  char *word;
  int count;
  WordListNode *next ;
};


Adding in list

code:

void addInOrder(WordListNode *&head, char data[])
{
  WordListNode *previous = NULL ;
  WordListNode *current  = head ;
 
  // notice use of short-circuit evaluation in next line
  while (current != NULL && strcmp (current->word, data)<0)
  {
    previous = current ;
    current = current->next ;
  }
 
  WordListNode *newNode = new WordListNode ;
  newNode->word = new char [strlen(data)+1] ;
  strcpy(newNode->word, data) ;
 
  if (previous == NULL) // we're adding at the head of the list
  {
    newNode->next = head ;
    head = newNode ;
  }
  else // this works in the middle or end of list
  {
    newNode->next = current ;
    previous->next = newNode ;
  }
}


Thanks
Author:  md [ Sun Nov 26, 2006 1:31 am ]
Post subject: 
Except for the ugly C strings (std::string is your friend) I see nothing wrong with this code. Can you post all of your code? That would make debugging easier.
Author:  jin [ Sun Nov 26, 2006 1:41 am ]
Post subject: 
code:

// Importing Libraries

# include <iostream>
# include <fstream>
# include <cstring>
# include <cctype>

using namespace std;

// Global Variable declaration

struct WordListNode
{
  char *word;
  int count;
  WordListNode *next ;
};

const int MAX_WORD_LENGTH = 25;
int Number_Words;
int Number_Words_Repeated;

// Function declaration
void Remove_Punctuation (char key [MAX_WORD_LENGTH + 1]);
void Read (WordListNode *&head, char file[]);
void Change_Case (char word [MAX_WORD_LENGTH + 1]);
void printList(WordListNode *head);
void addInOrder(WordListNode *&head, char data[]);

//////////////////////////////////////////////////////////////////////////////
/////////////////////////////   MAIN METHOD    //////////////////////////////
int main ()
{

    // Variable declaration

      WordListNode *head = NULL ;

    char key [MAX_WORD_LENGTH + 1];
    int result;

    // Function Calls
    char file[] = "test.txt";

    Read (head,  file);
    printList(head);

    cin >> result;
    return 0;
}

void printList(WordListNode *head)
{
  WordListNode *current = head ;
 
  cout << "(" ;
  while (current != NULL)
  {
    cout << current->word ;
    if (current->next != NULL) cout << " " ;
    current = current->next ;
  }
  cout << ")" << endl ;
}


void Remove_Punctuation (char key [MAX_WORD_LENGTH + 1])
{
    // Checks to see if either the first or last char are punctuations and if
    //they are then it removes them.

    for (int i = 0 ; i < strlen (key) ; i++)
    {
        if (ispunct (key [i]) && i == 0)
        {
            for (int j = i ; j < strlen (key) - 1 ; j++)
            {
                key [j] = key [j + 1];
            }

            key [strlen (key) - 1] = '\0';
        }


        if (ispunct (key [i]) && i == strlen (key) - 1)
        {
            key [i] = '\0';
        }
    }

    // Indicates the end of the function.

    return;
}

void Change_Case (char word [MAX_WORD_LENGTH + 1])
{
    // Changes the letters of the word into lower case.

    for (int i = 0 ; i < strlen (word) ; i++)
    {
        word [i] = tolower (word [i]);
    }

    // Indicates the end of the function.

    return;
}

void Read (WordListNode *&head, char file[])
{
    // Reads in the words from a file.

    // Variable declaration

    ifstream inFile;
    inFile.open (file);

    if (inFile.fail ())
    {
        cout << "\nUnable to open file containing puzzle. Program exiting.\n\n";
        exit (1);
    }

    int y = 0;
    int x = 0;
    char letter;
    char word [MAX_WORD_LENGTH+1];

    // Reads in words into the array and not empty spaces or punctuations.

    while (!inFile.eof ())
    {
        inFile >> (letter);
        while ((!isspace (letter)) && (y < MAX_WORD_LENGTH))
        {
            word [y] = (letter);
            y++;
            inFile.get (letter);
        }
        if (y != 0 && !inFile.eof ())
        {
            Change_Case (word);
            do
            {
                Remove_Punctuation (word);
            }
            while (ispunct (word [0]) || ispunct (word[strlen(word) - 1]));
            if (word [0] == '\0')
            {
                x--;
            }
            addInOrder(head, word);
            y = 0;
            x++;
        }

    }
    inFile.close ();
    Number_Words = x;

    // Indicates the end of the function.

    return;
}

void addInOrder(WordListNode *&head, char data[])
{
  WordListNode *previous = NULL ;
  WordListNode *current  = head ;
 
  // notice use of short-circuit evaluation in next line
  while (current != NULL && strcmp (current->word, data)<0)
  {
    previous = current ;
    current = current->next ;
  }
 
  WordListNode *newNode = new WordListNode ;
  newNode->word = new char [strlen(data)+1] ;
  strcpy(newNode->word, data) ;

  if (previous == NULL) // we're adding at the head of the list
  {
    newNode->next = head ;
    head = newNode ;
  }
  else // this works in the middle or end of list
  {
    newNode->next = current ;
    previous->next = newNode ;
  }
}
Author:  md [ Sun Nov 26, 2006 11:02 am ]
Post subject: 
Oh boy...

So g++ gives me the following warnings:
g++ wrote:

test.c: In function 'int main()':
test.c:39: warning: unused variable 'key'
test.c: In function 'void Remove_Punctuation(char*)':
test.c:72: warning: comparison between signed and unsigned integer expressions
test.c:76: warning: comparison between signed and unsigned integer expressions
test.c:85: warning: comparison between signed and unsigned integer expressions
test.c: In function 'void Change_Case(char*)':
test.c:100: warning: comparison between signed and unsigned integer expressions

While they are not serious, you may want to look into them. Second, since you are using C++ I HIGHLY recommend using std::string instead of C strings.

The problem with your code seems to stem from Read(). When you read your words you do not terminate your C string properly (you wouldn't have to with std::string!). Aside from that and some rather bizzare logic I can't see anything immediately wrong.

There are also a whole lot of code formatting things and code inconsistencies that should be fixed... Wink

Because I am in a good mood... here ya go Razz
c++:

// Importing Libraries

#include <iostream>
#include <fstream>
#include <string>
#include <ctype.h>


// Global Variable declaration

struct WordListNode
{
        std::string word;
        WordListNode *next ;
};

struct WordList
{
        unsigned short n_words;
        WordListNode *head;
};


void RemovePunctuation(std::string what);
void Read (WordList &list, std::string file);
void PrintList(WordList list);
void AddInOrder(WordList &list, std::string data);

int main ()
{
        WordList list;

    Read(list,  "test.txt");
    PrintList(list);

    return 0;
}

void PrintList(WordList list)
{
        WordListNode *current = list.head;

        std::cout << "(";
        while (current != NULL)
        {
                std::cout << current->word;
                if (current->next != NULL)
                        std::cout << " ";
               
                current = current->next;
        }
        std::cout << ")" << std::endl;
}


void RemovePunctuation(std::string what)
{
    // Checks to see if either the first or last char are punctuations and if
    //  they are then it removes them.

    while( ispunct(what[0]) && what.length() >= 1 )
        what.erase(what.begin());
   
    while( ispunct(what[what.length()]) && what.length() >= 1 )
        what.erase(--what.end());

}

void Read (WordList &list, std::string file)
{
    // Reads in the words from a file.
        list.head = 0;
        list.n_words = 0;

    std::ifstream inFile(file.c_str());

    if (inFile.fail() )
    {
        std::cout << "\nUnable to open file containing puzzle. Program exiting." << std::endl << std::endl;
        exit (1);
    }

    char letter;
    std::string word;

    while (!inFile.eof ())
    {
        word = "";
        do
        {
            inFile.get(letter);
                if( !isspace (letter) )
                word += tolower(letter);
            else
                break;

        }
        while ( !inFile.eof() );

                if( inFile.eof() || word == "")
                        break;       

            RemovePunctuation (word);
            
            AddInOrder(list, word);
            list.n_words++;
    }
    inFile.close ();

}

void AddInOrder(WordList &list, std::string data)
{
        WordListNode *previous = NULL;
        WordListNode *current  = list.head;

        while (current != NULL && current->word < data )
        {
                previous = current;
                current = current->next;
        }

        WordListNode *newNode = new WordListNode;
        newNode->word = data;

        if (previous == NULL) // we're adding at the head of the list
        {
                newNode->next = list.head;
                list.head = newNode;
        }
        else // this works in the middle or end of list
        {
                newNode->next = current;
                previous->next = newNode;
        }
}


All using std::strings, etc. I also fixed most (if not all) of hte formatting problems, but I left some of the extraneous comments.
Author:  jin [ Sun Nov 26, 2006 12:33 pm ]
Post subject: 
Thanks but we are supposed to use c-strings and also have not learned the format style you use. Here is my finished program if you have any comments on how to make better please let me know. (especially about the deletelist function). This basically reads words from a file and stores them in a linked list and how many times they appear. It also lets you search for words in the list.

code:

#include <iostream>
#include <fstream>
#include <cstring>
#include <cctype>

using namespace std;

struct WordListNode
{
    char * word;
    int count;
    WordListNode * next;
}
;

const int MAX_WORD_LENGTH = 25;
int Number_Words;
int Number_Words_Repeated;

void readWordList (WordListNode * & head, char file[]);
void cleanWord (char word[]);

void addInOrder (WordListNode * & head, char data[]);
void printList (WordListNode * head);
WordListNode * search (WordListNode * head, char data[]);
void printNode (WordListNode * head);
void deleteList (WordListNode * head);

int main ()
{

    WordListNode * head = NULL;


    char file[] = "Test.txt";

    readWordList (head, file);

    printList (head);

    cout << endl << Number_Words << " words read." << endl;
    cout << Number_Words - Number_Words_Repeated << " unique words found." << endl;


    char input [MAX_WORD_LENGTH + 1];
    do
    {
        cout << "Please enter a word to search for: ";
        cin >> input;

        cleanWord (input);
        if (isalpha (input [0]))
        {
            WordListNode * found = search (head, input);
            if (found != NULL)
                printNode (found);
            else
                cout << "\"" << input << "\" NOT FOUND" << endl;
        }

    }
    while (isalpha (input [0]));

    deleteList (head);
    cout<<"Press any key to exit."
    cin >> input;

    return 0;
}

void deleteList (WordListNode * head)
{
    WordListNode * previous = NULL;
    WordListNode * current = head;

    while (current != NULL)
    {
        previous = current;
        current = current - > next;
        delete previous;
    }
    head = NULL;
}

void printList (WordListNode * head)
{
    WordListNode * current = head;

    while (current != NULL)
    {
        cout << current - > word << " (" << current - > count << ")";
        cout << endl;
        current = current - > next;
    }
}

void printNode (WordListNode * head)
{
    cout << head - > word << " (" << head - > count << ")";
    cout << endl;
}

WordListNode * search (WordListNode * head, char data[])
{
    WordListNode * repeat;
    for (repeat = head ; repeat != NULL && strcmp (repeat - > word, data) != 0 ; repeat = repeat - > next)
        ;
    return repeat;
}

void addInOrder (WordListNode * & head, char data[])
{
    WordListNode * previous = NULL;
    WordListNode * current = head;
    WordListNode * repeat;

    //for (repeat = head;repeat!=NULL && strcmp(repeat->word,data)!=0;repeat=repeat->next);
    repeat = search (head, data);
    if (repeat != NULL)
    {
        repeat - > count = repeat - > count + 1;
        Number_Words_Repeated++;
    }

    else
    {
        // notice use of short-circuit evaluation in next line
        while (current != NULL && strcmp (current - > word, data) < 0)
        {
            previous = current;
            current = current - > next;
        }

        WordListNode * newNode = new WordListNode;
        newNode - > word = new char [strlen (data) + 1];
        strcpy (newNode - > word, data);
        newNode - > count = 1;

        if (previous == NULL) // we're adding at the head of the list
        {
            newNode - > next = head;
            head = newNode;
        }
        else // this works in the middle or end of list
        {
            newNode - > next = current;
            previous - > next = newNode;
        }
    }
}

void readWordList (WordListNode * & head, char file[])
{

    ifstream inFile;
    inFile.open (file);

    if (inFile.fail ())
    {
        cout << "\nUnable to open file. Program exiting.\n\n";
        exit (1);
    }


    while (!inFile.eof ())
    {
        char input [MAX_WORD_LENGTH + 1];

        inFile >> input;
        cleanWord (input);

        if (strlen (input) > 0) //&& !inFile.eof())
            // Only add the word to the list if
            // 1) it is non-empty ('words' that were all punctuation will be excluded
            //    this way, and
            // 2) eof() is not set (otherwise the data in 'input' is bogus)
            {
                addInOrder (head, input);
                Number_Words++;
            }
        //if (input!='\0')
    }
    inFile.close ();
}

void cleanWord (char s[])
{
    char temp [MAX_WORD_LENGTH + 1];

    strncpy (temp, s, MAX_WORD_LENGTH);

    // find index of first alpha/digit
    int i = 0;
    while (temp [i] != '\0' && !(isalpha (temp [i]) || isdigit (temp [i])))
        i++;

    // copy remaining characters, but remember where last alpha/digit stored
    int last_alphanum = i;
    int j = 0;
    s [0] = '\0';
    while (temp [i] != '\0')
    {
        s [j] = static_cast < char > (tolower (temp [i]));
        if (isalpha (temp [i]) || isdigit (temp [i]))
            last_alphanum = j;
        i++;
        j++;
    }
    s [last_alphanum + 1] = '\0'; // remove trailing punctuation
}

:


You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy