Связанные списки

[Shoosh]

Собственно, вот. Программа выводит список целых чисел, ввод прекращается при вводе числа 0. Функция del() не работает - не знаю, почему..( Нужно вставить еще 2 функции. Первая удаляет первый отрицательный элемент в списке, если он есть. Вторая удаляет все отрицательные элементы. Заранее, спасибо.. Не могу разобраться в указателях в этих функциях.

#include <cstdio>
#include <cstdlib>
#include <iostream>
#define NULLPTR 0

using namespace std;

class List
{
public:
int nElement;


List* pNext;
};


List* pHead = NULLPTR;


void add(List* pEl)
{

pEl->pNext = pHead;


pHead = pEl;
}


//int del()
//{ List* pEl = pHead -> pNext;
//while (pEl!=NULLPTR)
//{delete pHead;
//pHead=pEl;
//pEl=pHead -> pNext;
//}
//return 0;
//}

List* getData()
{

int element;
cout << "Enter element:";
cin >> element;


if (element == 0)
{

return NULLPTR;
}


List* pEl = new List;
pEl->nElement = element;
pEl->pNext = NULLPTR;


return pEl;
}

int main(int nNumberofArgs, char* pszArgs[])
{
cout << "Read elements\n"
<< "Enter '0' to exit"
<< endl;


List* pEl;
while (pEl = getData())
{

add(pEl);
}


cout << "\nList is:" << endl;
for(List *pIter = pHead;
pIter; pIter = pIter->pNext)
{

cout << pIter->nElement << endl;

}
//del();
system("PAUSE");
return 0;
}

[Farrel]

List* delel(List *d,List *head)
{
	List *previous;
	previous=head;
	while(previous!=d && previous->pNext!=d && previous!=NULL)
		previous=previous->pNext;
	previous->pNext=d->pNext;
	if(d==head)
		head=d->pNext;
	delete d;
	return head;
}
void negative(List **head, int mode)
{
	List* p;
	p=*head;
	while(p!=NULL)
	{
		if(p->nElement<0)
		{
			p=*head=delel(p,*head);
			if(mode==1) return;
		}
		p=p->pNext;
	}
}

delel понятное дело удаляет элемент
negative при mode=1 удаляет только 1-е отрицательное число, mode=другое число, удаляет все отрицательные числа

[sergey.d]

Держи, надеюсь пригодится. Удаление всех отрицательных чисел я сделал. Удаление первого отрицательного числа -- самостоятельно

#include <iostream>
#include <assert.h>

namespace sample
{
    template<typename T> 
    class List // двусвязный ациклический список данных типа T
    {
    public:
        class Item // элемент списка
        {
        public:
            const T &value() const { return _value; }
            const Item *prev() const { return _prev; }
            const Item *next() const { return _next; }

        private: // приватные конструктор/деструктор гарантируют, что создавать/удалять эл-ты сможет только дружественный List
            Item(const T &value, Item *prev =0, Item *next =0) 
                : _value(value), // значение создаваемого эл-та 
                _prev(prev), // указатель на предыдущий эл-т   
                _next(next) // указатель на следующий эл-т
            {
                // восстанавливаем связность списка:
                if(_prev) _prev->_next = this; // создаваемый эл-т является следующим для предыдущего...
                if(_next) _next->_prev = this; // ... и предыдущим для следующего
            }

            ~Item() // удаление эл-та
            {
                // восстанавливаем связность списка:
                if(_prev) _prev->_next = _next; // следующим для предыдущего становится следующий за удаляемым
                if(_next) _next->_prev = _prev; // предыдущим для следующего становится предыдущий для удаляемого
            }

            T _value;           // значение элемента
            Item *_prev;        // указатель на предыдущий 
            Item *_next;        // указатель на следующий

            friend class List; // List -- дружественный
        };

    public:
        List() :_head(0), _tail(0) { } // пустой список

        ~List() { clear(); } // деструктор очищает список

        void clear() { while(!empty()) remove(_head); } // очистка списка -- удаляем головной элемент пока список не пуст

        bool empty() const { return !_head; } // проверка на отсутствие элементов

        const Item *remove(const Item *item) // удаление эл-та, возвращает указатель на следующий за удаленным эл-т
        {
            assert(item); // отладочная проверка на ненулевой указатель

            // Локальный вспомогательный класс -- удаляет эл-т в деструкторе
            class Killer { const Item *_item; public: Killer(const Item *i): _item(i) { } ~Killer() { delete _item; } };
            Killer killer(item); // деструктор будет вызван при завершении функции

            if(_head == item) _head = item->_next; // если удаляется первый или последний эл-т списка,
            if(_tail == item) _tail = item->_prev; // нужно скорректировать _head и/или _tail
            return item->_next; // возвращаем указатель на слкдующий за удаляемым эл-т
        }

        // добавление элемента в хвост списка, возвращает указатель на созданный эл-т
        const Item *add_tail(const T &val) { return empty() ? _head = _tail = new Item(val) : _tail = new Item(val, _tail, 0); }

        // добавление элемента в голову списка, возвращает указатель на созданный эл-т
        const Item *add_head(const T &val) { return empty() ? _head = _tail = new Item(val) : _head = new Item(val, 0, _head); }

        const Item *head() const { return _head; }

        const Item *tail() const { return _tail; }

    private:
        Item *_head; // указатель на первый эл-т списка
        Item *_tail; // указатель на последний эл-т списка
    };
}

using namespace sample;

template<typename T> 
void removeNegatives(List<T> &list) // удаление отрицательных элементов списка
{
    for(const typename List<T>::Item *i = list.head(); i; )
    {
        if(i->value() < 0) i = list.remove(i);
        else i = i->next();
    }
}

template<typename T>
void printList(const List<T> &list) // печать списка
{
    for(const typename List<T>::Item *i = list.head(); i; i = i->next()) std::cout << i->value() << " ";
}

int main (void)
{
    List<int> l;
    std::cout << "Enter list of numbers, 0 terminates input:" << std::endl;
    while(true)
    {
        int n;
        std::cout << "? ";
        std::cin >> n;
        if(n) l.add_tail(n); else break;
    }

    std::cout << "List: "; printList(l); std::cout << std::endl;
    removeNegatives(l);
    std::cout << "List without negatives: "; printList(l); std::cout << std::endl;
}

[Shoosh]

такой вопрос. а то не у кого спросить: что значит && ?

[Shoosh]

ооо! спасибо)) полночи буду код разбирать..)

