2つの単一リンクリストをマージして3つ目のリストを作成する関数

Question

したがって、ユーザーが2つのリンクリストを整数で埋めるプログラムを作成しています。重複のないリスト。両方のリストに入力要素とは、それらを見ることができ、ユーザだから今

#include <iostream> 
#include <stdlib.h> 
using namespace std; 

struct node 
{ 
    int info; 
    node *next; 
    node (int i, node *n=NULL) 
    { 
     info = i; 
     next = n; 
    } 
    ~node() 
    { 
     cout <<"NODE CONTAINING \"" << info << "\" WAS DELETED!" << endl; 
    } 
}; 
struct list 
{ 
    node* startList1, *lastList1, *startList2, *lastList2; 
    int menuOption; 
    int nodeCount1=0, nodeCount2=0; 


    list() { 
     startList1 = NULL; 
     startList2 = NULL; 

    } 


    void addList1(node *p) 
    { 
     int n; 
     cout << "PLEASE INPUT VALUE WHICH YOU WANT IN THE NODE:"; 
     cin >> n; 
     p = new node(n); 
     nodeCount1++; 
     if(startList1==NULL) 
     { 
      startList1 = lastList1 = p; 
     } 
     else 
     { 
      lastList1->next = p; 
      lastList1 = p; 
     } 
    } 

    void printList1(node *pr) 
    { 
     node *pr; 
     for (pr=startList1; pr!=NULL; pr=pr->next) 
     { 
      cout << pr->info << endl; 
     } 
    } 



    void addList2(node *q) 
    { 
     int n; 
     cout << "PLEASE INPUT VALUE WHICH YOU WANT IN THE NODE:"; 
     cin >> n; 
     q = new node(n); 
     nodeCount2++; 
     if(startList2==NULL) 
     { 
      startList2 = lastList2 = q; 
     } 
     else 
     { 
      lastList2->next = q; 
      lastList2 = q; 
     } 
    } 
    void printList2(node *pr) 
    { 
     for (pr=startList2; pr!=NULL; pr=pr->next) 
     { 
      cout << pr->info << endl; 
     } 
    } 

    // this just prints first and second lists to show what is inside.. 
    void printBoth(node *pr, node *qr) 
    { 
     cout << "Elements of the first list:" << endl; 
     for (pr=startList1; pr!=NULL; pr=pr->next) 
     { 
      cout << pr->info << endl; 
     } 
     cout << "Elements of the second list:" << endl; 
     for (pr=startList2; pr!=NULL; pr=pr->next) 
     { 
      cout << pr->info << endl; 
     } 
    } 


    void printMenu() 
    { 
     cout << "MENU" << endl; 
     cout << "(1) ADD ELEMENT LIST1." << endl; 
     cout << "(2) PRINT LIST1" << endl; 
     cout << "(3) ADD ELEMENT LIST2" << endl; 
     cout << "(4) PRINT LIST2" << endl; 
     cout << "(5) PRINT BOTH LISTS" << endl; 
    cout << "(6) USE MERGE FUNCTION" << endl; 
     cout << "(7) TO EXIT" << endl; 

     cin >> menuOption; 
     system ("cls"); 
    }; 


    void dragons() 
    { 

     node *temp1 = startList1; 
     node *temp2 = startList2; 
     while(temp1) 
     { 
      temp1 = startList1->next; 
      delete startList1; 
      startList1=temp1; 
     } 
     while(temp2) 
     { 
      temp2 = startList2->next; 
      delete startList2; 
      startList2=temp2; 
     } 
    };  

}; 

int main() 
{ 
    struct node *p = NULL, *q = NULL; 

    list s; 
    s.printMenu(); 
    node* list1; 
    node* list2; 
    node* sorting; 
    while(s.menuOption!=7) 
    { 
     switch (s.menuOption) 
     { 
      case 1: s.addList1(list1); 
        break; 
      case 2: s.printList1(list1); 
        break; 
      case 3: s.addList2(list2); 
        break; 
      case 4: s.printList2(list2); 
        break; 
      case 5:s.printBoth(list1, list2); 
        break; 
      case 6:s.merge(); 
        break; 
      default: cout << "SOMETHING WENT WRONG!!!!" << endl; 
        break; 
     } 
     system ("pause"); 
     system ("cls"); 
     s.printMenu(); 
    } 
    s.dragons(); 
    return 0; 
} 

が、どのようにiは、重複した値なしでこれらのリストをマージする関数を作成することができます：ここで は私が今持っているコードですか？例えば、 List1 = 1,2,3,6,8; List2 = 2,4,5,7,8;

結合リスト= 1,2,3,4,5,7,8; （実際に注文しても問題ありません）

アドバイスありがとうございます！ありがとう！

Answer 1

