Thread: Converting C strings to list of characters

  1. #1
    Registered User
    Join Date
    Feb 2005
    Posts
    6

    Converting C strings to list of characters

    Hi,

    I'm doing an assignment at uni where I have to take a C string and convert it into a linked list of characters. I'm trying to do the function buildWord recursively but have run into a problem or two, mainly with where I can declare x = 0 I think.

    My code is as follows:
    Code:
    #include "boole.h"
    #include "listADT.h"
    #include <stdio.h>
    #include "wordADT.h"
    
    wordADT createWord()
    {
    	return createList();
    }
    
    wordADT buildWord (char str[])
    {
    	if(str[x] != '\0')
    		return createWord();
    	else
    		return consList(str[x++], createWord());
    }
    
    void displayWord( wordADT word)
    {
    	if(isEmptyList(word))
    		printf("\n");
    	else
    		printf("%c, ", headList(word));  displayWord(tailList(word));
    }
    
    int countChars( wordADT word )
    {
    	if(isEmptyList(word))
    		return 0;
    	else
    		return 1+ countChars(tailList(word));
    }
    
    boolean wordLess (wordADT word1, wordADT word2)
    {
    	if(headList(word1)>headList(word2))
    		return FALSE;
    	else if(headList(word1)==headList(word2))
    		return wordLess(tailList(word1), tailList(word2));
    	else
    		return TRUE;
    }
    
    boolean wordEqual ( wordADT word1, wordADT word2 )
    {
    	if(headList(word1)!=headList(word2))
    		return FALSE;
    	else if (headList(word1)==headList(word2))
    		return wordEqual(tailList(word1), tailList(word2));
    	else
    		return TRUE;
    }
    The rest of it compiles but I've not tested the it so there might be some problems but I'll sort them out when I come to test it.

    Also attached the header file for listADT.

  2. #2
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    Try something like
    Code:
    wordADT buildWord (char *str)
    {
        if(*str != '\0')
            return createWord();
        else
            return consList(str+1, createWord());
    }
    Of course its just a shot in the dark since you don't give us all the user defined functions and your header is lacking in any really meaningful comments.

  3. #3
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,218
    This isn't a very practical place to use recursion. Iteration is a much better approach.
    If you understand what you're doing, you're not learning anything.

  4. #4
    Registered User
    Join Date
    Feb 2005
    Posts
    6
    I'd already thought of doing it like that, but we've been told we have to declare each function as we've been given for their ease of marking. So it has to be done with str[] rather than *str

  5. #5
    Registered User
    Join Date
    Feb 2005
    Posts
    6
    Quote Originally Posted by itsme86
    This isn't a very practical place to use recursion. Iteration is a much better approach.
    We've been told it has to be done recursively or we lose marks.

  6. #6
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,218
    Ahh, you made the recursion sound like your idea rather than part of the assignment.
    If you understand what you're doing, you're not learning anything.

  7. #7
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    I'd already thought of doing it like that, but we've been told we have to declare each function as we've been given for their ease of marking. So it has to be done with str[] rather than *str
    Fine the make it str[]. It doesn't change what it really is.

  8. #8
    Registered User
    Join Date
    Feb 2005
    Posts
    6
    Quote Originally Posted by Thantos
    Fine the make it str[]. It doesn't change what it really is.
    But then surely I'm back to my issue of where I need to declare a variable to point to a particular character in the array.

  9. #9
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    Ok in a formal parameter list:
    str[] is exactly the same as *str. Which means you can just dereference it.

    Now looking at your function I really have no idea what your logic is.
    buildWord() isn't being called recursivly so I'm not sure where the recursion is happening.

    Try writing out your logic for us. Take us step by step in what you want to do. Doing so might help you to see what you need to do.

  10. #10
    Registered User
    Join Date
    Feb 2005
    Posts
    6
    Oops sorry I missed that out in this version of code. working on two machines when ftp from my host is down is doing my head in today.

    What I was meant to have for buildWord is:

    Code:
    wordADT buildWord (char str[])
    {
        if(str[x] != '\0')
            return createWord();
        else
            return consList(buildWord(str[x++]), createWord());
    }
    so what I want is:
    if the character at position x isn't the null character
    then add the character to the front of the list

    then using recursion to continue the above 2 stages until the null character is hit. At that stage I should have the characters backwards in the list.

  11. #11
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    Well think about it this way:
    We have "Hello World"
    We pass it to buildWord()
    At this time str is a pointer to the 'H'. We add it to the list.
    We then call buildWord again but increment the pointer by 1. That gives up the 'e'. We add it to the front of the list.
    We then call buildWord again but increment the pointer by 1. We then get the 'l'. We add it to the front of the list.
    Keep doing this until you hit the null.

    In psuedo C code
    Code:
    wordADT buildWord (char str[])
    {
      if ( *str == '\0' ) /* or str[0] == '\0' */
        return CreateAnEmptyList();
      else
      {
        return AddACharacterToList(*str, buildWord(str+1) ); /* or str[0] */
      }
    }
    So if we have reached the null character we are at the end of the string and need to construct a list. Then as the recursion unrolls we add the characters to the list.

  12. #12
    Registered User
    Join Date
    Feb 2005
    Posts
    6
    Thanks a lot Thantos all works great now.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Unknown memory leak with linked lists...
    By RaDeuX in forum C Programming
    Replies: 6
    Last Post: 12-07-2008, 04:09 AM
  2. singly linked circular list
    By DarkDot in forum C++ Programming
    Replies: 0
    Last Post: 04-24-2007, 08:55 PM
  3. Problem with linked list ADT and incomplete structure
    By prawntoast in forum C Programming
    Replies: 1
    Last Post: 04-30-2005, 01:29 AM
  4. problem with structures and linked list
    By Gkitty in forum C Programming
    Replies: 6
    Last Post: 12-12-2002, 06:40 PM
  5. Contest Results - May 27, 2002
    By ygfperson in forum A Brief History of Cprogramming.com
    Replies: 18
    Last Post: 06-18-2002, 01:27 PM