0

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

#include <iostream>
using namespace std;

template <typename T> class list   
{ 
   struct node       
{
   T value;     
   node *next;
   node *prev; 
};
   node *head;
   node *tail; 
public:
   list() : head(NULL), tail(NULL) {}; 
   ~list();
 void remove();
 void show_end();
 void show_beginning(); 
 void add(T value); 
};

template <typename T> list<T> :: ~list() 
{   
  while (tail) 
  {
     head = tail->prev; 
     delete [] tail; 
     tail = head; 
  }
}

template <typename T> void list<T> :: add(T value)
{
  node *temp = new node; 
  temp->next = NULL;  
  temp->value = value;

  if (head != NULL) 
 {
   temp->prev = tail; 
   tail->next = temp; 
   tail = temp; 
  }
  else 
  {
   temp->prev = NULL; 
   head = tail = temp;
  }
 }

 template <typename T> void list<T> :: remove()
 {
   if (head != NULL)
   {
    node *temp = tail;  
    tail= tail->prev;   
    tail->next = NULL;  
    delete temp;    
    }
   else
    cout << "List is empty";
  }

  template <typename T> void list<T> :: show_end()
  {
    node *temp = tail;

    while (temp != NULL)
   {
     cout << temp->value << " "; 
     temp = temp->prev; 
   }
    cout<<"\n";
  }

  template <typename T> void list<T> :: show_beginning()
  {
    node *temp = head; 
    while (temp != NULL) 
    {
      cout << temp->value << " "; 
      temp = temp->next; 
    }
    cout << "\n";
   }
1
  • Если вам дан исчерпывающий ответ, отметьте его как верный (галка напротив выбранного ответа). 23 мар 2016 в 7:28

1 ответ 1

2

Чтобы что-то найти в структуре данных, нужно перебирать элементы этой структуры данных.

Объект, который позволяет перемещаться между элементами называется итератор.
Это может быть не обязательно стандартным итератором С++.

Минимальный однонаправленный итератор - это

template <typename T>
class list   
{ 
public:
    struct iterator {
      node* node_;

      // продвижение вперед
      void next() { node_ = node_->next; }
      // текущий элемент
      const T& value() const { return node_->value; }
      // сравнение
      bool equal(iterator other) const { return node_ == other.node_; }
    };

    // первый элемент
    iterator begin() { iterator it = {head}; return it; }
    // следующий-за-концом
    iterator end() { iterator it = {nullptr}; return it; }
};

Далее осталось написать алгоритм, который находит минимальный элемент:

template<typename Iter>
Iter min_element(Iter first, Iter last) {
  if (first.equal(last)) return last;

  auto min = first;
  first.next();

  while (!first.equal(last)) {
    if (first.value() < min.value() min = first;
    first.next();
  }

  return min;
}

И использование:

list<int> l;
...
int min = min_element(l.begin(), l.end()).value();

Для перемещения назад такой итератор не подходит, но в задаче говорится только про поиск минимального элемента, а для этого надо только перемещение вперед.

0

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.