Question

You can complete this assignment individually or as a group of two people.

In this assignment you will create a ​​Sorted Singly-Linked List​ that performs basic list operations using C++. This linked list should not allow duplicate elements. Elements of the list should be of type ‘ItemType’. ‘ItemType’ class should have a private integer variable with the name ‘value’. Elements in the linked list should be sorted in the ascending order according to this ‘value’ variable.

You should create a command line application (main.cpp) to utilize the linked list. This application should take a single command line parameter. This parameter should be a ​path​ to a plain text file​ that contains a space separated list of positive integer numbers in an unsorted order. The main application should read this text file and insert the values to the sorted linked list.

The command line application should provide an interactive command line interface to allow users to perform operations on the list. ​You must implement all the operations that are shown in the example output​. ​And the command line interface must be exactly equal to the example output​ given at the end of this document.

This assignment includes one bonus question.
You must create the following files to implement the program.

input.txt

25 50 35 15 22 10 12 4 18 24

● ItemType.h
● ItemType.cpp
● SortedLinkedList.h
● SortedLinkedList.cpp

● ListNode.h
● main.cpp

You must create the following ​mandatory variables and functions​ in the above files. You may add your own functions and variables in addition to the following functions.

ItemType.h

Enumerations:
● There should be an enumeration called ‘​Comparison​’ with values GREATER, LESS,

and EQUAL. This enumeration should be used when comparing the ‘ItemType’ elements

when sorting. Private Data Members:

● int value Functions:

• ● ItemType( )​ - Default Constructor:

• ● Comparison compareTo( ItemType item ) ​- Compare the value of item with the current

  object's value and return GREATER, LESS or EQUAL.

• ● int getValue( ) const​ - Return the value instance variable.

• ● void initialize( int num ) ​- Initializes the data member by variable num

  ItemType.cpp

  This file should provide implementations for the members in ItemType.h.

  ListNode.h

  You should create a struct called ListNode to be used as the Nodes in the linked list. Public Data Members:

• ● ItemType item

• ● ListNode *next

  SortedLinkedList.h

  Private Data Members:

• ● int length

• ● ListNode *head

• ● ListNode *currentPos

  Functions:

• ● SortedLinkedList( )​ - Initialise a sorted linked list object.

• ● ~SortedLinkedList( )​ - Free up all the user allocated memory and destruct the

  SortedLinkedList instance. This method should handle memory leaks.

• ● int length( ) const​ - Return the length of the linked list.

• ● void insertItem( ItemType item )​ - item should be inserted to the linked list maintaining

  the ascending sorted order.

○ You have to handle inserting the first element as a special case.

● void deleteItem( ItemType item )​ - ListNode that contains an item equal to the item parameter should be removed. You should handle all cases of deleting an element.

• ○ Deleting first element.

• ○ Deleting the last element or an element in the middle.

• ○ Deleting the only element.

• ○ Attempt to delete a non-existing item should print “Item not found”.

2

• ● int searchItem( ItemType &item ) ​- Search the ListNode that contains an item equal to the parameter item and return its index. Print “Item not found” if the item was not found in the list.

• ● ItemType GetNextItem( ) ​- This function returns the next item in the list pointed by the currentPos pointer.

• ● void ResetList( ) - ​This will initialize the currentPos pointer to null. See the description below to check how you need to call these functions.

• ● void reverse( )​ - You should implement this method only if you wish to complete the bonus question. In this method you should reverse the linked list without using a separate list or an array.

  SortedLinkedList.cpp

  You should implement the members in the SortedLinkedList.h in this file.

  main.cpp

  You should implement the command line application in this file. It should be able to take the input file in the following command line format.
  $ ./main input.txt

  You can use the following code snippet to read numbers from the input file.

#include

#include

SortedLinkedList list;

ItemType item;

int input;

std::fstream fs;

fs.open(argv[1], std::fstream::in);

if (fs.is_open())

{

fs >> input;

while (!fs.eof())

{

item.initialize(input);

list.insertItem(item);

fs >> input;

}

}

else

{

std::cout << "Failed to open the input file" << std::endl;

return 0;

}

Your application must use the following character constants as the commands in the command line interface.

• ● INSERT =

• ● DELETE =

• ● SEARCH =

• ● ITR_NEXT =

• ● RESET_ITR =

• ● PRINT_ALL =

