找到最常见的元素链表

Question

我有这样的结构：

typedef struct data student, *pstudent; 


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

而且我需要找到一个无序链表最频繁的学生的功能。 例如： “约翰 - 值3” “大卫 - 值2” “安德鲁 - 值4” “约翰 - 值9” 在这种情况下，该函数将返回“约翰”，因为他出现了两次。

到目前为止的代码：

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）算法）。

因此，您将看到经典的时空交易。很大程度上取决于您将要处理的数据集的大小以及数据集中的重复数量。最适合小批量生产的产品在大批量生产时可能效果不佳。

Answer 2

这样做的一种方法是使用密钥转换或散列函数。对名称使用散列，如果散列值匹配，则将该名称的计数增加1。返回计数最高的那个。