Program C++: Gantikan nod pendua dalam senarai terpaut dengan salinan

Dalam artikel ini, kami diberikan senarai terpaut yang mengandungi elemen dari 1 hingga n dengan pendua. Elemen 1 hingga n akan sentiasa wujud dengan pendua dalam [1..n]. Kita perlu menggantikan setiap elemen berulang dengan n+1, n+2, dsb.

Mari kita pertimbangkan contoh

1→2→2→4→5→3→6→6

Seterusnya n = 42. Oleh itu, setiap pendua digantikan dengan n+1, n+2, dsb. 42 seterusnya digantikan dengan 47, 46 seterusnya digantikan dengan 48, dan contoh pertama kekal utuh.

Pertama, kita perlu membina pokok binari dalam kaedah utama seperti yang ditunjukkan di bawah -

Node* head = new Node(1);
head->next = new Node(2);
head->next->next = new Node(2);
head->next->next->next = new Node(4);
head->next->next->next->next = new Node(5);
head->next->next->next->next->next = new Node(3);
head->next->next->next->next->next->next = new Node(6);
head->next->next->next->next->next->next->next = new Node(6);
solve(head);

Kini nod adalah seperti berikut;

1→2→7→4→5→3→6→8

Seperti yang kita perhatikan, kita perlu menjejaki elemen yang kita lihat untuk mencari nilai permulaan n. Kami juga memerlukan mekanisme untuk menentukan elemen yang diulang untuk menggantikan nilainya.

Struktur data yang dicadangkan yang segera terlintas di fikiran dikenal pasti. Kami boleh mengulangi senarai terpaut dan menolak elemen ke dalam koleksi. Selepas menolak elemen dalam set, kita boleh mencari elemen terakhir, iaitu elemen terbesar yang terdapat dalam senarai terpaut, memandangkan set ialah struktur data yang diisih.

Dalam traversal kedua senarai terpaut, kita boleh menggunakan set sebagai cincang. Kami akan mencari setiap elemen dalam koleksi, dua situasi mungkin berlaku.

• Kami mencari elemen dalam koleksi, mengeluarkannya daripada koleksi dan menandainya.

• Kami tidak menemui elemen dalam set, bermakna kami sudah melihatnya dari pilihan satu dan kami akan menggantikannya dengan n seterusnya.

Contoh

Untuk menggantikan nod dengan nilai pendua dalam senarai terpaut, sila ikuti program C++ di bawah. Pelaksanaan C++ menggunakan struktur data pengumpulan untuk melintasi senarai terpaut, sekali gus memudahkan pencarian unsur pendua.

#include <iostream>
#include <set>
using namespace std;
class Node {
   public:
   int value;
   Node* next;
   Node(int value) {
      this->value = value;
      next = NULL;
   }
};
void solve(Node* head) {
   set<int> hash;
   Node* copy = head;
   while(copy) {
      hash.insert(copy->value);
      copy = copy->next;
   }
   auto it = hash.end();
   it--;
   int startingN = *it +1;
   while(head) {
      if(hash.find(head->value) != hash.end()) {
         hash.erase(head->value);
      } else {
         head->value = startingN++;
      }
      head = head->next;
   }
}
void printList(Node* head) {
   while(head) {
      cout << head->value << " ";
      head = head->next;
   }
}
int main() {
   Node* head = new Node(41);
   head->next = new Node(42);
   head->next->next = new Node(42);
   head->next->next->next = new Node(44);
   head->next->next->next->next = new Node(45);
   head->next->next->next->next->next = new Node(43);
   head->next->next->next->next->next->next = new Node(46);
   head->next->next->next->next->next->next->next = new Node(46);
   cout << "Before: ";
   printList(head);
   cout << "\n";
   solve(head);
   cout << "After: ";
   printList(head);
   return 0;
}

Output

Before: 41 42 42 44 45 43 46 46
After: 41 42 47 44 45 43 46 48  

Kesimpulan

Kami menggunakan konsep pencincangan dan menemui elemen terbesar dalam senarai terpaut dengan bantuan satu set struktur data. Kami juga boleh menggunakan peta atau unordered_map sebagai cincang.

Atas ialah kandungan terperinci Program C++: Gantikan nod pendua dalam senarai terpaut dengan salinan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!