Chương trình C++ mã hóa Run-Length Encoding với Linked List

Run-Length Encoding (RLE) nén dữ liệu: chuỗi ký tự liên tiếp giống nhau thay bằng ký tự + số lần. Ví dụ: "aaaaabb" → "a5b2". Triển khai trên linked list.

Ví dụ

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

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

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

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

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

void llist_encode(Node* head) {
    Node* p = head;
    Node* temp = newNode(p->data);
    char c = p->data;
    p = p->next;
    int count = 1;
    while (p != NULL) {
        char x = p->data;
        if (c == x)
            count++;
        else {
            if (count > 1) {
                if (count > 9)
                    add_node(temp, '0' + (count / 10));
                add_node(temp, '0' + (count % 10));
            }
            count = 1;
            add_node(temp, x);
            c = x;
        }
        p = p->next;
    }
    if (count != 0)
        add_node(temp, '0' + count);
    print_llist(temp);
}

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');
    llist_encode(head);
    return 0;
}

Kết quả

a 2 b 2 r 2