[Farrel]

Сообщение от Shoosh

такой вопрос. а то не у кого спросить: что значит && ?

&& значит логическое и

[Shoosh]

а чем отличается namespace std oт namaspace sample?

Item(const T &value, Item *prev =0, Item *next =0)
                : _value(value),
                _prev(prev),
                _next(next)
            {
                if(_prev) _prev->_next = this;
                if(_next) _next->_prev = this;
            }

// не понимаю запись

[QUOTE=Farrel;625548][CODE]List* delel(List *d,List *head)
{
List *previous;
previous=head;
while(previous!=d && previous->pNext!=d && previous!=NULL)
previous=previous->pNext;
previous->pNext=d->pNext;
if(d==head)
head=d->pNext;
delete d;
return head;
}


не указано же условие, что d<0

[sergey.d]

Сообщение от Shoosh

Item(const T &value, Item *prev =0, Item *next =0)
: _value(value),
_prev(prev),
_next(next)
{
if(_prev) _prev->_next = this;
if(_next) _next->_prev = this;
}
// не понимаю запись

Это конструктор для элемента списка. Он получает значение элемента и указатели на предыдущий и следующий элементы. Если эти указатели не нулевые, он корректирует соответствующие указатели у этих элементов, чтобы восстановить связность списка. Говоря по русски, это значит, что создааемые элемент будет следующим для предыдущего по отношению к нему и предыдущим для следующего за ним.

[sergey.d]

Сообщение от Shoosh

а чем отличается namespace std oт namaspace sample?

Большинство классов стандартной библиотеки объявлены в пространстве имен std. Чтобы избежать возможного конфликта имени класса List с чем-нибудь стандартным (или с другой реализацией), я ввел пространство имен для конкретного примера -- sample. Привычка

[Shoosh]

sergey.d, программа - просто гениальна!) слишкам сложная, правда, для меня)) но спасибо огромное.. мне очень интересно изучаю язык, правда, всего месяц