односвязано Список: Функции-члены

Question

Я с трудом пытается сделать эти последние функции в моей программе односвязного списка:

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); 

Я не знаю, как сделать это. Вот мой код

StringNode.h

#ifndef STRING_NODE_H 
#define STRING_NODE_H 

#include <string> 

// A node in string singly linked list 
class StringNode { 
private: 
    // element value of a node 
    std::string elem; 

    // pointer to the next node in the 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" 

Строка односвязанны список класс StringLinkedList { частное: // указатель на голову списка StringNode * head; StringNode * Tail; // размер перечня int n;

public: 
    // default constructor 
    StringLinkedList(); 

    // destructor 
    ~StringLinkedList(); 

    // ## this function is provided ## 
    // return the string representation of the list; each node is seperated 
    // by "->" 
    // example: 
    //  "A->B->C" (without quotes) 
    //   A is the head node, C is the tail 
    //  "" (without quotes) 
    //   empty list 
    std::string toString(); 

    // return true if the list is empty, false otherwise 
    bool empty() const; 

    // return the number of nodes in the list 
    // note: take advantage of the private member we have, implement this 
    //  running with O(1) 
    int size() const; 

    // return the element of front node 
    const std::string& front() const throw (EmptyException); 

    // return the element of back node 
    const std::string& back() const throw (EmptyException); 

    // return the element of a node at a specific index (index) of the list 
    // EmptyException is thrown if the list is empty 
    // The index should be in range of [0, n-1], which is 0 <= index <= (n-1) 
    // OutOfBoundException is thrown if index is out of that range 
    const std::string& get(int index) const throw (EmptyException, OutOfBoundException); 

    // add a new node with element e to the front of the list 
    void addFront(const std::string& e); 

    // add a new node with element e to the back of the list 
    void addBack(const std::string& e); 

    // insert a new node at a specific position (pos) of the list; 
    // the position should be in range of [0, n], which is 0 <= pos <= n. 
    // OutOfBoundException is thrown if index is out of that range 
    // 
    // example: 
    //  A->B 
    //   position can be inserted is 0 (before A), 1 (between 
    //   A and B), 2 (after B); other positions will cause 
    //   OutOfBoundException 
    void insert(int pos, const std::string& e) throw (OutOfBoundException); 

    // remove the front node from the list 
    // EmptyException is thrown if the list is empty 
    void removeFront() throw (EmptyException); 

    // remove the back node from the list 
    // EmptyException is thrown if the list is empty 
    void removeBack() throw (EmptyException); 

    // remove a node at a specific index (index) of the list; the 
    // index should be in range of [0, n-1], which is 0 <= index <= (n-1) 
    // OutOfBoundException is thrown if index is out of that range; 
    // EmptyException is thrown if the list is empty. 
    // 
    // example: 
    //  A->B 
    //   position can be removed is 0 (A), 1 (B); otherwise 
    //   position will cause OutOfBoundException 
    void remove(int index) throw (EmptyException, OutOfBoundException); 

    // remove the first node that has a matched element e, starting from 
    // the head node; return true if a match is found, false otherwise 
    bool remove(const std::string& e); 

    // remove the ALL elements that are matched e; return true if a match 
    // is found, false otherwise 
    bool removeAll(const std::string& e); 

    // reverse the order of the 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(); 
} 

// return the string representation of the list; each node is seperated by "->" 
std::string StringLinkedList::toString() { 
    // return blank if the list is empty 
    if (head == NULL) 
     return ""; 

    // traverse to each node and append element of each 
    // node to final output string 
    std::string out = ""; 
    StringNode *node = head; 
    while (node != NULL) { 
     out += node->elem + "->"; 
     node = node->next; 
    } 

    // return final string without last "->" 
    return 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"); 
    return head->elem; 
} 
const std::string& StringLinkedList::back() const throw (EmptyException) 
{ 
    if(tail==0)throw EmptyException("empty tail"); 
    return 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; 
} 

спасибо за любую помощь

Answer 1

Вы, кажется, есть все методы, необходимые уже для них. Вот какой-то псевдокод.

size - в основном то же, что и ваша функция toString, за исключением того, что вы считаете, а не строят строку (это проще!).

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

get - это же еще раз, за ​​исключение того, что вы остановитесь, как только вы расположены правый узел

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

remove будет немного сложнее. Сначала вы удаляете удаляемый узел, чем исправляете следующий указатель предыдущего узла, чтобы пропустить его.

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

После того, что цикл закончится:

• если prev еще нулевой, либо первый элемент соответствует (индекс дал это 0 или строка в элемента соответствует), или список был пуст. Если первый элемент соответствует, у вас уже есть код для его удаления.
• если current - null, вы не нашли его.
• если prev и current действительны, вы согласовали и должны устранить ток. Сделать prev->next указывает на current->next.

Не забывайте освобождать удаленные узлы. removeAll - это то же самое, что и remove, за исключением того, что вы не останавливаетесь, как только обнаруживаете удаляемый узел, и вам придется немного подумать о том, что (true/false) вам нужно вернуть.

тест

Всегда по крайней мере:

• пустой список
• список только с одним элементом
• список с более чем одного элемента
• индекс 0, отрицательные индексы, действительный не- нулевой индекс, индекс за пределами списка
• удалить, что сделает список пустым, removeAll, который сделает список пустым
• удалить и удалить veAll, что не будет сделать список пустым