Создать шаблон динамического списка

@AlexHolmes · Регистрация: 14.11.2013

Author24 — интернет-сервис помощи студентам

спроектировать шаблон для класса динамический список
Создать конструкторы: по умолчанию, с параметрами и копирования и продемонстрировать работу с ним.
Деструктор.
функции:
вставка элемента из головы (хвоста) в заданном месте;
вывода списка на экран;
поиск элемента списка;
очистки списка;

Попыталась что-то но совсем не то что нужно.... Читаю лекции и теорию, но в голову не лезет.
Как вообще должен выглядеть шаблон класса динамический список? И как в нем должна реализоваться функция вставки элемента?

C++ (Qt)

#include "stdafx.h"
 
#include <iostream>
#include <conio.h>
#include <string>
 
using namespace std;
 
template <class T>
class TList
{
private:
    class TElement
    {
    public:
        T data_;
        TElement * next_;
        TElement(T Data, TElement * Next) : data_(Data), next_(Next) {};
        TElement * Next(void) const { return next_; }
        void setNext(const TElement * Next) { next_ = Next; }
    TList(void);
    ~TList(void);
    void push_front(T el);
    void del_front(void);
    };

@AlexHolmes · 15.11.2014, 18:14 **[ТС]**

Я попробовала сначала создать класс односвязного динамического списка, а потом переделать его в шаблон (so dumb)

Но, мне кажется, что это какой-то НЕДОшаблон, а может и вовсе не он. Не совсем понимаю, что нужно сделать с классом Node.

C++ (Qt)

class Node
{
public:
    int elem;
    Node* next;
    Node();
};

Вот весь текст. Очень надеюсь на помощь. Подскажите, пожалуйста, что не так. Программа-то работает, но вот шаблон ли это?!

C++ (Qt)

#include "stdafx.h"
#include <iostream>
#include <conio.h>
#include <string>
 
using namespace std;
 
class Node
{
public:
    int elem;
    Node* next;
    Node();
};
Node::Node()
{
    next=0;elem=0;
}
template <typename T>
class List
{
public:
    Node* head;
    Node* tail;
    List();
    ~List();
    void push_back(int val);
    void push_front(int val);
    void insert(int val);
    void print();
    void erase(int val);
    void erase();
    void find(int val);
    void deleteall();
};
 
template <typename T>
List<T>::List()
{
    head=0;
    tail=0;
}
 
template <typename T>
List<T>::~List()
{
    if(head!=NULL)
        {
            delete head;
    delete tail;
    }
}
 
template <typename T>
void List<T>::push_back(int val)
{
    Node* Temp;
    Temp= new Node;
    Temp->elem=val;
    if(head==0)
    {
        head=Temp;
        tail=Temp;
        return;
    }
    tail->next=Temp;
    tail=Temp;
}
 
template <typename T>
void List<T>::push_front(int val)
{
    Node* Temp;
    Temp=new Node;
    Temp->elem=val;
    Temp->next=head;
    head=Temp;
}
 
template <typename T>
void List<T>::insert(int val)
{
    if(head==0)
    {
        push_front(val);
        return;
    }
    Node* Temp;
    Temp=new Node;
    Temp->elem=val;
    Node* founded=head;
    for(founded; founded!=0;founded=founded->next)
    {
        if(founded->elem<val)
            break;
    }
    if(founded==0)
    {
        push_front(val);
        return;
    }
    Temp->next=founded->next;
    founded->next=Temp;
}
 
template <typename T>
void List<T>::print()
{
    if(head==0)
    {
        cout<<"Список пуст";
        return;
    }
    
    cout<<"\n Список:";
    for(Node* ptr=head;ptr!=0;ptr=ptr->next)
    {
        cout<<ptr->elem<<" ";
    }
    cout<<"\n";
}
 
template <typename T>
void List<T>::find(int val)
{
    if(head==0)
    {
        cout<<"Список пуст";
    }
    Node* ptr=head;
    for(ptr;ptr!=0;ptr=ptr->next)
    {
        if(ptr->elem==val)
        {
            cout<<" Элемент "<<val<<" найден в списке\n";
            return;
        }
            
    }
    cout<<" Элемента "<<val<<" нет в списке\n";
}
 
template <typename T>
void List<T>::erase(int val)
{
    if(head==0)
    {
        cout<<"Список пуст";
    }
    Node* ptr=head;
    Node* ptrPrev;
    ptrPrev=new Node;
    for(ptr;ptr!=0;ptr=ptr->next)
    {
        if(ptr->elem==val)
        {
            ptrPrev->next=ptr->next;
            delete ptr;
            break;
        }
        ptrPrev=ptr;
    }
    if(ptrPrev->next==0)
    cout<<"Элемент не найдено\n";
}
 
template <typename T>
void List<T>::erase()
{
    if(head==0)
    {
        cout<<"Список пуст";
    }
    Node *delptr=head;
    head=head->next;
    delete delptr;
}
 
template <typename T>
void List<T>::deleteall()
{
    while(head!=NULL)
        erase();
}
int main()
{
    setlocale(LC_ALL, "Russian");
    List<int> Lst;
    Lst.push_back(5);
    Lst.push_back(10);
    Lst.push_back(15);
    Lst.push_front(1);
    Lst.push_front(25);
    Lst.print();
    
    int l;
    cout<<"\nВведите элемент списка";
    cin>>l;
    Lst.insert(l);
    Lst.print();
 
    cout<<"\nВведите элемент для поиска: ";
    cin>>l;
    Lst.find(l);
 
    cout<<"\nВведите элемент списка, который нужно удалить: ";
    cin>>l;
    Lst.erase(l);
    Lst.print();
 
    Lst.deleteall();
    Lst.print();
 
    getch();
    return 0;
}

@rikimaru2013 · 15.11.2014, 18:26

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

но вот шаблон ли это?!

Ваш узел хранит только инт, а должен хранить всё что угодно включая польз классы

@AlexHolmes · 15.11.2014, 19:24 **[ТС]**

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

Ваш узел хранит только инт, а должен хранить всё что угодно включая польз классы

Я так и подозревала. А не подскажите как это исправить, пожалуйста?
Тоже прописать там template <typename T>?

Добавлено через 8 минут
Вот так? Или это бред?

C++ (Qt)

#include "stdafx.h"
#include <iostream>
#include <conio.h>
#include <string>
 
using namespace std;
 
template <typename T> class Node
{
public:
    T elem;
    Node* next;
    Node();
};
 
template <typename T>
Node<T>::Node()
{
    next=0;elem=0;
}
 
template <typename T>
class List
{
public:
    Node<T>* head;
    Node<T>* tail;
    List();
    ~List();
    void push_back(int val);
    void push_front(int val);
    void insert(int val);
    void print();
    void erase(int val);
    void erase();
    void find(int val);
    void deleteall();
};
 
template <typename T>
List<T>::List()
{
    head=0;
    tail=0;
}
 
template <typename T>
List<T>::~List()
{
    if(head!=NULL)
        {
            delete head;
    delete tail;
    }
}
 
template <typename T>
void List<T>::push_back(int val)
{
    Node<T>* Temp;
    Temp= new Node<T>;
    Temp->elem=val;
    if(head==0)
    {
        head=Temp;
        tail=Temp;
        return;
    }
    tail->next=Temp;
    tail=Temp;
}
 
template <typename T>
void List<T>::push_front(int val)
{
    Node<T>* Temp;
    Temp=new Node<T>;
    Temp->elem=val;
    Temp->next=head;
    head=Temp;
}
 
template <typename T>
void List<T>::insert(int val)
{
    if(head==0)
    {
        push_front(val);
        return;
    }
    Node<T>* Temp;
    Temp=new Node<T>;
    Temp->elem=val;
    Node<T>* founded=head;
    for(founded; founded!=0;founded=founded->next)
    {
        if(founded->elem<val)
            break;
    }
    if(founded==0)
    {
        push_front(val);
        return;
    }
    Temp->next=founded->next;
    founded->next=Temp;
}
 
template <typename T>
void List<T>::print()
{
    if(head==0)
    {
        cout<<"Список пуст";
        return;
    }
    
    cout<<"\n Список:";
    for(Node<T>* ptr=head;ptr!=0;ptr=ptr->next)
    {
        cout<<ptr->elem<<" ";
    }
    cout<<"\n";
}
 
template <typename T>
void List<T>::find(int val)
{
    if(head==0)
    {
        cout<<"Список пуст";
    }
    Node<T>* ptr=head;
    for(ptr;ptr!=0;ptr=ptr->next)
    {
        if(ptr->elem==val)
        {
            cout<<" Элемент "<<val<<" найден в списке\n";
            return;
        }
            
    }
    cout<<" Элемента "<<val<<" нет в списке\n";
}
 
template <typename T>
void List<T>::erase(int val)
{
    if(head==0)
    {
        cout<<"Список пуст";
    }
    Node<T>* ptr=head;
    Node<T>* ptrPrev;
    ptrPrev=new Node<T>;
    for(ptr;ptr!=0;ptr=ptr->next)
    {
        if(ptr->elem==val)
        {
            ptrPrev->next=ptr->next;
            delete ptr;
            break;
        }
        ptrPrev=ptr;
    }
    if(ptrPrev->next==0)
    cout<<"Элемент не найдено\n";
}
 
template <typename T>
void List<T>::erase()
{
    if(head==0)
    {
        cout<<"Список пуст";
    }
    Node<T> *delptr=head;
    head=head->next;
    delete delptr;
}
 
template <typename T>
void List<T>::deleteall()
{
    while(head!=NULL)
        erase();
}
int main()
{
    setlocale(LC_ALL, "Russian");
    List<int> Lst;
    Lst.push_back(5);
    Lst.push_back(10);
    Lst.push_back(15);
    Lst.push_front(1);
    Lst.push_front(25);
    Lst.print();
    
    int l;
    cout<<"\nВведите элемент списка";
    cin>>l;
    Lst.insert(l);
    Lst.print();
 
    cout<<"\nВведите элемент для поиска: ";
    cin>>l;
    Lst.find(l);
 
    cout<<"\nВведите элемент списка, который нужно удалить: ";
    cin>>l;
    Lst.erase(l);
    Lst.print();
 
    Lst.deleteall();
    Lst.print();
 
    getch();
    return 0;
}

Добавлено через 39 минут
Кажется, поняла.
Так? Пожалуйста, проверьте)

