Модераторы: Daevaorn

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> удаление определенного элемента из списка 
:(
    Опции темы
SergXP
Дата 23.11.2008, 23:59 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


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

Репутация: нет
Всего: нет
Всем Доброе Время Суток.

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

Имеется структура:
Код

template <class M, class N, class O, class P, class Q, class R>
struct Element
    {
        M  key;
        N family;
        O model;
        P  num_dvig;
        Q color;
        R city;
        Element *next;        // указатель на следующий элемент списка
    };

    Element *pHead;           // указатель на первый элемент списка
    Element *pPrev;           //  указатель на последний элемент списка
    int countElem;            //  количество элементов.


Нужно удалить определенный элемент списка.

Так я добавляю в начало списка:
Код

void add_front(M key,N family,O model,P num_dvig, Q color, R city)
    {
        Element *temp = new Element;
        temp->next = pHead;
        pHead = temp;
        if(pPrev == NULL)
           pPrev = pHead;
        temp->key = key;
        temp->family = family;
        temp->model = model;
        temp->num_dvig = num_dvig;
        temp->color = color;
        temp->city = city;
        ++countElem;
    }

А как удалить, что-то не найду никак.  smile 
С Уважение! Спасибо!
--------------------
База IMEI-номеров украденных и утерянных мобильных телефоновhttp://imeis.net.ru/
PM MAIL WWW ICQ   Вверх
REZiaMIX
Дата 24.11.2008, 00:06 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


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

Репутация: нет
Всего: 4
Чтобы удалить из такого списка x надо:
узнать элемент следующий после x , т.е. x.next
и установить значение next предыдущего элемента , в значение x.next
ну и сделать delete всему что нужно.


--------------------
user posted image
PM MAIL   Вверх
SergXP
Дата 24.11.2008, 00:14 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


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

Репутация: нет
Всего: нет
REZiaMIX, извените, а можно на примере показать, как это сделать? Что-то я с этими указателями и списками путаюсь.  smile 
--------------------
База IMEI-номеров украденных и утерянных мобильных телефоновhttp://imeis.net.ru/
PM MAIL WWW ICQ   Вверх
REZiaMIX
Дата 24.11.2008, 00:27 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


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

Репутация: нет
Всего: 4
Код

struct Item
{
    int value;
    Item()
    {
        value = 0;
        next = NULL;
        prev = NULL;
    }
    void deletethis()
    {
        prev->next = this->next;
        this->next->prev = prev; 
        delete this;
    }
    Item * next;
    Item * prev;
};
Item * ListBegin;

void printlist(Item * begin)
{
    Item * current = begin;
    while(current != NULL)
    {
        printf("%i\n",current->value);
        current = current->next; 
    }
}

int main()
{
    Item * ptr, *prevptr , *ptr7th;
     for(int i=0;i < 100; i++)
     {
        ptr = new Item();
        if(i==0)
            ListBegin = ptr;
        else
        {
            ptr->prev = prevptr;
            prevptr->next = ptr;
        }
        //test
        if(i==7)
            ptr7th = ptr;
        //test

        ptr->value = i;
        prevptr = ptr;
     }
    printlist(ListBegin);
    ptr7th->deletethis();
    printlist(ListBegin);

Примерно так.

Это сообщение отредактировал(а) REZiaMIX - 24.11.2008, 00:28


--------------------
user posted image
PM MAIL   Вверх
SergXP
Дата 24.11.2008, 00:35 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


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

Репутация: нет
Всего: нет
REZiaMIX,  я так понимаю мне нужен вот этот кусочек из вашего кода?
Код

void deletethis()
    {
        prev->next = this->next;
        this->next->prev = prev; 
        delete this;
    }

--------------------
База IMEI-номеров украденных и утерянных мобильных телефоновhttp://imeis.net.ru/
PM MAIL WWW ICQ   Вверх
REZiaMIX
Дата 24.11.2008, 00:37 (ссылка) | (голосов:1) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


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

Репутация: нет
Всего: 4
Цитата(SergXP @ 24.11.2008,  00:35)
REZiaMIX,  я так понимаю мне нужен вот этот кусочек из вашего кода?
Код

void deletethis()
    {
        prev->next = this->next;
        this->next->prev = prev; 
        delete this;
    }

Да , но в Ваш список надо наверное добавить prev. Ну и подкорректировать все соответственно.


--------------------
user posted image
PM MAIL   Вверх
SergXP
Дата 24.11.2008, 01:36 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


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

Репутация: нет
Всего: нет
 smile  мда, что-то никак не могу сообразить smile 
--------------------
База IMEI-номеров украденных и утерянных мобильных телефоновhttp://imeis.net.ru/
PM MAIL WWW ICQ   Вверх
inside_pointer
Дата 24.11.2008, 04:44 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


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

Репутация: 5
Всего: 12
Код

  
#include <stdio.h>
#include <stdlib.h>

typedef struct nlist {
    struct nlist *next;
    char c;
} Listnode, *Listptr;

Listptr head = NULL;

main()
{
    Listptr addlist(Listptr, int), remlist(Listptr, int), p;
    
    head = addlist(head, 'A');
    addlist(head, 'B');
    addlist(head, 'C');
    for (p = head; p != NULL; p = p->next)
        printf("%2c%c", p->c, (p->next == NULL ? '\n' : '\0'));
    putchar('\n');
    
    head = remlist(head, 'B');
    for (p = head; p != NULL; p = p->next)
        printf("%2c%c", p->c, (p->next == NULL ? '\n' : '\0'));
    return 0;
}

Listptr addlist(Listptr p, int c)
{
    if (p == NULL) {
        if ((p = (Listptr) malloc(sizeof(Listnode))) != NULL) {
            p->next = NULL;
            p->c = c;
        }
    } else
        p->next = addlist(p->next, c);   
    return p;
}

Listptr remlist(Listptr p, int c)
{
    Listptr q, prev;
    
    if (p->c == c) {
        q = p->next;
        free(p);
        return q;
    }
    for (q = p, prev = p; q != NULL && q->c != c; prev = q, q = q->next)
        ;
    if (q != NULL) {
        prev->next = q->next;
        free(q);
    }
    return p;
}


вывод

Код

[guest@localhost tmp]$ ./test
 A B C

 A C
[guest@localhost tmp]$


удалять можно и голову и хвост, в случае когда удаляется что-то не существующее, список оставляется без изменений

update:
заменил функцию addlist, не было проверки при выделении памяти

Это сообщение отредактировал(а) inside_pointer - 26.11.2008, 03:55
PM MAIL   Вверх
REZiaMIX
Дата 24.11.2008, 12:06 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


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

Репутация: нет
Всего: 4
Цитата(inside_pointer @ 24.11.2008,  04:44)
удалять можно и голову и хвост, в случае когда удаляется что-то не существующее, список оставляется без изменений

В этом способе минус - надо обходить весь список чтобы удалить элемент.
а если в списке миллион элементов?!))


