C Programming A to Z (পর্ব-৬): ট্রি, গ্রাফ, বিগ-ও নোটেশন ও ক্যাপস্টোন প্রোজেক্ট

C Programming A to Z (পর্ব-৬): ট্রি, গ্রাফ, বিগ-ও নোটেশন ও ক্যাপস্টোন প্রোজেক্ট Detail Page

আমরা দীর্ঘ পথ পাড়ি দিয়েছি। অ্যারে, লিংকড লিস্ট, স্ট্যাক, কিউ—এগুলো সব লিনিয়ার (সরলরৈখিক) ডেটা স্ট্রাকচার। কিন্তু বাস্তব পৃথিবী কিন্তু সরলরৈখিক নয়! আপনার ফাইল সিস্টেমের ফোল্ডারগুলো কি সাজানো? এটি একটি ট্রি। আপনার সোশ্যাল মিডিয়া নেটওয়ার্ক কীভাবে কাজ করে? এটি একটি গ্রাফ।

আজ আমরা এই জটিল কিন্তু অসাধারণ ডেটা স্ট্রাকচার দুটি আয়ত্ত করব। আর শিখব কীভাবে কোনো অ্যালগরিদম দ্রুত নাকি ধীর তা পরিমাপ করা যায় (Big-O)। সবশেষে, আমরা একটি পূর্ণাঙ্গ প্রজেক্ট বানাবো যা দিয়ে আপনি ইন্টারভিউয়ে ঝড় তুলতে পারবেন। চলুন, ফাইনাল রাউন্ডে ডুব দিন! 🏊‍♂️🔥

🔄 পর্ব-৫ এর রিক্যাপ ও আজকের ভিশন

গত পর্বে আমরা জিসিসি (GCC) এর ফ্ল্যাগ, জিডিবি (GDB) ডিবাগার, বাইনারি ফাইল এবং typedef শিখেছি। আজ আমরা সেই হাতিয়ারগুলো ব্যবহার করে তৈরি করব নন-লিনিয়ার ডেটা স্ট্রাকচার। প্রস্তুত তো? শুরু করা যাক!

🌿 অধ্যায় ৩০: ট্রি ডেটা স্ট্রাকচার ও বাইনারি সার্চ ট্রি (BST)

ট্রি হলো একটি হায়ারার্কিক্যাল ডেটা স্ট্রাকচার। একটি রুট (Root) নোড থেকে শুরু হয়ে তা শাখা-প্রশাখায় (Children) বিভক্ত হয়।

বাইনারি ট্রি (Binary Tree): প্রতিটি নোডের সর্বোচ্চ ২টি চাইল্ড থাকতে পারে (লেফট ও রাইট)।

বাইনারি সার্চ ট্রি (BST): এটি বাইনারি ট্রির একটি বিশেষ রূপ, যেখানে:

বাম সাবট্রির সব নোডের মান রুটের চেয়ে ছোট।
ডান সাবট্রির সব নোডের মান রুটের চেয়ে বড়।
এই সম্পত্তির কারণেই BST-তে ডেটা খুঁজে বের করা অত্যন্ত দ্রুত!

BST-তে নোড ইনসার্ট ও সার্চ করার কোড:

#include <stdio.h>
#include <stdlib.h>

// ট্রির নোড
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

// নতুন নোড তৈরি
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// BST-তে ডেটা ইনসার্ট (রিকার্সিভ)
struct Node* insert(struct Node* root, int data) {
    if (root == NULL) return createNode(data); // বেস কেস

    if (data < root->data)
        root->left = insert(root->left, data);
    else if (data > root->data)
        root->right = insert(root->right, data);
    // যদি সমান হয়, তাহলে কিছু করি না (ডুপ্লিকেট নেওয়া হচ্ছে না)

    return root;
}

// BST-তে ডেটা খোঁজা (সার্চ)
struct Node* search(struct Node* root, int key) {
    if (root == NULL || root->data == key)
        return root;

    if (key < root->data)
        return search(root->left, key);
    else
        return search(root->right, key);
}

int main() {
    struct Node* root = NULL;
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 20);
    insert(root, 40);
    insert(root, 70);
    insert(root, 60);
    insert(root, 80);

    int key = 40;
    struct Node* result = search(root, key);
    if (result != NULL)
        printf("✅ %d টি খুঁজে পাওয়া গেছে!\n", key);
    else
        printf("❌ %d টি পাওয়া যায়নি!\n", key);
    
    return 0;
}

🚀 দ্রুততার রহস্য: BST-তে সার্চ করতে সময় লাগে গড়ে O(log n) , যা অ্যারের লিনিয়ার সার্চ (O(n))-এর চেয়ে অনেক দ্রুত!

🧭 অধ্যায় ৩১: ট্রি ট্রাভার্সাল (Inorder, Preorder, Postorder)