コードのバージョンですが、リンクリストを提供するためにSTLリストコンテナを使用していますが、これはあなたが望むものを達成する独自の関数を提供します。このコードはデモンストレーションのためのものであり、効率の点で最適化されていないため、2つのリストから一意の要素をマージする方法を示しています。 （これを行うには、リストの要素をソートする必要があり、リスト内のノードに対して「より小さい」と「等しい」の述語を指定する必要があります。 STLのコンテナと関数のうち、多くの人が最初からrawポインタベースのリンクリストを作成するのではなく、そうすることをお勧めします）。

これは役に立ちます。

#include <iostream> 
#include <stdlib.h> 
#include <list> 

struct node 
{ 
    int info; 
    node (int i) 
    { 
     info = i; 
    } 
    ~node() 
    { 
     //std::cout <<"NODE CONTAINING \"" << info << "\" WAS DELETED!" << std::endl; 
    } 
}; 

bool nodeLess(node n1, node n2) 
{ 
    return n1.info < n2.info; 
} 

bool nodeEqual(node n1, node n2) 
{ 
    return n1.info == n2.info; 
} 

struct mylist 
{ 
    int menuOption; 

    std::list<node> list1; 
    std::list<node> list2; 

    void addList(std::list<node>& l) 
    { 
     int x; 
     std::cout << "PLEASE INPUT VALUE WHICH YOU WANT IN THE NODE: "; 
     std::cin >> x; 
     node n(x); 
     l.push_back(n); 
    } 

    void printList(const std::list<node>& l) 
    { 
     for (std::list<node>::const_iterator it = l.cbegin(); it != l.cend(); ++it) 
     { 
      std::cout << it->info << std::endl; 
     } 
    } 

    void addList1() { addList(list1); } 
    void addList2() { addList(list2); } 

    void printList1() { printList(list1); } 
    void printList2() { printList(list2); } 

    // this just prints first and second lists to show what is inside.. 
    void printBoth() 
    { 
     std::cout << "Elements of the first list:" << std::endl; 
     printList1(); 
     std::cout << "Elements of the second list:" << std::endl; 
     printList2(); 
    } 

    void simpleMerge() 
    { 
     std::list<node> merged; 
     merged.insert(merged.end(), list1.begin(), list1.end()); 
     merged.insert(merged.end(), list2.begin(), list2.end()); 
     std::cout << "CONTENTS OF LIST1 THEN LIST2: " << std::endl; 
     printList(merged); 
    } 

    void uniqueSortMerge() 
    { 
     std::list<node> sorted1(list1.begin(), list1.end()); 
     std::list<node> sorted2(list2.begin(), list2.end()); 
     sorted1.sort(nodeLess); 
     sorted2.sort(nodeLess); 
     sorted1.unique(nodeEqual); 
     sorted2.unique(nodeEqual); 
     std::list<node> merged; 
     std::merge(sorted1.begin(), sorted1.end(), 
        sorted2.begin(), sorted2.end(), 
        std::back_inserter(merged), 
        nodeLess); 
     std::cout << "UNIQUE CONTENTS OF LIST1 AND LIST2 SORTED AND MERGED: " << std::endl; 
     printList(merged); 
    } 

    void printMenu() 
    { 
     std::cout << "MENU" << std::endl; 
     std::cout << "(1) ADD ELEMENT LIST1." << std::endl; 
     std::cout << "(2) PRINT LIST1" << std::endl; 
     std::cout << "(3) ADD ELEMENT LIST2" << std::endl; 
     std::cout << "(4) PRINT LIST2" << std::endl; 
     std::cout << "(5) PRINT BOTH LISTS" << std::endl; 
     std::cout << "(6) USE SIMPLE MERGE FUNCTION" << std::endl; 
     std::cout << "(7) USE UNIQUE, SORT AND MERGE FUNCTION" << std::endl; 
     std::cout << "(8) TO EXIT" << std::endl; 

     std::cin >> menuOption; 
     system ("cls"); 
    }; 


    void dragons() 
    { 
     list1.clear(); 
     list2.clear(); 
    }; 
}; 

int main() 
{ 
    mylist s; 

    do 
    { 
     s.printMenu(); 
     switch (s.menuOption) 
     { 
      case 1: 
       s.addList1(); 
       break; 
      case 2: 
       s.printList1(); 
       break; 
      case 3: 
       s.addList2(); 
       break; 
      case 4: 
       s.printList2(); 
       break; 
      case 5: 
       s.printBoth(); 
       break; 
      case 6: 
       s.simpleMerge(); 
       break; 
      case 7: 
       s.uniqueSortMerge(); 
       break; 
      case 8: 
       break; 
      default: 
       std::cout << "SOMETHING WENT WRONG!!!!" << std::endl; 
       break; 
     } 
     system ("pause"); 
     system ("cls"); 
    } while(s.menuOption != 8); 

    s.dragons(); 
    return 0; 
}