单链表：会员功能

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 *尾巴; //列表大小 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仍然是null，则匹配的第一个元素（定索引0或项目的字符串匹配），或列表是空的。如果第一个元素匹配，您已经有代码将其删除。
• 如果current为空，则表示没有找到它。
• 如果prev和current有效，则表示您匹配并需要删除当前值。使prev->next指向current->next。

记得取消分配已删除的节点。 removeAll与remove相同，除非您在找到要删除的节点后才会停下来，而且您必须考虑一下您需要返回的内容（真/假）。

始终测试与至少：

• 空列表
• 与恰好一个要素
• 与多于一个的元件
• 索引0，负指数，非有效的列表的列表零指数，超出列表的索引
• 删除将使列表为空，removeAll将使列表为空
• remove和remo ve所有不会使列表空