Неверное исключение элементов из массива

Question

Задание: Определить, есть ли в целочисленном массиве Q (10) заданное число Х, и если есть, удалить его (если встречается неоднократно, то удалить все такие значения), а если нет, добавить в конец массива.

Си

#include <stdlib.h>
int main()
{
    int size = 5, *Q, i, j, x, count = 0;
    Q = malloc(size * sizeof*Q);
    for(i = 0; i < size; i++)
        scanf("%d", &Q[i]);
    for(i = 0; i < size; i++)
        printf("%d ", Q[i]);
    putchar('\n');
    printf("Enter number:");
    while(1 != scanf("%d", &x)){
        printf("Incorrect data enter!Try again.");
        while(getchar() != '\n');
    }
    for(i = 0; i < size; i++){
        if(Q[i] == x){
            count++;
            for(j = i; j < size - 1; j++)
                Q[j] = Q[j + 1];
        }
    }
    if(count){
        size -= count;
        for(i = 0; i < size; i++)
            printf("%d ", Q[i]);
        putchar('\n');
    }
    else{
        size++;
        Q = realloc(Q, size * sizeof*Q);
        if(!Q){
            printf("Error allocate memory!");
            return 0;
        }
        for(i = 0; i < size; i++){
            if(i == size - 1)
                Q[i] = x;
            printf("%d ", Q[i]);
        }
        putchar('\n');
    }
    return 0;
}

В результате компиляции происходит неверное исключение элементов:

43

23

65

87

23

43 23 65 87 23

Enter number:23

43 65

Знакомый сказал, что это ошибка индексации, но я не понимаю в чём проблема.

Answer 1

Массив Q изменяется три раза на итерациях 1, 3 и 4. Изменяется - громко сказано. Два последних изменения оставляют массив в прежнем состоянии. Для нас важно значение переменной count в конце. Предполагается что count считает элементы равные 23. Их два в исходном массиве. Но массив меняется, последнее значение удваивается и два раза подсчитывается:

i           Q          count
0    [43 23 65 87 23]    0
1    [43 65 87 23 23]    1
2    [43 65 87 23 23]    1
3    [43 65 87 23 23]    2
4    [43 65 87 23 23]    3

Вот правка, которая починит ваш код. Надо остановить цикл раньше чем кончится массив Q:

// for(i = 0; i < size; i++){
for(i = 0; i < size - count; i++){

Answer 2

По мере удаления элементов из массива Q его размер уменьшается, и в хвосте массива остаются значения, оставшиеся после сдвига элементов. Их не следует удалять, но цикл for(i = 0; i < size; i++) никак не учитывает уменьшение размера массива Q и продолжает удаление элементов в хвосте. Поэтому счётчик количества удалённых элементов count наращивается больше, чем следует.
Предположим, что элементы массива Q с индексами i и i+1 должны быть удалены. На i-той итерации цикла for все элементы массива Q начиная с индекса i+1 будут сдвинуты на одну позицию левее. Т.е. элемент i+1, который необходимо удалить, займёт позицию элемента i и на следующей итерации цикла избежит удаления.
Сдвигать хвост массива на одну позицию левее при каждом удалении — не эффективно. Можно завести два индекса: dest — позиция в массиве Q, в которую будем копировать элементы, src — позиция из которой копируем элементы.
В цикле перебираем элементы массива. Если наткнулись на элемент массива не подлежащий удалению, то копируем его из src в dest и наращиваем оба индекса.
Если наткнулись на элемент подлежащий удалению, то ничего не копируем и наращиваем только индекс src.
Примерно так:

size_t src = 0, dest = 0;
while (src < size)
{
    if (Q[src] != x)
    {
        Q[dest] = Q[src];
        ++dest;
    }
    ++src;
}

if (src - dest > 0)
    size -= src - dest;
else
{
    ++size;
    int* Q_new = realloc(Q, size * sizeof *Q);
    if (!Q_new)
    {
        free(Q);
        printf("Error allocate memory!");
        return EXIT_FAILURE;
    }
    Q = Q_new;
    Q[size - 1] = x;
}

for (size_t i = 0; i < size; ++i)
    printf("%d ", Q[i]);
putchar('\n');

БЛОГ НА HUSL

Неверное исключение элементов из массива

Ответы (2 шт):