C++ (Qt)

#include "stdafx.h"
#include <iostream>
#include <conio.h>
#include <string>
 
using namespace std;
 
template <typename T> class Node
{
public:
    T elem;
    Node<T>* next;
    Node();
};
 
template <typename T>
Node<T>::Node()
{
    next=0;elem=0;
}
 
template <typename T>
class List
{
public:
    Node<T>* head;
    Node<T>* tail;
    List();
    ~List();
    void push_back(T val);
    void push_front(T val);
    void insert(T val);
    void print();
    void erase(T val);
    void erase();
    void find(T val);
    void deleteall();
};
 
template <typename T>
List<T>::List()
{
    head=0;
    tail=0;
}
 
template <typename T>
List<T>::~List()
{
    if(head!=NULL)
        {
            delete head;
    delete tail;
    }
}
 
template <typename T>
void List<T>::push_back(T val)
{
    Node<T>* Temp;
    Temp= new Node<T>;
    Temp->elem=val;
    if(head==0)
    {
        head=Temp;
        tail=Temp;
        return;
    }
    tail->next=Temp;
    tail=Temp;
}
 
template <typename T>
void List<T>::push_front(T val)
{
    Node<T>* Temp;
    Temp=new Node<T>;
    Temp->elem=val;
    Temp->next=head;
    head=Temp;
}
 