• ● LENGTH =

• ● REVERSE =

• ● QUIT =

'i' Inserts a node in the linked list
'd' Deletes a node in the linked list
's' Searches a node in the linked list
'n'
'r'
'p' Should print all the integer values stored in the linked list nodes 'l'
'b' Bonus function
'q' Quit the program

‘n’ (ITR_NEXT) and ‘r’ (RESET_ITR) Command Explanation

Repeated invocations of ‘n’ command should print elements in the list one by one, starting from the first element to the last element. If ‘n’ is invoked at the last element, you should print “The end of the list has reached”. Also if the ‘n’ is invoked when the list is empty, you should print “List is empty”. Assume that the user is not going to add or delete an item from the list while calling the iterator.

Invoking the ‘r’ command should cause the ‘n’ command to start printing the elements starting from the beginning in the consequent invocations. You need to call GetNextItem( ) function for command ‘n’ and ResetList functions for command ‘r’.

Example Output​:

Command line interface of your program must be exactly equal to the following examples. As shown in the example output, if any of the commands are going to modify the elements in the list, you must print the elements in the list before and after the modification is performed.

./main input.txt Commands:
(i) - Insert value
(d) - Delete value
(s) - Search value

(n) - Print next iterator value
(r) - Reset iterator
(p) - Print list
(l) - Print length

(b) - Reverse
(q) - Quit program

Enter a command: i
1 3 9 10 19 37 45 63 84 100
Enter number: 12
1 3 9 10 12 19 37 45 63 84 100

Enter a command: d
1 2 3 9 10 12 19 37 45 63 84 100
Enter value to delete: 12
1 2 3 9 10 19 37 45 63 84 100

Enter a command: s
Enter a value to search: 10
Index 4

Enter a command: n
1
Enter a command: n
2

Enter a command: r
Iterator reset.
Enter a command: n
1

Enter a command: p
1 2 3 9 10 19 37 45 63 84 100

Enter a command: l
List Length is 11
Enter a command: b
Before

1 2 3 9 10 19 37 45 63 84 100

5

After
100 84 63 45 37 19 10 9 3 2 1

Enter a command: q
Quitting program...

Compiling the Program:

You must create a Makefile to compile your program. The Makefile must compile your code into an executable program called “ main ”.

Your program should run with the following command syntax:

$ ./main

● ItemType.h
● ItemType.cpp
● SortedLinkedList.h
● SortedLinkedList.cpp ● ListNode.h
● main.cpp
● Makefile

Answer 1

Hi, Please find a solution and vote the answer. I could not use enums since it was giving many bugs. Compile errors for little or no reason.

main.cpp

#include <iostream>
#include "SortedLinkedList.h"
#include "string"
int countSpaces(std::string &s){
    int count=0;
    for (int i = 0; i < s.length(); ++i) {
        if(s.c_str()[i]==' '){
            count++;
        }
    }
    return count;
}
int main() {
    SortedLinkedList *list = new SortedLinkedList();
    bool loop = true;
    char ch;
    do{
        std::cout<<"Enter a command:"<<std::endl;
        std::cin>>ch;
        switch (ch){
            case 'i':
               {
                   char data[100];
                   std::cout<<"Enter data";
                   fgets(data,100,stdin);
                   std::string temp = data;
                   if(temp.compare("\n")==0){
                       fgets(data,100,stdin);
                   }
                   std::string s = data;
                   int delimCount = countSpaces(s);
                   for (int i = 0; i < delimCount+1; ++i) {
                       int no = 0;
                       if (i == 0) {
                           no = atoi(strtok(data, " "));
//                           continue;
                       }else {
                           no = atoi(strtok(NULL, " "));
                       }
                       ItemType *pType = new ItemType(no);
                       list->insertItem(*pType);
                   }
                   break;
               }

            case 'd':{
                int value =0;
                std::cout<<"Enter a value to delete"<<std::endl;
                std::cin>>value;
                list->deleteItem(*(new ItemType(value)));
                break;
            }

            case 'p':
                list->printList();
                break;
            default:
                exit(0);
                break;
        }
    }while(loop);
}

//

//

#ifndef LINKEDLISTSORTED_ITEMTYPE_H
#define LINKEDLISTSORTED_ITEMTYPE_H


class ItemType {
private:
    int value;
public:
    ItemType(int value) : value(value) {}

