VPF::Удаление повторяющихся n раз элементов списка

Thundaga

Дата 25.5.2009, 20:52 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 11
Регистрация: 25.5.2009

Репутация: 1
Всего: 1

zim22
В частном случае n=2. То есть - нужно удалять все пары одинаковых чисел (не обязательно идущие подряд) в массиве. К примеру при задании числа элементов семи и вводе, к примеру: 1 2 2 3 4 4 5 будет выведено: 1 3 5.
Проблема в том что если последний элемент тоже в паре с каким-либо, то при попытке удалить его программа выдает ошибку (вполне возможно, что вы, если проводили тесты, заметели). Хотелось бы узнать её причину, так как в остальном программа описанная в начале работает корректно. Буду очень благодарен.

Это сообщение отредактировал(а) Thundaga - 25.5.2009, 21:07

zim22

Дата 26.5.2009, 06:34 (ссылка)

(нет голосов)

Загрузка ...

depict1

Профиль
Группа: Завсегдатай
Сообщений: 2682
Регистрация: 15.1.2009
Где: Украина

Репутация: 29
Всего: 69

Цитата(Thundaga @ 25.5.2009, 20:52

)

Хотелось бы узнать её причину

Код


while(work) // цикл проверки
{
    del=true;
    if(twice(work,beg)) // проверка на пару элементов
    {
        for(helper=work->ref;helper&&del;helper=helper->ref)
            if(work->inf==helper->inf)
            {
                kill(helper); // удаление второго
                del = false; // выход из вторичного цикла
                
            }
            kill(work); // удаление первого
            //если было удаление - продолжаем проверку
    }
    
    work=work->ref; // сдвиг полюбому        
}

Это сообщение отредактировал(а) zim22 - 26.5.2009, 06:34

--------------------

C++ FAQ Lite

Thundaga

Дата 26.5.2009, 08:30 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 11
Регистрация: 25.5.2009

Репутация: 1
Всего: 1

zim22
Если сдвиг делать в любом случае, то некоторые элементы будут "выпадать". К примеру:
1 1 2 2 3
При удалении первой пары будет получено 2 2 3, однако счет пойдет от второй двойки и её пара не будет найдена. В лучшем случае (в 3 тестах из пяти, с вашим отрывком) выводилось 2 3.
Хм, если судить по замечаниям дебаггера, то ошибка находится на 30 строке. Пишет что helper не задан (если надо удалять последний элемент и пару к нему).

zim22

Дата 26.5.2009, 08:39 (ссылка)

(нет голосов)

Загрузка ...

depict1

Профиль
Группа: Завсегдатай
Сообщений: 2682
Регистрация: 15.1.2009
Где: Украина

Репутация: 29
Всего: 69

Thundaga, также вашу задачу можно решить за 2 прохода по циклу.
1 проход: считываем значения элементов в map<int, int> (ключ - значение элемента, value - количество повторений)
2 проход: все элементы, у которых map[key] > n - удалить
**
т.к. элементы вы вводите с клавиатуры, то первый проход можно не делать, а сразу строить map

Это сообщение отредактировал(а) zim22 - 26.5.2009, 08:48

--------------------

C++ FAQ Lite

Thundaga

Дата 26.5.2009, 17:42 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 11
Регистрация: 25.5.2009

Репутация: 1
Всего: 1

zim22
Огромное вам спасибо. Хотя с этой программой справился иным путем (созданием уникального закрывающего элемента), но в еще одном случае этот совет неоценим.
Искренне благодрю вас и gosn1ck за оказанную помощь. Спасибо.

zim22

Дата 26.5.2009, 18:12 (ссылка)

(нет голосов)

Загрузка ...

depict1

Профиль
Группа: Завсегдатай
Сообщений: 2682
Регистрация: 15.1.2009
Где: Украина

Репутация: 29
Всего: 69

Цитата(Thundaga @ 26.5.2009, 17:42

)

отя с этой программой справился иным путем (созданием уникального закрывающего элемента),

если вам не жалко - выкладывайте пожалуйста вариант решения проблемы. другим людям это может пригодиться.

--------------------

C++ FAQ Lite

Thundaga

Дата 26.5.2009, 19:56 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 11
Регистрация: 25.5.2009

Репутация: 1
Всего: 1

zim22
Код пока не оптимизирован, однако вот нынешний вариант:

Код


//Дана последовательность целых чисел. Сформировать линейный список. Преобразовать список удалив из него повторяющиеся ровно два раза числа.
#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;
struct node {int inf; node* ref;};
node * genesis(int); // Функция создания (Генезис - книга бытия)
void kill (node *); // Уничтожение частей списка
bool twice (node *, node *); // счетчик. 1 если 2 одинаковых элемента. 0 в иных случаях
int only (node *, int); // для создания уникального заглавного элемента (конец списка)
void main()
{
    node *beg,*work,*helper;
    int N,m;
    bool del;
    beg = new node;
    cout<<"Input the number of nodes";
    cin>>N;
    beg=genesis(N); // задаем список из N элементов
    helper=new node;
    helper->inf=N; // (1)
    helper->ref=beg; // (2)
    beg=helper; // (1), (2) и данная строки - задание головного (начального) элемента списка
    m=only(beg,N);
    for(work=beg->ref;work->ref;work=work->ref);
    work->ref=new node; //(1)
    work->ref->inf=m; // (2)
    work->ref->ref=NULL; // (3) -  создание заглавного элемента в конце списка.
    work=beg->ref;
    while(work->ref) // цикл проверки элементов
    {
        del=true;
        if(twice(work,beg)) // если два одинаковых то начаинаем прокрутку в поисках еще одного, окромя p элемента
        {
            for(helper=work->ref;helper&&del;helper=helper->ref)
                if(work->inf==helper->inf)
                {
                    kill(helper); // удаление второго из двух элементов
                    del = false; // как только нашли - выходим
                    
                }
                kill(work); // удаление первого из двух элементов
                // так как происходит сдвиг (из-за ф-ции kill), то сдвигать больше не надо
        }
        else
            work=work->ref; // если элементов не 2 - сдвиг
    }
    
    cout<<"After killing pairs will remain these elements: "<<'\n';
    if(beg->ref->inf==m)
        cout<<"All elements killed!"<<'\n';
        else
        for(work=beg->ref;work->ref;work=work->ref)
            cout<<work->inf<<" ";
        
}
node * genesis(int n)
{
    node *p,*c;
    int i=0;
    c=new node;
    cin>>c->inf;
    p=c;
    int x;
    while(i<n-1)
    {
        cin>>x;
        p->ref=new node;
        p=p->ref;
        p->inf=x;
        i++;
    }
    p->ref=NULL;
    return c;
    
}

void kill (node *c)
{
    if(c->ref==NULL)
    { delete c;
    c=NULL;
    }
    else
    {
        node *q;
        q=c->ref;
        *c=*q;
        delete q;
    }
    
}

bool twice (node *c,node *b) // счетчик элементов
{
    bool twicer=false;
    int i,x;
    node *k;
    b=b->ref;
    k=new node;
    i=0;
    x=c->inf;
    for(k=b;k;k=k->ref)
        if(k->inf==x)
            i++;
        if(i==2)
            twicer=true;
        return twicer;
}

int only (node *c, int t)
{
    int k,i;
    node *p;
    k=c->inf;
    for(i=0;i<t;i++)
    {
        for(p=c;p;p=p->ref)
            if(k==p->inf)
                k++;
    }
    return k;
}

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Для новичков \| Следующая тема »