Thread: Sorted Linked Lists

  1. #1
    Registered User
    Join Date
    Oct 2019
    Posts
    12

    Question Sorted Linked Lists

    I have been tasked to update code provided to me to what in class is called the "Ultimate Linked List". I am having some issues with removing errors in the code after adding what I think is necessary to complete it. I have listed the code that I have edited into this text block.
    Commented out code is the code that I am replacing, the replacement code is directly below the blocked portion with the same name.

    I have attached all the code in a file as well, due to the way our class works we create Projects in DevC++ rather than everything being held in a single source file. Sorry for the inconvenience.

    Any assistance with fixing the compile-time errors is very appreciated!
    LLSList.cpp
    LLSList.h
    main.cpp

    Note: This is an assignment for a class I am currently taking.

    Code:
    // Implementation file for List
    #include <iostream>
    #include "LLSList.h"
    
    struct LNode {
        int item;
        LNode* next;
        LNode* prev;
    };
    
    LLSList::LLSList() {
      ListStart=ListEnd;
      ListEnd=NULL; 
    }
    
    LLSList::~LLSList() {
      LNode* tempPtr;
      while (ListStart != NULL) {
        tempPtr = ListStart;
        ListStart = ListStart->next;
        delete tempPtr;
      }
    }
    
    bool LLSList::IsFull() const {
      LNode* testNode;
      try {
        testNode = new LNode;
        delete testNode;
        return false;
      }
      catch(std::bad_alloc exception) {
        return true;
      }
    }
    
    int LLSList::GetLength() const {
      LNode* LenPos = ListStart;
      int length=0;
      while (LenPos != NULL) {  
        LenPos=LenPos->next;
        length++;
      }
      return length;
    };
    
    int LLSList::FindItem(int GetItem, LNode*& nodeIter) {
       int position=0;
       nodeIter=ListEnd;
       while ((nodeIter != NULL)        && (nodeIter->next !=ListEnd )
           && (nodeIter->next->item <gitem)) {
          nodeIter=nodeIter->next;
          position++; }
       if ((nodeIter!=NULL)&&(nodeIter->next->item==gitem))
          return position;
       else
          return -1;
    }
    
    /*int LLSList::GetItem(int gitem) {
       int position=0;
       LNode* nodeIter;
       nodeIter=ListStart;
       while ((nodeIter != NULL) && (nodeIter->item <gitem)) {
          nodeIter=nodeIter->next;
          position++; }
       if ((nodeIter==NULL)||(nodeIter->item>gitem))
          return -1;
       else
          return position;
    }*/
    
    int LLSList::GetItem(int gitem) {
        LNode* unused_node;
        return FindItem(gitem,unused_node);
    }
    
    void LLSList::MakeEmpty() {
      LNode* tempPtr;
      while (ListStart != NULL) {
        tempPtr = ListStart;
        ListStart = ListStart->next;
        delete tempPtr;
      }  
    }
    
    
    /*void LLSList::PutItem(int newitem) {
      LNode* newNode; //Get a pointer for a new node             
      LNode* leadptr; //This points to the "current" node when searching for correct location in which to place item
      LNode* trailptr; //This points to the "previous" node when searching for correct location in which to place item             
      
      newNode = new LNode; //Allocate memory for the new node
      newNode->item = newitem; // Store the item in the node  
      if ((ListStart == NULL) || (ListStart->item > newitem)) { //List is empty or first element less than element for retrieval)
          newNode->next = ListStart; // Store address of next node 
          ListStart=newNode;
          
      } else {
          leadptr=ListStart->next;
          trailptr=ListStart;
          while ((leadptr!= NULL) && (leadptr->item<newitem)) {      
              leadptr=leadptr->next;
              trailptr=trailptr->next;
        }
          newNode->next=leadptr;
          trailptr->next=newNode;
      }    
    }*/
    
    void LLSList::PutItem(int newitem) {
       LNode* newNode=new LNode;   
       newNode->item=newitem;
       if (ListEnd==NULL) {
          ListEnd=newNode;
          ListEnd->next=ListEnd;      
       }  else if (newNode->item>ListEnd->item){
          newNode->next=ListEnd->next;
          ListEnd->next=newNode;
          ListEnd=newNode; 
       } else {
          LNode* nodePred;
          GetItem(newitem,nodePred);
          newNode->next=NodePred->next;
          nodePred->next=newNode;    
       }
    }
    
    
    /*void LLSList::DeleteItem(int ditem) {
      LNode* nodeIter;
      LNode* tmpNode;
      LNode* leadptr; //This points to the "current" node when searching for correct location in which to place item
      LNode* trailptr; //This points to the "previous" node when searching for correct location in which to place item     
      if (ListStart->item == ditem) {
        tmpNode=ListStart;
        ListStart=ListStart->next;
      } 
      else{
        leadptr=ListStart->next; //no empty lists allowed
        trailptr=ListStart;
        while (leadptr->item !=ditem) {
            trailptr=leadptr;
            leadptr=leadptr->next;         
        }      
        tmpNode=leadptr;
        trailptr->next=leadptr->next;    
      }
      delete(tmpNode);
    }*/
    
    bool LLSList::DeleteItem(int newitem) {
       LNode* tmpNode;
       int index;
       LNode* nodePred;
       index=FindItem(newitem,nodePred);
       if (index==-1)
          return false;
       else {
          tmpNode=nodePred->next;
          if (ListEnd->next==ListEnd)             
             ListEnd=NULL;             
          else {
             nodePred->next=tmpNode->next;
             if (tmpNode==ListEnd) 
               ListEnd=nodePred;        
          }
          delete(tmpNode);
          return true;
       }
    }
    
    void LLSList::ResetList() {
      curPos=ListStart;
    }
    
    int LLSList::GetNextItem() {
      if (curPos == NULL)
        throw;
      curPos=curPos->next;
      return curPos->item;
    };
    
    /*void LLSList::PrintList() {
      LNode* printPtr;
      printPtr=ListStart;
      std::cout<<"(";
      while (printPtr != NULL) {
        std::cout<<printPtr->item;
        if (printPtr->next!=NULL)
          std::cout<<", ";
        printPtr=printPtr->next;
      }    
      std::cout<<")"<<std::endl;
    }*/
    
    void LLSList::PrintList() {
      LNode* printPtr=ListEnd->next;
      std::cout<<"(";
      while (printPtr != ListEnd) {
        std::cout<<printPtr->item;
        if (printPtr->next!=ListEnd)
      std::cout<<", ";
      printPtr=printPtr->next;
      }
      std::cout<<")"<<std::endl;
    }

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,910
    What are the compile errors and what do you think they mean?

    By the way, I'd get rid of IsFull: it is fairly useless as far as normal usage will go: your linked list grows dynamically, so it doesn't get full, and if it does get full, the caller should just handle the exception or let it propagate.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    Oct 2019
    Posts
    12
    Quote Originally Posted by laserlight View Post
    What are the compile errors and what do you think they mean?

    By the way, I'd get rid of IsFull: it is fairly useless as far as normal usage will go: your linked list grows dynamically, so it doesn't get full, and if it does get full, the caller should just handle the exception or let it propagate.
    Here is an image of the errors I receive when I attempt to run the program. As for IsFull, I cannot remove it as it is required to be in the program, even though it does make sense to omit and let it propagate size as needed like you said.
    A lot of the code required to make this an "Ultimate Linked List or ULL" is provided to us but uses different names in the functions. We just have to add the code correctly and run it. I am also not accustomed to the project format (not all the code being run from a single source file), but we are required to run and use the code like it is provided to us. I think some of the issues come from other pages of code being incorrectly named after replacing the old code with the new code to make the ULL but I am honestly not very sure. This is only my second semester taking a CPP programing course so I don't fully understand all topics yet.
    Sorted Linked Lists-annotation-2020-02-25-165800-png
    Last edited by bob432; 02-25-2020 at 03:59 PM. Reason: Broken Image

  4. #4
    Registered User
    Join Date
    May 2019
    Posts
    214
    FindItem called on line 75, where the first error is indicated.

    That function is defined around line 47 or so, like this:

    Code:
    int LLSList::FindItem(int GetItem, LNode*& nodeIter) {...
    However, in the LLSList declaration, in the header file, the prototype for this function is not listed.

    That is the fundamental error. The prototype is not declared. GetItem is, but not FindItem.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Linked Lists and Pointer Arrays - Sorted insertion.
    By Xpl0ReRChR in forum C Programming
    Replies: 15
    Last Post: 01-01-2012, 03:10 AM
  2. Sorted Linked Lists
    By Mozza314 in forum C++ Programming
    Replies: 4
    Last Post: 03-31-2011, 12:18 AM
  3. separating mixed list into sorted two lists
    By transgalactic2 in forum C Programming
    Replies: 24
    Last Post: 04-20-2009, 03:32 PM
  4. learning how to do sorted linked lists
    By ktran03 in forum C Programming
    Replies: 2
    Last Post: 03-29-2009, 03:34 AM
  5. Help With Merging Sorted Lists of Strings
    By genjiguy in forum C++ Programming
    Replies: 3
    Last Post: 04-14-2005, 03:53 PM

Tags for this Thread