--------------------
user posted image
PM MAIL   Вверх
SergXP
  Дата 24.11.2008, 13:45 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


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

Репутация: нет
Всего: нет
Вроде все легко, а сделать все равно не получается. Хотелось бы внедрить в свой код, чтобы удалить. Но происходят то различные ошибки, то ниче не работает. 
--------------------
База IMEI-номеров украденных и утерянных мобильных телефоновhttp://imeis.net.ru/
PM MAIL WWW ICQ   Вверх
REZiaMIX
Дата 24.11.2008, 13:59 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


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

Репутация: нет
Всего: 4
Цитата(SergXP @ 24.11.2008,  13:45)
Вроде все легко, а сделать все равно не получается. Хотелось бы внедрить в свой код, чтобы удалить. Но происходят то различные ошибки, то ниче не работает.

Прикрепи исходник программы , попытаемся сделать)
Мб стоит использовать stl контейнеры?


--------------------
user posted image
PM MAIL   Вверх
SergXP
Дата 24.11.2008, 14:38 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


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

Репутация: нет
Всего: нет
REZiaMIX, огромное спасибо. 
Вот исходник список сделан в виде класса:

Код

//---------------------------------------------------------------------------

#include <stdio.h>
#include <alloc.h>
#include <iostream.h>
#include <math.h>
#include <ctype.h>
#include <string.h>
#include <conio.h>
#include <PROCESS.H>
#include <stdlib.h>
#include <dos.h>

