C从整数列表中获取模式
我需要编写一个程序来查找模式。 或者最多出现一个整数或整数。 所以，
1,2,3,4,1,10,4,23,12,4,1将具有1和4的模式。
我不确定应该使用哪种算法。 我很难想到能够奏效的东西。
我正在考虑某种频率表，也许我可以通过数组，然后通过创建一个链表。 如果链接不包含该值，则将其添加到链接，如果是，则将值加1。
所以，如果我从上面有同样的事情。 循环通过1,2,3,4,1,10,4,23,12,4,1
然后list为空，所以添加number = 1和value = 1的节点.2不存在，所以添加number = 2和value = 1的节点，依此类推。 到1和1已经存在，所以值= 2现在。
我必须循环遍历数组，然后每次循环遍历链表以找到该值。
完成后，请浏览链接列表并创建一个新的链接列表来保存模式。 所以我将头设置为第一个元素1.然后我浏览包含出现的链接列表并比较值。 如果当前节点的出现>当前最高，那么我将头设置为该节点。 如果它=到最高，那么我将节点添加到模式链表。
完成后，我遍历模式列表并打印值。
不确定这是否有效。 有没有人看到这个有什么问题？ 有更简单的方法吗？ 我也在考虑哈希表，但不确定如何在C中做到这一点。
谢谢。
您拥有的算法适用于家庭作业。 您可以使用各种方法来优化代码，例如：
- 使用二叉树提高效率，
- 使用一个计数数组，其中索引是数字（假设数字范围有限）。
但我想你会发现在这种情况下他们没有必要。 对于家庭作业来说，目的只是为了表明你理解如何编程，而不是你知道各种各样的技巧来榨取最后一盎司的表现。 您的教育工作者将更多地寻找可读，结构化的代码而不是棘手的优化。
我将在下面描述我会做什么。 你显然可以根据自己的意愿尽可能多地使用我的建议，这取决于你自己想要获得多少满足感。 我只提供伪代码，这是我的家庭作业问题的标准做法。
我将从一个包含数字，计数和下一个指针（用于链接列表）的结构和指向第一个指针的全局指针开始：
typedef struct sElement { int number; int count; struct sElement *next; } tElement; tElement first = NULL; 然后创建一些用于创建和使用列表的函数：
tElement *incrementElement (int number); tElement *getMaxCountElement (void); tElement *getNextMatching (tElement *ptr, int count);
这些function将分别为：
- 增加元素的计数（或创建它并将计数设置为1）。
- 扫描返回最大计数的所有元素。
- 获取与计数匹配的下一个元素指针，从给定点开始，如果不再，则为NULL。
每个伪代码：
def incrementElement (number): # Find matching number in list or NULL. set ptr to first while ptr is not NULL: if ptr->number is equal to number: return ptr set ptr to ptr->next # If not found, add one at start with zero count. if ptr is NULL: set ptr to newly allocated element set ptr->number to number set ptr->count to 0 set ptr->next to first set first to ptr # Increment count. set ptr->count to ptr->count + 1
def getMaxCountElement (number): # List empty, no mode. if first is NULL: return NULL # Assume first element is mode to start with. set retptr to first # Process all other elements. set ptr to first->next while ptr is not NULL: # Save new mode if you find one. if ptr->count is greater than retptr->count: set retptr to ptr set ptr to ptr->next # Return actual mode element pointer. return retptr
def getNextMatching (ptr, number): # Process all elements. while ptr is not NULL: # If match on count, return it. if ptr->number is equal to number: return ptr set ptr to ptr->next # Went through whole list with no match, return NULL. return NULL
然后你的主程序变成：
# Process all the numbers, adding to (or incrementing in) list . for each n in numbers to process: incrementElement (n) # Get the mode quantity, only look for modes if list was non-empty. maxElem = getMaxCountElement () if maxElem is not NULL: # Find the first one, whil exists, print and find the next one. ptr = getNextMatching (first, maxElem->count) while ptr is not NULL: print ptr->number ptr = getNextMatching (ptr->next, maxElem->count)
如果可以将整个整数列表保留在内存中，则可以先对列表进行排序，这将使重复值彼此相邻。 然后，您可以对排序列表执行单次传递以查找模式。 这样，您只需要跟踪到目前为止看到的模式的最佳候选者，以及到目前为止看到当前值的次数。
如果数字范围是预先知道的，并且是一个合理的数字，你可以为计数器分配一个足够大的数组，只需要count[i] += 1 。
如果数字范围未提前知道，或者对于天真使用数组而言太大，则可以维护一个值的二叉树来维护计数器。 这将使您的搜索量远远低于链接列表。 无论哪种方式，您都必须遍历数组或树并构建从最高到最低计数的顺序。 我再次推荐一棵树，但你的列表解决方案也可以。
另一个有趣的选择可能是在提取阶段使用优先级队列 。 完成计数器列表后，遍历树并以优先级等于其计数的值插入每个值。 然后，您只需从优先级队列中提取值，直到计数结束。
我会选择一个简单的基于哈希表的解决方案。
包含数字和相应频率的哈希表的结构。 另外还有指向哈希桶中链接的下一个元素的指针。
struct ItemFreq { struct ItemFreq * next_; int number_; int frequency_; };
处理开始于
max_freq_so_far = 0;
它遍历数字列表。 对于每个number ，查找哈希表以查找ItemFreq元素x ，使得x.number_ == number 。
- 如果没有找到这样的
x，则将ItemFreq元素创建为{ number_ = number, frequency_ = 1}并插入到散列表中。 - 如果找到一些
x，则其frequency_递增。 - 如果
frequency_ > max_freq_so_far则max_freq_so_far = frequency
遍历完成的数字列表后，我们遍历哈希表并打印其frequency_ == max_freq_so_far为ItemFreq frequency_ == max_freq_so_far的ItemFreq项目
算法的复杂性为O(N) ，其中N是输入列表中的项目数。
有关哈希表的简单而优雅的构造，请参阅K＆R（C编程语言）的 6.6节 。
这个回答是Paul Kuliniewicz想法的一个例子：
int CompInt(const void* ptr1, const void* ptr2) { const int a = *(int*)ptr1; const int b = *(int*)ptr2; if (a < b) return -1; if (a > b) return +1; return 0; } // This function leave the modes in output and return the number // of modes in output. The output pointer should be available to // hold at least n integers. int GetModes(const int* v, int n, int* output) { // Sort the data and initialize the best result. qsort(v, v + n, CompInt); int outputSize = 0; // Loop through elements while there are not exhausted. // (look there is no ++i after each iteration). for (int i = 0; i < n;) { // This is the begin of the new group. const int begin = i; // Move the pointer until there are no more equal elements. for (; i < n && v[i] == v[begin]; ++i); // This is one-past the last element in the current group. const int end = i; // Update the best mode found until now. if (end - begin > best) { best = end - begin; outputSize = 0; } if (end - begin == best) output[outputSize++] = v[begin]; } return outputSize; }