c++ - 如何在自定义链表实现中找到最常见的元素？

Question

我正在尝试制作自己的非 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; 
} 

标签： c++liststructsingly-linked-list

Answer 1

对于初学者来说，当函数依赖于全局变量时，这是一种不好的方法。例如，对于您的应用程序，您不能在一个程序中声明两个列表。

在不使用其他标准容器的情况下，可以通过以下方式定义功能。

#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

不幸的是，我的清单是空的。:)