VPF::[C++] Реализация однонаправленного списка

tishaishii

Дата 15.2.2007, 21:10 (ссылка)

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

Загрузка ...

Создатель

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

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

Помогите, пожалуйста, надо решить задачу.

Присоединённый файл ( Кол-во скачиваний: 18 )

_______.zip 5,34 Kb

Kuvaldis

Дата 16.2.2007, 16:07 (ссылка)

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

Загрузка ...

механик-вредитель

Профиль
Группа: Участник Клуба
Сообщений: 1189
Регистрация: 16.6.2006
Где: Минск

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

Модератор: Название темы должно отражать ее суть!

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

Помни - когда ты спишь, враг не дремлет
Спи чаще и дольше, изматывай врага бессоницей

Xenon

Дата 17.2.2007, 00:14 (ссылка)

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

Загрузка ...

Эксперт

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

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

А как сделать operator- ?.. То есть пишешь list1=list1-10 и он удаляет элемент 10? Или как? Или вообще нужно использовать конструкцию типа list<T>=list<T>-element<T> ? Я вообще не понял что прибавляется/вычитается - T или element<T> ? Ну сделал пока с T и только operator+:

Код


#include <iostream>

using std::cout;
using std::cin;

template <class TYPE>
struct element
{
    TYPE data;
    element* next;
};

template <class TYPE>
class key_list
{
public:
    void display_all() const; //Показать все элементы списка
    void add(TYPE data); //Добавить новый элемент
    void remove(int index); //Удалить необходимый элемент
    void insert(int index, TYPE data); //Вставка элемента после элемента по заданному индексу
    void sort(); //Сортировка по ключу
    element<TYPE>* cursor (int pos)const; //Итератор
    //Перегрузка операторов
    key_list<TYPE>& operator+(TYPE Data);
    key_list<TYPE>& operator=(const key_list<TYPE>& list);
    //Конструкторы
    key_list():m_begin(NULL),m_end(NULL),links_count(0){}
    key_list(const key_list<TYPE>& list)
    {
        element<TYPE>* new_element=new element<TYPE>;
        //Копируем первый элемент списка
        new_element->data=(list.cursor(0))->data;
        new_element->next=NULL;
        m_begin=new_element;
        m_end=new_element;
        //Копируем остальные элементы
        for (int i=1;i<list.links_count;++i)
        {
            new_element=new element<TYPE>;
            new_element->data=(list.cursor(i))->data;
            m_end->next=new_element;
            m_end=new_element;
        }
        m_end->next=NULL;
        links_count=list.links_count;
    }
    //Деструктор
    ~key_list()
    {
        cout << "Destructor is up to run ...\n";
        if (links_count>0)
        {
            element<TYPE>* current=m_begin;
            while(current->next!=NULL)
            {
                element<TYPE>* previous=current;
                current=current->next;
                cout << "Deleting element ...\n";
                delete previous;
            }
            cout << "Deleting element ...\n";
            delete m_end;
        }
    }
private:
    element<TYPE>* m_begin;//Первый элемент списка
    element<TYPE>* m_end;//Последний элемент списка
    int links_count; //Количество элементов в списке
};

