Рубрики

Напишите функцию, которая подсчитывает, сколько раз данное int встречается в связанном списке.

Если задан односвязный список и ключ, подсчитайте количество вхождений данного ключа в связанный список. Например, если данный связанный список равен 1-> 2-> 1-> 2-> 1-> 3-> 1, а заданный ключ равен 1, то значение должно быть 4.

Метод 1 — без рекурсии
Алгоритм:

1. Initialize count as zero.
2. Loop through each element of linked list:
     a) If element data is equal to the passed number then
        increment the count.
3. Return count. 

Реализация:

C ++

// C ++ программа для подсчета вхождений в связанном списке
#include <bits/stdc++.h>

using namespace std;

  
/ * Узел списка ссылок * /

class Node {

public:

    int data;

    Node* next;

};

  
/ * Дана ссылка (указатель на указатель) на голову
списка и int, нажмите новый узел на передней панели
из списка. * /

void push(Node** head_ref, int new_data)

{

    / * выделить узел * /

    Node* new_node = new Node();

  

    / * вставить данные * /

    new_node->data = new_data;

  

    / * связать старый список с новым узлом * /

    new_node->next = (*head_ref);

  

    / * переместить голову, чтобы указать на новый узел * /

    (*head_ref) = new_node;

}

  
/ * Считает нет. вхождений узла
(search_for) в связанном списке (заголовок) * /

int count(Node* head, int search_for)

{

    Node* current = head;

    int count = 0;

    while (current != NULL) {

        if (current->data == search_for)

            count++;

        current = current->next;

    }

    return count;

}

  
/ * Программа драйвера для проверки функции подсчета * /

int main()

{

    / * Начнем с пустого списка * /

    Node* head = NULL;

  

    / * Используйте push () для построения списка ниже

    1-> 2-> 1-> 3-> 1 * /

    push(&head, 1);

    push(&head, 3);

    push(&head, 1);

    push(&head, 2);

    push(&head, 1);

  

    / * Проверьте функцию подсчета * /

    cout << "count of 1 is " << count(head, 1);

    return 0;

}

  
// Это код, предоставленный rathbhupendra

С

// C программа для подсчета вхождений в связанном списке
#include <stdio.h>
#include <stdlib.h>

  
/ * Узел списка ссылок * /

struct Node {

    int data;

    struct Node* next;

};

  
/ * Дана ссылка (указатель на указатель) на голову

  списка и int, нажмите новый узел на передней панели

  из списка. * /

void push(struct Node** head_ref, int new_data)

{

    / * выделить узел * /

    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));

  

    / * вставить данные * /

    new_node->data = new_data;

  

    / * связать старый список с новым узлом * /

    new_node->next = (*head_ref);

  

    / * переместить голову, чтобы указать на новый узел * /

    (*head_ref) = new_node;

}

  
/ * Считает нет. вхождений узла

   (search_for) в связанном списке (заголовок) * /

int count(struct Node* head, int search_for)

{

    struct Node* current = head;

    int count = 0;

    while (current != NULL) {

        if (current->data == search_for)

            count++;

        current = current->next;

    }

    return count;

}

  
/ * Программа драйвера для проверки функции подсчета * /

int main()

{

    / * Начнем с пустого списка * /

    struct Node* head = NULL;

  

    / * Используйте push () для построения списка ниже

     1-> 2-> 1-> 3-> 1 * /

    push(&head, 1);

    push(&head, 3);

    push(&head, 1);

    push(&head, 2);

    push(&head, 1);

  

    / * Проверьте функцию подсчета * /

    printf("count of 1 is %d", count(head, 1));

    return 0;

}

Джава

// Java-программа для подсчета вхождений в связанном списке

class LinkedList {

    Node head; // заголовок списка

  

    / * Узел связанного списка * /

    class Node {

        int data;

        Node next;

        Node(int d)

        {

            data = d;

            next = null;

        }

    }

  

    / * Вставляет новый узел в начало списка. * /

    public void push(int new_data)

