Рубрики

Удалить все специальные символы из единственного связанного списка

Учитывая односвязный список, в котором каждый узел представляет символ, включающий специальные символы, задача состоит в том, чтобы удалить все вхождения специальных символов из связанного списка, чтобы в связанном списке присутствовали только допустимые символы.

Примеры:

Input: List = ( -> G -> E -> E -> * -> K -> S -> * -> NULL
Output: G -> E -> E -> K -> S -> NULL

Input: A -> B -> C -> * -> @ -> NULL
Output: A -> B -> C -> NULL

Подход. Перейдите по связанному списку, если данные текущего узла являются специальным символом, а затем укажите следующий за предыдущим узлом следующий за текущим узлом. Сделайте это для каждого узла со специальным символом и, наконец, напечатайте обновленный список.

Ниже приведена реализация вышеуказанного подхода:

C ++

// C ++ реализация подхода
#include <iostream>

using namespace std;

  
// Структура для узла
// связанного списка

struct node {

    char data;

    node* next;

};

  
// Сервисная функция для добавления нового
// узел в связанном списке

node* add(char data)

{

    node* newnode = new node;

  

    // Присваиваем данные части данных

    // и присваиваем NULL адресной части

    newnode->data = data;

    newnode->next = NULL;

    return newnode;

}

  
// Функция для печати связанного списка

void print(node* head)

{

    while (head != NULL) {

        cout << head->data << " -> ";

        head = head->next;

    }

    cout << "NULL";

}

  
// Функция, которая возвращает true, если
// ch это специальный символ

bool isSpecialChar(char ch)

{

  

    // Если строчные буквы

    if (ch >= 'a' && ch <= 'z')

        return false;

  

    // Если заглавные буквы

    if (ch >= 'A' && ch <= 'Z')

        return false;

  

    // Если цифра

    if (ch >= '0' && ch <= '9')

        return false;

  

    // ch это специальный символ

    return true;

}

  
// Функция для удаления специального
// символы из связанного списка
node* removeFromLL(node* head)
{

  

    // Объявляем две переменные curr и

    // предыдущая и указывающая на голову

    node *curr = head, *prev = head;

  

    // Следующий цикл удаляет специальные

    // символы из заголовка связанного списка

    // Если специальный символ присутствует в

    // заголовок связанного списка, сделать заголовок

    // к следующему действительному символу

    while (curr != NULL && isSpecialChar(curr->data)) {

        node* temp = curr;

        head = curr->next;

        curr = curr->next;

        delete temp;

    }

  

    // Сделать предыдущую точку головой

    prev = head;

  

    // Повторить процесс для

    // весь связанный список

    while (curr != NULL) {

  

        // Повторить процесс для всех элементов

        // связанного списка, в случае специального символа

        // встречаемся, затем делаем предыдущий действительным

        // символ указывает на следующий действительный символ

        // и удаляем текущий узел из связанного списка

        while (curr != NULL && isSpecialChar(curr->data)) {

            node* temp = curr;

            prev->next = curr->next;

            curr = curr->next;

            delete temp;

        }

  

        // Если достигнут конец

        if (curr == NULL)

            break;

        prev = curr;

        curr = curr->next;

    }

    return head;

}

  
// Код драйвера

int main()

{

  

    // Создаем связанный список

    node* head = NULL;

    head = add('(');

    head->next = add('G');

    head->next->next = add('E');

    head->next->next->next = add('E');

    head->next->next->next->next = add('*');

    head->next->next->next->next->next = add('K');

    head->next->next->next->next->next->next = add('S');

    head->next->next->next->next->next->next->next = add('*');

  

    // Удалить специальные символы

    // из связанного списка

    head = removeFromLL(head);

  

    // Распечатать обновленный список

    print(head);

  

    return 0;

}

Джава

// Java реализация подхода

class GFG

{

  
// Структура для узла
// связанного списка

static class node

{

    char data;

    node next;

};

  
// Сервисная функция для добавления нового
// узел в связанном списке

static node add(char data)

{

    node newnode = new node();

  

    // Присваиваем данные части данных

    // и присваиваем нуль адресной части

    newnode.data = data;

    newnode.next = null;

    return newnode;

}

  
// Функция для печати связанного списка

static void print(node head)

{

    while (head != null

    {

        System.out.print(head.data + " -> ");

        head = head.next;

    }

    System.out.print("null");

}

  
// Функция, которая возвращает true, если
// ch это специальный символ

static boolean isSpecialChar(char ch)

{

  

    // Если строчные буквы

    if (ch >= 'a' && ch <= 'z')

        return false;

  

    // Если заглавные буквы

    if (ch >= 'A' && ch <= 'Z')

        return false;

  

    // Если цифра

    if (ch >= '0' && ch <= '9')

        return false;

  

    // ch это специальный символ

    return true;

}

  
// Функция для удаления специального
// символы из связанного списка

static node removeFromLL(node head)

{

  

    // Объявляем две переменные curr и

    // предыдущая и указывающая на голову

    node curr = head; node prev = head;

  

    // Следующий цикл удаляет специальные

    // символы из заголовка связанного списка

    // Если специальный символ присутствует в

    // заголовок связанного списка, сделать заголовок

    // к следующему действительному символу

    while (curr != null && 

           isSpecialChar(curr.data)) 

    {

        node temp = curr;

        head = curr.next;

        curr = curr.next;

        temp = null;

    }

  

    // Сделать предыдущую точку головой

    prev = head;

  

    // Повторить процесс для

    // весь связанный список

    while (curr != null)

    {

  

        // Повторить процесс для всех элементов

        // связанного списка, в случае специального символа

        // встречаемся, затем делаем предыдущий действительным

        // символ указывает на следующий действительный символ

        // и удаляем текущий узел из связанного списка

        while (curr != null &&

               isSpecialChar(curr.data))

        {

            node temp = curr;

            prev.next = curr.next;

            curr = curr.next;

            temp = null;

        }

  

        // Если достигнут конец

        if (curr == null)

            break;

        prev = curr;

        curr = curr.next;

    }

    return head;

}

  
// Код драйвера

public static void main(String[] args)

{

    // Создаем связанный список

    node head = null;

    head = add('(');

    head.next = add('G');

    head.next.next = add('E');

    head.next.next.next = add('E');

    head.next.next.next.next = add('*');

    head.next.next.next.next.next = add('K');

    head.next.next.next.next.next.next = add('S');

    head.next.next.next.next.next.next.next = add('*');

  

    // Удалить специальные символы

    // из связанного списка

    head = removeFromLL(head);

  

    // Распечатать обновленный список

    print(head);

}
}

  
// Этот код предоставлен PrinciRaj1992

python3

# Python3 реализация подхода

import math 

  
# Структура для узла
№ связанного списка

class Node: 

    def __init__(self, data): 

        self.data = data 

        self.next = None

  
# Сервисная функция для добавления нового
# узел в связанном списке

def add(data):

    newnode = Node(data)

  

    # Присвойте данные части данных

    # и присвойте None адресной части

    newnode.data = data

    newnode.next = None

    return newnode

  
# Функция для печати связанного списка

def printlist(head):

    while (head != None) :

        print(head.data, end = " -> ")

        head = head.next

      

    print("None")

  
# Функция, которая возвращает true, если
# ch - специальный символ

def isSpecialChar(ch):

  

    # Если строчные буквы

    if (ch >= 'a' and ch <= 'z'):

        return False

  

    # Если заглавные буквы

    if (ch >= 'A' and ch <= 'Z'):

        return False

  

    # Если цифра

    if (ch >= '0' and ch <= '9'):

        return False

  

    # ch - специальный символ

    return True

  
# Функция для удаления специального
# символов из связанного списка

def removeFromLL(head):

  

    # Объявляем две переменные curr и

    # предыдущая и указывающая на голову

    curr = head

    prev = head

  

    # Следующий цикл удаляет специальные

    # символов из заголовка связанного списка

    # Если специальный символ присутствует на

    # заголовок связанного списка, сделать заголовок

    # до следующего действительного символа

    while (curr != None and 

           isSpecialChar(curr.data)):

        temp = curr

        head = curr.next

        curr = curr.next

        temp = None

      

    # Сделать предыдущую точку головой

    prev = head

  

    # Повторите процесс для

    # весь связанный список

    while (curr != None):

  

        # Повторите процесс для всех элементов

        # связанного списка, в случае специального символа

        # встречается, тогда сделайте предыдущее действительным

        # символ указывает на следующий действительный символ

        # и удалить текущий узел из связанного списка

        while (curr != None and 

               isSpecialChar(curr.data)):

            temp = curr

            prev.next = curr.next

            curr = curr.next

            temp = None

          

        # Если конец достигнут

        if (curr == None):

            break

        prev = curr

        curr = curr.next

      

    return head

  
# Код драйвера

if __name__=='__main__':

  

    # Создайте связанный список

    head = None

    head = add('(')

    head.next = add('G')

    head.next.next = add('E')

    head.next.next.next = add('E')

    head.next.next.next.next = add('*')

    head.next.next.next.next.next = add('K')

    head.next.next.next.next.next.next = add('S')

    head.next.next.next.next.next.next.next = add('*')

  

    # Удалить специальные символы

    # из связанного списка

    head = removeFromLL(head)

  

    # Распечатать обновленный список

    printlist(head)

  
# Этот код предоставлен Srathore

C #

// C # реализация подхода

using System;

      

class GFG

{

  
// Структура для узла
// связанного списка

class node

{

    public char data;

    public node next;

};

  
// Сервисная функция для добавления нового
// узел в связанном списке

static node add(char data)

{

    node newnode = new node();

  

    // Присваиваем данные части данных

    // и присваиваем нуль адресной части

    newnode.data = data;

    newnode.next = null;

    return newnode;

}

  
// Функция для печати связанного списка

static void print(node head)

{

    while (head != null

    {

        Console.Write(head.data + " -> ");

        head = head.next;

    }

    Console.Write("null");

}

  
// Функция, которая возвращает true, если
// ch это специальный символ

static Boolean isSpecialChar(char ch)

{

  

    // Если строчные буквы

    if (ch >= 'a' && ch <= 'z')

        return false;

  

    // Если заглавные буквы

    if (ch >= 'A' && ch <= 'Z')

        return false;

  

    // Если цифра

    if (ch >= '0' && ch <= '9')

        return false;

  

    // ch это специальный символ

    return true;

}

  
// Функция для удаления специального
// символы из связанного списка

static node removeFromLL(node head)

{

  

    // Объявляем две переменные curr и

    // предыдущая и указывающая на голову

    node curr = head; node prev = head;

  

    // Следующий цикл удаляет специальные

    // символы из заголовка связанного списка

    // Если специальный символ присутствует в

    // заголовок связанного списка, сделать заголовок

    // к следующему действительному символу

    while (curr != null && 

           isSpecialChar(curr.data)) 

    {

        node temp = curr;

        head = curr.next;

        curr = curr.next;

        temp = null;

    }

  

    // Сделать предыдущую точку головой

    prev = head;

  

    // Повторить процесс для

    // весь связанный список

    while (curr != null)

    {

  

        // Повторить процесс для всех элементов

        // связанного списка, в случае специального символа

        // встречаемся, затем делаем предыдущий действительным

        // символ указывает на следующий действительный символ

        // и удаляем текущий узел из связанного списка

        while (curr != null &&

               isSpecialChar(curr.data))

        {

            node temp = curr;

            prev.next = curr.next;

            curr = curr.next;

            temp = null;

        }

  

        // Если достигнут конец

        if (curr == null)

            break;

        prev = curr;

        curr = curr.next;

    }

    return head;

}

  
// Код драйвера

public static void Main(String[] args)

{

    // Создаем связанный список

    node head = null;

    head = add('(');

    head.next = add('G');

    head.next.next = add('E');

    head.next.next.next = add('E');

    head.next.next.next.next = add('*');

    head.next.next.next.next.next = add('K');

    head.next.next.next.next.next.next = add('S');

    head.next.next.next.next.next.next.next = add('*');

  

    // Удалить специальные символы

    // из связанного списка

    head = removeFromLL(head);

  

    // Распечатать обновленный список

    print(head);

}
}

  
// Этот код предоставлен PrinciRaj1992

Выход:

G -> E -> E -> K -> S -> NULL

Рекомендуемые посты:

Удалить все специальные символы из единственного связанного списка

0.00 (0%) 0 votes