C++: Создание Шаблона Класса

[inek]

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

Все действия реализовала:

#include <iostream>

using namespace std;

template <typename T>
class List
{
struct Node
{
T data;
Node *next;
Node(T d, Node *n = 0):data(d), next(n) {}
};
Node *head;
public:
List(Node *h = 0):head(h){}
~List();
bool isEmpty(); //проверка, пуст ли список;
void insertAfter(Node *pre, T d); 
void removeAfter(Node *pre); 
void pushFront(T d);
T popFront();
void print();
Node *search(T d);
void create(int k); 
void createFrom(List<T> *L1, List<T> *L2);

};

template <typename T>
List<T>::~List()
{
while (!isEmpty())
popFront();
}

template <typename T>
bool List<T>::isEmpty() 
{
return !head;
}

template <typename T>
void List<T>::insertAfter(Node *pre, T d) 
{ 
if(!pre) return;
Node *newNode = new Node(d,0);
newNode->next = pre->next;
pre->next = newNode;
}

template <typename T>
void List<T>::removeAfter(Node *pre)
{
if (!pre || !pre->next) return;
Node *tmp = pre->next; 
pre->next = pre->next->next;
delete tmp;
}

template <typename T>
void List<T>::pushFront(T d)
{
Node *newNode = new Node(d,0);
if(!head) {
head = newNode;
return;
}
newNode->next = head;
head = newNode;
}

template <typename T>
T List<T>::popFront()
{
T data;				 
if(!head) return data;
Node *tmp = head;
data = head->data;
if(head->next) {
head = head->next;
delete tmp;
return data;
}
delete tmp;
head = NULL;
return data;
}


template <typename T>
typename List<T>::Node* List<T>::search(T d)
{
if(!head) return NULL;
Node* cur = head;
while(cur) {
if(cur->data == d) return cur;
cur = cur->next;
}
return NULL;
}


template <typename T>
void List<T>::print()
{
if(!head) return;
Node *cur = head;
while(cur) {
cout << cur->data << "; ";
cur = cur->next;
}
cout << endl;
}

template <typename T>
void List<T>::create(int k)
{
T d;
for (int i = 1; i <= k; i++)
{
cout << "Enter " << i << "-i element: ";
cin >> d;
pushFront(d);

}
}

template <typename T>
void List<T>::createFrom(List<T> *L1, List<T> *L2)
{ T dt;
while(!L1->isEmpty())
{
dt = L1->popFront();
if(L2->search(dt) == NULL && search(dt) == NULL)
{
pushFront(dt);
}
}

while(!L2->isEmpty())
{
dt = L2->popFront();
if(search(dt) == NULL)
{
pushFront(dt);
}
}
}

Метод main выглядит следующим образом:

#include "List.h"
#include <iostream>
#include <string>

using namespace std;

int main()
{

List<string> *L1 = new List<string>(NULL);
L1->create(7);
L1->print();

List<string> *L2 = new List<string>(NULL);
L2->create(7);
L2->print();

List<string> *L = new List<string>(NULL);
L->createFrom(L1,L2);
L->print();

system("PAUSE");
return EXIT_SUCCESS;
}

Список формируется слегка неправильно. При работе с L2 он включает в L3 элементы, которые присутствуют в L1.
то есть если у нас L1 выглядит так : 1,2,3,4,5,6,7
L2 : 8,1,2,3,4,9,10
то L3 будет выглядеть так: 8,1,2,3,4,9,10, 5,6,7
а должен выглядеть так: 8,9,10,5,6,7

Помогите разобраться с ошибкой!

 

[rrrFer]

Пользуясь только реализованным набором операций, нормально реализовать "createFrom" не получится. Я бы добавил метод удаления всех узлов списка с заданным значением из списка. Добавите такой метод - помогу с "createFrom".

 

[inek]

template <typename T>
void List<T>::Front(T d)
{
T data;				 
if(!head) return;
Node *tmp = head;
data = head->data;
if((head->next)&&(data==d)) {
head = head->next;
delete tmp;
}
return;
}

по-моему так.

 

[rrrFer]

Нет, не так. Все не так.
почему всегда сдвигается голова? - элемент должен удаляться из середины тоже, и из конца.
data получает значение до цикла, в цикле не меняется, так и надо?
tmp не изменяет значение, при выполнении delete tmp второй раз получим ошибку.
проверьте сперва.

 

[rrrFer]

вобщем ждал я, ждал...не пишите ((
нате вот через задницу:

template <typename T>
void List<T>::createFrom(List<T> *L1, List<T> *L2){
Node	*p, *p_, *pt, *pt_;
bool	fl;

while(!L1->isEmpty())
pushFront(L1->popFront());

while(!L2->isEmpty())
pushFront(L2->popFront());

p = head;
while( p ) {
p_ = p;
fl = 0;
while( 1 ) {
pt = p_ ->next;
if( 0 == pt )
break;
if( pt ->data == p ->data ) {
p_ ->next = p_ ->next ->next;
delete pt;
fl = 1;
}
p_ = p_ ->next;
if( 0 == p_ )
break;
}
if( fl ) {
if( p == head )
head = head ->next;
else
pt_ ->next = p ->next;
pt = p;
p = p ->next;
delete pt;
}
else {
pt_= p;
p = p ->next;
}
}
}

 

[inek]

вобщем ждал я, ждал...не пишите ((
нате вот через задницу:

template <typename T>
void List<T>::createFrom(List<T> *L1, List<T> *L2){
Node	*p, *p_, *pt, *pt_;
bool	fl;

while(!L1->isEmpty())
pushFront(L1->popFront());

while(!L2->isEmpty())
pushFront(L2->popFront());

p = head;
while( p ) {
p_ = p;
fl = 0;
while( 1 ) {
pt = p_ ->next;
if( 0 == pt )
break;
if( pt ->data == p ->data ) {
p_ ->next = p_ ->next ->next;
delete pt;
fl = 1;
}
p_ = p_ ->next;
if( 0 == p_ )
break;
}
if( fl ) {
if( p == head )
head = head ->next;
else
pt_ ->next = p ->next;
pt = p;
p = p ->next;
delete pt;
}
else {
pt_= p;
p = p ->next;
}
}
}

спасибо огромное, конечно! занимаюсь решением задач только по ночам, вот и задержка.. сейчас буду тестировать все!

Добавлено: еще раз спасибо! программа выдержала тест на все нужные типы данных!

 

[rrrFer]

да пожалсто )