    {

        / * 1 & 2: выделить узел &

                  Введите данные * /

        Node new_node = new Node(new_data);

  

        / * 3. Сделать следующий новый узел в качестве головы * /

        new_node.next = head;

  

        / * 4. Переместить голову, чтобы указать на новый узел * /

        head = new_node;

    }

  

    / * Считает нет. вхождений узла

    (search_for) в связанном списке (заголовок) * /

    int count(int search_for)

    {

        Node current = head;

        int count = 0;

        while (current != null) {

            if (current.data == search_for)

                count++;

            current = current.next;

        }

        return count;

    }

  

    / * Функция драйвера для проверки вышеуказанных методов * /

    public static void main(String args[])

    {

        LinkedList llist = new LinkedList();

  

        / * Используйте push () для построения списка ниже

          1-> 2-> 1-> 3-> 1 * /

        llist.push(1);

        llist.push(2);

        llist.push(1);

        llist.push(3);

        llist.push(1);

  

        / * Проверка функции счета * /

        System.out.println("Count of 1 is " + llist.count(1));

    }

}
// Этот код предоставлен Раджатом Мишрой

питон

# Программа Python для подсчета количества раз, данное
# int встречается в связанном списке

  
# Класс узла

class Node:

  

    # Конструктор для инициализации объекта узла

    def __init__(self, data):

        self.data = data

        self.next = None

  

class LinkedList:

  

    # Функция для инициализации головы

    def __init__(self):

        self.head = None

  

    # Считает нет. вхождений узла

    # (search_for) в связанном списке (заголовок)

    def count(self, search_for):

        current = self.head

        count = 0

        while(current is not None):

            if current.data == search_for:

                count += 1

            current = current.next

        return count

  

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

    def push(self, new_data):

        new_node = Node(new_data)

        new_node.next = self.head

        self.head = new_node

  

    # Утилита для печати связанного LinkedList

    def printList(self):

        temp = self.head

        while(temp):

            print temp.data,

            temp = temp.next

  

  
# Драйверная программа

llist = LinkedList()

llist.push(1)

llist.push(3)

llist.push(1)

llist.push(2)

llist.push(1)

  
# Проверьте функцию подсчета

print "count of 1 is % d" %(llist.count(1))

  
# Этот код предоставлен Nikhil Kumar Singh (nickzuck_007)

C #

// C # программа для подсчета вхождений в связанном списке

using System;

class LinkedList {

    Node head; // заголовок списка

  

    / * Узел связанного списка * /

    public class Node {

        public int data;

        public Node next;

        public Node(int d)

        {

            data = d;

            next = null;

        }

    }

  

    / * Вставляет новый узел в начало списка. * /

    public void push(int new_data)

    {

        / * 1 & 2: выделить узел &

                Введите данные * /

        Node new_node = new Node(new_data);

  

        / * 3. Сделать следующий новый узел в качестве головы * /

        new_node.next = head;

  

        / * 4. Переместить голову, чтобы указать на новый узел * /

        head = new_node;

    }

  

    / * Считает нет. вхождений узла

    (search_for) в связанном списке (заголовок) * /

    int count(int search_for)

    {

        Node current = head;

        int count = 0;

        while (current != null) {

            if (current.data == search_for)

                count++;

            current = current.next;

        }

        return count;

    }

  

    / * Код водителя * /

    public static void Main(String[] args)

    {

        LinkedList llist = new LinkedList();

  

        / * Используйте push () для построения списка ниже

        1-> 2-> 1-> 3-> 1 * /

        llist.push(1);

        llist.push(2);

        llist.push(1);

        llist.push(3);

        llist.push(1);

  

        / * Проверка функции счета * /

        Console.WriteLine("Count of 1 is " + llist.count(1));

    }

}

  
// Этот код предоставлен Арнабом Кунду


Выход:

count of 1 is 3

Сложность времени: O (n)
Вспомогательное пространство: O (1)

Метод 2 — с рекурсией
Этот метод предоставлен MY_DOOM .
Алгоритм:

Algorithm
count(head, key);
if head is NULL
return frequency
if(head->data==key)
increase frequency by 1
count(head->next, key)

Реализация:

C ++

