0

Tm 试图获取链表中 2 个集合的差异

示例：
输入：
A 组：1 - 2 - 3 - 5
B 组：2 - 4 - 5

输出：并集
：5 - 4 - 2 - 5 - 3 - 2 - 1
交点：5 - 2
差值：3 - 4 - 1（这里的问题）我的输出差异：5 - 3 - 2 - 1

此代码位于“LinkedList.h”下

#include "Node.h"
#include <iostream>

using namespace std;

class LinkedList
{      
   public:
  Node *head;
  LinkedList()
  {
       head = NULL;
  }

  bool find(Node *value)
  {
       int cnt(0);
       Node *iterator = head;
       while(iterator != NULL)
       {
             if(value->data == iterator->data) return 1;
             iterator = iterator->next;
       }

       return cnt;
  }

  void insertBeginning(int value)
  {

       Node *newNode = new Node;
       newNode->data = value;

       if(find(newNode) != 1)
       {
             Node *temp = head;
             head = newNode;
             newNode->next = temp;
       }
  }      

  void deleteBeginning()
  {
       if(head != NULL)
       {
               Node *temp = head->next;
               head = temp;
       }
  }

  void display()
  {

       Node *iterator = head;
       while (iterator != NULL)
       {
             cout<<iterator->data<<" ->";
             iterator = iterator->next;
       }
       cout<<" end";
  }

  bool isEmpty()
  {
       int c;
       head == NULL ? c = 1: c = 0;
       return c;
   }
}; 



class Set:public LinkedList
{
  public:

  void Union(Set& myListA,Set& myListB)
  {

        for(Node* iterator1 = myListA.head; iterator1 != NULL; iterator1 = iterator1->next)
        {
            LinkedList::insertBeginning(iterator1->data);
        }
        for(Node* iterator2 = myListB.head; iterator2 != NULL; iterator2 = iterator2->next)
        {
            LinkedList::insertBeginning(iterator2->data);      
        }
  }

  void Intersection(Set& myListA, Set& myListB)
  {
           for(Node* iterator3 = myListA.head; iterator3 != NULL; iterator3 = iterator3->next)
           {
                        //if(LinkedList::find(iterator3) != 1)
                        for(Node* iterator4 = myListB.head; iterator4 != NULL; iterator4 = iterator4->next)
                        {
                                  //if(LinkedList::find(iterator4) != 1)
                                  if( iterator3->data == iterator4->data )
                                  {
                                      LinkedList::insertBeginning(iterator4->data);
                                  }
                        }
           }
  }

  void Difference(Set& myListA, Set& myListB)
  {
       for(Node* iterator5 = myListA.head; iterator5 != NULL; iterator5 = iterator5->next)
        {

            for(Node* iterator6 = myListB.head; iterator6 != NULL; iterator6 = iterator6->next)
            {
            if (iterator6->data != iterator5->data && LinkedList::find(iterator5) != 1 && LinkedList::find(iterator6) != 1) {
                  LinkedList::insertBeginning(iterator5->data);
                  }
            else {
                 continue;
                 }   
            }
        }

  }
};

这是在“Node.h”下

class Node
{
   public:
      int data;
      Node *next;
};
4

2 回答 2

2

您的实现Difference太复杂了：由于您的列表已排序，您需要做的就是找到不匹配的元素。这需要一个循环，您在每次迭代中移动

  • 如果元素在两个集合中，则两个迭代器，即它不是差异的一部分
  • 第一个列表的迭代器，在这种情况下，您有一个元素在第一个集合中但不在第二个集合中
  • 第二个列表的迭代器，在这种情况下，您有一个元素在第二个集合中但不在第一个集合中

您的实现Intersection同样过于复杂，并且只需要一个循环：它只会在没有存储元素的情况下存储公共值 for Difference()。最后，Union()还是太复杂了：它会在每次迭代中存储一个元素，要么是普通的，要么是跳过的，这取决于采用哪个分支。这也将产生正确的结果。

显然，你真正想要使用的是

std::set_intersection(s0.begin(), s0.end(), s1.begin(), s1.end(),
                      std::back_inserter(result_intersection));
std::set_union(s0.begin(), s0.end(), s1.begin(), s1.end(),
               std::back_inserter(result_union));
std::set_symmetric_difference(s0.begin(), s0.end(), s1.begin(), s1.end(),
                              std::back_inserter(result_difference));

假设您已经为列表和迭代器提供了标准接口。

于 2012-03-18T14:30:45.833 回答
0

7年后你的答案

void Difference(Set& ListA, Set& ListB)
    {
        for (member* i5 = ListA.head; i5 != NULL; i5 = i5->next)
        {

            for (member* i6 = ListB.head; i6 != NULL; i6 = i6->next)
            {
                if (i6->data != i5->data && ListA.find(i6) != 1 && ListB.find(i5) != 1) {
                    List::insert(i5->data);
                    List::insert(i6->data);
                }
                else {
                    continue;
                }
            }
        }
    }
于 2019-03-22T14:01:25.183 回答