0

我有这个结构：

typedef struct data student, *pstudent;


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

我需要一个函数来在未排序的链表中找到最常见的学生。例如：“John - value 3” “David - value 2” “Andrew - value 4” “John - 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;
     }
    }

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

4

2 回答 2

2

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

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

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

于 2013-06-23T14:33:19.520 回答
1

One way to do it will be to use a key transformation or hash function. Use a hash on the name and if the hashed value matches, increment the count for that name by one. Return the one with the highest count.

于 2013-06-23T14:18:14.893 回答