// C ++ программа для подсчета вхождений в
// связанный список с использованием рекурсии
#include <bits/stdc++.h>

using namespace std;

  
/ * Узел списка ссылок * /

struct Node {

    int data;

    struct Node* next;

};
// глобальная переменная для подсчета частоты
// заданный элемент k

int frequency = 0;

  
/ * Дана ссылка (указатель на указатель) на голову
списка и int, нажмите новый узел на передней панели
из списка. * /

void push(struct Node** head_ref, int new_data)

{

    / * выделить узел * /

    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));

  

    / * вставить данные * /

    new_node->data = new_data;

  

    / * связать старый список с новым узлом * /

    new_node->next = (*head_ref);

  

    / * переместить голову, чтобы указать на новый узел * /

    (*head_ref) = new_node;

}

  
/ * Считает нет. вхождений узла
(search_for) в связанном списке (заголовок) * /

int count(struct Node* head, int key)

{

    if (head == NULL)

        return frequency;

    if (head->data == key)

        frequency++;

    return count(head->next, key);

}

  
/ * Программа драйвера для проверки функции подсчета * /

int main()

{

    / * Начнем с пустого списка * /

    struct Node* head = NULL;

  

    / * Используйте push () для построения списка ниже

     1-> 2-> 1-> 3-> 1 * /

    push(&head, 1);

    push(&head, 3);

    push(&head, 1);

    push(&head, 2);

    push(&head, 1);

  

    / * Проверьте функцию подсчета * /

    cout << "count of 1 is " << count(head, 1);

    return 0;

}

Джава

// Java-программа для подсчета вхождений в
// связанный список с использованием рекурсии

import java.io.*;

import java.util.*;

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

class Node {

    int data;

    Node next;

    Node(int val)

    {

        data = val;

        next = null;

    }

}

  

class GFG {

  

    // глобальная переменная для подсчета частоты

    // заданный элемент k

    static int frequency = 0;

  

    / * Дана ссылка (указатель на указатель) на голову

    списка и int, нажмите новый узел на передней панели

    из списка. * /

  

    static Node push(Node head, int new_data)

    {

        // выделить узел

        Node new_node = new Node(new_data);

  

        // связать старый список с новым узлом

        new_node.next = head;

  

        // перемещаем голову, чтобы указать на новый узел

        head = new_node;

  

        return head;

    }

  

    / * Считает нет. вхождений узла

    (search_for) в связанном списке (заголовок) * /

    static int count(Node head, int key)

    {

        if (head == null)

            return frequency;

        if (head.data == key)

            frequency++;

        return count(head.next, key);

    }

  

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

    public static void main(String args[])

    {

        // Начнем с пустого списка

        Node head = null;

  

        / * Используйте push () для построения списка ниже

        1-> 2-> 1-> 3-> 1 * /

        head = push(head, 1);

        head = push(head, 3);

        head = push(head, 1);

        head = push(head, 2);

        head = push(head, 1);

  

        / * Проверьте функцию подсчета * /

        System.out.print("count of 1 is " + count(head, 1));

    }

}

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

python3

# Python программа для подсчета количества
# время, когда данный int встречается в связанном списке
# Класс узла

class Node:

      

    # Конструктор для инициализации объекта узла

    def __init__(self, data):

        self.data = data

        self.next = None

  

class LinkedList:

      

    # Функция для инициализации головы

    def __init__(self):

        self.head = None

        self.counter = 0

          

    # Считает нет. вхождения узла

    # (seach_for) в связанном списке (заголовок)

    def count(self, li, key):     

          

        # Базовый вариант

        if(not li): 

            return self.counter

          

        # Если ключ присутствует в

        # текущий узел, верните true

        if(li.data == key): 

            self.counter = self.counter + 1

          

        # Повтор для оставшегося списка

        return self.count(li.next, key) 

  

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

    # с начала

    def push(self, new_data):

        new_node = Node(new_data)

        new_node.next = self.head

        self.head = new_node

  

    # Утилита для печати

    # связанный LinkedList

    def printList(self):

        temp = self.head

        while(temp):

            print (temp.data)

            temp = temp.next

  