#pragma hdrstop

#include "list.h"
#ifndef CLASS_LIST_H_INCLUDED
#define CLASS_LIST_H_INCLUDED

template <class M, class N, class O, class P, class Q, class R> class List
{
   typedef struct Element
    {
        M  key;
        N family;
        O model;
        P  num_dvig;
        Q color;
        R city;
        Element *next;      
    };


    Element *pHead;           
    Element *pPrev;         
    int countElem;            

  public :

    List()
    {
        pHead = NULL;
        pPrev = NULL;
        countElem = 0;
    }

    ~List()
    {
        delAllList();
    }


    void add_front(M key,N family,O model,P num_dvig, Q color, R city)
    {
        Element *temp = new Element;
        temp->next = pHead;
        pHead = temp;
        if(pPrev == NULL)
           pPrev = pHead;
        temp->key = key;
        temp->family = family;
        temp->model = model;
        temp->num_dvig = num_dvig;
        temp->color = color;
        temp->city = city;
        ++countElem;
    }

    void add_back(M key,N family,O model,P num_dvig, Q color, R city)
    {
        Element *temp = new Element;

        if(pHead == NULL)
            pHead = temp;
        else
            pPrev->next = temp;

        temp->key = key;
        temp->family = family;
        temp->model = model;
        temp->num_dvig = num_dvig;
        temp->color = color;
        temp->city = city;
        temp->next = NULL;
        pPrev = temp;
        countElem++;
    }

    void print()
    {
        int i;
        Element *pTemp = pHead;
        textcolor(2);
        gotoxy(1,1);  cprintf("N");
        gotoxy(4,1);  cprintf("Family");
        gotoxy(19,1); cprintf("Model");
        gotoxy(34,1); cprintf("Motor");
        gotoxy(49,1); cprintf("Color");
        gotoxy(64,1); cprintf("Adres");
        gotoxy(1,2);  cprintf("--------------------------------------------------------------------------");

        textcolor(7);
        i = 1;

        while(pTemp != NULL)
        {
            gotoxy(1,i+2);  printf("%i",pTemp->key);
            gotoxy(4,i+2);  printf("%s",pTemp->family);
            gotoxy(19,i+2); printf("%s",pTemp->model);
            gotoxy(34,i+2); printf("%i",pTemp->num_dvig);
            gotoxy(49,i+2); printf("%s",pTemp->color);
            gotoxy(64,i+2); printf("%s",pTemp->city);

            cout<< endl;
            pTemp = pTemp->next;
            i++;
        }
    }

    void delAllList()
    {
        while(pHead != NULL)
        {
            Element *pTemp = pHead;
            pHead = pHead->next;
            delete pTemp;
        }
    }

    bool IsEmpty()
    {
        if(countElem == 0)
            return true;
        else
            return false;
    }

};

#endif // CLASS_LIST_H_INCLUDED

//---------------------------------------------------------------------------

#pragma package(smart_init)


Соответственно, чтобы довать в список:
Вызываем:
list.add_back(все параметры); // для добавления в конец списка
list.add_front(все параметры); // для добавления в начало списка

И при возможности, тоже вопрос. как добавить в список элемент в определенное место списка?

Очень нужна ваша, помощь. Не гуру я в этом C++.  Ну и не совсем чайник.  smile 

Это сообщение отредактировал(а) SergXP - 24.11.2008, 14:38
--------------------
База IMEI-номеров украденных и утерянных мобильных телефоновhttp://imeis.net.ru/
PM MAIL WWW ICQ   Вверх
REZiaMIX
Дата 24.11.2008, 14:59 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


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

