user:dblanch1:portfolio:dataproject3
Singly Linked List Menu Programme
The purpose of this project was to gain familiarity and comfort with manipulating singly linked lists of our own creation. In addition, this and the doubly linked variant were the first projects we split into multiple files. The functions I implemented build list, two display list functions (one graphical, the other a 'detailed' view, showing what's going on in memory more clearly), insert before/after, view, remove, grab, and delete nodes, sort list (in ascending order), and clear list. The source code for the two files is listed below, and the command to compile them is:
g++ -o s_main s_main.cpp -g
ltsl.hpp
#ifndef LTSL
#define LTSL
template <class T> struct SNode{
T data;
SNode<T>* next;
SNode(){ next = NULL; }
};
template <class T> class SList{
private:
SNode<T>* head, * tail;
unsigned long long capacity;
bool destroy;
public:
SList(){ head = NULL; tail = NULL; capacity = 0; destroy = true; }
unsigned long long get_capacity(){ return capacity; }
void set_destroy(bool d){ destroy = d; }
void reset(){ capacity = 0; head = NULL; tail = NULL; }
SNode<T>* find_node(unsigned long long i){
if (capacity == 0) return NULL;
else if (i == 0) return this->head;
else if (i == (capacity - 1)) return this->tail;
else if ((i >= 0) && (i < capacity)){
SNode<T>* curr = head;
for (unsigned long long c = 0; c < i; c++){
curr = curr->next;
}
return curr;
}
else return NULL;
}
SNode<T>* grab_node(unsigned long long i){
if ((i >= 0) && (i < capacity)){
SNode<T>* curr = find_node(i);
if (curr != NULL){
SNode<T>* curr_prev = find_node(i - 1);
if (curr_prev != NULL) curr_prev->next = curr->next;
if (curr == head) head = curr->next;
if (curr == tail) tail = curr_prev;
capacity--;
return curr;
}
}
else return NULL;
}
bool remove_node(SNode<T>* node){
SNode<T>* curr = head;
SNode<T>* curr_prev = NULL;
while (curr != NULL){
if (curr == node){
break;
}
curr_prev = curr;
curr = curr->next;
}
if (curr != NULL){
if (curr_prev != NULL) curr_prev->next = curr->next;
return false;
}
else return true;
}
bool delete_node(unsigned long long i){
SNode<T>* tmp = grab_node(i);
if (tmp != NULL){
capacity--;
delete tmp;
return false;
}
else return true;
}
bool eliminate_node(SNode<T>* node){
if (remove_node(node) == false){
delete node;
return false;
}
else return true;
}
void clear(){
SNode<T>* curr = head;
SNode<T>* curr_n = NULL;
if (curr != NULL) curr_n = curr->next;
while (curr != NULL){
delete curr;
curr = curr_n;
if (curr != NULL) curr_n = curr->next;
}
reset();
}
bool prepend_node(SNode<T>* node){
if (node != NULL){
node->next = head;
head = node;
capacity++;
return false;
}
else return true;
}
bool append_node(SNode<T>* node){
if (node != NULL){
if (tail != NULL) tail->next = node;
if (head == NULL) head = node;
tail = node;
capacity++;
return false;
}
else return true;
}
bool insert_before(unsigned long long i, SNode<T>* node){
if ((i >= 0) && ((i < capacity) || (capacity == 0))){
if (head == NULL){
head = node;
head->next = NULL;
tail = node;
capacity++;
return false;
}
else {
SNode<T>* curr = find_node(i);
SNode<T>* curr_prev = find_node(i - 1);
if (curr != NULL){
if (curr == head){
node->next = head;
head = node;
capacity++;
return false;
}
else {
node->next = curr;
curr_prev->next = node;
capacity++;
return false;
}
}
}
}
else return true;
}
bool insert_after(unsigned long long i, SNode<T>* node){
if ((i >= 0) && ((i < capacity) || (capacity == 0))){
if (head == NULL){
head = node;
head->next = NULL;
tail = node;
capacity++;
return false;
}
else {
SNode<T>* curr = find_node(i);
if (curr != NULL){
if (curr == tail){
node->next = NULL;
tail->next = node;
tail = node;
capacity++;
return false;
}
else {
node->next = curr->next;
curr->next = node;
capacity++;
return false;
}
}
}
}
else return true;
}
bool swap_nodes(SNode<T>* node1, SNode<T>* node2){
if (((node1 != NULL)&&(node2 != NULL)) && (node1 != node2)){
SNode<T>* node1_prev = NULL;
SNode<T>* node2_prev = NULL;
SNode<T>* curr = head;
int c = 0;
while (curr->next != NULL && c<2){
if (curr->next == node1){
node1_prev = curr;
c++;
}
if (curr->next == node2){
node2_prev = curr;
c++;
}
curr = curr->next;
}
SNode<T> tmp;
if (node1->next == node2){
}
}
else return true;
}
void append_list(SList<T> &other){
SNode<T>* other_head = other.find_node(0);
SNode<T>* other_tail = other.find_node(other.get_capacity - 1);
tail->next = other_head;
tail = other_tail;
other.reset();
}
void sort(){
SNode<T>* lowest = NULL;
SNode<T>* curr = NULL;
SNode<T>* new_head = NULL;
SNode<T>* new_tail = NULL;
unsigned long long tmp_cap = capacity;
while (tmp_cap > 0){
curr = head;
lowest = head;
while (curr != NULL){
if (curr->data < lowest->data){
lowest = curr;
}
curr = curr->next;
}
remove_node(lowest);
tmp_cap--;
if (new_head == NULL){
new_head = lowest;
lowest->next = NULL;
new_tail = lowest;
}
else {
if (new_tail != NULL){
new_tail->next = lowest;
new_tail = lowest;
lowest->next = NULL;
}
}
}
head = new_head;
tail = new_tail;
}
~SList(){ if (destroy == true) clear(); }
};
s_main.cpp
#include <iostream>
#include "ltsl.hpp"
int main(){
SList<double> slist;
char opt= 'Q';
bool running = true;
while (running == true){
std::cout << std::endl;
std::cout << " *** Options ***" << std::endl;
std::cout << "(B) - Build List" << std::endl;
std::cout << "(P) - Print List" << std::endl;
std::cout << "(D) - Print Detailed List" << std::endl;
std::cout << "(I) - Insert New Node Before" << std::endl;
std::cout << "(i) - Insert New Node After" << std::endl;
std::cout << "(p) - Prepend New Node" << std::endl;
std::cout << "(A) - Append New Node" << std::endl;
std::cout << "(V) - View Node" << std::endl;
std::cout << "(R) - Remove Node" << std::endl;
std::cout << "(G) - Grab Node" << std::endl;
std::cout << "(d) - Delete Node" << std::endl;
std::cout << "(s) - Sort List (Ascending)" << std::endl;
std::cout << "(C) - Clear List" << std::endl;
std::cout << "(Q) - Quit Demo Programme" << std::endl;
std::cout << std::endl << "Choice: ";
std::cin >> opt;
if (opt == 'P'){
std::cout << std::endl;
SNode<double>* curr = slist.find_node(0);
unsigned long long c = 0;
std::cout << "NULL";
while (curr != NULL){
std::cout << "-> (" << c << "[" << curr->data << "]) ";
curr = curr->next;
if (curr == NULL) std::cout << "-> NULL";
c++;
}
std::cout << std::endl;
}
else if (opt == 'D'){
std::cout << std::endl;
SNode<double>* curr = slist.find_node(0);
unsigned long long c = 0;
std::cout << " list.capacity: " << slist.get_capacity() << std::endl;
std::cout << " list.head: " << curr << std::endl;
while (curr != NULL){
std::cout << "Node[" << c << "]->value: " << curr->data << std::endl;
std::cout << "Node[" << c << "] : " << curr << std::endl;
std::cout << "Node[" << c << "]->next : " << curr->next << std::endl;
if (curr->next == NULL){
std::cout << " list.tail: " << curr <<std::endl;
}
std::cout << std::endl;
curr = curr->next;
c++;
}
std::cout << std::endl;
}
else if (opt == 'V'){
unsigned long long i = 0;
std::cout << "Node to view: ";
std::cin >> i;
SNode<double>* tmp = slist.find_node(i);
std::cout << "Node: " << tmp << std::endl;
std::cout << "Node value: " << tmp->data << std::endl;
std::cout << "Node->next: " << tmp->next << std::endl;
}
else if (opt == 'B'){
unsigned long long c = 0;
bool build = true;
char cont = 'y';
while (build == true){
std::cout << "Node[" << c << "] value: ";
SNode<double>* tmp = new SNode<double>;
std::cin >> tmp->data;
slist.append_node(tmp);
std::cout << "Add more nodes? y/n: ";
std::cin >> cont;
if (cont != 'y') build = false;
c++;
}
}
else if (opt == 'A'){
SNode<double>* tmp = new SNode<double>;
std::cout << "New node value: ";
std::cin >> tmp->data;
slist.append_node(tmp);
}
else if (opt == 'p'){
SNode<double>* tmp = new SNode<double>;
std::cout << "New node value: ";
std::cin >> tmp->data;
slist.prepend_node(tmp);
}
else if (opt == 'C'){
slist.clear();
}
else if (opt == 'Q'){
std::cout << "Demo programme is exiting. Good-bye." << std::endl;
return false;
}
else if (opt == 's'){
slist.sort();
}
else if (opt == 'd'){
unsigned long long i = 0;
std::cout << "Node to delete: ";
std::cin >> i;
slist.delete_node(i);
}
else if (opt == 'G'){
unsigned long long i = 0;
std::cout << "Node to grab: ";
std::cin >> i;
SNode<double>* tmp = slist.grab_node(i);
std::cout << "Grabbed node : " << tmp << std::endl;
if (tmp != NULL){
std::cout << "Grabbed node value: " << tmp->data << std::endl;
std::cout << "Grabbed node->next: " << tmp->next << std::endl;
std::cout << "Deleting grabbed node..." << std::endl << std::endl;
delete tmp;
}
}
else if (opt == 'I'){
unsigned long long i = 0;
SNode<double>* tmp = new SNode<double>;
std::cout << "Node to insert before: ";
std::cin >> i;
std::cout << "Value of new node: " << std::endl;
std::cin >> tmp->data;
bool fail = slist.insert_before(i, tmp);
if (fail == true){
std::cout << "Sorry. Cannot insert before the specified node."
<< std::endl;
}
}
else if (opt == 'i'){
SNode<double>* tmp = new SNode<double>;
unsigned long long i = 0;
std::cout << "Node to insert after: ";
std::cin >> i;
std::cout << "Value of new node: ";
std::cin >> tmp->data;
bool fail = slist.insert_after(i, tmp);
if (fail == true){
std::cout << "Sorry. Cannot insert after the specified node."
<< std::endl;
}
}
}
return false;
}
user/dblanch1/portfolio/dataproject3.txt · Last modified: 2013/10/30 04:59 by dblanch1