Код водителя

llist = LinkedList()

llist.push(1)

llist.push(3)

llist.push(1)

llist.push(2)

llist.push(1)

  
# Проверьте функцию подсчета

print ("count of 1 is", llist.count(llist.head, 1))

  
# Этот код предоставлен
# Гаурав Кумар Рагхав

C #

// C # программа для подсчета вхождений в
// связанный список с использованием рекурсии

using System;

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

public class Node {

    public int data;

    public Node next;

    public Node(int val)

    {

        data = val;

        next = null;

    }

}

  

class GFG {

  

    // глобальная переменная для подсчета частоты

    // заданный элемент k

    static int frequency = 0;

  

    / * Дана ссылка (указатель на указатель) на голову

    списка и int, нажмите новый узел на передней панели

    из списка. * /

  

    static Node push(Node head, int new_data)

    {

        // выделить узел

        Node new_node = new Node(new_data);

  

        // связать старый список с новым узлом

        new_node.next = head;

  

        // перемещаем голову, чтобы указать на новый узел

        head = new_node;

  

        return head;

    }

  

    / * Считает нет. вхождений узла

    (search_for) в связанном списке (заголовок) * /

    static int count(Node head, int key)

    {

        if (head == null)

            return frequency;

        if (head.data == key)

            frequency++;

        return count(head.next, key);

    }

  

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

    public static void Main(String[] args)

    {

        // Начнем с пустого списка

        Node head = null;

  

        / * Используйте push () для построения списка ниже

        1-> 2-> 1-> 3-> 1 * /

        head = push(head, 1);

        head = push(head, 3);

        head = push(head, 1);

        head = push(head, 2);

        head = push(head, 1);

  

        / * Проверьте функцию подсчета * /

        Console.Write("count of 1 is " + count(head, 1));

    }

}

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

Выход:

count of 1 is 3

Приведенный ниже метод может быть использован, чтобы избежать Глобальной переменной «частота» (счетчик в случае кода Python 3).

C ++

// метод может быть использован, чтобы избежать
// Глобальная переменная 'частота'

  
/ * Считает нет. вхождений узла
(search_for) в связанном списке (заголовок) * /

int count(struct Node* head, int key)

{

    if (head == NULL)

        return 0;

    if (head->data == key)

        return 1 + count(head->next, key);

    return count(head->next, key);

}

Джава

// метод может быть использован, чтобы избежать
// Глобальная переменная 'частота'

  
/ * Считает нет. вхождений узла
(search_for) в связанном списке (заголовок) * /

int count(Node head, int key)

{

    if (head == null)

        return 0;

    if (head.data == key)

        return 1 + count(head.next, key);

    return count(head.next, key);

}

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

C #

// метод может быть использован, чтобы избежать
// Глобальная переменная 'частота'

using System; 

  
/ * Считает нет. вхождений узла
(search_for) в связанном списке (заголовок) * /

static int count(Node head, int key) 

    if (head == null

        return 0; 

    if (head.data == key) 

        return 1 + count(head.next, key);

    return count(head.next, key); 

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

python3

def count(self, temp, key):

      

    # во время первого звонка, темп

    # имеет значение головы

      

    # Базовый вариант

    if temp is None:

        return 0

          

    # если совпадение найдено, мы

    # увеличить счетчик

    if temp.data == key:

        return 1 + count(temp.next, key)

    return count(temp.next, key)

      
# для подсчета звонков, используйте
# connected_list_name.count (голова, ключ)

Вышеуказанный метод реализует рекурсию головы. Ниже приведена хвостовая рекурсивная реализация того же самого. Спасибо Puneet Jain за предложение такого подхода:

int count(struct Node* head, int key)
{
    if(head == NULL)
        return 0;
        
   int frequency = count(head->next, key);
   if(head->data == key)
     return 1 + frequency;
    
    // else 
    return frequency;
}

Сложность времени: O (n)

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

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

Напишите функцию, которая подсчитывает, сколько раз данное int встречается в связанном списке.

0.00 (0%) 0 votes