إدراج
الدرس 5 من 14 في دورة Tries - سلسلة هياكل البيانات #8 على Coddy.
لإدراج كلمة في الـ trie، انتقل للأسفل من الجذر حرفاً واحداً في كل مرة. لكل حرف من الكلمة: إذا لم يكن للعقدة الحالية ابن لهذا الحرف، فأنشئ TrieNode جديداً وقم بإرفاقه. في كلتا الحالتين، انتقل إلى ذلك الابن واستمر مع الحرف التالي.
عندما تصل إلى نهاية الكلمة، قم بتمييز العقدة التي وصلت إليها بـ isEndOfWord = true. هذه العلامة هي ما يميز لاحقاً الكلمة المخزنة الحقيقية عن المسار الذي يتصادف وجوده فقط لأنه بادئة لشيء آخر.
إدراج "cat" ثم "car" يشترك في المسار c -> a ويتفرع فقط عند الحرف الثالث. هذا التشارك هو ما يجعل الـ tries فعالة للغاية من حيث المساحة للقواميس.
التحدي
سهلأضف طريقة insert إلى فئة Trie.
تستقبل هذه الطريقة سلسلة نصية word وتقوم بتخزينها في الـ trie:
- ابدأ من الـ
root. لكل حرفcفيword، إذا لم يكن للعقدة الحالية ابن للحرفc، فقم بإضافةTrieNodeجديدة هناك. - انتقل إلى ذلك الابن واستمر في العملية.
- بعد الحرف الأخير، قم بتعيين قيمة
isEndOfWordللعقدة النهائية إلىtrue.
جرّب بنفسك
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "trie.h"
int main() {
Trie t;
Trie_init(&t);
char line[1024];
while (fgets(line, sizeof(line), stdin)) {
line[strcspn(line, "\r\n")] = '\0';
char* cmd = strtok(line, " \t");
if (!cmd) continue;
if (strcmp(cmd, "rootIsEmpty") == 0) { printf("%s\n", TrieNode_childrenCount(t.root) == 0 ? "true" : "false"); }
if (strcmp(cmd, "hasChild") == 0) { char* arg = strtok(NULL, " \t"); if (arg) printf("%s\n", t.root->children[(unsigned char)arg[0]] != NULL ? "true" : "false"); }
if (strcmp(cmd, "insert") == 0) { char* arg = strtok(NULL, " \t"); if (arg) Trie_insert(&t, arg); }
}
return 0;
}