Membuat Singly linked lists dengan C++

Bagikan :

Tweet

Linked lists adalah cara untuk menyimpan data dengan struktur sehingga programmer dapat secara otomatis membuat tempat baru untuk menyimpan data kapan pun diperlukan. Secara khusus, programmer menulis sebuah struct atau kelas definisi yang berisi variabel memegang informasi tentang sesuatu, dan kemudian memiliki pointer ke struct dari jenis. Masing-masing individu atau struct kelas dalam daftar umumnya dikenal sebagai node.
Anggap saja seperti kereta api. Programmer selalu menyimpan node pertama dari daftar. Ini akan menjadi mesin kereta. Pointer adalah penghubung antara mobil dari kereta. Setiap kali kereta menambahkan mobil, menggunakan konektor untuk menambahkan mobil baru. Ini adalah seperti seorang programmer menggunakan kata kunci baru untuk membuat pointer ke struct baru atau kelas. Dalam memori sering digambarkan sebagai tampak seperti ini:

----------        ----------
- Data   -        - Data   -    
----------        ----------   
- Pointer- - - -> - Pointer-  
----------        ----------

Representasi tidak sepenuhnya akurat, tetapi akan cukup untuk tujuan kita. Setiap blok besar adalah struct (atau kelas) yang memiliki pointer ke satu sama lain. Ingat bahwa pointer hanya menyimpan lokasi memori sesuatu, itu bukan hal itu, jadi panah pergi ke yang berikutnya. Pada akhirnya, tidak ada untuk pointer untuk menunjuk ke, sehingga tidak menunjukkan apa-apa, itu harus pointer nol atau node dummy untuk mencegah dari sengaja menunjuk ke lokasi yang benar-benar sewenang-wenang dan acak di memori (yang sangat buruk). Sejauh ini kita tahu apa simpul struct akan terlihat seperti:

struct node {
  int x;
  node *next;
};

int main()
{
  node *root;      // This will be the unchanging first node

  root = new node; // Now root points to a node struct
  root->next = 0;  // The node root points to has its next pointer
                   //  set equal to a null pointer
  root->x = 5;     // By using the -> operator, you can modify the node
                   //  a pointer (root in this case) points to.
}

Sejauh ini tidak sangat berguna untuk melakukan sesuatu. Hal ini diperlukan untuk memahami bagaimana untuk melintasi (melalui) linked list sebelum pergi lebih jauh. Pikirkan kembali ke kereta. Mari bayangkan konduktor yang hanya bisa masuk kereta melalui mesin, dan dapat berjalan melalui kereta bawah garis sepanjang konektor menghubungkan ke mobil lain. Ini adalah bagaimana program akan melintasi linked list. Konduktor akan menjadi pointer ke node, dan titik akan pertama yang akar, dan kemudian, jika akar pointer ke node berikutnya menunjuk ke sesuatu, "konduktor" (bukan istilah teknis) akan diatur untuk menunjuk ke node berikutnya. Dengan cara ini, daftar dapat dilalui. Sekarang, selama ada adalah pointer ke sesuatu, traversal akan terus. Setelah mencapai pointer nol (atau simpul dummy), yang berarti tidak ada node lebih (mobil kereta) maka akan berada di akhir daftar, dan node baru kemudian dapat ditambahkan jika diinginkan. Inilah yang yang terlihat seperti:

struct node {
  int x;
  node *next;
};

int main()
{
  node *root;       // This won't change, or we would lose the list in memory
  node *conductor;  // This will point to each node as it traverses the list

  root = new node;  // Sets it to actually point to something
  root->next = 0;   //  Otherwise it would not work well
  root->x = 12;
  conductor = root; // The conductor points to the first node
  if ( conductor != 0 ) {
    while ( conductor->next != 0)
      conductor = conductor->next;
  }
  conductor->next = new node;  // Creates a node at the end of the list
  conductor = conductor->next; // Points to that node
  conductor->next = 0;         // Prevents it from going any further
  conductor->x = 42;
}

Itu adalah dasar kode untuk melintasi daftar. Jika pernyataan memastikan bahwa ada sesuatu untuk memulai dengan (node ​​pertama). Dalam contoh itu akan selalu begitu, tetapi jika itu berubah, itu mungkin tidak benar. Jika jika pernyataan itu benar, maka tidak apa-apa untuk mencoba dan mengakses simpul yang ditunjuk oleh konduktor. Sementara loop akan terus berlanjut selama ada pointer lain di depan. Kondektur hanya bergerak sepanjang. Perubahan apa yang menunjuk ke dengan mendapatkan alamat conductor-> berikutnya. Akhirnya, kode pada akhirnya dapat digunakan untuk menambahkan node baru sampai akhir. Setelah loop sementara sebagai selesai, konduktor akan menunjuk ke node terakhir dalam array. (Ingat konduktor kereta akan bergerak sampai ada yang beralih ke? Ia bekerja dengan cara yang sama di loop sementara.) Oleh karena itu, conductor-> selanjutnya diatur ke nol, jadi tidak apa-apa untuk mengalokasikan daerah baru memori untuk itu untuk menunjuk ke. Kemudian konduktor melintasi satu elemen lebih (seperti konduktor kereta pindah ke mobil baru ditambahkan) dan memastikan bahwa ia memiliki pointer ke set berikutnya dengan 0 sehingga daftar tersebut berakhir. 0 fungsi seperti periode, itu berarti tidak ada lagi di luar. Akhirnya, node baru memiliki nya set x nilai. (Hal ini dapat diatur melalui input pengguna. Saya hanya menulis di '= 42' sebagai contoh.) Untuk mencetak daftar link, fungsi traversal hampir sama. Hal ini diperlukan untuk memastikan bahwa elemen terakhir dicetak setelah loop sementara berakhir. Sebagai contoh:

conductor = root;
if ( conductor != 0 ) { //Makes sure there is a place to start
  while ( conductor->next != 0 ) {
    cout<< conductor->x;
    conductor = conductor->next;
  }
  cout<< conductor->x;
}

Hasil akhir ini diperlukan karena loop sementara tidak akan berjalan setelah mencapai node terakhir, tetapi masih akan diperlukan untuk output isi dari node berikutnya. Akibatnya, penawaran keluaran terakhir dengan ini. Karena kita memiliki pointer ke awal daftar (root), kita dapat menghindari redundansi ini dengan memungkinkan konduktor untuk berjalan dari bagian belakang kereta. Buruk untuk konduktor (jika itu adalah orang yang nyata), tapi kode sederhana karena juga memungkinkan kita untuk menghapus cek awal for (jika akar null, maka konduktor akan segera diatur ke nol dan loop tidak akan mulai ):

conductor = root;
while ( conductor != NULL ) {
  cout<< conductor->x;
  conductor = conductor->next;
}

Tag : C++