Register    Login    Forum    Search    FAQ

Board index » Everything




Post new topic Reply to topic  [ 627 posts ]  Go to page Previous  1 ... 53, 54, 55, 56, 57, 58, 59 ... 63  Next
Author Message
 Post Posted: September 11th, 2017, 8:46 pm 
User avatar

Joined: January 19th, 2017, 10:28 pm
Posts: 495
Location: Idiot from northern Europe
^ muchos no buenos

So I missed todays lecture about linked lists due to being ill. But a classmate sent me the assignment.
Fighting throught the illnes by cycling sleep with doing assignment.
Have 3 tasks on the assignment

task 1: make a singly linked list with these functions:
Prepend(value)
Append(value)
Clear()
PopFront()
PopBack()
PrintItems()

task 2: implement a doubly linked list class with the same functions as in task 1

task 3: use templates to allow construction of a linked list containing any data type

I've finshed task 1, think I'm not leaking any memory

Node.h (made 2 constructors and Node* prev so I wont have to make a whole new Node class for task 2)
Code:
#pragma once

class Node
{
public:
   Node(Node* next_in, int value_in);
   Node(Node* next_in, Node* prev_in, int value_in);
   Node* next = nullptr;
   Node* prev = nullptr;
   int value;
};


Node.cpp

Code:
#include "Node.h"

Node::Node(Node * next_in, int value_in)
   :
   next(next_in),
   prev(nullptr),
   value(value_in)
{}

Node::Node(Node * next_in, Node * prev_in, int value_in)
   :
   next(next_in),
   prev(prev_in),
   value(value_in)
{}



SinglyLinkedList.h
Code:
#pragma once

#include "Node.h"
#include <iostream>

class SinglyLinkedList
{
public:
   SinglyLinkedList();
   ~SinglyLinkedList();
   void Prepend(int value_in);
   void Append(int value_in);
   void Clear();
   void PopFront();
   void PopBack();
   void PrintItems();

private:
   Node* m_First = nullptr;
};


SinglyLinkedList.cpp
Code:
#include "SinglyLinkedList.h"

SinglyLinkedList::SinglyLinkedList()
{
   m_First = nullptr;
}

SinglyLinkedList::~SinglyLinkedList()
{
   Clear();
   delete m_First;
}

void SinglyLinkedList::Prepend(int value_in)
{
   m_First = new Node(m_First, value_in);
}

void SinglyLinkedList::Append(int value_in)
{
   if (!m_First)
   {
      Prepend(value_in);
   }
   else
   {
      Node* node;
      for (node = m_First; node->next; node = node->next);
      node->next = new Node(nullptr, value_in);
   }
}

void SinglyLinkedList::Clear()
{
   if (m_First)
   {
      Node* curNode = m_First;
      Node* prevNode = nullptr;

      while (curNode)
      {
         prevNode = curNode;
         curNode = curNode->next;
         delete prevNode;
         prevNode = nullptr;
      }
   }
}

void SinglyLinkedList::PopFront()
{
   if (m_First)
   {
      if (m_First->next)
      {
         Node* first = m_First;
         m_First = m_First->next;
         delete first;
         first = nullptr;
      }
      else
      {
         delete m_First;
         m_First = nullptr;
      }
   }
}

void SinglyLinkedList::PopBack()
{
   if (m_First)
   {
      if (m_First->next)
      {
         Node* last = m_First;
         Node* prev = m_First;
         for (; last->next; prev = last, last = last->next);
         delete last;
         last = nullptr;
         prev->next = nullptr;
      }
      else
      {
         delete m_First;
         m_First = nullptr;
      }
   }
}

void SinglyLinkedList::PrintItems()
{
   if (!m_First)
   {
      std::cout << "List is empty.\n";
   }
   else
   {
      for (Node* i = m_First; i; i = i->next)
      {
         std::cout << i->value << std::endl;
      }
   }
}

_________________
I just like to thumb my nose at millionaires.
If I was rolled I'd bust them heads up.


Top 
 Profile  
Reply with quote  
 Post Posted: September 11th, 2017, 9:36 pm 
 

