Program C++: Cari elemen kedua terkecil dalam senarai terpaut

Kumpulan elemen data yang tersusun, setiap elemen data mempunyai pautan ke elemen seterusnya (kadangkala elemen sebelumnya), dengan mengandaikan terdapat senarai terpaut, maka kita perlu mencari elemen kedua terkecil . Di bawah ialah senario berikut.

Mari kita anggap beberapa senario input dan output yang mudah

Andaikan senario ini, kami mempunyai senarai terpaut, elemen yang terkandung di dalamnya ialah "8->4->6->2->9,". Kemudian selepas mengulangi keseluruhan senarai terpaut, elemen kedua terkecil ialah 8.

Input = 8->4->6->2->9
Output = 8

Pelaksanaan pengaturcaraan senarai terpaut

Node* head = new Node(8);
head->next = new Node(4);
head->next->next = new Node(6);
head->next->next->next = new Node(2);
head->next->next->next->next = new Node(9);
result = solve(head);

Pertimbangkan kes lain di mana setiap elemen dalam senarai terpaut mempunyai nilai yang sama. Selepas melelakan semua elemen, elemen kedua terkecil tidak akan ditemui dalam senarai terpaut. Oleh kerana setiap elemen dalam senarai terpaut mengandungi nilai yang sama.

Input = 1->1->1->1->1->1
Output = There is no second smallest element in Linked list

Algoritma

Berikut adalah langkah yang perlu diikuti semasa melaksanakan tugas

• Tugaskan dua pembolehubah (S1, S2)

• S1 akan menyimpan elemen terkecil dalam senarai terpaut

• S2 akan memegang elemen kedua terkecil dalam senarai terpaut.

• Setiap lelaran, elemen terkecil akan dialihkan ke S1, dan apabila ia ditemui, ia akan dialihkan ke S2

• Apabila minimum (S1) lebih kecil daripada nilai baru yang lebih kecil, yang lebih kecil baru akan menjadi minimum (S1).

• Yang baru yang lebih kecil akan menjadi lebih kecil (S1) dan yang lebih kecil (S1) akan berpindah ke yang kedua yang lebih kecil (S2).

• Selepas setiap kemungkinan traversal, elemen kedua terkecil dalam output akhir akan menjadi output.

Contoh

Dalam pelaksanaan C++, kita boleh menyimpan 2 pembolehubah. 1 ialah yang terkecil, satu lagi adalah yang kedua terkecil, dan kemudian senarai terpaut dilalui Setiap kali elemen yang lebih kecil ditemui, pembolehubah terkecil dikemas kini kepada terkecil seterusnya, dan yang lebih kecil baharu menjadi yang terkecil. Jadi apabila sesuatu unsur lebih kecil daripada unsur terkecil, unsur kedua terkecil menjadi terkecil dan unsur terkecil menjadi unsur baharu. Jika tidak, kami membandingkan elemen kedua terkecil dan menentukan sama ada elemen semasa lebih kecil daripada elemen kedua terkecil, dan mengemas kini dengan sewajarnya.

#include <iostream>
using namespace std;
class Node {
   public:
   int val;
   Node *next;
   Node(int val) {
      this->val = val;
      next = NULL;
   }
};
int solve(Node* root) {
   int s1=root->val, s2=root->val;
   while(root) {
      if(root->val <= s1) {
         s2 = s1;
         s1 = root->val;
      } else if(root->val < s2) {
         s2 = root->val;
      }
      root = root->next;
   }
   return s2;
}
int main() {
   Node* head = new Node(5);
   head->next = new Node(8);
   head->next->next = new Node(9);
   head->next->next->next = new Node(2);
   head->next->next->next->next = new Node(4);
   cout << "Second smallest element in the linked list is : " << solve(head);
   return 0;
}

Output

Second smallest element in the linked list is: 4

Kesimpulan

Lintas senarai terpaut sekali, kerumitan masa ialah O(n). Jika anda mendapati maklumat di atas berguna, sila lawati laman web rasmi kami untuk mengetahui lebih banyak topik berkaitan tentang pengaturcaraan.

Atas ialah kandungan terperinci Program C++: Cari elemen kedua terkecil dalam senarai terpaut. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!