Program JavaScript untuk mencari elemen dalam senarai terpaut

Senarai terpaut ialah struktur data linear di mana setiap elemen (juga dipanggil nod) mengandungi nilai data dan rujukan kepada nod seterusnya dalam senarai. Operasi biasa pada senarai terpaut adalah untuk mencari elemen tertentu. Ini melibatkan berjalan melalui senarai dan membandingkan nilai data setiap nod dengan elemen sasaran sehingga padanan ditemui.

Berikut ialah contoh senarai pautan yang akan kami gunakan sepanjang artikel ini -

10 -> 20 -> 30 -> 40 -> Kosong

Dalam senarai terpaut ini, setiap nod mengandungi nilai dan anak panah menunjukkan nod seterusnya dalam jujukan. Senarai ini bermula dengan nod kepala, yang mengandungi nilai 10, dan berakhir dengan nod ekor, yang mengandungi nilai 40 dan menunjuk ke nol. Kami akan menggunakan senarai terpaut ini untuk menunjukkan cara mencari elemen dalam senarai terpaut menggunakan JavaScript.

Jom lihat contoh di bawah -

Linked list: 10 -> 20 -> 30 -> 40 -> null
Input: 40
Output: Element found at index 3
Input: 10
Output: Element found at index 0
Input: null
Output: Element not found

Sekarang mari kita bincangkan algoritma untuk membuat senarai terpaut dalam JavaScript.

Algoritma

Langkah 1 - Tentukan kelas Nod dengan dua sifat: nilai dan seterusnya. Atribut nilai mewakili data yang disimpan dalam nod, dan atribut seterusnya ialah rujukan kepada nod seterusnya dalam senarai terpaut.

Langkah 2 - Tentukan kelas LinkedList dengan tiga sifat: kepala, ekor dan panjang. Atribut kepala mewakili nod pertama dalam senarai terpaut, atribut ekor mewakili nod terakhir dalam senarai terpaut, dan atribut panjang mewakili bilangan nod dalam senarai terpaut.

Langkah 3 - Tentukan kaedah bernama - tambah pada kelas LinkedList yang mengambil nilai sebagai parameter. Kaedah tambah harus mencipta nod baharu dengan nilai yang diberikan dan menambahnya pada penghujung senarai terpaut.

Langkah 4 - Tentukan kaedah yang dipanggil "alih keluar" untuk kelas LinkedList yang mengambil nilai sebagai parameter. Kaedah alih keluar harus mengalih keluar nod pertama dengan nilai yang diberikan dalam senarai terpaut.

Langkah 5 - Tentukan kaedah yang dipanggil carian untuk kelas LinkedList yang mengambil nilai sebagai parameter. Kaedah carian harus mengembalikan nod pertama dalam senarai terpaut dengan nilai yang diberikan, atau batal jika nod tidak ditemui.

Langkah 6 - Tentukan kaedah yang dipanggil terbalik untuk kelas LinkedList, yang digunakan untuk membalikkan susunan nod dalam senarai terpaut.

Contoh: Laksanakan algoritma di atas menggunakan JavaScript

Atur cara berikut mentakrifkan kelas Node dan kelas LinkedList. Kelas Node mencipta nod baharu menggunakan nilai data yang diberikan dan rujukan kepada nod seterusnya dalam senarai. Kelas LinkedList mencipta senarai terpaut baharu dengan nod kepala pada mulanya menghala ke nol dan sifat saiz ditetapkan kepada 0. Kaedah tambah menambah nod baharu pada penghujung senarai terpaut. Kaedah carian merentasi senarai terpaut dan mengembalikan indeks elemen jika ditemui, atau mesej jika tidak ditemui. Akhir sekali, program mencipta senarai terpaut baharu, menambah elemen padanya dan mencari elemen tertentu.

// Define the Node class for a singly linked list
class Node {
   constructor(data) {
      this.data = data;
      this.next = null;
   }
}
// Define the LinkedList class
class LinkedList {
   constructor() {
      this.head = null;
      this.size = 0;
   }
   // Add an element to the linked list
   add(element) {
      const node = new Node(element);
      // If the linked list is empty, set the new node as the head
      if (this.head === null) {
         this.head = node;
      } else {
         // Traverse to the end of the linked list and add the new node
         let current = this.head;
         while (current.next !== null) {
            current = current.next;
         }
         current.next = node;
      }
      this.size++;
   }
   // Search for an element in the linked list
   search(element) {
      let current = this.head;
      let index = 0;
      // Traverse through the linked list until the element is found
      while (current !== null) {
         if (current.data === element) {
            return `Element found at index ${index}`;
         }
         current = current.next;
         index++;
      }
      return "Element not found";
   }
}
// Create a new linked list
const ll = new LinkedList();
// Add elements to the linked list
ll.add(10);
ll.add(20);
ll.add(30);
ll.add(40);
ll.add(50);
// Search for an element in the linked list
const result = ll.search(30);
console.log(result); 

Kesimpulan

Prosedur untuk mencari elemen dalam senarai terpaut menggunakan JavaScript melibatkan mencipta kelas "LinkedList" yang mentakrifkan kaedah untuk menambah elemen pada senarai dan untuk mencari elemen dalam senarai. Program ini menggunakan gelung sementara untuk melintasi senarai terpaut dan membandingkan elemen data dalam setiap nod dengan elemen yang dicari. Jika elemen ditemui, atur cara mengembalikan indeks nod, jika elemen tidak dijumpai, atur cara mengembalikan "Elemen tidak dijumpai".

Atas ialah kandungan terperinci Program JavaScript untuk mencari elemen dalam senarai terpaut. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!