单链表:成员函数

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*头；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为null，则表示您没有找到它
• 如果prev和current有效，则匹配并需要删除current。使prev->next指向current->next

请记住取消分配已删除的节点。removeAll与remove相同，只是在找到要删除的节点后不会停止，并且您必须考虑需要返回什么（true/false）。

始终至少使用进行测试

• 空列表
• 只有一个元素的列表
• 包含多个元素的列表
• 索引0，负索引，有效的非零索引，超出列表的索引
• remove将使列表变空，removeAll将使列表为空
• remove和remove不会使列表为空的所有内容