ট্রি প্রিন্ট করার ৩টি ক্লাসিক্যাল পদ্ধতি আছে। এগুলোর প্রত্যেকটির ভিন্ন ভিন্ন ব্যবহার আছে।

// ১. Inorder (বাম -> রুট -> ডান): BST-তে করলে ডেটা সর্টেড অর্ডারে আসে!
void inorder(struct Node* root) {
    if (root != NULL) {
        inorder(root->left);
        printf("%d ", root->data);
        inorder(root->right);
    }
}

// ২. Preorder (রুট -> বাম -> ডান): ট্রি কপি করতে ব্যবহার হয়।
void preorder(struct Node* root) {
    if (root != NULL) {
        printf("%d ", root->data);
        preorder(root->left);
        preorder(root->right);
    }
}

// ৩. Postorder (বাম -> ডান -> রুট): ট্রি ডিলিট করতে ব্যবহার হয়।
void postorder(struct Node* root) {
    if (root != NULL) {
        postorder(root->left);
        postorder(root->right);
        printf("%d ", root->data);
    }
}

আপনি যদি উপরের BST-তে inorder চালান, আউটপুট আসবে: 20 30 40 50 60 70 80 (দেখুন, সর্টেড!)।

🕸️ অধ্যায় ৩২: গ্রাফ (Graph) বেসিক – সংযোগের জগৎ

গ্রাফ হলো নোড (ভার্টেক্স) এবং তাদের মধ্যে সংযোগ (এজ)-এর একটি সেট। ফেসবুকের বন্ধুদের নেটওয়ার্ক বা গুগল ম্যাপের রাস্তাগুলো গ্রাফ দিয়ে বোঝানো হয়।

গ্রাফ প্রকাশের ২টি উপায়:

১. অ্যাজাসেন্সি ম্যাট্রিক্স (Adjacency Matrix): ২D অ্যারে। matrix[i][j] = 1 মানে i থেকে j-এ সরাসরি সংযোগ আছে।

int graph[4][4] = {
    {0, 1, 1, 0},
    {1, 0, 0, 1},
    {1, 0, 0, 1},
    {0, 1, 1, 0}
}; // এটি একটি অনির্দেশিত (Undirected) গ্রাফ

২. অ্যাজাসেন্সি লিস্ট (Adjacency List): লিংকড লিস্টের অ্যারে। এটি মেমোরি সাশ্রয়ী।

// ধারণাগত উদাহরণ (স্ট্রাকচার ব্যবহার করে)
struct AdjListNode { int dest; struct AdjListNode* next; };
struct AdjList { struct AdjListNode* head; };
struct Graph { int V; struct AdjList* array; };

👨‍💻 আমাদের প্রোজেক্টের জন্য: গ্রাফ অনেক বড় টপিক। তবে বেসিক জানা দরকার, কারণ ইন্টারভিউতে প্রায়ই গ্রাফ-বেসিক প্রশ্ন আসে (যেমন: সংযোগ আছে কিনা চেক করা)।

⏳ অধ্যায় ৩৩: টাইম কমপ্লেক্সিটি (Big-O নোটেশন) – অ্যালগরিদমের গতি পরিমাপ

আপনি কেন লিংকড লিস্টের বদলে BST ব্যবহার করবেন? উত্তর হলো গতি। Big-O নোটেশন একটি অ্যালগরিদম খারাপ থেকে খারাপ কীভাবে আচরণ করে তা বোঝায়।

নোটেশন	নাম	উদাহরণ	মন্তব্য
O(1)	কনস্ট্যান্ট	অ্যারে থেকে ইন্ডেক্স দিয়ে মান বের করা	সবচেয়ে দ্রুত (পারফেক্ট)
O(log n)	লগারিদমিক	BST-তে সার্চ করা	অসাধারণ (দ্রুত)
O(n)	লিনিয়ার	লিংকড লিস্ট ট্রাভার্স	ঠিকঠাক (মধ্যম)
O(n²)	কোয়াড্রাটিক	বাবল সর্ট (Bubble Sort)	ধীর (বড় ডেটায় ব্যবহার করবেন না!)

📢 পেশাদার টিপস: ইন্টারভিউয়ে প্রশ্ন করলেই তারা Big-O জিজ্ঞেস করে। মনে রাখবেন, আপনার কোড যদি O(n²) হয়, তাহলে ১ লাখ ডেটায় তা ১০ বিলিয়ন অপারেশন করবে! সেজন্য BST (O(log n)) শিখা এত জরুরি ছিল।

🧬 অধ্যায় ৩৪: মডার্ন C – `stdbool.h` ও `stdint.h` ব্যবহার করুন

