Cetak semua kemungkinan nod Trie yang dibina daripada senarai rentetan yang diberikan

Dalam C++, percubaan ialah struktur data peringkat tinggi yang digunakan untuk menyimpan koleksi pokok. Perkataan cuba berasal daripada perkataan retrieval, ia dipanggil pokok nombor atau pokok awalan.

Mari kita ambil contoh semua kemungkinan gabungan dengan mengambil senarai rentetan yang diberikan.

Kami mentakrifkan input rentetan sebagai {"tutor", "true", "tuo"}

Kita dapat perhatikan bahawa rentetan yang berbeza digabungkan dengan rentetan tunggal. Jadi di sini t dan u ialah senarai aksara yang menggabungkan semua rentetan yang mungkin.

Dalam artikel ini, kami akan menggunakan struktur data cuba untuk menyelesaikan semua kemungkinan penggabungan dalam senarai rentetan.

Tatabahasa

struct name_of_structure{
   data_type var_name;   // data member or field of the structure.
}

Parameter

• struct − Kata kunci ini digunakan untuk mewakili jenis data struktur.

• nama_struktur − Kami menyediakan sebarang nama untuk struktur tersebut.

• Sesuatu struktur ialah himpunan pelbagai pembolehubah yang berkaitan di satu tempat.

treetrie* alpha[alphabet]

alpha ialah nama pembolehubah yang menunjuk kepada penunjuk struktur/ahli data bernama treetrie. abjad ialah makro yang menetapkan jumlah nilai aksara, dinyatakan sebagai integer.

Algoritma

• Kami mula-mula menggunakan fail pengepala bernama ‘bits/stdc++.h’, yang mengandungi semua perpustakaan templat standard C++.

• Kami mentakrifkan dua makro, ‘abjad’ dan ‘maks’, yang mentakrifkan jumlah bilangan aksara dalam abjad dan nilai maksimum aksara.

• Kami sedang mencipta struktur yang dipanggil ‘nod pokok’ dan mentakrifkan penuding kepada ‘nod_pokok’ untuk menyimpan alamat surat. Tentukan pembolehubah 'end_word' menggunakan jenis data bool, yang akan digunakan untuk aksara akhir rentetan.

• Kami menggunakan penuding untuk menyambung ke nod baharu yang mewakili pepohon yang dibina oleh trie, mentakrifkan fungsi yang dipanggil ‘buildNode’.

• Untuk memasukkan rentetan, kami mencipta fungsi rekursif yang dipanggil ‘ins_recursive_of_string’ yang menerima tiga parameter - itm, str (rentetan yang akan dimasukkan), i (mewakili aksara semasa sedang diproses).

Fungsi

• ins() ditakrifkan dalam kod sebagai fungsi pembalut ins_recursive_of_str(). Ia menerima dua parameter: tree_trie* itm (objek tree_trie) dan string str (rentetan yang akan dimasukkan). Ia memanggil fungsi rekursif menggunakan nod semasa, rentetan yang akan dimasukkan, dan indeks permulaan 0.

• Seterusnya, kami mencipta fungsi yang dipanggil LeafNode() yang menerima objek tree_trie sebagai parameter dan menyemak sama ada ia adalah nod daun, iaitu jika ia tidak mempunyai anak.

Fungsi

• display_joint() ditakrifkan dalam kod dan menerima empat parameter: tree_trie* root, tree_trie* itm (nod yang sedang diproses), char str[] (str tatasusunan aksara, untuk Stores rentetan laluan yang terbentuk daripada nod akar ke nod semasa), dan tahap int (tahap integer yang mewakili kedalaman nod semasa).

• Kod ini mentakrifkan fungsi displayJ(), iaitu fungsi pembungkus untuk display_joint(). Ia menerima objek tree_trie sebagai hujah dan memanggil fungsi display_joint() dengan nod akar, tatasusunan aksara kosong dan tahap permulaan 0 sebagai argumen.

• Kod ini mentakrifkan fungsi main(), yang menjana objek tree_trie baharu sebagai nod akar Trie. Ia menjana vektor yang mengandungi senarai rentetan untuk dimasukkan ke dalam Trie. Kemudian, ia memanggil fungsi ins() untuk memasukkan setiap rentetan ke dalam Trie.

• Akhir sekali, ia mencetak mesej untuk menunjukkan permulaan output dan memanggil fungsi displayJ() untuk memaparkan semua titik gabungan Trie.

Contoh

Dalam program ini, kami akan mencetak semua titik gabungan yang mungkin bagi percubaan yang dibina daripada senarai rentetan yang diberikan.

#include <bits/stdc++.h>
using namespace std;
#define alphabet 26
#define max 200

// creating a structure for trie node
struct tree_trie {
   tree_trie* alpha[alphabet];
   bool end_word;
};
tree_trie* buildNode(){
   tree_trie* temp = new tree_trie();
   temp->end_word = false;
   for (int i = 0; i < alphabet; i++) {
      temp->alpha[i] = NULL;
   }
   return temp;
}

// We will insert the string using trie recursively
void ins_recursive_of_str(tree_trie* itm,
string str, int i){
   if (i < str.length()) {
      int idx = str[i] - 'a';
      if (itm->alpha[idx] == NULL) {
         // We are creating a new node
         itm->alpha[idx] = buildNode();
      }
      // calling recursion function for inserting a string
      ins_recursive_of_str(itm->alpha[idx],
      str, i + 1);
   }
   else {
      // We make the end_word true which represents the end of string
      itm->end_word = true;
   }
}

// By using function call we are inserting a tree
void ins(tree_trie* itm, string str){

   // The necessary argument required for function call
   ins_recursive_of_str(itm, str, 0);
}

// Using function we check whether the node is a leaf or not
bool isLeafNode(tree_trie* root){
   return root->end_word != false;
}

// This function is an important part of the program to display the joints of trie
void display_joint(tree_trie* root, tree_trie* itm,
char str[], int level){

   //Using this variable we are counting the current child
   int current_alpha = 0;
   for (int i = 0; i < alphabet; i++){
      if (itm->alpha[i]) {
         str[level] = i + 'a';
         display_joint(root, itm->alpha[i],
         str, level + 1);
         current_alpha++;
      }
   }
   
   // We are printing the character if it has more than 1 character
   if (current_alpha > 1 && itm != root) {
      cout << str[level - 1] << endl;
   }
}

// By using this function call we are diplaying the joint of trie.
void displayJ(tree_trie* root){
   int level = 0;
   char str[max];
   display_joint(root, root, str, level);
}

// main function 
int main(){
   tree_trie* root = buildNode();
   vector<string> s = { "tutor", "true", "tuo"};

   for (string str : s) {
      ins(root, str);
   }
   cout<<"All possible joint of trie using the given list of string"<<endl;
   displayJ(root);
   return 0;
}

Output

All possible joint of trie using the given list of string
u
t

Kesimpulan

Kami meneroka konsep struktur data cuba, di mana kami membina semua titik sambung cuba yang mungkin daripada senarai rentetan yang diberikan. Kami melihat dalam output bahawa aksara u dan t menyambung semua titik sambungan yang mungkin bagi trie dengan menggunakan rentetan seperti tutor, true dan tuo. Oleh itu, dengan memberikan titik sambungan yang mungkin, pokok boleh mengurangkan nodnya.

Atas ialah kandungan terperinci Cetak semua kemungkinan nod Trie yang dibina daripada senarai rentetan yang diberikan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!