C++ Program: Run Length Encoding ด้วย Linked List

Run Length Encoding (RLE): บีบอัดข้อมูลโดยแทนลำดับตัวอักษรซ้ำด้วย ตัวอักษร + จำนวนครั้ง

Linked List: a→a→a→a→a → RLE: a→5

ตัวอย่างโค้ด

#include <bits/stdc++.h>
using namespace std;

struct Node {
    char data;
    Node* next;
};

Node* newNode(char data) {
    Node* temp = new Node;
    temp->data = data;
    temp->next = NULL;
    return temp;
}

void add_node(Node*& head_ref, char new_data) {
    Node* new_node = newNode(new_data);
    if (head_ref == NULL) {
        head_ref = new_node;
        return;
    }
    Node* last = head_ref;
    while (last->next != NULL) last = last->next;
    last->next = new_node;
}

void print_list(Node* node) {
    while (node != NULL) {
        cout << node->data << " ";
        node = node->next;
    }
}

void rle_encode(Node* head) {
    if (!head) return;

    Node* result = newNode(head->data);
    char current_char = head->data;
    int count = 1;
    head = head->next;

    while (head != NULL) {
        if (head->data == current_char) {
            count++;
        } else {
            // เขียน count (ถ้า > 1)
            if (count > 1) {
                if (count > 9) add_node(result, '0' + count / 10);
                add_node(result, '0' + count % 10);
            }
            // เริ่มตัวใหม่
            add_node(result, head->data);
            current_char = head->data;
            count = 1;
        }
        head = head->next;
    }

    // ตัวสุดท้าย
    if (count > 1) {
        if (count > 9) add_node(result, '0' + count / 10);
        add_node(result, '0' + count % 10);
    }

    print_list(result);
}

int main() {
    Node* head = newNode('a');
    head->next = newNode('a');
    head->next->next = newNode('b');
    head->next->next->next = newNode('b');
    head->next->next->next->next = newNode('r');
    head->next->next->next->next->next = newNode('r');

    rle_encode(head); // Output: a 2 b 2 r 2
    return 0;
}

ผลลัพธ์

a 2 b 2 r 2

หมายเหตุ

• โค้ดรองรับ Count > 9 โดยแยกหลักสิบและหลักหน่วย
• Input: a a b b r r → Output: a 2 b 2 r 2
• RLE เหมาะกับข้อมูลที่มีการซ้ำติดต่อกันมาก (เช่น Bitmap, Fax)