Developing.ru

Вроде теоретически массивы понимаю - ничего сложного. Но на практике выходит какая-то ересь.
Есть частично заполненный массив типа char.
Цель: функция, удаляющая одинаковые вхождения символов и сдвигающая последующие элементы.

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

Теория следующая:
- Для поставленной задачи используем еще один массив (b), такого же размера, где первый элемент совпадает с первым элементом массива a. В него будут записываться вхождения без повторов.
- Сравниваем элемент массива a[0] с каждым элементом до a[size-1].
- Если элементы не совпадают, то записываем их в массив b[index] (index = 1), после чего index++.
- Если элементы совпадают, то запись в массив b не производится, а size массива b уменьшаем на 1.

В итоге, если изначально массив a[] = {a, b, a, c}, то на выходе b[] = {a, b, c}.

Я явно что-то упустил или чего-то не понял, но у меня получилось что-то вроде такого:

Код: Выделить всё

void del{char a[], int size)
{//size = 4;
   char b[size];
   int a_index1, a_index2, b_index1 = 1, b_total = size;
   
   b[0] = a[0]
   for(a_index1 = 0; a_index < size; a_index1++)
   {//сравниваем поочередно каждый элемент массива 'a' с остальными элементами.
     for(a_index2 = 1; a_index2 < size; a_index2++)
     {
       if(a[a_index1] != a[a_index2]
       {
         b[b_index1] = a[a_index2];
         b_index1++;
       }
     }
   }
}

В итоге выходит бред: b_index1 = 9, элементы массива b представляют собой a b c a c b c b a. Т.е. не то, что надо.
Дальше начинаю экспериментировать (это неправильно, нужно понимать что делаешь) и прихожу к вообще странным результатам, но никак не к тому, что требуется.
Где я допустил ошибку? Не туда начал думать и как следствие реализовывать?

Ошибка в том что когда ты сравниваешь первый элемент то не смотришь остальные...

Тоесть если у тебя будет {A,B,B} то ты в первый же раз сразу дважды добавишь B...

Я бы сделал так:

Код: Выделить всё

for(a_index1 = 0; a_index1 < size; a_index1++)
   {//сравниваем поочередно каждый элемент массива 'a' с остальными элементами.
    bool IsIn=false;
     for(a_index2 = 0; a_index2 < b_index1; a_index2++)
       if(a[a_index1] == b[a_index2])
	   {
		   IsIn=true;
		   break;
	   }
	 if(!IsIn)
	 {
		b[b_index1] = a[a_index1];
		b_index1++;
	 }
   }

Принцип такой - берешь элемент первого массива и смотришь есть ли он во втором, если нету - добавляешь, есть - идешь дальше

Т.е. сравниваем не элемент массива a с остальными элементами, а элемент массива a с элементами массива b?

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

Код: Выделить всё

void del(char a[], int size)
{
    using namespace std;
    int a_index, b_index, b_size = 1;
    char b[b_size];
    bool flag = false;

    for(a_index = 0; a_index < size; a_index++)
    {
        for(b_index = 0; b_index < b_size; b_index++)
        {
            if(a[a_index] == b[b_index])
            {
                flag = true;
            }
        }
        if(!flag)
            {
                b[b_index] = a[a_index];
                b_size++;
            }
        flag = false;
    }

    cout << "b_size = " << b_size << endl;
    for(b_index = 0; b_index < b_size; b_index++)
    {
        cout << "b[" << b_index << "] = " << b[b_index] << endl;
    }
}

А этот код компилируется? Особенно смущает строка

char b[size];

, ведь size - не константа и компилятор не может знать сколько выделять памяти под массив b.

Albor писал(а):А этот код компилируется? Особенно смущает строка , ведь size - не константа и компилятор не может знать сколько выделять памяти под массив b.

Компилируется.
Есть константа:
const int ARRAY_SIZE = 10;
Есть функция для заполнения массива (массив может быть заполнен не полностью):
void fill_array(char a[], int size, int& used);
В size передаю константу.
А уже в функцию:
void del(char a[], int size);
передаю то, что получилось в used.

Хотя да, с размером массива b... компилятор GNU GCC Compiler, не ругается. Но на что вы намекаете я понял. Есть над чем поудмать.

Я сейчас немного другую мысль развиваю, чтобы выполнить задачу без доп.массива, чтобы сам массив изменялся в размере (в меньшую сторону со сдвигом), если есть повторные символы.
Алгоритм следующий:
- Сверяем поочередно элемент массива с остальным массивом.
- Если есть совпадение, то заменяем повтор на ' '.
- Проверяем массив на наличие ' '.
- Если встречается ' ' и index+1 != размеру массива, то элементу массива index присваивается значение элемента массива index+1, а index+1 = ' '.

И опять не выходит

Код: Выделить всё

void del(char a[], int size)
{
    using namespace std;
    int index1, index2, index, count = 0;
    for(index1 = 0; index1 < number_used; index1++)
    {
        for(index2 = 1; index2 < size; index2++)
        {
            if((index1 != index2) && (a[index1] == a[index2])) //исключаем замену единичного символа, когда будет сверяться второй (тертий и т.д.) элемент с другими элементами массива
            {
                a[index2] = ' ';
            }
        }
        for(index = 0; index < size; index++)
        {
            if((a[index1] == ' ') && (a[index1+1] !=  size))
            {
                a[index1] = a[index1+1];
                a[index1+1] = ' ';
                count++; //size - count = новый размер массива
            }
        }
    }

    cout << "count = " << count << endl;
    for(index = 0; index < size; index++)
    {
        cout << "a[ " << index << "] = " << a[index] << endl;
    }
}

Не видел в первом посте, что вы пытаетесь сделать без дополнительного массива.

Ничего не мешает записывать данные в этот же...

Ведь в худшем варианте, если все буквы разные оно будет добавлять на ту позицию на которой оно и стоит...

Вот примерчик рабочий, не парился с объявлением массива чаров, тем более как я понял в этом нету сложности

Код: Выделить всё

#include "stdafx.h"
#include <conio.h>
#include <stdio.h>
const int size_array=12;

void main()
{
    int a_index, a_newsize=0,a_second_index;
    char a[size_array+1]="ababaacdsdsc";
    bool flag = false;

    for(a_index = 0; a_index < size_array; a_index++)
    {
        for(a_second_index = 0; a_second_index < a_newsize; a_second_index++)
        {
            if(a[a_index] == a[a_second_index])
            {
                flag = true;
            }
        }
        if(!flag)
            {
                a[a_newsize] = a[a_index];
                a_newsize++;
            }
        flag = false;
    }

    printf("a_newsize = %i\n", a_newsize);
    for(a_index = 0; a_index < a_newsize; a_index++)
    {
        //cout << "a[" << a_index << "] = " << a[a_index] << endl;
		printf("a[%i]=%c\n",a_index,a[a_index]);
    }
	getch();
}

Ну потом остается только обрезать массив до a_newsize

P.S какой тег для срр-го кода?)

