Функция, которая проверяет, сколько раз каждый элемент появляется в массиве

Question

Я создаю функцию, которая перечисляет массив и говорит, сколько раз каждый элемент появляется.

То, что я думал о себе до сих пор, это то, что я должен проходить через массив, и должен быть счетчик, чтобы отслеживать количество раз, которое он появляется, а затем второй массив, чтобы поместить значение этого счетчика в соответствие значению в первом массиве.

Но я не могу найти алгоритм поиска, чтобы увидеть, повторялось ли каждое значение внутри цикла.

Answer 1

Пример кода был упрощен, и имеет больше комментариев

Вот некоторые предлагаемые шаги:
1) предполагая int a[] отсортирован (для простоты подсчета) (по возрастанию или убыванию, Это не имеет значения).
2) Создание отдельных массивов, чтобы держать найдены результаты где
первых один, num[] хранит уникальное значение, и
второгоcnt[] хранит количество этого значения не найдено.
3) цикл через отсортированный массив.
4) в цикле, хранить уникальное значение и количество встречаемости в массиве keep.

Распределяющей рутинного qsort() это понятие вы узнаете позже, если вы только начинаете, (не отвлекайтесь с ним сейчас) но делают наблюдать часть этого примера решения вашего вопроса, смотрите для комментариев "Посмотри здесь". Как описано выше, он проходит через массив и сохраняет информацию о том, когда числа меняются, и сколько из них есть.

Вот небольшой пример кода:

Посмотрите на комментарии, чтобы знать, где сосредоточить внимание на установки счетчиков и т.д.

#include <stdio.h> 
#define sizea 100 //to make variable declarations easier and consistent 

    int num[sizea];//unless array has all unique numbers, will never use this many 
    int cnt[sizea];//same comment 

int cmpfunc (const void * a, const void * b);//DISREGARD for now (it just works) 

int main(void) 
{ //a[] is created here as an unsorted array... 
    int a[sizea]={1,3,6,8,3,6,7,4,6,9,0,3,5,12,65,3,76,5,3,54, 
        1,3,6,89,3,6,7,4,6,9,0,4,5,12,65,3,76,5,3,54, 
        1,9,6,8,3,45,7,4,6,9,0,89,5,12,65,3,76,5,3,54, 
        6,3,6,8,3,6,7,4,6,9,0,23,5,12,65,3,76,5,3,54, 
        1,3,6,90,3,6,7,4,6,9,0,5,5,12,65,3,76,5,3,54}; 

    int i, j, ncount; 

    for(i=0;i<sizea;i++) cnt[i] = -1; 
    for(i=0;i<sizea;i++) num[i] = -999; 

    //sort array (AGAIN - DON'T spend time on this part, it just sorts the array) 
    qsort(a, sizea, sizeof(int), cmpfunc); 

    // a is NOW SORTED, in ascending order, now loop through... 
    j=0; //start num and cnt arrays at first element and set ncount to 1 
    num[j] = a[0]; 
    cnt[j] = 1; 
    ncount = 1;//start off with at least one of the first number 
    //***Look Here***// 
    for(i=0;i<sizea-1;i++)//"sizea - 1" so we do not go past a[sizea-1] elements 
    {      //a has sizea elements, indexed from 0 to sizea-1 
          //or a[0] to a[99] 
     if(a[i+1] != a[i]) 
     { 
      j++; //new unique number, increment num[] array 
      num[j] = a[i+1]; 
      ncount = 1; //different number start over 
      cnt[j] = ncount;//initialize new cnt[j] with 1 
     } 
     else 
     { 
      cnt[j] = ++ncount; //increment cnt, apply it to array 
     } 
    } 
    i=0; 

    //We now have a list of unique numbers, and count of each one. Print it out 
    for(i=0;i<j;i++) 
    { 
     printf("number %d occurs %d times\n", num[i], cnt[i]); 
    } 
    getchar(); //so results will show. 

    return 0; 
} 
//Note num[j] and cnt[j] correspond to each other 
//num contains a unique number 
//cnt contains the number of occurrences for that number 

int cmpfunc (const void * a, const void * b) 
{ 
    return (*(int*)a - *(int*)b); 
} 

Для примера массива включены, вот результаты, используя этот код:

Answer 2

Я опубликовал псевдокод, чтобы помочь вам с алгоритмом, который вы сказали, что не можете понять. Надеюсь, это поможет вам начать код.

//store the first number in a variable and find 
//how many times it occurs in the array, repeat this for all 
//the elements in the array 

int current = arr[0]; 
int i=0, count=0; 

for(i=0; i < arr.length;i++){ // loop through all the elements of the array 

    if(arr[i]==current) { 
     count++; // if current number is same as the number you are looking for 
        // then increment the counter 
    } // end of if-loop 
} 

Answer 3

Сначала вы должны определить список с целыми числами у вас есть и их число появлений

struct linked_list { 
    int value; 
    int numOf; 

    linked_list *next; 
}; 

тогда у вас должны быть функции для работы с этим списком, например, создание списка, нажатие на него элемента, поиск узла в этом списке и пр. int it the list.

linked_list* newItem(int value) { 
    linked_list * temp = (linked_list *)malloc(sizeof(linked_list)); 

    (*temp).value = value; 
    (*temp).numOf = 1; 

    return temp; 
} 

linked_list* findItem(linked_list *head, int value) { 
    linked_list *counter = head; 

    while (counter != NULL && (*counter).value != value) { 
     counter = (*counter).next; 
    } 

    return counter; 
} 

void pushToList(linked_list **head, linked_list *item) { 
    (*item).next = *head; 
    *head = item; 
} 

void printList(linked_list *head) { 
    while (head != NULL) { 
     printf("%d:%d\n", (*head).value, (*head).numOf); 
     head = (*head).next; 
    } 
} 

Вы должны изучить списки, чтобы понять, как они работают. Тогда ваш код логика выглядит следующим образом:

linked_list *duplicate = NULL; 
int i; 

int list[11] = { 1, 2, 3, 4, 1, 2, 3, 4, 0, 1, 2 }; 

for (i = 0; i < 11; i++) { 
    linked_list *current = findItem(duplicate, list[i]); 

    if (current == NULL) 
     pushToList(&duplicate, newItem(list[i])); 
    else 
     (*current).numOf++; 
} 

printList(duplicate); 

while (1); 

return 0; 

(я должен освободить список, но я не сделал в этом коде: P)

составляет список с деталями/элементами, которые могут быть дубликат , Я начинаю с начала массива. Я проверяю первый элемент массива, а затем проверяю, находится ли он в дублированном списке. Если я не могу найти его в списке, я делаю новую запись в дубликатном списке с 1 количеством выступлений. Затем я проверяю остальное, если они появляются в списке, я добавляю количество явлений на один, если они не являются, я делаю новую запись. В конце мой список будет иметь количество и количество выступлений.

Этот код принимает шаги O (n), если ваша разность данных является константой. Если ваша разница в данных растет с количеством элементов, это потребует больше шагов.

Этот подход лучше, чем алгоритмы сортировки во многих случаях с точки зрения количества шагов для выполнения и распределения памяти.