Joined: February 28th, 2013, 3:23 am
Posts: 2827
Location: Oklahoma, United States
Looks solid to me.

_________________
If you think paging some data from disk into RAM is slow, try paging it into a simian cerebrum over a pair of optical nerves. - gameprogrammingpatterns.com


Top 
 Profile  
Reply with quote  
 Post Posted: September 11th, 2017, 11:35 pm 
User avatar

Joined: January 19th, 2017, 10:28 pm
Posts: 495
Location: Idiot from northern Europe
Thanks papa! That feels reassuring :)

Doubly linked was a bit of a brain teaser.. this seems to work though.
Added a function init() to this class.

Code:
#include "DoublyLinkedList.h"

DoublyLinkedList::DoublyLinkedList()
{
   Init();
}

DoublyLinkedList::~DoublyLinkedList()
{
   Clear();
   delete m_First;
   m_First = nullptr;
}

void DoublyLinkedList::Init()
{
   m_First = new Node;
   m_First->next = m_First;
   m_First->prev = m_First;
}

void DoublyLinkedList::Prepend(int value_in)
{
   if (!m_First)
   {
      Init();
   }

   Node* node = new Node(m_First->next, m_First, value_in);
   m_First->next = node;
}

void DoublyLinkedList::Append(int value_in)
{
   if (!m_First)
   {
      Init();
   }

   Node* node = new Node(m_First, m_First->prev, value_in);
   m_First->prev->next = node;
   m_First->prev = node;
}

void DoublyLinkedList::Clear()
{
   if (m_First->next != m_First)
   {
      Node* curNode = m_First->next;
      Node* prevNode = nullptr;

      while (curNode != m_First)
      {
         prevNode = curNode;
         curNode = curNode->next;
         delete prevNode;
         prevNode = nullptr;
      }
      delete m_First;
      m_First = nullptr;
   }
}

void DoublyLinkedList::PopFront()
{
   if (m_First->next != m_First)
   {
      Node* first = m_First->next;
      m_First->next = first->next;
      first->next->prev = m_First;
      delete first;
      first = nullptr;
   }
}

void DoublyLinkedList::PopBack()
{
   if (m_First->next != m_First)
   {
      Node* last = m_First->prev;
      m_First->prev = last->prev;
      last->prev->next = m_First;
      delete last;
      last = nullptr;
   }
}

void DoublyLinkedList::PrintItems()
{   
   if (m_First->next != m_First)
   {
      for (Node* i = m_First->next; i != m_First; i = i->next)
      {
         std::cout << i->value << std::endl;
      }
   }
   else
   {
      std::cout << "List is empty." << std::endl;
   }
}


Just templates left now

_________________
I just like to thumb my nose at millionaires.
If I was rolled I'd bust them heads up.


Top 
 Profile  
Reply with quote  
 Post Posted: September 12th, 2017, 12:10 am 
User avatar

Joined: January 19th, 2017, 10:28 pm
Posts: 495
Location: Idiot from northern Europe
Wait, if I do a tempalte class I need to write template <class T> before every single function of that class??? or am I doing something wrong??


Code:
template <class T>
DoublyLinkedList<T>::DoublyLinkedList()
{
   Init();
}

template <class T>
DoublyLinkedList<T>::~DoublyLinkedList()
{
   Clear();
   delete m_First;
   m_First = nullptr;
}


etcetc

_________________
I just like to thumb my nose at millionaires.
If I was rolled I'd bust them heads up.


Top 
 Profile  
Reply with quote  
 Post Posted: September 12th, 2017, 12:26 am 
User avatar

Joined: January 19th, 2017, 10:28 pm
Posts: 495
Location: Idiot from northern Europe
Double wait... I can't do template and implement the functions in a cpp file?? I need to implement the functions in the h file?

_________________
I just like to thumb my nose at millionaires.
If I was rolled I'd bust them heads up.


Top 
 Profile  
Reply with quote  
 Post Posted: September 12th, 2017, 1:05 am 
Site Admin
User avatar

Joined: December 31st, 2011, 4:53 pm
Posts: 3468
Location: Japan
Template classes and template functions are completely separate bro. And yeah, you need to put the whole thing in the .h file for a template. The compiler needs access to the entire implementation at the time of compilation.

