連結リストでランレングス符号化（RLE）を実装するC++プログラム

はじめに

本記事では、連結リスト（Linked List）を用いてランレングス符号化（Run Length Encoding：RLE）を実装するC++プログラムについて解説します。

連結リストが与えられたとき、その各要素をランレングス符号化の手法で変換することが課題となります。

例えば、連結リストの要素が「a → a → a → a → a」と並んでいる場合、ランレングス符号化ではこれが「a → 5」に置き換えられます。これは、同じ値が連続して現れる区間を「値 ＋ 連続回数」の組み合わせで表現することで、データ量を削減できるシンプルかつ効果的な圧縮手法です。

アルゴリズムの流れ

1. 連結リストを先頭から順に走査し、現在のノードと次のノードのデータを比較します。
2. 同じ値が連続している間は、カウントを1ずつ増やしていきます。
3. 異なる値が現れた時点で、それまでの「文字」と「連続回数」を結果のリストに追加します。
4. 連続回数が2桁になった場合は、十の位と一の位に分けて個別のノードとして追加します。
5. リストの終端まで到達したら、最後の文字とその連続回数を忘れずに追加します。

C++による実装例

#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;
    return;
}
//連結リストの内容を出力
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;
}

出力

a 2 b 2 r 2

コードの解説

• newNode()：新しいノードを生成し、データと次ノードへのポインタを初期化する関数です。
• add_node()：リストの末尾に新しいノードを追加する関数です。
• print_llist()：連結リストの全要素を先頭から順番に出力する関数です。
• llist_encode()：符号化処理の中核となる関数です。リストを走査しながら連続する同一文字の数を数え、「文字 ＋ 回数」の形式で結果のリストを構築します。

まとめ

このように、連結リストを一度走査するだけでランレングス符号化を実現できます。計算量はリストの長さをNとするとO(N)となり、非常に効率的です。ランレングス符号化はデータ圧縮の基礎となる手法であり、画像フォーマットなど幅広い分野で実際に応用されています。ぜひ本記事のコードを参考に、ご自身でも動作を確認してみてください。