template <typename T>
void List<T>::insert(T val)
{
    if(head==0)
    {
        push_front(val);
        return;
    }
    Node<T>* Temp;
    Temp=new Node<T>;
    Temp->elem=val;
    Node<T>* founded=head;
    for(founded; founded!=0;founded=founded->next)
    {
        if(founded->elem<val)
            break;
    }
    if(founded==0)
    {
        push_front(val);
        return;
    }
    Temp->next=founded->next;
    founded->next=Temp;
}
 
template <typename T>
void List<T>::print()
{
    if(head==0)
    {
        cout<<"\nСписок пуст";
        return;
    }
    
    cout<<"Список:";
    for(Node<T>* ptr=head;ptr!=0;ptr=ptr->next)
    {
        cout<<ptr->elem<<" ";
    }
    cout<<"\n";
}
 
template <typename T>
void List<T>::find(T val)
{
    if(head==0)
    {
        cout<<"\nСписок пуст";
    }
    Node<T>* ptr=head;
    for(ptr;ptr!=0;ptr=ptr->next)
    {
        if(ptr->elem==val)
        {
            cout<<"\n Элемент "<<val<<" найден в списке\n";
            return;
        }
            
    }
    cout<<"\n Элемента "<<val<<" нет в списке\n";
}
 
template <typename T>
void List<T>::erase(T val)
{
    if(head==0)
    {
        cout<<"\nСписок пуст";
    }
    Node<T>* ptr=head;
    Node<T>* ptrPrev;
    ptrPrev=new Node<T>;
    for(ptr;ptr!=0;ptr=ptr->next)
    {
        if(ptr->elem==val)
        {
            ptrPrev->next=ptr->next;
            delete ptr;
            break;
        }
        ptrPrev=ptr;
    }
    if(ptrPrev->next==0)
    cout<<"\nЭлемент не найдено\n";
}
 
