/*
вопрос № 178253
Написать программу, реализующую двухсвязный список, который хранит
элементы произвольного типа (Программа заранее не знает, данные какого
типа будут хранится в элементах списка). Реализовать полный набор
операций (создание списка, вставка эл-та, удаление эл-та).
Вариант с избыточным использованием шаблонов.
*/
#include <stdlib.h>
#include <stdio.h>
template <class T> struct t_DoubleListItem
{
t_DoubleListItem<T>( T val ) { data = val; }
t_DoubleListItem<T>* next;
t_DoubleListItem<T>* prev;
T data;
};
template <class T> class t_DoubleList
{
public:
t_DoubleList();
virtual ~t_DoubleList();
virtual void freeItem( t_DoubleListItem<T>* pItem );
void clear();
void add( t_DoubleListItem<T>* pItem );
bool insertAfter( const t_DoubleListItem<T>* pAfter, t_DoubleListItem<T>* pItem );
bool removeItem( t_DoubleListItem<T>* pItem );
bool deleteItem( t_DoubleListItem<T>* pItem );
void forEach( void (*func)( t_DoubleListItem<T>* ) );
protected:
t_DoubleListItem<T>* m_pHead; // указатель на первый добавленный элемент
t_DoubleListItem<T>* m_pTail; // указатель на последний добавленный элемент
};
// создание пустого списка
template <class T>
inline t_DoubleList<T>::t_DoubleList() : m_pHead(0), m_pTail(0)
{
}
// уничтожение списка
template <class T>
t_DoubleList<T>::~t_DoubleList()
{
clear();
}
//--------------------------------------------------------------
// Функция очищает список. Все элементы также уничтожаются.
//--------------------------------------------------------------
template <class T>
void t_DoubleList<T>::clear()
{
t_DoubleListItem<T>* p = m_pHead;
while( p ) {
t_DoubleListItem<T>* pNext = p->next;
freeItem( p ); // удаляем элемент
p = pNext; // переходим к следующему
}
m_pHead = 0; m_pTail = 0;
}
//--------------------------------------------------------------
// Виртуальная функция - удаление элемента в предположении, что
// память для него выделена посредством new. Если это не так, то
// функция должна быть перекрыта в производном классе.
//--------------------------------------------------------------
template <class T>
void t_DoubleList<T>::freeItem( t_DoubleListItem<T>* pItem )
{
delete pItem;
}
//--------------------------------------------------------------
// Функция вставляет новый элемент в конец списка
//--------------------------------------------------------------
template <class T>
void t_DoubleList<T>::add( t_DoubleListItem<T>* pItem )
{
pItem->prev = m_pTail; // предыдущий элемент - прежний конец списка
pItem->next = NULL; // следующего элемента пока нет
if( !m_pHead ) // если первый элемент в списке,
m_pHead = pItem; // ... то инициализируем указатель на начало
else // иначе добавляем в конец
m_pTail->next = pItem;
m_pTail = pItem; // новый конец списка
}
//--------------------------------------------------------------
// Вставляем новый элемент после элемента pInsertAfter.
// Если pInsertAfter == NULL, то вставляем в начало списка.
// Функция возвращает true, если элемент вставлен в список,
// false - если элемент pInsertAfter не найден.
//--------------------------------------------------------------
template <class T>
bool t_DoubleList<T>::insertAfter( const t_DoubleListItem<T>* pInsertAfter, t_DoubleListItem<T>* pItem )
{
t_DoubleListItem<T>* p = m_pHead;
if( !pInsertAfter ) { // вставляем в начало списка
pItem->next = p; // следующий элемент - прежнее начало списка
pItem->prev = NULL; // предыдущего элемента нет - это новое начало списка
if( !p ) // если первый элемент в списке,
m_pHead = pItem; // ... то инициализируем указатель на начало
else
p->prev = pItem;
m_pHead = pItem; // новое начало списка
return true;
}
while( p ) {
// ищем элемент, после которого нужно вставлять
if( p == pInsertAfter ) {
t_DoubleListItem<T>* pNext = p->next;
if( pNext )
pNext->prev = pItem;
else // pInsertAfter == m_pTail, причем здесь m_pTail != 0
m_pTail = pItem; // новый конец списка
pItem->prev = p;
pItem->next = pNext;
p->next = pItem;
return true;
}
p = p->next; // переходим к следующему
}
return false;
}
//--------------------------------------------------------------
// Удаляем элемент pItem из списка, сам элемент не меняется.
// Функция возвращает true, если элемент удален из списка,
// false - если элемент pItem не найден.
//--------------------------------------------------------------
template <class T>
bool t_DoubleList<T>::removeItem( t_DoubleListItem<T>* pItem )
{
t_DoubleListItem<T>* p = m_pHead;
while( p ) {
// ищем удаляемый элемент
if( p == pItem ) {
if( p->prev )
p->prev->next = p->next;
else // удаляется начало списка
m_pHead = p->next;
if( p->next )
p->next->prev = p->prev;
else // удаляется конец списка
m_pTail = p->prev;
return true;
}
p = p->next; // переходим к следующему
}
return false;
}
//--------------------------------------------------------------
// Удаляем элемент pItem из списка, затем уничтожаем сам элемент.
// Функция возвращает true, если элемент удален из списка,
// false - если элемент pItem не найден, в этом случае элемент
// не меняется.
//--------------------------------------------------------------
template <class T>
bool t_DoubleList<T>::deleteItem( t_DoubleListItem<T>* pItem )
{
if( removeItem(pItem) ) {
freeItem( pItem );
return true;
}
return false;
}
//--------------------------------------------------------------
// Выполняет функцию func для каждого элемента списка
//--------------------------------------------------------------
template <class T>
void t_DoubleList<T>::forEach( void (*func)( t_DoubleListItem<T>* ) )
{
if( !func ) return;
t_DoubleListItem<T>* p = m_pHead;
while( p ) {
func( p );
p = p->next;
}
}
//==============================================================
// Проверка некоторых функций списка
//==============================================================
void printValue( t_DoubleListItem<int>* p )
{
printf( "%4d\n", p->data );
}
void main()
{
// при использовании класса указываем нужный нам тип
t_DoubleList<int>* pListInt = new t_DoubleList<int>();
t_DoubleListItem<int>* a[10];
for( int i = 0; i < 10; ++i ) {
t_DoubleListItem<int>* p = new t_DoubleListItem<int>( i );
a[i] = p;
pListInt->add( p );
}
pListInt->insertAfter( 0, new t_DoubleListItem<int>(-1)); // вставка в начало
pListInt->insertAfter( a[5], new t_DoubleListItem<int>(-5)); // вставка в середину
pListInt->insertAfter( a[9], new t_DoubleListItem<int>(50)); // добавление в конец
pListInt->add( new t_DoubleListItem<int>(100) ); // добавление в конец
pListInt->deleteItem( a[7] ); // удаление элемента
pListInt->forEach( printValue ); // распечатываем список
delete pListInt;
}
/*
вопрос № 178253
Написать программу, реализующую двухсвязный список, который хранит
элементы произвольного типа (Программа заранее не знает, данные какого
типа будут хранится в элементах списка). Реализовать полный набор
операций (создание списка, вставка эл-та, удаление эл-та).
Вариант с использованием шаблонов.
*/
#include <stdlib.h>
#include <stdio.h>
// Эта структура напрямую используется только в классе t_DoubleList
// Пользовательские типы данных следует объявлять с использованием шаблона
struct __t_DoubleListItem
{
__t_DoubleListItem* next;
__t_DoubleListItem* prev;
};
// шаблон для объявления пользовательских типов данных
template <class T> struct t_DoubleListItem : __t_DoubleListItem
{
t_DoubleListItem<T>( T val ) { data = val; }
T data;
};
class t_DoubleList
{
public:
t_DoubleList();
virtual ~t_DoubleList();
virtual void freeItem( __t_DoubleListItem* pItem );
void clear();
void add( __t_DoubleListItem* pItem );
bool insertAfter( const __t_DoubleListItem* pAfter, __t_DoubleListItem* pItem );
bool removeItem( __t_DoubleListItem* pItem );
bool deleteItem( __t_DoubleListItem* pItem );
void forEach( void (*func)( __t_DoubleListItem* ) );
protected:
__t_DoubleListItem* m_pHead; // указатель на первый добавленный элемент
__t_DoubleListItem* m_pTail; // указатель на последний добавленный элемент
};
// создание пустого списка
inline t_DoubleList::t_DoubleList() : m_pHead(0), m_pTail(0)
{
}
// уничтожение списка
t_DoubleList::~t_DoubleList()
{
clear();
}
//--------------------------------------------------------------
// Функция очищает список. Все элементы также уничтожаются.
//--------------------------------------------------------------
void t_DoubleList::clear()
{
__t_DoubleListItem* p = m_pHead;
while( p ) {
__t_DoubleListItem* pNext = p->next;
freeItem( p ); // удаляем элемент
p = pNext; // переходим к следующему
}
m_pHead = 0; m_pTail = 0;
}
//--------------------------------------------------------------
// Виртуальная функция - удаление элемента в предположении, что
// память для него выделена посредством new. Если это не так, то
// функция должна быть перекрыта в производном классе.
//--------------------------------------------------------------
void t_DoubleList::freeItem( __t_DoubleListItem* pItem )
{
delete pItem;
}
//--------------------------------------------------------------
// Функция вставляет новый элемент в конец списка
//--------------------------------------------------------------
void t_DoubleList::add( __t_DoubleListItem* pItem )
{
pItem->prev = m_pTail; // предыдущий элемент - прежний конец списка
pItem->next = NULL; // следующего элемента пока нет
if( !m_pHead ) // если первый элемент в списке,
m_pHead = pItem; // ... то инициализируем указатель на начало
else // иначе добавляем в конец
m_pTail->next = pItem;
m_pTail = pItem; // новый конец списка
}
//--------------------------------------------------------------
// Вставляем новый элемент после элемента pInsertAfter.
// Если pInsertAfter == NULL, то вставляем в начало списка.
// Функция возвращает true, если элемент вставлен в список,
// false - если элемент pInsertAfter не найден.
//--------------------------------------------------------------
bool t_DoubleList::insertAfter( const __t_DoubleListItem* pInsertAfter, __t_DoubleListItem* pItem )
{
__t_DoubleListItem* p = m_pHead;
if( !pInsertAfter ) { // вставляем в начало списка
pItem->next = p; // следующий элемент - прежнее начало списка
pItem->prev = NULL; // предыдущего элемента нет - это новое начало списка
if( !p ) // если первый элемент в списке,
m_pHead = pItem; // ... то инициализируем указатель на начало
else
p->prev = pItem;
m_pHead = pItem; // новое начало списка
return true;
}
while( p ) {
// ищем элемент, после которого нужно вставлять
if( p == pInsertAfter ) {
__t_DoubleListItem* pNext = p->next;
if( pNext )
pNext->prev = pItem;
else // pInsertAfter == m_pTail, причем здесь m_pTail != 0
m_pTail = pItem; // новый конец списка
pItem->prev = p;
pItem->next = pNext;
p->next = pItem;
return true;
}
p = p->next; // переходим к следующему
}
return false;
}
//--------------------------------------------------------------
// Удаляем элемент pItem из списка, сам элемент не меняется.
// Функция возвращает true, если элемент удален из списка,
// false - если элемент pItem не найден.
//--------------------------------------------------------------
bool t_DoubleList::removeItem( __t_DoubleListItem* pItem )
{
__t_DoubleListItem* p = m_pHead;
while( p ) {
// ищем удаляемый элемент
if( p == pItem ) {
if( p->prev )
p->prev->next = p->next;
else // удаляется начало списка
m_pHead = p->next;
if( p->next )
p->next->prev = p->prev;
else // удаляется конец списка
m_pTail = p->prev;
return true;
}
p = p->next; // переходим к следующему
}
return false;
}
//--------------------------------------------------------------
// Удаляем элемент pItem из списка, затем уничтожаем сам элемент.
// Функция возвращает true, если элемент удален из списка,
// false - если элемент pItem не найден, в этом случае элемент
// не меняется.
//--------------------------------------------------------------
bool t_DoubleList::deleteItem( __t_DoubleListItem* pItem )
{
if( removeItem(pItem) ) {
freeItem( pItem );
return true;
}
return false;
}
//--------------------------------------------------------------
// Выполняет функцию func для каждого элемента списка
//--------------------------------------------------------------
void t_DoubleList::forEach( void (*func)( __t_DoubleListItem* ) )
{
if( !func ) return;
__t_DoubleListItem* p = m_pHead;
while( p ) {
func( p );
p = p->next;
}
}
//==============================================================
// Проверка некоторых функций списка
//==============================================================
void printValue( __t_DoubleListItem* p )
{
printf( "%4d\n", ((t_DoubleListItem<int>*)p)->data );
}
void main()
{
t_DoubleList* pListInt = new t_DoubleList();
// при использовании класса указываем нужный нам тип элементов
t_DoubleListItem<int>* a[10];
for( int i = 0; i < 10; ++i ) {
t_DoubleListItem<int>* p = new t_DoubleListItem<int>( i );
a[i] = p;
pListInt->add( p );
}
pListInt->insertAfter( 0, new t_DoubleListItem<int>(-1)); // вставка в начало
pListInt->insertAfter( a[5], new t_DoubleListItem<int>(-5)); // вставка в середину
pListInt->insertAfter( a[9], new t_DoubleListItem<int>(50)); // добавление в конец
pListInt->add( new t_DoubleListItem<int>(100) ); // добавление в конец
pListInt->deleteItem( a[7] ); // удаление элемента
pListInt->forEach( printValue ); // распечатываем список
delete pListInt;
}
Если Вы уже зарегистрированы на Портале - войдите в систему, если Вы еще не регистрировались - пройдите простую процедуру регистрации.