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

Thundaga

Дата 25.5.2009, 17:34 (ссылка)

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

Загрузка ...

Новичок

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

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

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

Код ниже (C++ VS 6.0):

Код


#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 *); // Функция, выдающая false если не 2 элемента и true  если 2
void main()
{
    node *beg,*work,*helper;
    int N;
    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) создание заглавного элемента
    work=beg->ref;
    
    while(work->ref) // цикл проверки
    {
        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); // удаление первого
                //если было удаление - продолжаем проверку
        }
        else
            work=work->ref; // если нет - сдвиг
    }
    
    
    cout<<"After some transformations we'll get: "<<'\n';
    for(work=beg->ref;work;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;
}

Использовать Remove нельзя

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

zim22

Дата 25.5.2009, 17:58 (ссылка)

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

Загрузка ...

depict1

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

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

Цитата(Thundaga @ 25.5.2009, 17:34

)

Использовать Remove нельзя

что за Remove?
не хотите std::list использовать?

Это сообщение отредактировал(а) zim22 - 25.5.2009, 17:59

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

C++ FAQ Lite

Thundaga

Дата 25.5.2009, 18:03 (ссылка)

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

Загрузка ...

Новичок

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

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

Remove - функция стандартной библиотеки, убирающая элемент с определенным значением в конец списка и не выводящая его на печать. Здесь же требуется освобождение памяти.
Проблема не в этом, а в том что при тестовых значениях вроде:
4 элемента (1 2 3 2) - программа выдаст сообщение об ошибке при запуске. Дебаггер, увы, не помогает. Хотелось бы выяснить причину ошибки и устранить её.
std::list тоже не рекомендуется использовать, хм.

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

gosn1ck

Дата 25.5.2009, 18:07 (ссылка)

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

Загрузка ...

Шустрый

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

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

код может быть коряв, но я новичок smile

Код


struct TNode {
   string value;     
   TNode* pnext;      
   TNode(string val): pnext(0), value(val) {} 

};

void deleteItem(TNode *phead, string val)
{
  TNode* p = phead, *temp;      
  int i = 0;                   
  while(p) {
      if (p->value == val) break;
      else {
        p = p->pnext; ++i;}
   }

   temp = p->pnext;            

   p = phead;

   int y = 0;                   
   while (y+1 < i){
     p = p->pnext;
     ++y;
   }
   p->pnext = temp;            
                                
   delete temp;
}

int main(){
  TNode *phead = 0;
  string buf;
  deleteItem(phead, buf);
}

останется урбать элементы, которые остануться висеть в памяти smile

Это сообщение отредактировал(а) gosn1ck - 25.5.2009, 18:08

Thundaga

Дата 25.5.2009, 18:14 (ссылка)

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

Загрузка ...

Новичок

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

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

gosn1ck
Здравствуйте, хотелось бы вас попросить пояснить ваш вариант комментариями. Однако, спасибо за столь быстрый ответ. Сейчас постараюсь провести тесты.

gosn1ck

Дата 25.5.2009, 18:32 (ссылка)

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

Загрузка ...

Шустрый

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

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

суть такова, что я перебираю все элементы до того как встречу нужный для удалению if (p->value == val) break;, сохраняю адресс следующего элемента temp = p->pnext; и номер по счету в списке i. перебираю опять весь список до этого элемента while (y+1 < i) (другого метода в голову не пришло (: ) и меняю у него адресс следующего в списке p->pnext = temp;. получается прыжок через элемент, который мы хотим удалить, но он до сих пор висит в памяти.

Thundaga

Дата 25.5.2009, 18:39 (ссылка)

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

Загрузка ...

Новичок

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

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

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

Код


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

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

zim22

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

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

Загрузка ...

depict1

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

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

Цитата(Thundaga @ 25.5.2009, 18:03

)

Здесь же требуется освобождение памяти.

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

Цитата(Thundaga @ 25.5.2009, 18:03

)

std::list тоже не рекомендуется использовать, хм.

рекомендациями можно пренебречь.

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

C++ FAQ Lite

Thundaga

Дата 25.5.2009, 18:57 (ссылка)

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

Загрузка ...

Новичок

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

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

zim22
Можно, однако хотелось бы все оставить максимально близко к текущему варианту. В случае с ремувом будет, конечно немного муторно - придется 2*K раз удалять последний элемент (к - число пар). Однако это самый крайний случай. Пока что хочется узнать, можно исправить ошибку, и как это сделать. Но с вами я согласен - уже давно хочется пренебречь рекомендациями и сделать как хочется, но увы, моветон.

gosn1ck

Дата 25.5.2009, 19:13 (ссылка)

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

Загрузка ...

Шустрый

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

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

Цитата(Thundaga @ 25.5.2009, 18:39)

Код


delete c;
c=NULL;

может я чего не понимаю, но как вообще понять эту последовательность ?

Thundaga

Дата 25.5.2009, 19:29 (ссылка)

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

Загрузка ...

Новичок

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

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

gosn1ck
Если элемент последний - удалить и сделать его окончанием списка.

gosn1ck

Дата 25.5.2009, 19:42 (ссылка)

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

Загрузка ...

Шустрый

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

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

а зачем вообще проверять последний он или нет ? smile

прикрутите конструтор как у меня и при удалении последнего тут q=c->ref; q будет null

Thundaga

Дата 25.5.2009, 19:50 (ссылка)

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

Загрузка ...

Новичок

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

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

gosn1ck
Удаление первых и последних элементов всегда отличается от удаления остальных элементов списка.
Хорошо, сейчас попробую.

zim22

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

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

Загрузка ...

depict1

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

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

Thundaga, уточните задачу.
вам нужно удалить все дубликаты из списка?

Код


std::list<int> li;
li.push_back(10);
li.push_back(20);
li.push_back(10);

std::sort(li.begin(), li.end();
std::list<int>::iterator end_it = std::unique(li.begin(), li.end();
li.erase(end_it, li.end());

или удалять только тогда, когда количество подряд идущих одинаковых элементов >=n ?

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

C++ FAQ Lite

gosn1ck

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

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

Загрузка ...

Шустрый

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

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

последний удаляется также как и все остальные, а первый - заменой адреса "головного" указателя. имхо smile

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