С++: Двусвязные Списки

  • Автор темы inek
  • Дата начала
I

inek

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

ЗАДАЧА: Необходимо удалить все элементы между минимальным и максимальным элементами.

Функцию нахождения минимума и максимума написала, помогите дописать ее для удаления элементов между min и max.

Вот шаблон:
C++:
#include <iostream>

using namespace std;

template <typename T>
class ListD
{
struct Node
{
T data;
Node *next, *prev;
Node(T d, Node *n = 0, Node *p = 0):data(d), next(n), prev(p) {}
};
Node *head;
public:
ListD(Node *h = 0):head(h){}
~ListD();
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);
Node *searchMinMax();
// void MinMax();
//void createFrom(List<T> *L1);
};

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

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

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

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

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

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

template <typename T>
typename ListD<T>::Node* ListD<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 ListD<T>::print()
{
if(!head) return;
Node *cur = head;
while(cur) {
cout << cur->data << "; ";
cur = cur->next;
}
cout << endl;
}

template <typename T>
void ListD<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>
typename ListD<T>::Node* ListD<T>::searchMinMax()
{ T min;
T max;
Node* cur = head;
min = cur->data;
max = cur->data;
while(cur) {
if(min > cur->data ) {min = cur->data;}
if(max < cur->data ) {max = cur->data;}
cur = cur->next;
}
cout << "Min " << min << ": ";
cout << "Max " << max << ": ";
}
Функция main:
C++:
#include "List.h"
#include "ListD.h"
#include <string>
#include <iostream>

using namespace std;

int main()
{

ListD<string> *L = new ListD<string>();
L->create(7);
L->print();
L->searchMinMax();

system("PAUSE");
return EXIT_SUCCESS;
}
Заранее благодарна!
 
R

rrrFer

Гость
#2
поправил ваш код, допишите сами?
Код:
template <typename T>
typename ListD<T>::Node* ListD<T>::searchMinMax(){ 
Node* min = head, *max = head;
Node* cur = head;

int	nmin, nmax, i, t;

min = max = cur;
for( nmin = nmax = i = 0;cur;i++) {
if(min ->data > cur->data ) {
min = cur;
nmin = i;
}
if(max ->data < cur->data ) {
max = cur;
nmax = i;
}
cur = cur->next;
}

if( nmin < nmax ) {
i = nmax - nmin;
cur = min;
}
else {
cur = max;
i = nmin - nmax;
}

//осталось удалить i элементов начиная с указателя cur


cout << "Min " << min << ": ";
cout << "Max " << max << ": ";

return 0;
}