Data Strucutres Lab 2 Guide

Lab 2 is tough for some students. These are some helpful tips to do well.

Table of contents

Setup

First, unzip the folder and place it into your IDE. We will be using Donovan’s replit as the starting code. Put the content of this file into your main.cpp

The code is fine*, I have my opinions on how this should be ordered. At least rename the output ofstream properly.

Issues:

Make sure you understanding how (output >> data) is working. It takes one word at a time. Use that information to get the right info in.

Getting into a modular state

A big issue of a lot of programs is that they have no clue what actually works. Students come in with 500 lines of code not knowing if getting the input actually runs. At this point, you should be able to run the code and see that it cout prints the file everytime you run the test file.

Use this feedback loop to drive your structure.

List basics

This is a sample structure to a good program. You could have everything in one file, however it is good form to structure the list into a header file and another file to implement the code.

List Header file:

A header file is a way to structure a class.

• Ask yourself, what should this class have to implement all the commands and the LinkedList?

• You would need a struct node, what will this node carry?

  • A next that points to the next node.
  • A data that stores a string.

• What does this List class have as variables?

  • A head node
  • A tail node
  • Maybe a length node.
    • (Reasoning for length since you can get invalid position, makes other commands easier.)

• Commands could be:

  • Insert commands
    • InsertAtHead
    • InsertAtTail
    • InsertAtPosition
  • Remove commands
    • RemoveAtHead
    • RemoveAtTail
    • RemoveAtPosition
  • Print commands
    • PrintAtHead
    • PrintAtTail
    • PrintAtPosition

• You could also just have one command for each, since head is just position 0, and tail is the length of the list position. - This can be done by keep tracking of length in the LinkedList. A sample header file following this could look like:

#ifndef LINKEDLIST_H

#define LINKEDLIST_H



#include <iostream>

#include <fstream>

#include <string>



using namespace std;



struct Node

{

string value;

Node *next;

};

class LinkedList

{

private:

Node *head;

Node *tail;

int length;



public:

LinkedList()

{

head = nullptr;

tail = nullptr;

length = 0;

}

void insertAtPos(string data, int pos);

void insertAtHead(string data);

void insertAtTail(string data);


void removeAtHead();

void removeAtTail();

void removeAtPos(int pos);

void print(int pos, ofstream &output);

// for testing

void printList(ofstream& output);

};


#endif

List implementation.

This is where you should do the majority of your work. I will give you the printList which is a useful method to use to see the state of the linkedList at every command.

Put a call to the method inside the main while loop.

#include "LinkedList.h"

#include <iostream>

#include <fstream>

#include <string>

#include <sstream>

#include <algorithm>

using namespace std;

void LinkedList::printList(ofstream &output)

{

output << "Printing List! ";

Node *temp = head;

while (temp != nullptr)

{

output << temp->value << " ";

temp = temp->next;

}

}

Good luck!

This should give you the basics to develop lab2 in a modular way. You should able to find out when one function does not work properly.