    int getValue() const {
        return value;
    }

    void setValue(int value) {
        ItemType::value = value;
    }

    int compareTo(ItemType item){
        if(this->value>item.getValue())
            return 10;
        else if(this->value<item.getValue()){
            return -10;
        }else{
            return 0;
        }
    }
    void initialize( int num ){
            this->value = num;
    }
};


#endif //LINKEDLISTSORTED_ITEMTYPE_H

//
// 
//

#ifndef LINKEDLISTSORTED_SORTEDLINKEDLIST_H
#define LINKEDLISTSORTED_SORTEDLINKEDLIST_H


#include "ListNode.h"
#include "iostream"

class SortedLinkedList {
private:
    int length;
    ListNode *head;
    ListNode *currentPos;
public:
    void deleteEnd(){
        if(head->next== nullptr){
            delete head;
            length=0;
            return;
        }
        if(head->next->next== nullptr){
            delete head->next;
            length--;
        }
        ListNode *temp = head;
        ListNode *tempNext = head->next;
        while(tempNext->next!= nullptr){
            temp = temp->next;
            tempNext = tempNext->next;
        }
        delete tempNext;
        length--;
    }
    int lengthh(){
        ListNode *temp = head;
        int i=0;
        while(temp!= nullptr){
            i++;
            temp = temp->next;

        }
        return i;
    }
    SortedLinkedList();
    ~SortedLinkedList();
    void insertItem(ItemType item){
        length++;
        ListNode *pNode = new ListNode(item);
        pNode->item = item;
        pNode->next = nullptr;
        if(head== NULL){
            head = pNode;
            return;
        }
        if(head->item.compareTo(item)==0){
            //duplicate
            return;
        }
        ListNode *temp = head;
        ListNode *tempNext = head->next;
        while(tempNext!= nullptr && tempNext->item.compareTo(item)<0){
            if (tempNext->item.compareTo(item) == 0) {
                //duplicate
                return;
            }
            temp=temp->next;
            tempNext = tempNext->next;
        }
        if(tempNext!= nullptr){//position found
            pNode->next = tempNext;
            temp->next = pNode;
            length++;
        }else{
            temp->next = pNode;
            length++;
        }

    }
    void deleteItem(ItemType item){
        if(head== nullptr){
            std::cout<<"Item not found"<<std::endl;
            return;
        }
        if(head->item.compareTo(item)==0){
            head = head->next;
            length--;
            return;
        }
        ListNode *temp = head;
        ListNode *tempNext = head->next;
        while(tempNext!= nullptr && tempNext->item.compareTo(item)!=0){
            temp = temp->next;
            tempNext = tempNext->next;
        }
        if(tempNext== nullptr){
            //item does not exist
            std::cout<<"Item not found"<<std::endl;
        }else{
            temp->next = tempNext->next;
            tempNext->next = nullptr;
            delete tempNext;
            length--;
        }
    }
    int searchItem(ItemType &item){
        ListNode *temp = head;
        int index=0;
        while(temp!= nullptr){
            if(temp->item.compareTo(item)==0){
                return index;
            }
            index++;
            temp=temp->next;
        }
        std::cout << "not found";
        return index;
    }
    ItemType GetNextItem(){
        return currentPos->item;
    }
    void resetList(){
        currentPos = nullptr;
    }
    void printList(){
        ListNode *temp = head;
        int i=1;
        while(temp!= nullptr){
            std::cout<<"Value "<<i++<<" is "<<temp->item.getValue()<<std::endl;
            temp=temp->next;
        }
    }

};



#endif //LINKEDLISTSORTED_SORTEDLINKEDLIST_H

//

//

#include "SortedLinkedList.h"

SortedLinkedList::SortedLinkedList() {head=NULL;}

SortedLinkedList::~SortedLinkedList() {
    while (length != 0) {
        deleteEnd();
    }

}

//

//

#ifndef LINKEDLISTSORTED_LISTNODE_H
#define LINKEDLISTSORTED_LISTNODE_H


#include "ItemType.h"

//typedef enum ItemType ITEM;
class ListNode {
public:
    ListNode(ItemType &item) : item(item) {}

    ItemType item;
    ListNode *next;

};


#endif //LINKEDLISTSORTED_LISTNODE_H

For the files which dont hve cpp here, they are empty.

Sample out: Value no below will increment. Screen shot is old.