リンクリストを使用してランレングスエンコーディングを実装するC++プログラム

このチュートリアルでは、リンクリストを使用してランレングスエンコーディングを実装するプログラムについて説明します。

このために、リンクリストが提供されます。私たちのタスクは、ランレングスエンコーディングを使用してリンクリストの要素をエンコードしすぎています。

たとえば、リンクリストの要素が「a-> a-> a-> a-> a」の場合、ランレングスエンコーディングでは「a→5」に置き換えられます。

例

#include <bits/stdc++.h>
using namespace std;
//structuring linked list node
struct Node {
   char data;
   struct Node* next;
};
//creating a new node
Node* newNode(char data){
   Node* temp = new Node;
   temp->data = data;
   temp->next = NULL;
   return temp;
}
//adding nodes to the list
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;
   }
}
//encoding the given list
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