单链接列表：成员函数

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

我不太知道如何做这些。这是我的密码

#####################################################################################

#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{Private：//指向列表头部的指针StringNode*head； StringNode*Tail；//size of the list 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或项的字符串匹配），或者列表为空。如果第一个元素匹配，那么您已经有了删除它的代码
• 如果当前<代码>为空，则未找到它
• 如果prev和current有效，则匹配并需要删除当前。使prev-

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

始终至少使用以下设备进行测试：

• 空列表