0

我有一个包含雇主名称的列表，例如：

节点 1：吉尔、马特、乔、鲍勃、马特

节点 2：杰夫、詹姆斯、约翰、乔纳森、约翰、爱德华

节点 3：马特、多伊、罗恩、巴勃罗、罗恩、蔡斯、罗恩、蔡斯、路易

我正试图让它到达哪里，如果它看到重复，它将把它发送到列表的前面并删除该当前节点，这样它就会看起来像这样

节点 1：马特、吉尔、乔、鲍勃

节点 2：约翰、杰夫、詹姆斯、乔纳森、爱德华

节点 3：Chase、Ron、Matt、Doe、Pablo、Loui

不幸的是，我的输出接近我想要的。它正在删除重复的条目，但不会发送到前面。.

我的输出：

节点 1：吉尔、马特、乔、鲍勃、

4

4 回答 4

1

好吧，走着瞧：

当你击中if (ptr->data == p->data)那个点时：

  • pp指向列表的末尾
  • p你是新节点吗（没有任何东西指向它，它也没有指向任何东西）
  • ptr指向具有重复数据的节点

为了删除节点，您实际上需要有指向的next指针，ptr否则如何ptr从列表中删除？所以你实际上需要检查：

if (head && head->data == p->data)
{
    // do nothing as duplicate entry is already head of list
    delete p;
    return;
}

node *ptr = head;
while (ptr)
{
    if (ptr->next && ptr->next->data == p->data)
    {
        node *duplicate = ptr->next;
        ptr->next = duplicate->next; // skip the duplicate node
        duplicate->next = head;      // duplicate points to head
        head = duplicate;            // head is now the duplicate
        delete p;                    // otherwise leaking memory
        return;
    }
    ptr = ptr->next;
}

if (pp) // points to tail as per your code
{
    pp->next = p;
    ++N;
}
于 2013-09-23T00:57:13.483 回答
0

我将您的变量名称更改为更具可读性，但保留前向声明以防您想要这样。我发现的问题是您总是在列表末尾插入节点，无论您是否发现它是重复的。此外，您的评论行看起来很接近，但仅当单独出现时。有了这些pp=p东西，它会引起问题。尝试以下方法，看看它是否有效。你仍然会泄漏内存，但它会让你开始：

void list::put(int i) {  //Where i is a random number
    node *current =head;
    node *added =new node(employers[i]);
    node *tail =head;
    node *prev = NULL;
    bool foundRepeat = false;



    while (current!=NULL)
    {
        if (current->data == added->data)
        {  
            if (prev)
                prev->next = current->next;

            current->next=head;
            head=current;
            foundRepeat = true;
            break;
        }
        prev = current;
        current=current->next;
    }

    if (!foundRepeat)
    {
        while (tail->next) 
        {
            tail=tail->next;
        }
        tail->next=added;
    }

    N++;
}
于 2013-09-23T00:48:24.510 回答
0

对于它的价值，我可能会这样实现它。

class EmployerCollection
{
public:
    typedef std::list<std::string> EmployerList;

public:
    bool AddEmployer(const std::string& name)
    {
        EmployerList::const_iterator it = std::find(m_employers.begin(), m_employers.end(), name);
        if (it != m_employers.end()) // Already exists in list.
        {
            m_employers.splice(m_employers.begin(), m_employers, it, std::next(it));
            return true;
        }
        m_employers.push_front(name);
        return false;
    }

private:
    EmployerList m_employers;
};

int main()
{
    const int NUM_EMPLOYERS = 15;
    std::string employers[NUM_EMPLOYERS] = {"Jill", "Jeff", "Doe", "Pablo", "Loui", "Ron", "Bob", "Joe", "Monica", "Luis", "Edward", "Matt", "James", "Edward", "John"};

    EmployerCollection c;

    for (int i=0; i<NUM_EMPLOYERS; i++)
    {
        bool duplicate = c.AddEmployer(employers[i]);
        printf("Added %s to employer list - duplicate: %s \n", employers[i].c_str(), duplicate ? "True" : "False");
    }

    system("pause");
}
于 2013-09-23T01:05:29.607 回答
0

我添加了一个查找功能

typedef struct node{
  string data;
  struct node *net, *prev;
 }node;      


class list {
public:
    list():head(NULL), N(0){}
    ~list(){
    //Implementation for cleanup
     }

void add(string name){  //rather than accessing the global data, use the value passed
    node* p = new node(name);
    p->next=p->prev=NULL;
    node* pp = find(name);
    if(pp==NULL){
      // No match found, append to rear
      if(head==NULL)
        head=p;  //list empty, add first element
      else{
        node* cur=head;
        while(cur->next!=NULL) //Keep looking until a slot is found
          cur=cur->next;
        cur->next=p;
        p->prev=cur;
      }
    }
    else{
        //Match found, detach it from its location
        node* pPrev = pp->prev;
        pPrev->next = pp->next;
        pp->next->prev=pPrev;
        p->next = head; //append it to the front & adjust pointers
        head->prev=p;
    }
    N++;
    }

    //MER: finds a matching element and returns the node otherwise returns NULL
    node* find(string name){
        node *cur=head;
        if(cur==NULL) // is it a blank list?
          return NULL;
        else if(cur->data==head) //is first element the same?
          return head;
        else   // Keep looking until the list ends
          while(cur->next!=NULL){
          if(cur->data==name)
            return cur;
            cur=cur->next;
          }
        return NULL;
}
friend ostream& operator << (ostream& os, const list& mylist);

private:
    int N;
    node *head;

};

现在有些人可能会告诉您使用 STL n 中的列表永远不要编写自己的代码，因为您无法击败 STL，但对我来说，您自己实现以清楚了解它在现实中是如何工作的，这很好。

于 2013-09-24T06:33:23.640 回答