c - 查找最常见的元素链表

Question

我有这个结构:

typedef struct data student, *pstudent;


struct data{
    char name[50];
    int value;
   pstudent next;
};

而且我需要一个函数来查找未排序链表中出现频率最高的学生。例如:“约翰 - 值(value) 3”“大卫 - 值(value)2”“安德鲁 - 值(value) 4”“约翰 - 值(value) 9”在这种情况下，该函数将返回“John”，因为他出现了两次。

到目前为止的代码:

void count(pstudent p)
{
    pstudent ptr1, ptr2;
    ptr1 = p;

   while(ptr1 != NULL && ptr1->next!=NULL)
   {
        ptr2 = ptr1;

        while(ptr2->next != NULL)
        {
            if(strcmp(ptr1->name,ptr2->next->name)==0)
            {
                printf("Found %s, %s", ptr1->name,ptr2->name);
            }
        }
        ptr1 = ptr1->next;
     }
    }

我怎样才能使这项工作？感谢您的帮助。

Answer 1

如果想尽量减少内存的使用，遍历一次链表。对于您遇到的每个名字，计算它在列表中当前位置之后出现的次数。记录计数最高的名称(及其计数)。当您第一次遇到一个名字时，您将获得该名字的最高计数。这是一个 O(N²) 的算法，但只需要存储一个指向具有最大计数和最大计数的名称的指针。代价是它在大型列表上很慢。

主要的替代方案将是某种算法，该算法会密切关注遇到的名称，并在您遇到列表中的每个名称时增加与该名称关联的计数。这可能是 unxnut 建议的散列函数或者它可能使用不同名称的直接副本或指针。它需要某种数组，因此对于大型列表，它可能需要大量存储空间(但只要您谨慎管理数组，它就是一个 O(N) 算法)。

因此，您将面临经典的时空权衡。很大程度上取决于您要处理的数据集的大小以及数据集中的重复次数。最适合小批量的方法可能不适用于大批量。