0

リンクされたリストで2つのセットの違いを取得しようとしているTm

例:
入力:
セット 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は非常に複雑です。リストは並べ替えられているため、不一致の要素を見つけるだけで済みます。これには、各反復で移動する1つのループが必要です。

  • 要素が両方のセットにある場合、つまり違いの一部ではない場合は、両方のイテレータ
  • 最初のリストのイテレータ。この場合、最初のセットにはあるが2番目のセットにはない要素があります。
  • 2番目のリストのイテレータ。この場合、2番目のセットにはあるが、最初のセットにはない要素があります。

の実装Intersectionも同様に複雑すぎて、ループが1つだけ必要です。これは、の要素が格納されていない場合に共通の値を格納するだけです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 に答える