Thread: Help with pointers and linked lists

  1. #1
    Registered User
    Join Date
    Feb 2011
    Posts
    16

    Help with pointers and linked lists

    Hello,
    I'm doing my university assignment which is about radix sort for strings using linked lists. Actually, I'm kind of new with pointers and linked lists.
    Each string has a maximum size of 15. In each iteration the index of character in the string moves backwards until zero. But I think there's a problem in the code that has to do with NULL pointers. Here's part of the code where the problem exists:
    Code:
    typedef struct Node
    {
        char word[MAXSIZ];
        struct Node *next;
    }Node;
    
    
    typedef struct Node *PtrToNode;
    typedef PtrToNode Position;
    typedef PtrToNode List;
    
    <some code>
    //This is part of the Sort function
    
    // arrays A and B are of type List and they have the header nodes added to them earlier in the code
    int k;
    int index =15;
    for(k=1;k<=index;k++)
        {
            for (i=0; i<number_of_alpha;i++) // number _of_alpha is 53
            {
                p=A[i]->next;                 //p points to the first node under A[i]
                while(p!=NULL)
                  {
                        A[i]->next=p->next; // Link the header node with the node that is after the previous node 
                       
                         if (strlen(p->word) < (index-k))
                        {
                            add(B[0],p);
                         }
                        else
                        {
    
                            if ((p->word[index-k] >= 'A') && (p->word[index-k] <= 'Z'))
                                add(B[(p->word[index-k] - 64)],p);
                            else if ((p->word[index-k] >= 'a') && (p->word[index-k] <= 'z'))
                                    add(B[(p->word[index-k] -70)],p);
                        }
                             p=A[i]->next; //Move p to point to the next node(which is now   linked to the header node)
                  }
            }
    
            if(++k > index)
            break;
    
            for (j=0;j<number_of_alpha;j++)
            {
                p=B[j]->next;
                    while (p!= NULL)
                    {
                        B[j]->next=p->next;
    
                        if (strlen(p->word) < (index-k) )    // If strlen is less than 15 add to the first linked list in the array (under A[0])
                        {
                            add(A[0],p);
                        }
                        else
                        {
    
                            if ((p->word[index-k] >= 'A') && (p->word[index-k] <= 'Z'))
                                add(A[(int)(p->word[index-k] - 64)],p);
                            else if ((p->word[index-k] >= 'a') && (p->word[index-k] <= 'z'))
                                add(A[(int)(p->word[index-k] -70)],p);
                        }
                        p=B[j]->next;
                    }
                }
    <some code>
    
    // This function adds each node to the beginning of the linked list
    void add(List L, Position p)    // L points to header , p points to the Node
    {
        p->next = L->next;
        L->next = p;
    }
    If one of the strings I enter is "Jane" then the array that represent this string must be filled to only sub4(including '\0'), so it's length is less than 15. After a number of iterations, (index-k) will equal 3. This is where it begins to check the first letter from the right. But eveytime it comes to this stage somehow the pointer p loses the data or points to NULL. And ends up giving me two empty arrays A and B without the original data.
    Is there anything that I missed in the code?
    Any help would be appreciated.

  2. #2
    Registered User
    Join Date
    Feb 2011
    Posts
    16
    I really appreciate someone's help.

  3. #3
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,909
    This isn't really any different from your other thread, and I don't see much of an overhaul of your type and pointer use (which is thoroughly confusing, as rags_to_riches and my self pointed out). Did you go through tutorials? Did you successfully make a simple linked list, insert and delete nodes, glue two lists together and print it all out?

    Code:
    typedef struct Node
    {
        char word[MAXSIZ];
        struct Node *next;
    }Node;
    
    typedef struct Node *PtrToNode;
    typedef PtrToNode Position;
    typedef PtrToNode List;
    This is confusing. You have two identical types (Position and List), for no apparent reason. Your PtrToNode is just an extra level of confusing indirection in your typedefs, and it masks the pointerness of the type, making it easy to forget exactly what it is you're working with. How about something simple like:
    Code:
    struct NodeStruct {
        char word[MAXSIZ+1];  // assuming MAXSIZ is 15, you need an extra character for the terminating '\0'
        struct Node *next;
    };
    typedef struct NodeStruct    Node;
    Then, when you declare a list, you just do:
    Code:
    Node *list;
    Also, your use of a header node is unusual, especially since it doesn't contain any relevant header information (it's just a plain old node with no data). Generally, a null pointer signifies an empty list:
    Code:
    list = NULL;  // "initialize" to an empty list
    Forget you're doing a radix sort for the time being, and just worry about your list manipulation. No point in sorting a list of data if the list is wrong to begin with. You should write a number of functions to manage your list, specifically things like prepend (stick a new node on the front of the list), append (stick a new node on the back), maybe an insert node to put it somewhere in the middle of the list (as specified by a parameter), and a print function to make sure your list has the correct data and is properly linked. Given the algorithm, I might make a function that concatenates two lists as well, for when you join up the parts. There may be other function you find you need later. Write these in small chunks and test as you go, then you can be sure that your list manipulation is solid and there are no wacky pointer issues there.

    The general rule I'm getting at here is a good design/development process. First, fully understand your problem. Figure out what data structures you need, then, come up with a solution on paper using said data structures. 90% of "programming" is not actually writing code. Then, once you have a full understanding and solution, you start coding, in small chunks, testing as you go.

  4. #4
    Registered User
    Join Date
    Feb 2011
    Posts
    16
    I went through tutorials and got a better understanding of linked lists, and I did test wether the function is building the linked list properly. I changed a part of the code and put it in a function, and it worked! Honestly I don't know what's the difference. I changed the contents of the two while-loops with the following code:
    Code:
    while(p!=NULL)
    {
                  A[i]->next=p->next;
                add(B[charToInt(p->word[k])],p);
                  p=A[i]->next
    }
    
    ... and the second while-loop:
    
    while(p!=NULL)
    {
                  B[i]->next=p->next;
                add(A[charToInt(p->word[k])],p);
                  p=B[i]->next
     }
    
    <some code>
    int charToInt(char ch)
    {
        if(ch>= 'A' && ch<= 'Z')
        return (int)(ch-64);
        else if(ch>= 'a' && ch <='z')
        return (int)(ch-70);
        else return 0;
    }
    I only added a new function as you see which is charToInt().

    Again thanks for your advise.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Pointers to pointers in linked lists
    By G4B3 in forum C++ Programming
    Replies: 2
    Last Post: 07-23-2008, 03:54 AM
  2. pointers and linked lists in place of arrays
    By kordric in forum C++ Programming
    Replies: 8
    Last Post: 05-14-2008, 10:59 AM
  3. Double pointers and linked lists.
    By simo_r in forum C Programming
    Replies: 2
    Last Post: 05-06-2008, 04:25 AM
  4. Linked Lists & Pointers
    By fkheng in forum C Programming
    Replies: 4
    Last Post: 06-10-2003, 07:26 AM
  5. Problem with pointers and linked lists
    By bsimbeck in forum C Programming
    Replies: 2
    Last Post: 02-21-2003, 11:05 AM