_________________
Chili


Top 
 Profile  
Reply with quote  
 Post Posted: September 12th, 2017, 11:12 am 
User avatar

Joined: January 19th, 2017, 10:28 pm
Posts: 495
Location: Idiot from northern Europe
Alrighty. It feels kinda dirty do have so much code in the h file but oh well. Here's my final code for the assignments


Singly linked
Code:
#pragma once

#include <iostream>

template <class T>
class SinglyLinkedList
{
private:
   class Node
   {
   public:
      Node(Node* next_in = nullptr, T data_in = T())
         :
         next(next_in),
         data(data_in)
      {}
      Node* next;
      T data;
   };

private:
   Node* m_First = nullptr;

public:
   SinglyLinkedList()
   {
      m_First = nullptr;
   }
   ~SinglyLinkedList()
   {
      Clear();
      delete m_First;
      m_First = nullptr;
   }
   void Prepend(T data_in)
   {
      m_First = new Node(m_First, data_in);
   }
   void Append(T data_in)
   {
      if (!m_First)
      {
         Prepend(data_in);
      }
      else
      {
         Node* node;
         for (node = m_First; node->next; node = node->next);
         node->next = new Node(nullptr, data_in);
      }
   }
   void Clear()
   {
      if (m_First)
      {
         Node* curNode = m_First;
         Node* prevNode = nullptr;

         while (curNode)
         {
            prevNode = curNode;
            curNode = curNode->next;
            delete prevNode;
            prevNode = nullptr;
         }
         m_First = nullptr;
      }
   }
   void PopFront()
   {
      if (m_First)
      {
         if (m_First->next)
         {
            Node* first = m_First;
            m_First = m_First->next;
            delete first;
            first = nullptr;
         }
         else
         {
            delete m_First;
            m_First = nullptr;
         }
      }
   }
   void PopBack()
   {
      if (m_First)
      {
         if (m_First->next)
         {
            Node* last = m_First;
            Node* prev = m_First;
            for (; last->next; prev = last, last = last->next);
            delete last;
            last = nullptr;
            prev->next = nullptr;
         }
         else
         {
            delete m_First;
            m_First = nullptr;
         }
      }
   }
   void PrintItems()
   {
      if (!m_First)
      {
         std::cout << "List is empty.\n";
      }
      else
      {
         for (Node* i = m_First; i; i = i->next)
         {
            std::cout << i->data << std::endl;
         }
      }
   }
};


Doubly linked
Code:
#pragma once

#include <iostream>

template <class T>
class DoublyLinkedList
{
private:
   class Node
   {
   public:
      Node(Node* next_in = nullptr, Node* prev_in = nullptr, T data_in = T())
         :
         next(next_in),
         prev(prev_in),
         data(data_in)
      {}
      Node* next;
      Node* prev;
      T data;
   };

private:
   Node* m_First = nullptr;

public:
   DoublyLinkedList()
   {
      Init();
   }
   ~DoublyLinkedList()
   {
      Clear();
      delete m_First;
      m_First = nullptr;
   }
   void Init()
   {
      m_First = new Node;
      m_First->next = m_First;
      m_First->prev = m_First;
   }
   void Prepend(T data_in)
   {
      if (!m_First)
      {
         Init();
      }

      Node* node = new Node(m_First->next, m_First, data_in);
      m_First->next = node;
   }
   void Append(T data_in)
   {
      if (!m_First)
      {
         Init();
      }

      Node* node = new Node(m_First, m_First->prev, data_in);
      m_First->prev->next = node;
      m_First->prev = node;
   }
   void Clear()
   {
      if (m_First->next != m_First)
      {
         Node* curNode = m_First->next;
         Node* prevNode = nullptr;

         while (curNode != m_First)
         {
            prevNode = curNode;
            curNode = curNode->next;
            delete prevNode;
            prevNode = nullptr;
         }
         delete m_First;
         m_First = nullptr;
      }
   }
   void PopFront()
   {
      if (m_First->next != m_First)
      {
         Node* first = m_First->next;
         m_First->next = first->next;
         first->next->prev = m_First;
         delete first;
         first = nullptr;
      }
   }
   void PopBack()
   {
      if (m_First->next != m_First)
      {
         Node* last = m_First->prev;
         m_First->prev = last->prev;
         last->prev->next = m_First;
         delete last;
         last = nullptr;
      }
   }
   void PrintItems()
   {
      if (m_First && m_First->next != m_First)
      {
         for (Node* i = m_First->next; i != m_First; i = i->next)
         {
            std::cout << i->data << std::endl;
         }
      }
      else
      {
         std::cout << "List is empty." << std::endl;
      }
   }
};