Хм, это на С? Разберусь. Идею выше тоже надо довести до ума, хотя странно, что проверка не работает (дебаггер показывает накрутку index2 без всяких действий).

Кстати, не могу понять почему с двумя массивами 1 элемент (b[0]) пустой.

DexterUa писал(а): P.S какой тег для срр-го кода?)

[код=срр][/код]
код = code

Прикрутить глюк к одномерному - это надо уметь. Я начал с шестимерных динамических, так и то глюков не было.

Застыдили вы меня. Но еще раз пересмотрев код, пересмотрел дебаггер, ночью пару снов про массивы в этой задаче увидел. Собственно вот решение (отличается от предложенного DexterUa, но наверное менее оптимизированное, хотя не замерял), может кому пригодится (будет из чего выбирать).

Код: Выделить всё

void del(char a[], int& size)
{
    using namespace std;
    int index1, index2, index, count = 0, i = 1, temp;
    //index1, index2 - индексация массива для сверки 1 элемента со всеми остальными
    //index - индексация для сортировки массив
    //i - установка index2, дабы избежать удаления одиночного элемента.
    //count - счетчик, для уменьшения размера массива на кол-во повторов
    //temp - для пузырьковой сортировки

    for(index1 = 0; index1 < size; index1++)
    {
        for(index2 = i; index2 < size; index2++)
        {
            if((a[index1] == a[index2]) && (a[index1] != ' '))
            {
                a[index2] = ' ';
                count++;
            }  
        }
        for(index = 0; index < size; index++)
        {
            if((a[index] == ' ') && (a[index+1] !=  size))
            {
                temp = a[index+1];
                a[index+1] = a[index];
                a[index] = temp;;
            }
        }

        i++;
    }

    size -= count;

     //Тестируем результат обработки массива
    for(index = 0; index < size; index++)
    {
        cout << "a[ " << index << "] = " << a[index] << endl;
    }
}

Может его можно как-то оптимизировать, дабы уменьшить кол-во переменных, но думаю тут всего в меру (ни больше. ни меньше).

Dragon писал(а):Может его можно как-то оптимизировать, дабы уменьшить кол-во переменных, но думаю тут всего в меру (ни больше. ни меньше).

Зря так думаешь. Попробуй решить свою задачу вообще без индексов, используя указатели - это раз, второе - избавься от вложенного цикла, разрисуй свой массив на бумаге и продумай решение "на пальцах" - достаточно одного прохода по массиву, а значит и одного цикла. Третье, можно, при обнаружении дубля, не изменять элемент массива, а просто скопировать остаток массива со смещением на этот символ, для чего либо написать свою функцию копирования, либо использовать стандартную (memcpy, если мне не изменяет память, позволяет копировать перекрывающиеся диапазоны). Четвёртое, в твоей программе есть большой недостаток, заключающийся в том, что уменьшить размер исходного массива нельзя, размер его фиксированный и где его конец после обработки неизвестно, а поскольку ты в массиве хранишь символы, то не лучше ли обратить взор на С-строки, то есть на массив, заканчивающийся символом '\0'.

Developing.ru

Проблема с одномерным массивом.

Проблема с одномерным массивом.

Re: Проблема с одномерным массивом.

Re: Проблема с одномерным массивом.

Re: Проблема с одномерным массивом.

Re: Проблема с одномерным массивом.

Re: Проблема с одномерным массивом.

Re: Проблема с одномерным массивом.

Re: Проблема с одномерным массивом.

Re: Проблема с одномерным массивом.

Re: Проблема с одномерным массивом.