Репутация: нет
Всего: 4
Без добавления дополнительных полей(этот 100% работает):
Код

bool deleteitem(unsigned int indx)
    {
        Element  * ptr = pHead;
        Element  * prev = NULL;
        unsigned int current_pos = 0;
        while(ptr != NULL)
        {
            if(current_pos == indx)
            {
                prev->next = ptr->next; 
                --countElem;
                return true;
            }

            prev = ptr;
            ptr = ptr->next;
            current_pos ++;
        }
        return false;
        
    }


Добавлено @ 15:08
Добавить :
Код

bool insert_after(Element * after,M key,N family,O model,P num_dvig, Q color, R city)
    {
        if(after == NULL)
            return;
        Element *temp = new Element;
        temp->next = after->next;
        after->next = temp;
        temp->key = key;
        temp->family = family;
        temp->model = model;
        temp->num_dvig = num_dvig;
        temp->color = color;
        temp->city = city;
        ++countElem;
        
    }

Этот ^ код не проверял.

Это сообщение отредактировал(а) REZiaMIX - 24.11.2008, 15:08


--------------------
user posted image
PM MAIL   Вверх
inside_pointer
Дата 25.11.2008, 06:09 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


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

Репутация: 5
Всего: 12
а, так бы и сказал (прочитал первое сообщение)

Код

void rem_front(void)
{
    Element *pTemp;
    
    pTemp = pHead;
    pHead = pHead->next;
    delete pTemp;
    countElem--;
}

void rem_back(void)
{
    Element *pTemp;
    
    if (pPrev != NULL) {
        for (pTemp = pHead; pTemp->next != pPrev; pTemp = pTemp->next)
            ;
        pTemp->next = NULL;
        delete pPrev;
        pPrev = pTemp;
        countElem--;
    }    
}


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

Добавлено через 9 минут и 57 секунд
Код

bool deleteitem(unsigned int indx)
    {
        Element  * ptr = pHead;
        Element  * prev = NULL;
        unsigned int current_pos = 0;
        while(ptr != NULL)
        {
            if(current_pos == indx)
            {
                prev->next = ptr->next; 
                --countElem;
                return true;
            }
            prev = ptr;
            ptr = ptr->next;
            current_pos ++;
        }
        return false;
        
    }


REZiaMIX, а что там ошибок нет, в строчке prev->next = ptr->next; ?
PM MAIL   Вверх
REZiaMIX
Дата 25.11.2008, 12:47 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


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

Репутация: нет
Всего: 4
Цитата

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

Сделать двусвязным) как в 1 примере
Цитата

REZiaMIX, а что там ошибок нет, в строчке prev->next = ptr->next; ?

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

user posted image
---------------------------------------------------------------------------
user posted image

Для односвязного списка все также , только без prev.

Это сообщение отредактировал(а) REZiaMIX - 25.11.2008, 13:00


--------------------
user posted image
PM MAIL   Вверх
Ответ в темуСоздание новой темы Создание опроса
Правила форума "С++:Общие вопросы"
Earnest Daevaorn

Добро пожаловать!

  • Черновик стандарта C++ (за октябрь 2005) можно скачать с этого сайта. Прямая ссылка на файл черновика(4.4мб).
  • Черновик стандарта C (за сентябрь 2005) можно скачать с этого сайта. Прямая ссылка на файл черновика (3.4мб).
  • Прежде чем задать вопрос, прочтите это и/или это!
  • Здесь хранится весь мировой запас ссылок на документы, связанные с C++ :)
  • Не брезгуйте пользоваться тегами [code=cpp][/code].
  • Пожалуйста, не просите написать за вас программы в этом разделе - для этого существует "Центр Помощи".
  • C++ FAQ

Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, Earnest Daevaorn
 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | C/C++: Общие вопросы | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.0709 ]   [ Использовано запросов: 22 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.