আপনি কি জানেন, C-তে সরাসরি true বা false নেই? (C99 এর আগে)। এখনকার স্ট্যান্ডার্ডে এই সুবিধা আছে। আবার int-এর সাইজ প্ল্যাটফর্মভেদে (৩২-বিট/৬৪-বিট) বদলায়। পেশাদাররা নির্দিষ্ট সাইজের ইন্টিজার ব্যবহার করেন।

#include <stdio.h>
#include <stdbool.h>  // true/false এর জন্য
#include <stdint.h>   // int32_t, uint8_t ইত্যাদির জন্য

int main() {
    bool isLoggedIn = true;
    if (isLoggedIn) {
        printf("✅ ইউজার লগইন করেছেন!\n");
    }

    int32_t myAge = 25;    // ৩২-বিট ইন্টিজার (যেকোনো কম্পাইলারে ৪ বাইট)
    uint8_t smallNum = 255; // ৮-বিট (০ থেকে ২৫৫)
    printf("আমার বয়স: %d\n", myAge);
    return 0;
}

এটি আপনার কোডকে পোর্টেবল (Portable) করে তোলে। যেকোনো মেশিনে কম্পাইল করলে একই আচরণ পাবেন।

🎓 অধ্যায় ৩৫: ফাইনাল ক্যাপস্টোন – ‘ইউনিভার্সিটি কোর্স এনরোলমেন্ট সিস্টেম’

এখন আমরা সবকিছু একসাথে ফেলব। আমরা একটি প্রজেক্ট বানাবো যা BST ব্যবহার করে শিক্ষার্থীদের আইডি অনুযায়ী সাজিয়ে রাখবে, বাইনারি ফাইল ব্যবহার করে ডেটা সেভ করবে, এবং সার্চ ফিচার থাকবে যা O(log n) সময়ে রেজাল্ট দেবে।

প্রজেক্টের বৈশিষ্ট্য:

শিক্ষার্থী যোগ করুন (আইডি, নাম, সিজিপিএ)।
আইডি দিয়ে দ্রুত খোঁজ করুন।
Inorder ট্রাভার্সাল করে আইডি অনুযায়ী সাজানো সব শিক্ষার্থী দেখান।
প্রোগ্রাম বন্ধ করলে ফাইলে সেভ, শুরু করলে লোড।

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

// স্ট্রাকচার ডিফাইন
typedef struct {
    int id;
    char name[50];
    float cgpa;
} Student;

// BST নোড
typedef struct Node {
    Student data;
    struct Node* left;
    struct Node* right;
} Node;

