Как найти наиболее распространенный элемент в реализации пользовательского связанного списка? - PullRequest
Новая
       10

Как найти наиболее распространенный элемент в реализации пользовательского связанного списка?

0 голосов
/ 13 апреля 2020

Я пытаюсь создать собственную реализацию связанного списка без STL.

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

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

Я хотел иметь возможность изменить функцию для поиска наиболее распространенного элемента. Ты хоть представляешь, как добиться того, что я пытаюсь сделать? 

#include <iostream>
using namespace std;

void add_е(int n);
void list();
int search_elem(int n);

 struct elem 
 {
    int key; 

    elem *next; 
 } *start=NULL; 


int main()
    {  
        int ch, num, amount, i, element;
    do
    {   cout<<"\n\t Menu";
        cout<<"\n 1.Add elements";
        cout<<"\n 2.Find the most common element";
        cout<<"\n 3.Print the stack";
        cout<<"\n 4.Exit";
    do
    {   cout<<"\n Your choice is:";
        cin>>ch;
    }
    while (ch<1||ch>4);
    switch(ch)
{

    case 1: 
        cout<<"\n How many elements do you want to add?";
        cin>>amount;
        for(i=0; i<amount; i++)
        {
            cout<<"Input stack elements:\n";
            cin>>num;
            add_е(num);
        }
    break;


    case 2:
        cout<<"\n Which element do you want to find? \n ";
        cin>>element;
        search_elem(element);   
        break;


    case 3: list();
    break;
}

}while(ch!=4); 
}

void add_е(int n) {  elem *p=start, *q=p;
    q=new elem;      
    q->key=n;    
    q->next=NULL;   
if (start)      
    {  
        while (p->next)
        p=p->next;  
        p->next=q;  
    }   
else    
    start=q;    
}       



void list()  
{   
    if (start) 
    { 
        elem *p=start;
        cout<<"\n List is: \n";
        while (p) 

        { 
            cout<<p->key<<"\n"; 
            p=p->next;   
        }   
    }  
    else 
        cout<<"\n Empty list";
} 


int search_elem(int n)   // here's what confuses me
{  
    elem *p=start; 
    if (start) 
    {
        while ((p->key!=n)&&(p->next))   
            p=p->next;  

        if (p->key==n)
    {
        cout<<"p->key"<<"\n";
        return 1; 
    }
    else 
        cout<<"No element found";
        return 0; 
    } 
    return 0; 
}

1 Ответ

0 голосов
/ 13 апреля 2020

Для начала это плохой подход, когда функции зависят от глобальной переменной. В случае вашего приложения вы не можете, например, объявить два списка в программе.

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

#include <utility>

struct elem 
{
    int key; 
    elem *next; 
} *start=NULL; 

std::pair<int, size_t> most_frequent( const elem *head )
{
    std::pair<int, size_t> max( 0, 0 );

    for ( ; head != nullptr; head = head->next )
    {
        if ( max.second == 0 || max.first != head->key )
        {
            size_t n = 1;

            for ( const elem *current = head->next; current != nullptr; current = current->next )
            {
                if ( current->key == head->key ) ++n;
            }

            if ( max.second < n )
            {
                max = { head->key, n };
            }
        }           
    }

    return max;
}

Она не полагается для глобальной переменной и может вызываться как 

auto max = most_frequent( start );

Вот демонстрационная программа 

#include <iostream>
#include <utility>

struct elem 
{
    int key; 
    elem *next; 
} *start=NULL; 

std::pair<int, size_t> most_frequent( const elem *head )
{
    std::pair<int, size_t> max( 0, 0 );

    for ( ; head != nullptr; head = head->next )
    {
        if ( max.second == 0 || max.first != head->key )
        {
            size_t n = 1;

            for ( const elem *current = head->next; current != nullptr; current = current->next )
            {
                if ( current->key == head->key ) ++n;
            }

            if ( max.second < n )
            {
                max = { head->key, n };
            }
        }           
    }

    return max;
}

int main() 
{
    auto max = most_frequent( start );

    std::cout << "the key " << max.first 
              << " is encountered most frequently "
              << max.second << " times\n";

    return 0;
}

Вывод программы: 

the key 0 is encountered most frequently 0 times

К сожалению, мой список был пуст .:)

...