Thread: Creating a Sorted Linked List

  1. #1
    Registered User
    Join Date
    Nov 2011
    Posts
    46

    Creating a Sorted Linked List

    So I've gotten to the point where my data is being read in correctly in my getData function, but it crashes when I try to create the linked list..
    Code:
    /*    Test driver for list functions.
           Written by:
           Date:
    */
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    #define GPA_DS "gpaDS.txt"
    #define MAX_SIZE 1000
    
    //    Global Declarations
    
    typedef struct
    {
        char pin[4];
        char *name;
        double gpa;
    }   STU;
    typedef struct nodeTag
    {
        STU            data;
        struct nodeTag* link;
    } NODE;
    
    //    Function Declarations
    NODE* insertNode (NODE*  pList, NODE*  pPre, STU  item);
    int  searchList (NODE*  pList, NODE**   pPre,
                      NODE** pCur,  char* target);
    void  printList  (NODE*  pList);
    NODE* buildList  (char*  fileID);
    int  getData    (FILE*  fpData, STU* pData);
    
    
    //    Header file to include functions (Not in text)
    
    int main (void)
    {
    //    Local Declarations
        NODE*  pList;
        NODE*  pPre;
        NODE*  pCur;
        STU   data;
    
    //    Statements
        printf("Begin list test driver\n\n");
    
        //    Build List
        pList = buildList(GPA_DS);
        if (!pList)
        {
            printf("Error building chron file\a\n");
            exit  (100);
        } // if
        printList (pList);
    
        printf("\nTests complete.\n");
    
        system("pause");
        return 0;
    } // main
    /*    ==================== insertNode ====================
        This function inserts a single node into a linear list.
           Pre   pList is pointer to the list; may be null
                 pPre points to new node’s predecessor
                 item contains data to be inserted
           Post  returns the head pointer
    */
    NODE* insertNode (NODE* pList, NODE* pPre, STU item)
    {
    //    Local Declarations
        NODE* pNew;
    
    //    Statements
        if (!(pNew  = (NODE*)malloc(sizeof(NODE))))
            printf("\aMemory overflow in insert\n"), exit (100);
    
        pNew->data = item;
        if (pPre == NULL)
        {
            // Inserting before first node or to empty list
            pNew->link  = pList;
            pList       = pNew;
        } // if pPre
        else
        {
            // Inserting in middle or at end
            pNew->link = pPre->link;
            pPre->link = pNew;
        } // else
        return pList;
    }    // insertNode
    
    /*    ==================== searchList ====================
        Given key value, finds the location of a node
           Pre   pList points to a head node
                 pPre points to variable to receive pred
                 pCur points to variable for current node
                 target is key being sought
           Post  pCur points to first node with >= key
                 -or- null if target > key of last node
                 pPre points to largest node < than key
                 -or- null if target < key of first node
                 function returns true if found
                                  false if not found
    */
    int searchList (NODE*  pList, NODE**   pPre,
                     NODE** pCur,  char* target)
    {
    //    Local Declarations
        int found = 0;
    
    //    Statements
        *pPre = NULL;
        *pCur = pList;
    
        // start the search from beginning
        while (*pCur != NULL && (strcmp(target, (*pCur)->data.pin) > 0))
        {
            *pPre = *pCur;
            *pCur = (*pCur)->link;
        } // while
    
        if (*pCur && (strcmp(target, (*pCur)->data.pin) == 0))
           found = 1;
        return found;
    }    // searchList
    
    /*    Traverse and print a linear list.
           Pre   pList is a valid linear list
           Post  List has been printed
    */
    void printList (NODE* pList)
    {
    //    Local Declarations
        NODE* pWalker;
    
    //    Statements
        pWalker = pList;
        printf("List contains:\n");
    
        while (pWalker)
        {
            printf("%s %s %4.2lf\n", pWalker->data.pin, pWalker->data.name, pWalker->data.gpa);
            pWalker = pWalker->link;
        } // while
        printf("\n");
        return;
    } // printList
    
    /*    ==================== buildList ====================
        This program builds a key-sequenced linear list.
           Pre   fileID is file that contains data for list
           Post  list built
                 returns pointer to head of list
    */
    NODE* buildList (char* fileID)
    {
    //    Local Declarations
        STU  data;
        NODE* pList;
        NODE* pPre;
        NODE* pCur;
        FILE* fpData;
    
    //    Statements
        pList = NULL;
    
        fpData = fopen(fileID, "r");
        if (!fpData)
        {
            printf("Error opening file %s\a\n", fileID);
            system("pause");
            //exit (210);
        } // if open fail
    
        while (getData (fpData, &data))
        {
            // Determine insert position
            searchList (pList, &pPre, &pCur, data.pin);
            pList = insertNode(pList, pPre, data);
        } // while
        return pList;
    } // buildList
    
    /*    ==================== getData ====================
        Reads data from file.
           Pre   fpData is an open file
                 pData is pointer to input structure
           Post  data read
                 returns success/failure
    */
    
    int getData (FILE* fpData, STU* pData)
    {
    //    Local Definitions
        int ioResult;
        char temp[MAX_SIZE];
        char *pGpa, *pEnd, *pName;
    
    //    Statements
        fgets(temp, sizeof(temp), fpData);
    
        sscanf(temp, "%4s", pData->pin);
    
        pGpa = strrchr(temp, ';') + 1;
        pData->gpa = strtod(pGpa, &pEnd);
    
        *pGpa = '\0';
        pName = temp + sizeof(pData->pin);
        pData->name = (char *)calloc (strlen(pName) + 1, sizeof(char));
        if(!pData->name)
            printf("Error! Out of memory\n");
        strcpy(pData->name, pName);
    
        printf("%s %s %.2lf\n", pData->pin, pData->name, pData->gpa);
        ioResult = 1;
        //system("pause");
        if (ioResult == 1)
           return 1;
        else
           return 0;
    }    // getData
    I'm getting really frustrated.. I know there's something in the buildList function but I can't seem to find the bug..

  2. #2
    Registered User
    Join Date
    Nov 2011
    Posts
    46
    The data is in the format:
    40T Trapp, Dave; 3.9

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    So what line does your debugger say it is crashing on, and what is the crash message?
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. sorted linked list
    By budala in forum C Programming
    Replies: 12
    Last Post: 07-29-2009, 08:47 AM
  2. Creating a Sorted Linked List, Help Please!
    By larry_2k4 in forum C Programming
    Replies: 4
    Last Post: 04-28-2009, 01:12 AM
  3. Sorted Linked List...What am i doing wrong!
    By S15_88 in forum C Programming
    Replies: 9
    Last Post: 03-20-2008, 03:29 PM
  4. creating a sorted list
    By S15_88 in forum C Programming
    Replies: 3
    Last Post: 03-20-2008, 01:14 AM
  5. sorted linked list
    By Unregistered in forum C++ Programming
    Replies: 1
    Last Post: 02-03-2002, 09:11 PM

Tags for this Thread