Dada una lista enlazada como entrada. La tarea es codificar la lista enlazada dada utilizando la codificación de longitud de ejecución . Es decir, reemplazar un bloque de caracteres contiguos por el carácter seguido de su cuenta.
Por ejemplo, en la codificación de longitud de ejecución, «a->a->a->a->a» se reemplazará por «a->5».
Nota : para los Nodes que no se repiten, no agregue el recuento 1. Por ejemplo, a->b->b se reemplazará por «a->b->2» y no por «a->1->b-> 2”.
Ejemplos:
Entrada: Lista = a->a->a->a->a->b->r->r->r->NULL
Salida: a->5->b->r->3->NULL
Explicación:
el carácter ‘a’ se repite 5 veces.
El carácter ‘b’ se repite 1 vez.
El carácter ‘r’ se repite 3 veces.
Por lo tanto, la salida es a->5->b->r->3->NULL .
Entrada: a->a->a->a->a->a->a->a->a->a->b->r->r->r->a->a-> a->NULL
Salida: a->1->0->b->r->3->a->3->NULL
Enfoque :
- Recorra la lista.
- Considere el primer carácter como c .
- Considere el carácter actual como x .
- Si el carácter es el mismo que c , incremente el conteo.
- Si los caracteres no son los mismos, agregue el conteo a la lista y agregue el siguiente carácter a la lista, restablezca el conteo a 1 .
C++
// C++ program to encode a linked list
// using Run Length Encoding
#include <bits/stdc++.h>
using namespace std;
// A linked list node
struct Node {
char data;
struct Node* next;
Node(int x)
{
data = x;
next = NULL;
}
};
// Function to append nodes to a list
void append(struct Node* head_ref, char new_data)
{
struct Node* new_node = new Node(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;
}
// Function to print list
void printList(Node* node)
{
while (node != NULL) {
cout << node->data << " ";
node = node->next;
}
}
// Function to encode the list
void RLE(Node* head)
{
// Pointer used to traverse through
// all the nodes in the list
Node* p = head;
// List to store the encoded message
Node* temp = new Node(p->data);
// Store the first character in c
char c = p->data;
p = p->next;
// Count to count the number of
// continuous elements
int count = 1;
// Traverse through all the
// elements in the list
while (p != NULL) {
// Store the current character in x
char x = p->data;
// If the characters are same
if (c == x)
// Increment count
count++;
// Else
else {
// If the count is greater than 1
if (count > 1) {
// Append the count to list
if (count > 9)
append(temp, '0' + (count / 10));
append(temp, '0' + (count % 10));
}
// Reset the count
count = 1;
// Add the next character
// to the list
append(temp, x);
// Take the character to check as
// the current character
c = x;
}
p = p->next;
}
// Add the final count
if (count != 0)
append(temp, '0' + count);
// Print the list
printList(temp);
}
// Driver code
int main()
{
// Creating the linked list
Node* head = new Node('a');
head->next = new Node('a');
head->next->next = new Node('a');
head->next->next->next = new Node('b');
head->next->next->next->next = new Node('r');
head->next->next->next->next->next = new Node('r');
RLE(head);
return 0;
}
Java
// Java program to encode a linked list
// using Run Length Encoding
class GFG
{
// A linked list node
static class Node
{
char data;
Node next;
};
// Utility function to create a new Node
static Node newNode(char data)
{
Node temp = new Node();
temp.data = data;
temp.next = null;
return temp;
}
// Function to append nodes to a list
static void append(Node head_ref, char new_data)
{
Node new_node = newNode(new_data);
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;
}
// Function to print list
static void printList(Node node)
{
while (node != null)
{
System.out.print(node.data+" ");
node = node.next;
}
}
// Function to encode the list
static void RLE(Node head)
{
// Pointer used to traverse through
// all the nodes in the list
Node p = head;
// List to store the encoded message
Node temp = newNode(p.data);
// Store the first character in c
char c = p.data;
p = p.next;
// Count to count the number of
// continuous elements
int count = 1;
// Traverse through all the
// elements in the list
while (p != null)
{
// Store the current character in x
char x = p.data;
// If the characters are same
if (c == x)
// Increment count
count++;
// Else
else
{
// If the count is greater than 1
if (count > 1)
{
// Append the count to list
if (count > 9)
append(temp, (char) ('0' + (count / 10)));
append(temp, (char) ('0' + (count % 10)));
}
// Reset the count
count = 1;
// Add the next character
// to the list
append(temp, x);
// Take the character to check as
// the current character
c = x;
}
p = p.next;
}
// Add the final count
if (count != 0)
append(temp, (char) ('0' + count));
// Print the list
printList(temp);
}
// Driver code
public static void main(String[] args)
{
// Creating the linked list
Node head = newNode('a');
head.next = newNode('a');
head.next.next = newNode('a');
head.next.next.next = newNode('b');
head.next.next.next.next = newNode('r');
head.next.next.next.next.next = newNode('r');
RLE(head);
}
}
// This code has been contributed by 29AjayKumar
Python3
# Python3 program to encode a linked list
# using Run Length Encoding
# A linked list node
class Node:
def __init__(self, data):
self.data = data
self.next = None
# Function to append nodes to a list
def append(head_ref, new_data):
_node = Node(new_data);
last = head_ref;
if (head_ref == None):
head_ref =_node;
return;
while (last.next != None):
last = last.next;
last.next =_node;
return;
# Function to print list
def printList(node):
while (node != None):
print(node.data, end = ' ')
node = node.next;
# Function to encode the list
def RLE(head):
# Pointer used to traverse through
# all the nodes in the list
p = head;
# List to store the encoded message
temp = Node(p.data);
# Store the first character in c
c = p.data;
p = p.next;
# Count to count the number of
# continuous elements
count = 1;
# Traverse through all the
# elements in the list
while (p != None):
# Store the current character in x
x = p.data;
# If the characters are same
if (c == x):
# Increment count
count += 1
# Else
else:
# If the count is greater than 1
if (count > 1):
# Append the count to list
if (count > 9):
append(temp, chr(ord('0') + (count // 10)));
append(temp, chr(ord('0') + (count % 10)));
# Reset the count
count = 1;
# Add the next character
# to the list
append(temp, x);
# Take the character to check as
# the current character
c = x;
p = p.next;
# Add the final count
if (count != 0):
append(temp, chr(ord('0') + count))
# Print the list
printList(temp);
# Driver code
if __name__=='__main__':
# Creating the linked list
head = Node('a');
head.next = Node('a');
head.next.next = Node('a');
head.next.next.next = Node('b');
head.next.next.next.next = Node('r');
head.next.next.next.next.next = Node('r');
RLE(head);
# This code is contributed by pratham76
C#
// C# program to encode a linked list
// using Run Length Encoding
using System;
class GFG
{
// A linked list node
public class Node
{
public char data;
public Node next;
};
// Utility function to create a new Node
static Node newNode(char data)
{
Node temp = new Node();
temp.data = data;
temp.next = null;
return temp;
}
// Function to append nodes to a list
static void append(Node head_ref, char new_data)
{
Node new_node = newNode(new_data);
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;
}
// Function to print list
static void printList(Node node)
{
while (node != null)
{
Console.Write(node.data+" ");
node = node.next;
}
}
// Function to encode the list
static void RLE(Node head)
{
// Pointer used to traverse through
// all the nodes in the list
Node p = head;
// List to store the encoded message
Node temp = newNode(p.data);
// Store the first character in c
char c = p.data;
p = p.next;
// Count to count the number of
// continuous elements
int count = 1;
// Traverse through all the
// elements in the list
while (p != null)
{
// Store the current character in x
char x = p.data;
// If the characters are same
if (c == x)
// Increment count
count++;
// Else
else
{
// If the count is greater than 1
if (count > 1)
{
// Append the count to list
if (count > 9)
append(temp, (char) ('0' + (count / 10)));
append(temp, (char) ('0' + (count % 10)));
}
// Reset the count
count = 1;
// Add the next character
// to the list
append(temp, x);
// Take the character to check as
// the current character
c = x;
}
p = p.next;
}
// Add the final count
if (count != 0)
append(temp, (char) ('0' + count));
// Print the list
printList(temp);
}
// Driver code
public static void Main()
{
// Creating the linked list
Node head = newNode('a');
head.next = newNode('a');
head.next.next = newNode('a');
head.next.next.next = newNode('b');
head.next.next.next.next = newNode('r');
head.next.next.next.next.next = newNode('r');
RLE(head);
}
}
/* This code contributed by PrinciRaj1992 */
Javascript
<script>
// JavaScript program to encode a linked list
// using Run Length Encoding
// A linked list node
class Node {
constructor() {
this.data = 0;
this.next = null;
}
}
// Utility function to create a new Node
function newNode(data) {
var temp = new Node();
temp.data = data;
temp.next = null;
return temp;
}
// Function to append nodes to a list
function append(head_ref, new_data) {
var new_node = newNode(new_data);
var last = head_ref;
if (head_ref == null) {
head_ref = new_node;
return;
}
while (last.next != null) last = last.next;
last.next = new_node;
return;
}
// Function to print list
function printList(node) {
while (node != null) {
document.write(node.data + " ");
node = node.next;
}
}
// Function to encode the list
function RLE(head) {
// Pointer used to traverse through
// all the nodes in the list
var p = head;
// List to store the encoded message
var temp = newNode(p.data);
// Store the first character in c
var c = p.data;
p = p.next;
// Count to count the number of
// continuous elements
var count = 1;
// Traverse through all the
// elements in the list
while (p != null) {
// Store the current character in x
var x = p.data;
// If the characters are same
if (c == x)
// Increment count
count++;
// Else
else {
// If the count is greater than 1
if (count > 1) {
// Append the count to list
if (count > 9)
append(
temp,
String.fromCharCode("0".charCodeAt(0) +
parseInt(count / 10))
);
append(
temp,
String.fromCharCode("0".charCodeAt(0) +
(count % 10))
);
}
// Reset the count
count = 1;
// Add the next character
// to the list
append(temp, x);
// Take the character to check as
// the current character
c = x;
}
p = p.next;
}
// Add the final count
if (count != 0)
append(temp, String.fromCharCode("0".charCodeAt(0) +
count));
// Print the list
printList(temp);
}
// Driver code
// Creating the linked list
var head = newNode("a");
head.next = newNode("a");
head.next.next = newNode("a");
head.next.next.next = newNode("b");
head.next.next.next.next = newNode("r");
head.next.next.next.next.next = newNode("r");
RLE(head);
</script>
Producción:
a 3 b r 2
Conversión en el lugar : la idea aquí es modificar la lista existente en función de la frecuencia de los caracteres en lugar de crear una nueva lista si el sistema impone restricciones de espacio.
- Recorra la lista.
- Compara el carácter actual con el carácter siguiente. Si es lo mismo, entonces incremente el valor de conteo.
- Eliminar Nodes cuya frecuencia sea superior a 2.
- Si los caracteres no son iguales, actualice el valor de conteo.
C++
// C++ program implementing run length encoding
#include<stdio.h>
#include<stdlib.h>
struct Node
{
char data;
struct Node* next;
Node(int x)
{
data = x;
next = NULL;
}
};
// Function to add node to the list
Node* insert (Node *head, int data)
{
if (head == NULL)
return new Node(data);
head->next = insert(head->next, data);
return head;
}
// Function to print the list
void printList (Node* head)
{
while (head != NULL)
{
printf ("%c ",head->data);
head = head->next;
}
return;
}
void runLengthEncode (Node* head)
{
Node* temp = NULL;
Node* ptr = NULL;
int count = 0; //count the number of characters
temp = head;
while (temp != NULL)
{
ptr = temp;
count = 1;
//check if current data and next data is same.If same, then increment count
while (temp->next != NULL &&
temp->data == temp->next->data)
{
count++;
if (count > 2)
{
// delete only when the node value is repeated more than
// twice.
ptr->next = temp->next;
free(temp);
temp = ptr;
}
temp = temp->next;
}
// update only when the node value is repeated more than one time.
if (count > 1)
temp->data = count + '0';
temp = temp->next;
}
return;
}
// Driver code
int main()
{
// Creating the linked list
Node* head = new Node('a');
head->next = new Node('a');
head->next->next = new Node('a');
head->next->next->next = new Node('b');
head->next->next->next->next = new Node('r');
head->next->next->next->next->next = new Node('r');
runLengthEncode (head);
printList (head);
return 0;
}
Java
// java program implementing run length encoding
class GFG {
// A linked list node
static class Node
{
char data;
Node next;
};
// Utility function to create a new Node
static Node newNode(char data)
{
Node temp = new Node();
temp.data = data;
temp.next = null;
return temp;
}
// Function to add node to the list
static Node insert(Node head, char data)
{
if (head == null)
return newNode(data);
head.next = insert(head.next, data);
return head;
}
// Function to print the list
static void printList (Node head)
{
while (head != null)
{
System.out.print(head.data + " ");
head = head.next;
}
return;
}
static void runLengthEncode (Node head)
{
Node temp;
Node ptr;
int count = 0; //count the number of characters
temp = head;
while (temp != null)
{
ptr = temp;
count = 1;
//check if current data and next data is same.If same, then increment count
while (temp.next != null &&
temp.data == temp.next.data)
{
count++;
if (count > 2)
{
// delete only when the node value is repeated more than
// twice.
ptr.next = temp.next;
temp= null;
temp = ptr;
}
temp = temp.next;
}
// update only when the node value is repeated more than one time.
if (count > 1)
temp.data = (char) (count + '0');
temp = temp.next;
}
return;
}
// Driver code
public static void main(String [] args)
{
// Creating the linked list
Node head = newNode('a');
head.next = newNode('a');
head.next.next = newNode('a');
head.next.next.next = newNode('b');
head.next.next.next.next = newNode('r');
head.next.next.next.next.next = newNode('r');
runLengthEncode (head);
printList (head);
}
}
// This code is contributed by AR_Gaurav
Python3
# Python3 program implementing run length encoding
class Node:
def __init__(self, data):
self.data = data
self.next = None
# Function to add node to the list
def insert(head, data):
if (head == None):
return Node(data);
head.next = insert(head.next, data);
return head;
# Function to print the list
def printList(head):
while (head != None):
print(head.data, end = ' ')
head = head.next;
return;
def runLengthEncode(head):
temp = None;
ptr = None;
count = 0; #count the number of characters
temp = head;
while (temp != None):
ptr = temp;
count = 1;
# check if current data and next data
# is same.If same, then increment count
while (temp.next != None and
temp.data == temp.next.data):
count += 1
if (count > 2):
# delete only when the node
# value is repeated more than
# twice.
ptr.next = temp.next;
del (temp);
temp = ptr;
temp = temp.next;
# update only when the node value
# is repeated more than one time.
if (count > 1):
temp.data = count ;
temp = temp.next;
return;
# Driver code
if __name__=='__main__':
# Creating the linked list
head = Node('a');
head.next = Node('a');
head.next.next = Node('a');
head.next.next.next = Node('b');
head.next.next.next.next = Node('r');
head.next.next.next.next.next = Node('r');
runLengthEncode(head);
printList(head);
# This code is contributed by rutvik_56
Javascript
<script>
// JavaScript program implementing
// run length encoding
class Node
{
constructor(x)
{
this.data=x;
this.next=null;
}
}
// Function to add node to the list
function insert (head,data)
{
if (head == null)
return new Node(data);
head.next = insert(head.next, data);
return head;
}
// Function to print the list
function printList (head)
{
while (head != null)
{
document.write(head.data+" ");
head = head.next;
}
return;
}
function runLengthEncode (head)
{
let temp = null;
let ptr = null;
let count = 0; //count the number of characters
temp = head;
while (temp != null)
{
ptr = temp;
count = 1;
//check if current data and next data is same.If same,
// then increment count
while (temp.next != null &&
temp.data == temp.next.data)
{
count++;
if (count > 2)
{
// delete only when the node value
// is repeated more than
// twice.
ptr.next = temp.next;
delete(temp);
temp = ptr;
}
temp = temp.next;
}
// update only when the node value is
// repeated more than one time.
if (count > 1)
temp.data = count ;
temp = temp.next;
}
return;
}
// Driver code
let head = new Node('a');
head.next = new Node('a');
head.next.next = new Node('a');
head.next.next.next = new Node('b');
head.next.next.next.next = new Node('r');
head.next.next.next.next.next = new Node('r');
runLengthEncode (head);
printList (head);
// This code is contributed by unknown2108
</script>
Producción:
a 3 b r 2