c++ - Singly Linked List: Member functions -

c++ - Singly Linked List: Member functions -

i having hard time trying these lastly functions in singly linked list programme :

int size() const; const std::string& get(int index) const throw (emptyexception, outofboundexception); void remove(int index) throw (emptyexception, outofboundexception); bool remove(const std::string& e); bool removeall(const std::string& e);

i dont quite know how these. here code

stringnode.h

#ifndef string_node_h #define string_node_h #include <string> // node in string singly linked list class stringnode { private: // element value of node std::string elem; // pointer next node in list stringnode *next; // provide stringlinkedlist access friend class stringlinkedlist; }; #endif

stringlinkedlist.h

#ifndef string_linked_list_h #define string_linked_list_h #pragma warning(disable: 4290) #include "stringnode.h" #include "exception.h"

string singly linked list class stringlinkedlist { private: // pointer head of list stringnode *head; stringnode *tail; // size of list int n;

public: // default constructor stringlinkedlist(); // destructor ~stringlinkedlist(); // ## function provided ## // homecoming string representation of list; each node seperated // "->" // example: // "a->b->c" (without quotes) // head node, c tail // "" (without quotes) // empty list std::string tostring(); // homecoming true if list empty, false otherwise bool empty() const; // homecoming number of nodes in list // note: take advantage of private fellow member have, implement // running o(1) int size() const; // homecoming element of front end node const std::string& front() const throw (emptyexception); // homecoming element of node const std::string& back() const throw (emptyexception); // homecoming element of node @ specific index (index) of list // emptyexception thrown if list empty // index should in range of [0, n-1], 0 <= index <= (n-1) // outofboundexception thrown if index out of range const std::string& get(int index) const throw (emptyexception, outofboundexception); // add together new node element e front end of list void addfront(const std::string& e); // add together new node element e of list void addback(const std::string& e); // insert new node @ specific position (pos) of list; // position should in range of [0, n], 0 <= pos <= n. // outofboundexception thrown if index out of range // // example: // a->b // position can inserted 0 (before a), 1 (between // , b), 2 (after b); other positions cause // outofboundexception void insert(int pos, const std::string& e) throw (outofboundexception); // remove front end node list // emptyexception thrown if list empty void removefront() throw (emptyexception); // remove node list // emptyexception thrown if list empty void removeback() throw (emptyexception); // remove node @ specific index (index) of list; // index should in range of [0, n-1], 0 <= index <= (n-1) // outofboundexception thrown if index out of range; // emptyexception thrown if list empty. // // example: // a->b // position can removed 0 (a), 1 (b); otherwise // position cause outofboundexception void remove(int index) throw (emptyexception, outofboundexception); // remove first node has matched element e, starting // head node; homecoming true if match found, false otherwise bool remove(const std::string& e); // remove elements matched e; homecoming true if match // found, false otherwise bool removeall(const std::string& e); // reverse order of list // example: // a->b->c->d // after reverse(), d->c->b->a void reverse(); }; #endif

stringlinkedlist.cpp

#include "stringlinkedlist.h" // default constructor (completed) stringlinkedlist::stringlinkedlist() : head(null), n(0) { } // destructor stringlinkedlist::~stringlinkedlist() { while(!empty()) removefront(); } // homecoming string representation of list; each node seperated "->" std::string stringlinkedlist::tostring() { // homecoming blank if list empty if (head == null) homecoming ""; // traverse each node , append element of each // node final output string std::string out = ""; stringnode *node = head; while (node != null) { out += node->elem + "->"; node = node->next; } // homecoming final string without lastly "->" homecoming out.substr(0, out.size()-2); } bool stringlinkedlist::empty() const {return head==null;} const std::string& stringlinkedlist::front() const throw (emptyexception) { if(head==0)throw emptyexception("empty head"); homecoming head->elem; } const std::string& stringlinkedlist::back() const throw (emptyexception) { if(tail==0)throw emptyexception("empty tail"); homecoming tail->elem; } void stringlikedlist::addfront(const std::string& e) { stringnode* v= new stringnode; v->elem=e; v->next=head; head=v; } void stringlinkedlist::addback(const std::string& e) { stringnode* node=head; while(node->next!=null) node=node->next; stringnode* v=new stringnode; v->elem=e; v->next=null; node->next=v; } void stinglinkedlist::removefront() throw (emptyexception) { if(head==0) throw emptyexception("empty"); else { stringnode* remove; remove=head; if(head==tail) { head=null; tail=null; } else { head=head->next; } delete remove; } } void stringlinkedlist::removeback() throw (emptyexception) { if (tail==0)throw emptyexception("empty"); else { stringnode* remove; remove=tail; if(head==tail) { head=null; tail=null; } else { stringnode* previoustotail=head; while(previoustotail->next !=tail) previoustotail=previoustotail->next; tail=previoustotail; tail->next=null; } delete remove; } } void stringlinkedlist::reverse() { stringnode* temphead=head; stringnode* nodes=null; stringnode* nextnode=null: if (head==null) return; tail=head; nodes=head->next; while(nodes!=null) { nextnode=nodes; nodes=nodes->next; nextnode->next=temphead; temphead=nextnode; } head=temphead; tail->next=null; }

thanks help

you seem have techniques needed these. here's pseudo-code.

size - same thing tostring function, except count rather build string (it's easier!).

int count = 0; while (current != null) { count++; current = current->next; } homecoming count;

get - same again, except stop short 1 time you've located right node

int cur_index = 0; while ((current != null) && (cur_index < index)) { cur_index++; current = current->next; } // create sure found before you: homecoming current->data;

remove bit trickier. first locate node removed, prepare previous node's next pointer skip on it.

prev = null; while ((current != null) && (/* compare count or compare string */)) { /* update counter */ prev = current; current = current->next; }

once loop over:

if prev still null, either first element matched (index given 0 or item's string matched), or list empty. if first element matched, have code remove it. if current null, didn't find it. if prev , current valid, matched , need remove current. create prev->next point current->next.

remember deallocate removed nodes. removeall same remove, except don't stop 1 time you've found node remove, , you'll have think bit (true/false) need return.

always test @ least:

an empty list a list 1 element a list more 1 element index 0, negative indexes, valid non-zero index, index beyond list remove create list empty, removeall create list empty remove , removeall won't create list empty

c++ string visual-c++ linked-list singly-linked-list