template <typename T>
void List<T>::erase()
{
    if(head==0)
    {
        cout<<"\nСписок пуст";
    }
    Node<T> *delptr=head;
    head=head->next;
    delete delptr;
}
 
template <typename T>
void List<T>::deleteall()
{
    while(head!=NULL)
        erase();
}
int main()
{
    setlocale(LC_ALL, "Russian");
    List<int> Lst;
    Lst.push_back(5);
    Lst.push_back(10);
    Lst.push_back(15);
    Lst.push_front(1);
    Lst.push_front(25);
    Lst.print();
    
    int l;
    cout<<"\nВведите элемент списка ";
    cin>>l;
    Lst.insert(l);
    Lst.print();
 
    cout<<"\nВведите элемент для поиска: ";
    cin>>l;
    Lst.find(l);
 
    cout<<"\nВведите элемент списка, который нужно удалить: ";
    cin>>l;
    Lst.erase(l);
    Lst.print();
 
    Lst.deleteall();
    Lst.print();
 
    getch();
    return 0;
}

То есть в этом промежутке

C++ (Qt)

List<int> Lst;
    Lst.push_back(5);
    Lst.push_back(10);
    Lst.push_back(15);
    Lst.push_front(1);
    Lst.push_front(25);
    Lst.print();
    
    int l;

я могу инт менять на любой тип, так? Я проверяла с float, char, ну только для string коряво пашет.

@rikimaru2013 · 15.11.2014, 19:38

кажись так)

@AlexHolmes · 15.11.2014, 19:44 **[ТС]**

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

кажись так)

Фух, спасибо))

Главное - разобралась в сути самих шаблонов))

@rikimaru2013 · 15.11.2014, 19:47

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

template <typename T>
List<T>::~List()
{
* * if(head!=NULL)
* * * * {
* * * * * * delete head;
* * delete tail;
* * }
}

Если в списке 40 элемментов - удаляете первый и сороковый?) Умно) Но утечка)) в 38 эл

@DrOffset · 15.11.2014, 19:51

AlexHolmes,

C++

template <typename T> 
Node<T>::Node()
    : next(0), elem()
{ }

Иначе будет ошибка на типах, которым нельзя присваивать число. Например на строках.

@AlexHolmes · 15.11.2014, 19:53 **[ТС]**

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

Иначе будет ошибка на типах, которым нельзя присваивать число. Например на строках.

Спасибо)) потому у меня со строками и были проблемы.

@Renji · 15.11.2014, 20:00

del

@AlexHolmes · 15.11.2014, 20:01 **[ТС]**

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

"next=0;elem=0;" сглючит если elem нельзя присваивать число (это std::map, например). Просто не инициализируйте его, пусть работает конструктор по умолчанию.

Спасибо, уже исправила))

@DrOffset · 15.11.2014, 20:10

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

Спасибо, уже исправила))

Только вот вообще не инициализировать не надо (надо инициализировать как в моем примере). Иначе у значений POD-типов (int, double и т.д.) начальное значение будет неопределенным.

@rikimaru2013 · 15.11.2014, 20:13

