Question

6.9 Lab: Singly-Linked Lists

As an entry-level programmer you have to be able to read, understand existing code and update it (add new features). One of this assignment’s goals is to read about 400 lines of code in five files, compile and run the program, understand it, and change it as required.

Download and review the following files (read code and all comments carefully):

• College.h
• College.cpp
• LinkedList.h
• LinkedList.cpp
• main.cpp

---------------------------------------------------------

//colleges.txt

3 SBCC Santa Barbara City College; 18524
97 ZZC ZZ College; 9997
5 PCC Pasadena City College; 17666
7 NVC Napa Valley College; 18920
15 PVC Palo Verde College; 18266
4 DVC Diablo Valley College; 20579
6 FC Foothill College; 19302
12 CS College of the Siskiyous; 21936
99 CPC Cupertino College; 9999
10 CC Cuesta College; 19135
8 OC Ohlone College; 15878
98 ABC AB College; 9998
1 DAC De Anza College; 19302
9 IVC Irvine Valley College; 20577

--------------------------------------------------------------------------------

//LinkedList.cpp

#include <iostream>

#include "LinkedList.h"

using namespace std;

//**************************************************

// Constructor

// This function allocates and initializes a sentinel node

// A sentinel (or dummy) node is an extra node added before the first data record.

// This convention simplifies and accelerates some list-manipulation algorithms,

// by making sure that all links can be safely dereferenced and that every list

// (even one that contains no data elements) always has a "first" node.

//**************************************************

LinkedList::LinkedList()

{

head = new Node; // head points to the sentinel node

head->next = NULL;

length = 0;

}

//**************************************************

// The insertNode function inserts a new node in a

// sorted linked list

//**************************************************

void LinkedList::insertNode(College dataIn)

{

Node *newNode; // A new node

Node *pCur; // To traverse the list

Node *pPre; // The previous node

  

// Allocate a new node and store num there.

newNode = new Node;

newNode->college = dataIn;

// Initialize pointers

pPre = head;

pCur = head->next;

// Find location: skip all nodes whose code is less than dataIn's code

while (pCur && newNode->college.getCode() > pCur->college.getCode())

{

pPre = pCur;

pCur = pCur->next;

}

  

// Insert the new node between pPre and pCur

pPre->next = newNode;

newNode->next = pCur;

  

// Update the counter

length++;

}

//**************************************************

// The deleteNode function searches for a node

// in a sorted linked list; if found, the node is

// deleted from the list and from memory.

//**************************************************

bool LinkedList::deleteNode(string target)

{

Node *pCur; // To traverse the list

Node *pPre; // To point to the previous node

bool deleted = false;

  

// Initialize pointers

pPre = head;

pCur = head->next;

// Find node containing the target: Skip all nodes whose gpa is less than the target

while (pCur != NULL && pCur->college.getCode() < target)

{

pPre = pCur;

pCur = pCur->next;

}

  

// If found, delte the node

if (pCur && pCur->college.getCode() == target)

{

pPre->next = pCur->next;

delete pCur;

deleted = true;

length--;

}

return deleted;

}

//**************************************************

// displayList shows the value

// stored in each node of the linked list

// pointed to by head, except the sentinel node

//**************************************************

void LinkedList::displayList() const

{

   Node *pCur; // To move through the list

   // Position pCur: skip the head of the list.

   pCur = head->next;

   // While pCur points to a node, traverse the list.

   while (pCur)

   {

   // Display the value in this node.

   pCur->college.hDdisplay();

   // Move to the next node.

   pCur = pCur->next;

}

cout << endl;

}

//**************************************************

// The searchList function looks for a target college

// in the sorted linked list: if found, returns true

// and copies the data in that node to the output parameter

//**************************************************

bool LinkedList::searchList(string target, College &dataOut) const

{

bool found = false; // assume target not found

Node *pCur; // To move through the list

  

/* Write your code here */

  

return found;

}

//**************************************************

// Destructor

// This function deletes every node in the list.

//**************************************************

LinkedList::~LinkedList()

{

Node *pCur; // To traverse the list

Node *pNext; // To hold the address of the next node

  

// Position nodePtr: skip the head of the list

pCur = head->next;

// While pCur is not at the end of the list...

while(pCur != NULL)

{

// Save a pointer to the next node.

pNext = pCur->next;

  

// Delete the current node.

delete pCur;

  

   // Position pCur at the next node.

pCur = pNext;

}

  

delete head; // delete the sentinel node

}

--------------------------------------------------------------------------------------

//LinkedList.h

#ifndef LINKED_LIST_H

#define LINKED_LIST_H

#include "College.h"

class LinkedList

{

private:

struct Node

{

College college;

Node *next;

};

Node *head;

int length;

public:

LinkedList(); // constructor

~LinkedList(); // destructor

// Linked list operations

int getLength() const {return length;}

void insertNode(College);

bool deleteNode(string);

void displayList() const;

bool searchList(string, College &) const;

};

#endif

Answer 1

As nothing is mentioned, I'm assuming you need the searchList function done, as it's left incomplete.

Code:

bool LinkedList::searchList(string target, College &dataOut) const
{
    bool found = false;  // assume target not found
    ListNode *pCur; //To move through the list

    pCur = head->next;
    //Loop throught the list until we get the target
    while (pCur && pCur->dataOut.getCode() != target)
        pCur = pCur->next;
    if (pCur)
    {
        dataOut = pCur->dataOut;
        found = true;
    }
    return (found);
}

Screenshot:

Can't provide output as the main function is not provided.

Let me know if you need anything else.

-------------------------END---------------------

Please give a thumbs up(upvote) if you liked the answer.