// নতুন নোড তৈরি
Node* createNode(Student s) {
    Node* newNode = (Node*) malloc(sizeof(Node));
    newNode->data = s;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// BST-তে ইনসার্ট (আইডি অনুযায়ী)
Node* insert(Node* root, Student s) {
    if (root == NULL) return createNode(s);
    if (s.id < root->data.id)
        root->left = insert(root->left, s);
    else if (s.id > root->data.id)
        root->right = insert(root->right, s);
    else
        printf("⚠️ এই আইডি আগেই আছে! (ডুপ্লিকেট নেওয়া হবে না)\n");
    return root;
}

// BST-তে সার্চ
Node* search(Node* root, int id) {
    if (root == NULL || root->data.id == id)
        return root;
    if (id < root->data.id)
        return search(root->left, id);
    else
        return search(root->right, id);
}

// Inorder ট্রাভার্সাল (সর্টেড অর্ডার)
void inorder(Node* root) {
    if (root != NULL) {
        inorder(root->left);
        printf("আইডি: %d | নাম: %s | সিজিপিএ: %.2f\n", root->data.id, root->data.name, root->data.cgpa);
        inorder(root->right);
    }
}

// ট্রি ডিলিট (মেমোরি ফ্রি)
void freeTree(Node* root) {
    if (root != NULL) {
        freeTree(root->left);
        freeTree(root->right);
        free(root);
    }
}

// বাইনারি ফাইলে সেভ (Preorder ব্যবহার করে)
void saveToFile(Node* root, FILE* file) {
    if (root == NULL) return;
    fwrite(&(root->data), sizeof(Student), 1, file); // বাইনারি লেখা
    saveToFile(root->left, file);
    saveToFile(root->right, file);
}

// ফাইল থেকে লোড (আবার ইনসার্ট)
Node* loadFromFile(Node* root, const char* filename) {
    FILE* file = fopen(filename, "rb");
    if (file == NULL) return root;
    Student s;
    while (fread(&s, sizeof(Student), 1, file) == 1) {
        root = insert(root, s);
    }
    fclose(file);
    printf("📂 ফাইল থেকে ডেটা লোড হয়েছে!\n");
    return root;
}

int main() {
    Node* root = NULL;
    root = loadFromFile(root, "students.bin");

    int choice, id;
    Student s;
    Node* found;

    while (1) {
        printf("\n🎓 **ইউনিভার্সিটি এনরোলমেন্ট সিস্টেম**\n");
        printf("1. শিক্ষার্থী যোগ করুন\n");
        printf("2. আইডি দিয়ে খোঁজ করুন (দ্রুত)\n");
        printf("3. সব শিক্ষার্থী দেখান (আইডি অনুযায়ী সাজানো)\n");
        printf("4. সেভ করে প্রস্থান\n");
        printf("পছন্দ: ");
        scanf("%d", &choice);
        getchar(); // buffer clean

        if (choice == 1) {
            printf("আইডি: "); scanf("%d", &s.id); getchar();
            printf("নাম: "); gets(s.name);
            printf("সিজিপিএ: "); scanf("%f", &s.cgpa);
            root = insert(root, s);
            printf("✅ শিক্ষার্থী যোগ হয়েছে!\n");
        }
        else if (choice == 2) {
            printf("আইডি দিন: "); scanf("%d", &id);
            found = search(root, id);
            if (found != NULL) {
                printf("🔍 পাওয়া গেছে! নাম: %s, সিজিপিএ: %.2f\n", found->data.name, found->data.cgpa);
            } else {
                printf("❌ এই আইডির কোনো শিক্ষার্থী নেই!\n");
            }
        }
        else if (choice == 3) {
            if (root == NULL) printf("📭 তালিকা ফাঁকা!\n");
            else {
                printf("\n📋 **শিক্ষার্থীদের সাজানো তালিকা:**\n");
                inorder(root);
            }
        }
        else if (choice == 4) {
            FILE* file = fopen("students.bin", "wb");
            if (file != NULL) {
                saveToFile(root, file);
                fclose(file);
                printf("💾 সব ডেটা 'students.bin'-এ সেভ হয়েছে!\n");
            }
            freeTree(root); // মেমোরি মুক্ত
            printf("👋 প্রস্থান করছি। ভালো থাকুন!\n");
            break;
        }
        else {
            printf("❌ ভুল ইনপুট! ১-৪ এর মধ্যে চাপুন।\n");
        }
    }
    return 0;
}

⚡ এই প্রজেক্টটি রান করান। ১০০০ শিক্ষার্থী থাকলেও এটি অত্যন্ত দ্রুত কাজ করবে, কারণ সব অপারেশনই O(log n) টাইমে হচ্ছে!

🏁 পুরো সিরিজের মহাসমাপ্তি

আমরা “C Programming A to Z” -এর এই ৬টি বিশাল পর্বের যাত্রা শেষ করলাম।

আমরা যা যা কাভার করেছি:

✅ বেসিক সিনট্যাক্স, লুপ, ফাংশন।
✅ পয়েন্টার ও ডায়নামিক মেমোরি (malloc, free)।
✅ অ্যারে, স্ট্রিং, স্ট্রাকচার, ইউনিয়ন।
✅ লিংকড লিস্ট, স্ট্যাক, কিউ।
✅ ট্রি (BST), গ্রাফ বেসিক ও অ্যালগরিদম (সার্চ/সর্ট)।
✅ ফাইল হ্যান্ডলিং (টেক্সট ও বাইনারি)।
✅ প্রফেশনাল টুলস (GCC, GDB, Makefile ধারণা) ও Big-O কমপ্লেক্সিটি।

আপনি এখন প্রস্তুত:
আপনি যদি এই ৬টি পর্বের প্রতিটি কোড নিজে হাতে লিখে থাকেন, তাহলে আপনি যেকোনো কোম্পানির জুনিয়র সি ডেভেলপার ইন্টারভিউয়ের জন্য ১০০% প্রস্তুত। C শেখা শেষ নয়, এটি আপনার প্রোগ্রামিং জীবনের সেরা বিনিয়োগ।

এখন আপনার পথচলা:

LeetCode বা CodeChef-এ গিয়ে C দিয়ে ডেইলি চ্যালেঞ্জ সলভ করুন।
GitHub-এ একটি রিপোজিটরি খুলুন এবং আজকের এই প্রোজেক্টটি আপলোড দিন (এটি আপনার পোর্টফোলিও হবে)।
লিনাক্স কার্নেল বা ওপেন সোর্স ড্রাইভারের কোড পড়ার চেষ্টা করুন—এখন আপনি তা বুঝতে পারবেন।

ToLearnTeam-এর পক্ষ থেকে আপনাকে অসংখ্য ধন্যবাদ এই যাত্রায় আমাদের সঙ্গী হওয়ার জন্য। বিশ্বাস রাখুন, কঠিন পথটি আপনিই পাড়ি দিয়েছেন। এখন যান, কোড লিখুন, ভুল করুন, শিখুন—এবং একদিন না একদিন জগৎ বদলে দেওয়ার মতো কিছু তৈরি করুন!

শুভকামনা, প্রিয় প্রোগ্রামার।