А еще лучше: запретить создавать Node конструктором по умолчанию. При создание узла в него уже надо передать значение, что он должен хранить. Зачем пустой узел?)

@DrOffset · 15.11.2014, 20:26

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

Зачем пустой узел?)

Не пустой, а со значением по-умолчанию. Понадобиться это может, например, при реализации метода resize.

@rikimaru2013 · 15.11.2014, 20:29

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

при реализации метода resize

Напомните, пожалуйста, что делает метод resize в списке???

@DrOffset · 15.11.2014, 20:30

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

Напомните, пожалуйста, что делает метод resize в списке???

Тут

@DrOffset 18822 / 9826 / 2401 Регистрация: 30.01.2014 Сообщений: 17,260
	15.11.2014, 20:10	12
	Сообщение от AlexHolmes Спасибо, уже исправила)) Только вот вообще не инициализировать не надо (надо инициализировать как в моем примере). Иначе у значений POD-типов (int, double и т.д.) начальное значение будет неопределенным. 0

@DrOffset 18822 / 9826 / 2401 Регистрация: 30.01.2014 Сообщений: 17,260
	15.11.2014, 20:30	16
	Сообщение от rikimaru2013 Напомните, пожалуйста, что делает метод resize в списке??? Тут 1

@rikimaru2013 2549 / 1208 / 358 Регистрация: 30.11.2013 Сообщений: 3,826
	15.11.2014, 18:26	3
	Сообщение от AlexHolmes но вот шаблон ли это?! Ваш узел хранит только инт, а должен хранить всё что угодно включая польз классы 0

@rikimaru2013 2549 / 1208 / 358 Регистрация: 30.11.2013 Сообщений: 3,826
	15.11.2014, 19:38	5
	кажись так) 0

@AlexHolmes 1 / 1 / 0 Регистрация: 14.11.2013 Сообщений: 77
	15.11.2014, 19:44 [ТС]	6
	Сообщение от rikimaru2013 кажись так) Фух, спасибо)) Главное - разобралась в сути самих шаблонов)) 0

@rikimaru2013 2549 / 1208 / 358 Регистрация: 30.11.2013 Сообщений: 3,826
	15.11.2014, 19:47	7
	Сообщение от AlexHolmes template <typename T> List<T>::~List() { * * if(head!=NULL) * * * * { * * * * * * delete head; * * delete tail; * * } } Если в списке 40 элемментов - удаляете первый и сороковый?) Умно) Но утечка)) в 38 эл 1

@AlexHolmes 1 / 1 / 0 Регистрация: 14.11.2013 Сообщений: 77
	15.11.2014, 19:53 [ТС]	9
	Сообщение от DrOffset Иначе будет ошибка на типах, которым нельзя присваивать число. Например на строках. Спасибо)) потому у меня со строками и были проблемы. 0

@Renji 2782 / 1935 / 570 Регистрация: 05.06.2014 Сообщений: 5,600
	15.11.2014, 20:00	10
	del 0

@AlexHolmes 1 / 1 / 0 Регистрация: 14.11.2013 Сообщений: 77
	15.11.2014, 20:01 [ТС]	11
	Сообщение от Renji "next=0;elem=0;" сглючит если elem нельзя присваивать число (это std::map, например). Просто не инициализируйте его, пусть работает конструктор по умолчанию. Спасибо, уже исправила)) 0

@rikimaru2013 2549 / 1208 / 358 Регистрация: 30.11.2013 Сообщений: 3,826
	15.11.2014, 20:13	13
	А еще лучше: запретить создавать Node конструктором по умолчанию. При создание узла в него уже надо передать значение, что он должен хранить. Зачем пустой узел?) 0

@DrOffset 18822 / 9826 / 2401 Регистрация: 30.01.2014 Сообщений: 17,260
	15.11.2014, 20:26	14
	Сообщение от rikimaru2013 Зачем пустой узел?) Не пустой, а со значением по-умолчанию. Понадобиться это может, например, при реализации метода resize. 0

@rikimaru2013 2549 / 1208 / 358 Регистрация: 30.11.2013 Сообщений: 3,826
	15.11.2014, 20:29	15
	Сообщение от DrOffset при реализации метода resize Напомните, пожалуйста, что делает метод resize в списке??? 0