_________________
I just like to thumb my nose at millionaires.
If I was rolled I'd bust them heads up.


Top 
 Profile  
Reply with quote  
 Post Posted: September 12th, 2017, 12:00 pm 
User avatar

Joined: January 19th, 2017, 10:28 pm
Posts: 495
Location: Idiot from northern Europe
nvm made some small changes. Realized the program wasn't completely safe. It crashed if you tried to clear or pop an already cleared list. So added else conditions to those functions

if (m_First && m_First->next != m_First)
{
Node* last = m_First->prev;
m_First->prev = last->prev;
last->prev->next = m_First;
delete last;
last = nullptr;
}
else
{
std::cout << "List is already empty." << std::endl;
}

Think I'm also gonna add deep copy or at least make it not allowed to try and do list1 = list2.
The assignment doesn't mention it but it says "retain program stability" and this, I guess would add to the stability of the program


Edit:
Just added this in private: for singly and doubly linked so it gives an error if someone tries to list1 = list2. That wil do for this assignment imo

DoublyLinkedList(const DoublyLinkedList&) {};
DoublyLinkedList& operator=(const DoublyLinkedList&) { return *this; };

_________________
I just like to thumb my nose at millionaires.
If I was rolled I'd bust them heads up.


Top 
 Profile  
Reply with quote  
 Post Posted: September 12th, 2017, 4:11 pm 
User avatar

Joined: January 19th, 2017, 10:28 pm
Posts: 495
Location: Idiot from northern Europe
Aparently we're starting the math course next week!
Good thing I studied some maths this summer.
Will do some repetition over the weekend after I've watched the last few episodes of intermediate.

Enough spamming for today!

_________________
I just like to thumb my nose at millionaires.
If I was rolled I'd bust them heads up.


Top 
 Profile  
Reply with quote  
 Post Posted: September 12th, 2017, 9:18 pm 
 

Joined: February 28th, 2013, 3:23 am
Posts: 2827
Location: Oklahoma, United States
Yumtard wrote:
nvm made some small changes. Realized the program wasn't completely safe. It crashed if you tried to clear or pop an already cleared list. So added else conditions to those functions

if (m_First && m_First->next != m_First)
{
Node* last = m_First->prev;
m_First->prev = last->prev;
last->prev->next = m_First;
delete last;
last = nullptr;
}
else
{
std::cout << "List is already empty." << std::endl;
}

Think I'm also gonna add deep copy or at least make it not allowed to try and do list1 = list2.
The assignment doesn't mention it but it says "retain program stability" and this, I guess would add to the stability of the program


Edit:
Just added this in private: for singly and doubly linked so it gives an error if someone tries to list1 = list2. That wil do for this assignment imo

DoublyLinkedList(const DoublyLinkedList&) {};
DoublyLinkedList& operator=(const DoublyLinkedList&) { return *this; };


Code:
DoublyLinkedList(const DoublyLinkedList&) = delete;
DoublyLinkedList& operator=(const DoublyLinkedList&) = delete;

The way you did it is the old way, you can disable those functions with = delete.

_________________
If you think paging some data from disk into RAM is slow, try paging it into a simian cerebrum over a pair of optical nerves. - gameprogrammingpatterns.com


Top 
 Profile  
Reply with quote  
Display posts from previous:  Sort by  
 
Post new topic Reply to topic  [ 627 posts ]  Go to page Previous  1 ... 53, 54, 55, 56, 57, 58, 59 ... 63  Next

Board index » Everything


 
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for: