01 Jul Programming Assignment 1: Linked Lists
Question Description
I have a C++ programming HW assignment that deals with linked listed. in the List.h file there is a comment that says TODO and those are what need to be done to complete the assignment. I included a handout document describing what needs to be done. If there are any questions please feel free to ask. thank you! ( this website wont let me upload .h and cpp files so im done leave in it text here for you to copy it.
Demo.cpp****************
#include “List.h”
#include
#include
#include
using namespace std;
List
// placeholder
return nullptr;
}
int main(int argc, char *argv[]){
List
List
List
int x;
int n, ndel;
n = 1000;
if(argc == 2) {
n = atoi(argv[1]);
}
for(x=1; x<=4; x++) { list->push_front(x);
}
list->print();
for(x=1; x<=4; x++) { list->push_back(x);
}
list->print();
list->pop_front(x);
cout << "popped " << x <
list->slow_remove_all(2);
cout << "after remove-all(2):\n"; list->print();
// string words[] = {“hello”, “goodbye”, “sunrise”, “sunset”};
string words[] = {“alice”, “bob”, “cathy”, “donald”};
for(int i=0; i<4; i++) { list2->push_front(words[i]);
list3->push_back(words[i]);
}
list2->print();
list3->print();
cout << "list sorted? " << list->is_sorted() << endl; cout << "list2 sorted? " << list2->is_sorted() << endl; cout << "list3 sorted? " << list3->is_sorted() << endl; // list2->front = NULL;
delete list;
delete list2;
delete list3;
/*** UNCOMMENT THIS CODE ONCE YOU HAVE WRITTEN YOUR
* slow_list FUNCTION
list = slow_list(n);
cout << "starting slow_remove_all (n=" << n << ")" << endl; ndel = list->slow_remove_all(0);
cout << "slow_remove_all done!" << endl;
cout << " num-deleted: " << ndel << endl;
cout << " list-len after: " << list->length() << endl;
delete list;
***/
return 0;
}
**********************************************************************************************************
List.h****************************************************************************************************
#ifndef LIST_H
#define LIST_H
#include
#include
using namespace std;
template
class List
{
private:
// struct for singly-linked list nodes
struct Node
{
T data;
Node *next;
Node( const T & d = T{}, Node * n = nullptr)
: data{ d }, next{ n } { }
};
public:
// constructors
List( ) {
init( );
}
~List( ) {
clear( );
}
/**
* Disclaimer: C++ conventions tell us that we should have a couple
* of additional constructors here (a copy constructor, assignment operator
* etc.)
*
* However, to keep things simple for now we will ignore that convention
* (since the exposure to C++ is pretty variable it seems — some students
* having taken 141 before last semester; some students coming from 107,
* etc.)
*/
/**
* function: clear
* desc: makes the calling list empty (but the list still
* exists).
*/
void clear(){
Node * p = front;
Node *pnext;
while(p != nullptr) {
pnext = p->next;
delete p;
p = pnext;
}
front = back = nullptr;
}
/**
* TODO
*
* function: length
* desc: returns the length of the calling list
*
* REQUIREMENTS: this is a working implementation, but
* it takes linear time.
*
* Your job (todo): make modifications so that this
* operation becomes constant time (O(1)).
*
* This task is different from most others in that most of
* the “real” work you do to make this work
* in O(1) time will be in _other_ functions which affect
* the length of lists.
*
* HINT: you are free to add data members to the List class…
* maybe for “bookkeeping”??
*/
int length( ) const {
Node *p = front;
int n=0;
while(p != nullptr) {
n++;
p = p->next;
}
return n;
}
public:
// Return true if the list is empty, false otherwise.
bool is_empty( ) const {
return front == nullptr;
}
void print() const {
Node *p = front;
cout << "[ "; while(p != nullptr) { cout << p->data << " "; p = p->next;
}
cout << "]\n"; } void push_front(const T & data) { front = new Node(data, front); if(back == nullptr) back = front; } bool pop_front(T &val) { Node *tmp; if(front==nullptr) return false; val = front->data;
tmp = front;
front = front->next;
delete tmp;
if(front==nullptr)
back = nullptr;
return true;
}
void push_back(const T & val) {
Node *tmp = new Node(val, nullptr);
if(front == nullptr) {
front = back = tmp;
}
else {
back->next = tmp;
back = tmp;
}
}
bool remove_first(const T &x) {
Node *p, *tmp;
T dummy;
if(front==nullptr) return false;
if(front->data == x) {
pop_front(dummy);
return true;
}
p = front;
while(p->next != nullptr) {
if(x == p->next->data) {
tmp = p->next;
p->next = tmp->next;
if(tmp == back)
back = p;
delete tmp;
return true;
}
p = p->next;
}
return false;
}
int slow_remove_all(const T &x) {
int n=0;
while(remove_first(x))
n++;
return n;
}
bool is_sorted() const {
Node *p = front;
while(p!=nullptr && p->next != nullptr) {
if(p->data > p->next->data)
return false;
p = p->next;
}
return true;
}
/** TODO
* function: count
* description: Counts number of occurrences
* of x in the list and returns that count.
*
* REQUIRMENT: Linear runtime (O(n) where n is the length
* of the list.)
*/
int count(const T &x) const {
return 0;
}
/* TODO
*
* function: pop_back
*
* if list is empty, we do nothing and return false
* otherwise, the last element in the list is removed, its
* value (data field) is assigned to the reference parameter
* data (so the removed element can be ‘passed-back’ to the
* caller) and true is returned.
*
* REQUIRMENT: Linear runtime (O(n) where n is the length
* of the list.)
*
*/
bool pop_back(T &data) {
return false;
}
/**
* TODO:
* function: equal_to
* description: returns true if lst1 and lst2
* contain exactly the same sequence of values.
* Returns false otherwise.
*
* REQUIRMENT: Linear runtime (O(n) where n is the length
* of the shorter of the two lists.
**/
bool equal_to(const List
return 0; // placeholder
}
/**
* TODO: print in reverse order
*
* Try to do without looking at notes!
* Hints: recursive helper function
*
* REQUIRMENT: Linear runtime (O(n) where n is the length
* of the list.)
*/
void print_rev() const {
}
/* TODO
* For full credit, you cannot allocate any new memory!
*
* description: self-evident
*
* REQUIRMENT: Linear runtime (O(n) where n is the length
* of the list.)
*/
void reverse() {
}
/** TODO
* function: fast_remove_all
* description: same behavior/semantics as
* slow_remove_all. However, this function
* must guarantee linear time worst case
* runtime (hence, “fast”).
*
* REQUIREMENT: linear worst-case runtime.
*
* Note: your solution may be either recursive or
* iteratieve.
**/
int fast_remove_all(const T &x) {
return 0;
}
/** TODO
* function: insert_sorted
*
* description: assumes given list is already in sorted order
* and inserts x into the appropriate position
* retaining sorted-ness.
* Note 1: duplicates are allowed.
*
* Note 2: if given list not sorted, behavior is undefined/implementation
* dependent. We blame the caller.
* So… you don’t need to check ahead of time if it is sorted.
*
*
* REQUIREMENTS:
*
* O(n) runtime
*/
void insert_sorted(const T &x) {
}
/** TODO
* function: merge_with
*
* description: assumes both list a and b are in
* sorted (non-descending) order and merges them
* into a single sorted list with the same
* elements.
*
* This single sorted list is stored in a while
* b becomes empty.
*
* if either of given lists are not sorted,
* we blame the caller and the behavior is
* implementation dependent — i.e., don’t worry
* about it!
*
* Condition in which both parameters are the same
* list (not merely “equal”), the function simply
* does nothing and returns. This can be tested
* with simple pointer comparison.
*
* Example:
*
* a: [2 3 4 9 10 30]
* b: [5 8 8 11 20 40]
*
* after call a.merge_with(b):
*
* a: [2 3 4 5 8 8 9 10 11 20 30 40]
* b: []
*
*
* REQUIREMENTS:
*
* Runtime Must be linear in the length of the
* resulting merged list (or using variables above,
* O(a.length()+b.length()).
*
* should not allocate ANY new list
* nodes — it should just re-link existing
* nodes.
*/
void merge_with(List &other){
}
/**
* TODO
* function: clone
*
* description: makes a “deep copy” of the given list a
* and returns it (as a List pointer).
*
* NOTE: this functionality would normally be folded into
* a “copy constructor”
*
*/
List * clone() const {
return nullptr;
}
/**
* TODO
* function: prefix
*
* description: removes the first k elements from the
* calling list which are used to form a new list
* which is then returned.
*
*if n is the length of the given list, we have the
*following boundary conditions:
*
* if k==0:
* calling list unchanged and an empty list returned
* if k>=n:
* calling becomes empty and a list containing
* all elements previously in lst is returned.
*
*examples:
*
* EX1: lst: [2, 3, 9, 7, 8]
*k: 3
*
*call:
*
* List
*
*after call:
* lst: [7, 8]
* returned list (prefix): [2, 3, 9]
*
* EX2 lst: [2, 3, 9, 7, 8]
*k: 0
*
* call:
*
* List
*
*after call:
* lst: [2, 3, 9, 7, 8] (unchanged)
* returned list: []
*
* EX3 lst: [2, 3, 9, 7, 8]
*k: 5
*
* call:
*
* List
*
*after call:
* lst: []
* returned list: [2, 3, 9, 7, 8]
*
* REQUIREMENTS:
*
* RUNTIME: THETA(n) worst case where n is the length of the given list
*
* ORDERING: the ordering of the returned prefix should be the same as
* in the given list
*
* MEMORY: for full credit, no new nodes should be
* allocated or deallocated; you should just
* “re-use” the existing nodes. HOWEVER, you will
* need to allocate a List object for the returned
* prefix (but, again, the underlying Nodes should be
* re-used from the calling list).
*/
List
return nullptr;
}
/**
* TODO
* function: filter_leq
*
* description: removes all elements of the given list (lst) which
*are less than or equal to a given value (cutoff)
*
*A list containing the removed elements is returned.
*
* examples:
*
* EX1: lst: [4, 9, 2, 4, 8, 12, 7, 3]
*cutoff: 4
*
*after call:
*lst: [9, 8, 12, 7]
*returned list: [4, 2, 4, 3]
*
* —————————————–
* EX2: lst: [6, 5, 2, 1]
*cutoff: 6
*
*after call:
*lst: []
* returned list: [6, 5, 2, 1]
*
* REQUIREMENTS:
*
* RUNTIME: THETA(n) where n is the length of the given list
*
* ORDERING: the ordering of the returned list should be the same as
* in the given list
*
* MEMORY: for full credit, no new nodes should be allocated or deallocated;
* you should just “re-use” the existing nodes. HOWEVER, you will
* need to allocate a LIST structure itself (i.e., for the returned
* list).
*
*/
List * filter_leq(const T & cutoff) {
return nullptr;
}
/**
* TODO
* function: concat
*
* description: concatenates the calling list with parameter list (other)
* The resulting concatenation is reflected the calling list; the
* parameter list (other) becomes empty.
*
* example:
*
* EX1: a: [2, 9, 1]
* b: [5, 1, 2]
*
* call:
* a.concat(b);
*
* after call:
*
*a: [2, 9, 1, 5, 1, 2]
*b: []
*
* REQUIREMENTS:
*
* runtime: O(1)
*
* sanity: this operation makes sense when a and b
*are distinct lists. For example, we don’t
*want/allow the caller to do something like
*this:
*
*List
*
*my_list->push_front(my_lst, 4);
*my_list->push_front(my_lst, 2);
*
*my_lst->concat(my_lst);
*
*your implementation must detect if it is being
*called this way. If so the function does nothing
*and (optionally) prints an error message to
*stderr.
*
*/
void concat(List
if(this == &other) {
cerr << "warning: List::concat(): calling object same as parameter"; cerr << "\n list unchanged\n"; return; } cout << "List::concat(): no error...\n"; } /** * TODO * * function: compare_with * description: compares the calling list with parameter list (other) * "LEXICALLY" (essentially a generalization of dictionary * ordering). * * link: https://en.wikipedia.org/wiki/Lexicographical_orde... * * Return Value: * * o if the two lists are identical, 0 is returned. * o if the calling list is lexically BEFORE the other list, * -1 is returned * o otherwise, the other list is lexically before the calling * list and 1 (positive one) is returned. * * Properties and examples: * * The empty list is lexically before all non-empty lists * (you can say it is "less than" all non-empty lists). * * Examples (using mathematical notation): * * [2 5 1] < [3 1 1 1 1] (think dictionary ordering!) * * [4 1 3] < [4 1 3 0 0 0] (prefix: just like "car" is before * "cartoon" in the dictionary). * * [4 5 6 1 2 3 9 9 9] < [4 5 6 1 4 0 0] * ^ ^ * (they have a common prefix of length 4; but at * the fifth position they differ and the left list * is the winner (smaller) -- no need to look further) * * * Templates? * * Since List is a template class, the elements of a particular * list need not be integers. For example, we could have * lists of strings. * * Good news: the exact same principle applies because * strings can be compared just like integers can be compared! * * Great news: you don't need to think about this at all! * The exact same code you would write if you assumed the element * type is integer will work for other types like strings. * * Why? Because, for example, all of these operators: * * <, <=, ==, > and >=
*
* all work on strings. They are not ‘built-in’ to C++, but
* the class string has “overloaded” these operators (they
* result in an appropriate function call).
*
* (In a subsequent exercise, we will do this kind of
* overloading ourselves!)
*
* Examples with lists of strings:
*
* [“egg”, “goat”] < ["egg", "globe", "apple"]
*
* ["zebra", "fun"] < ["zebra", "funny"]
*
* [Yes, the components of these lists are THEMSELVES compared
* lexically, but the string class is doing those comparisons)
*
*/
int compare_with(const List
return 0;
}
/*
* TODO
*
* function: suffix_maxes
*
* desc: constructs a new list of the same length as the calling object
* with the value stored at position i of the new list is the MAXIMUM
* value in the suffix (or tail) of the calling list starting from
* position i.
*
* This new list is returned and the calling list is unchanged.
*
* Example:
*
* Given List: [6, -18, 12, 4, 1, 7, 2, 5 4]
* ^^^^^^^^^^^^^^^^
*
* New list: [12, 12, 12, 7, 7, 7, 5, 5, 4]
* ^
*
* (as a sub-example, the marked entry in the new list
* (marked with ‘^’) is the max of the marked suffix in the
* given list (marked with a bunch of ‘^’s).
*
* REQUIREMENTS:
*
* Total Runtime: O(n)
* Calling list is unchanged.
*
*/
List
return nullptr;
}
private:
Node *front;
Node *back;
void init( ) {
front = nullptr;
back = nullptr;
}
};
#endif
Our website has a team of professional writers who can help you write any of your homework. They will write your papers from scratch. We also have a team of editors just to make sure all papers are of HIGH QUALITY & PLAGIARISM FREE. To make an Order you only need to click Ask A Question and we will direct you to our Order Page at WriteDemy. Then fill Our Order Form with all your assignment instructions. Select your deadline and pay for your paper. You will get it few hours before your set deadline.
Fill in all the assignment paper details that are required in the order form with the standard information being the page count, deadline, academic level and type of paper. It is advisable to have this information at hand so that you can quickly fill in the necessary information needed in the form for the essay writer to be immediately assigned to your writing project. Make payment for the custom essay order to enable us to assign a suitable writer to your order. Payments are made through Paypal on a secured billing page. Finally, sit back and relax.
About Writedemy
We are a professional paper writing website. If you have searched a question and bumped into our website just know you are in the right place to get help in your coursework. We offer HIGH QUALITY & PLAGIARISM FREE Papers.
How It Works
To make an Order you only need to click on “Order Now” and we will direct you to our Order Page. Fill Our Order Form with all your assignment instructions. Select your deadline and pay for your paper. You will get it few hours before your set deadline.
Are there Discounts?
All new clients are eligible for 20% off in their first Order. Our payment method is safe and secure.