Linked Lists Help

[TinnyMintz]

I am relatively new to C++ programming and this is an extra problem assigned to me that I do not understand but want to do it so I can learn more about it. Basically its requiring that the program reads the input.txt, does what is asked to in the instructions, and then prints the output to an output.txt but I am completely lost and I don't think I wrote my code properly since it just gives me numbers instead of words.


You will create a C++ program to add, remove and sort objects in a linked list. The purpose of this is to get students familiar with Linked List and simple sorting techniques.

2. Input, Command, Output and example files
a. Input file

● The first line of the input file will tell you how to add data to your
linked list
a. Alphabetically
■ A-Z-a-z (capital letters count first this is how c++
handles comparing strings anyway)

b. Length
■ Shortest length - longest length of string
c. Beginning
■ Add current string to the front of your list
d. End
■ Add current string to the end of your list

● The rest of the file will contain a list of sentences. Don’t add empty
lines or duplicate sentences (case and space sensitive)

b. Command file

● Command file will be filled with 3 types commands that will be run
in order they appear
a. Add (int location) [string sentence]
■ The add command will be followed by an integer
inside parenthesis and then followed by a sentence
inside brackets
■ If the location is bigger than the size of the list then
don’t add it
■ If the sentence is a duplicate don’t add it
■ EX: Add (0) [this would add to the beginning of your
list]
■ EX: Add (3) [example sentence]
● This will be the added to the 3rd index
meaning it will be the 4th thing in your list
● Won’t get added if your list is size 2 or less

b. Remove [string sentence segment]
■ The remove function will be followed by a string
inside of brackets
■ Every sentence that contains that string in any part
of the sentence will get removed
■ EX: Remove [a]

● This will remove every single sentence with
the letter a in it
c. Sort (alphabetically/length)
■ The sort command will be followed by the word
alphabetically or length inside of parenthesis
■ This will sort the entire list either alphabetically or
by length
■ EX: Sort (alphabetically)

c. Output file

● The output file will contain every element of your list after it’s been
modified by the command file.
● Each element will be on its own line

d. Examples

Ex1:
input21.txt:
Alphabetically
for this example the command file will be empty
that means you just need to sort this file alphabetically
don't add any empty lines
test lines
duplicate line there should only be one of this in the output
duplicate line there should only be one of this in the output
extra sentence

command21.txt: (Empty)

ans21.txt:
don't add any empty lines
duplicate line there should only be one of this in the output
extra sentence
for this example the command file will be empty
test lines
that means you just need to sort this file alphabetically

Ex2:
input22.txt
Length
this file will be testing each of the different commands with your sentences
test sentence number one

another sentence
longer sentence than another sentence
most of the sentences have the word sentence in them
last sentence of the input

command22.txt
Add (15) [this sentence shouldn't be added because it's out of bounds]
Sort (alphabetically)
Add (6) [this sentence should be added to the end of the list]
Remove [test]
Add (0) [another sentence]

ans22.txt
another sentence
last sentence of the input
longer sentence than another sentence
most of the sentences have the word sentence in them
this sentence should be added to the end of the list

Ex3:
input23.txt
Beginning
here i go typing out a bunch of
random sentences so that this assignment can have
enough inputs
I hope this assignment isn't too challenging
but if you're having trouble with it don't give up
just take a deep breath and you'll get it
however this giant message
is just
going
to
be
a
random
jumble of
words
in
the
output
file

command23.txt
Remove [us]
Sort (length)
Sort (alphabetically)
Add (0) [this should go to the beginning until it gets sorted]
Add (70) [this should not be added]

Sort (length)
Remove [a]
Remove [e]
Remove [i]
Remove [o]
Remove [u]
Remove [y]
Add (0) [first]
Add (1) [second]
Add (2) [third]
Add (4) [Not added]

ans23.txt
first
second
third

Current Code:

#include<iostream>
#include<string>
#include<fstream>
#include "ArgumentManager.h"

using namespace std;

struct Node {
int item;
struct Node* next;
};

void add(struct Node** ref, int data) {

struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));

new_node->item = data;
new_node->next = (*ref);

(*ref) = new_node;
}


void Remove(struct Node** ref, int key)
{
  struct Node *temp = *ref, *prev;
  if (temp != NULL && temp->item == key) 
  {
    *ref = temp->next;
    free(temp);
    return;
  }
  while (temp != NULL && temp->item != key) {
    prev = temp;
    temp = temp->next;
  }
  if (temp == NULL) return;
  prev->next = temp->next;
  free(temp);
}

void swap (Node *node1, Node *node2)
{
  int temp = node1->item;
  node1->item = node2 -> item;
  node2 ->item = temp;
}

void sort(Node *head)
{
  int swapped;
  Node *leftPtr; 
  Node *rightPrt = NULL; 
  do
  {  
    swapped = 0;
    leftPtr = head;
    while(leftPtr->next != rightPrt)
    {
      if (leftPtr->item > leftPtr->next->item)
      {
        swap(leftPtr, leftPtr->next);
swapped = 1;
      }
      leftPtr = leftPtr->next;
    }
    rightPrt = leftPtr;
  }while(swapped);
}

void Display(struct Node* node) 
{
  while (node != NULL)
  {
    cout << node->item << " ";
    node = node->next;
  }
}

int main(int argc, char* argv[])
{
  ArgumentManager am(argc, argv);
  ifstream input;
  ofstream output;

  string infileName = am.get("input");
  string outfileName = am.get("output");
  string cmdfilename = am.get("command");
  input.open(infileName);
  output.open(outfileName);
  
  struct Node* head = NULL;
  
  add(&head, 2);
  add(&head, 3);
  add(&head, 4);
  add(&head, 5);
  add(&head, 0);
  add(&head, 5);
  add(&head, 8);
  add(&head, 6);
  
  output << "Linked list: ";
  Display(head);
  
  output << "\nAfter sorting an element: ";
  sort(head);
  Display(head);
  
  output << "\nAfter deleting an element: ";
  Remove(&head, 4);
  Display(head);
  
}

[jonnin]

malloc and free are c. use new/delete for most c++ unless you also require realloc or something, in which case, you may need to borrow the C functions.


your linked list struct has int as the data type. if you want a string, put a string in instead.

there may be other issues but using a string has to improve the behavior :)

[TinnyMintz]

Ah I see about replacing int with string, thank you! What do you mean though about malloc and free are c and using new/delete?

[jonnin]

C++ inherits a lot from C language.
malloc and free are C language memory routines that work in C++ but are not the C++ tools.
the C++ tools are called new and delete. The syntax is slightly different: c++ is strongly typed, so the void * from malloc isnt really a good fit, and the strong typing tells C++ compiler the sizes that C needs from the programmer (c++ knows the sizeof the thing and does not need you to provide it).
like this
int * ip = new int[1000];
ip[3] = 42;
delete[] ip;

if you only have 1 of them, the [] go away:
int * ip1 = new int; //only 1 of these
...
delete ip1; //no bracket

another inherited feature from C are the C-strings: arrays of a character type. C++ tries to avoid them with a more powerful object type called string found in <string>. string.h (actual C code or ancient c++ code) or cstring are the C tools. You used the correct one here, but you will invariably see the other one sooner or later. If nothing else, argv is a C-string array.

[TheIdeasMan]

Also, use nullptr instead of NULL

[seeplus]

You're writing c code for using memory.

void add(struct Node** ref, int data) {

This is the c way. The c++ way would be:

void add(Node*& ref, int data) {

ie pass ref as a ref pointer and not as a pointer to pointer.

You don't use struct when passing a struct type:

void Display(struct Node* node) 

becomes:

void Display(Node* node) 

and the same L10 etc.