找到最常見的元素鏈表

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。返回計數最高的那個。