//////////////////////////////////////
//Показать все элементы
template <class TYPE>
void key_list<TYPE>::display_all() const
{
    if (links_count==0)
    {
        cout << "Nothing to display\n";
        return;
    }
    element<TYPE>* current=m_begin;
    int i=0;
    while(current)
    {
        cout << i++ << ") " << current->data << std::endl;
        current=current->next;
    }
}
//////////////////////////////////////
///Добавление нового элемента
template <class TYPE>
void key_list<TYPE>::add(TYPE data)
{
    element<TYPE>* link=new element<TYPE>;
    link->data=data;
    if (m_begin==NULL)
    {
        m_begin=link;
        m_end=link;
        m_begin->next=link;
    }
    else
    {
        m_end->next=link;
        m_end=link;
    }
    link->next=NULL;
    ++links_count;
}
//////////////////////////////////////
///Удаление элемента
template <class TYPE>
void key_list<TYPE>::remove(int index)
{
    if (index<0 || index>=links_count)
    {
        throw "Incorrect index - item doesn`t exist\n";
    }
    element<TYPE>* current;
    if (index>0 && index<=links_count) //Если элемент по середине списка
    {
        current=cursor(index);//Едем к элементу по заданному индексу
        element<TYPE>* prev=cursor(index-1);//Запоминаем адрес элемента до удаляемого
        element<TYPE>* next=cursor(index+1);//Запоминаем адрес после удаляемого
        prev->next=next; //Ссылаем элемент перед удаляемым с элементом после удаляемого
        delete current; //Удаляем необходимый элемент
    }
    else
    {
        if (index==0) //Если это первый элемент ...
        {
            current=m_begin;
            current=current->next;
            delete m_begin;
            m_begin=current;
        }
        else //Если это последний элемент ...
        {
            current=cursor(index-1);
            current->next=NULL;
            delete m_end;
            m_end=current;
        }
    }
    --links_count;
}
//////////////////////////////////////
///Вставка элемента
template <class TYPE>
void key_list<TYPE>::insert(int index, TYPE data)
{
    if (index<0 || index>=links_count)
    {
        throw ("Incorrect index - item doesn`t exists\n");
    }
    element<TYPE>* new_element=new element<TYPE>;
    new_element->data=data;
    element<TYPE>* current=cursor(index);
    if (index==links_count-1)//Если мы всталяем элемент после последнего в списке ...
    {
        m_end=new_element;
        new_element->next=NULL;
        current->next=new_element;
    }
    else
    {
        element<TYPE>* after_current=current->next;//Запоминаем адрес элемента, стоящего после элемента по заданному индексу
        current->next=new_element;
        new_element->next=after_current;
    }
    ++links_count;
}
//////////////////////////////////////
///Итератор
template <class TYPE>
element<TYPE>* key_list<TYPE>::cursor (int pos)const
{
    if (pos<0 || pos>=links_count)
    {
        throw ("Incorrect index - item doesn`t exists\n");
    }
    element<TYPE>* current=m_begin;
    for (int i=0;i<pos;++i)
    {
        current=current->next;
    }
    return current;
}
//////////////////////////////////////
//Сортировка по ключу
template <class TYPE>
void key_list<TYPE>::sort()
{
    for (int j=1,i=0;j<links_count;++j)
    {
        TYPE last_value=(cursor(j))->data;
        for (i=j-1;i>=0 && (last_value < (cursor(i))->data);--i)
        {
            (cursor(i+1))->data=cursor(i)->data;
        }
        (cursor(i+1))->data=last_value;
    }
}
//////////////////////////////////////
///Operator +
template <class TYPE>
key_list<TYPE>& key_list<TYPE>::operator+(const TYPE Data)
{
    add(Data);
    return *this;
}
//////////////////////////////////////
template <class TYPE>
key_list<TYPE>& key_list<TYPE>::operator=(const key_list<TYPE>& list)
{
    if (this!=&list)//Проверяем на a=a
    {
        if(links_count>0)
        {
            for (int i=0;i<links_count;++i)
            {
                remove(i);
            }
        }
        for (int i=0;i<list.links_count;++i)
        {
            add((list.cursor(i))->data);
        }
        links_count=list.links_count;
    }
    return *this;
}
//////////////////////////////////////

int main(int argc, char* argv[])
{
    try
    {
        //key_list<int> list;
        //list.add(24);
        //list.add(142);
        //list.add(352);
        key_list<int> list1;
        list1.add(2);
        list1=list1+10;
        list1.insert(0,11);
        //list1.add(3);
        //list1=list;
        list1.display_all();
    }
    catch (char* msg)
    {
        cout << msg;
    }
    cin.get();
    return 0;
}

PS. Упс, забыл сортировку - исправил

Это сообщение отредактировал(а) Xenon - 17.2.2007, 01:49

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

tishaishii

Дата 19.2.2007, 04:54 (ссылка)

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

Загрузка ...

Создатель

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

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

Спасибо и на том. Думаю, пока что хватит.

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