<< Пред.           стр. 21 (из 121)           След. >>

Список литературы по разделу

 mylist.insert( mylist.find( 8 ), some_value );
 Перед тем как тестировать операции вставки элементов, нам нужно написать функцию display(), которая поможет нам при отладке. Алгоритм display() достаточно прост: печатаем все элементы, с первого до последнего. Можете ли вы сказать, где в данной реализации ошибка?
 // не работает правильно!
 
 for ( ilist_item *iter = _at_front; // начнем с первого
  iter != _at_end; // пока не последний
  ++iter ) // возьмем следующий
  cout << iter->value() << ' ';
 
 // теперь напечатаем последний
 cout << iter->value();
 Список – это не массив, его элементы не занимают непрерывную область памяти. Инкремент итератора
 ++iter;
 вовсе не сдвигает его на следующий элемент списка. Вместо этого он указывает на место в памяти, непосредственно следующее за данным элементом, а там может быть все что угодно. Для изменения значения итератора нужно воспользоваться членом _next объекта ilist_item:
 iter = iter->_next;
 Мы инкапсулировали доступ к членам ilist_item набором встраиваемых функций. Определение класса ilist_item теперь выглядит так:
 class ilist_item {
 public:
  ilist_item( int value, ilist_item *item_to_link_to = 0 );
  int value() { return _value; }
  iilst_item* next() { return _next; }
 
  void next( ilist_item *link ) { _next = link; }
  void value( int new_value ) { _value = new_value; }
 
 private:
  int _value;
  ilist_item *_next;
 };
 Вот определение функции display(), использующее последнюю реализацию класса ilist_item:
 #include
 
 class ilist {
 public:
  void display( ostream &os = cout );
  // ...
 };
 
 void ilist::
 display( ostream &os )
 {
  os << "\n( " << _size << " )( ";
 
  ilist_item *ptr = _at_front;
  while ( ptr ) {
  os << ptr->value() << " ";
  ptr = ptr->next();
  }
 
  os << ")\n";
 }
 Тестовую программу для нашего класса ilist в его текущей реализации можно представить таким образом:
 #include
 #include "ilist.h"
 
 int main()
 {
  ilist mylist;
 
  for ( int ix = 0; ix < 10; ++ix ) {
  mylist.insert_front( ix );
  mylist.insert_end( ix );
  }
  cout <<
  "Ok: после insert_front() и insert_end()\n";
  mylist.display();
 
  ilist_item *it = mylist.find( 8 );
  cout << "\n"
  << "Ищем значение 8: нашли?"
  << ( it ? " да!\n" : " нет!\n" );
 
  mylist.insert( it, 1024 );
  cout << "\n" <<
  "Вставка элемента 1024 после 8\n";
 
  mylist.display();
  int elem_cnt = mylist.remove( 8 );
  cout << "\n"
  << "Удалено " << elem_cnt
  << " элемент(ов) со значением 8\n";
 
  mylist.display();
  cout << "\n" << "Удален первый элемент\n";
 
  mylist.remove_front(); mylist.display();
 
  cout << "\n" << "Удалены все элементы\n";
  mylist.remove_all(); mylist.display();
 }
 Результат работы программы:
 
 Ok: после insert_front() и insert_end()
 
 (20)( 9 8 7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 8 9 )
 
 Ищем значение 8: нашли? да!
 
 Вставка элемента 1024 после 8
 
 ( 21 )( 9 8 1024 7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 8 9 )
 
 Удалено 2 элемент(ов) со значением 8
 
 ( 19 )( 9 1024 7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 9 )
 
 Удален первый элемент
 
 ( 18 )( 1024 7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 9 )
 
 Удалены все элементы
 
 ( 0 )( )
 
 Помимо вставки элементов, необходима возможность их удаления. Мы реализуем три таких операции:
 void remove_front();
 void remove_all ();
 int remove( int value );
 Вот как выглядит реализация remove_front():
 inline void
 i1ist::
 remove_front()
 {
  if ( _at_front ) {
  ilist_item *ptr = _at_front;
  _at_front = _at_front->next();
 
  bump_down_size() ;
  delete ptr;
  }
 }
 remove_all() вызывает remove_front() до тех пор, пока все элементы не будут удалены:
 void ilist::
 remove_all()
 {
  while ( _at_front )
  remove_front();
 
  _size = 0;
  _at_front = _at_end = 0;
 }
 Общая функция remove() также использует remove_front() для обработки специального случая, когда удаляемый элемент (элементы) находится в начале списка. Для удаления из середины списка используется итерация. У элемента, предшествующего удаляемому, необходимо модифицировать указатель _next. Вот реализация функции:
 int ilist::
 remove( int value )
 {
  ilist_item *plist = _at_front;
  int elem_cnt = 0;
 
  while ( plist && plist->value() == value )
  {
  plist = plist->next();
  remove_front();
  ++elem_cnt;
  }
 
  if ( ! plist )
  return elem_cnt;
 
  ilist_item *prev = plist;
  plist = plist->next();
 
  while ( plist ) {
  if ( plist->value() == value ) {
  prev->next( plist->next() );
  delete plist;
  ++elem_cnt;
  bump_down_size();
  plist = prev->next();
  if ( ! plist ) {
  _at_end = prev;
  return elem_cnt;
  }
  }
  else {
  prev = plist;
  plist = plist->next();
  }
 
  return elem_cnt;
 }
 Следующая программа проверяет работу операций в четырех случаях: когда удаляемые элементы расположены в конце списка, удаляются все элементы, таких элементов нет или они находятся и в начале, и в конце списка.
 #include
 #include "ilist.h"
 int main()
 {
  ilist mylist;
  cout << "\n-----------------------------------------------\n"
  << "тест #1: - элементы в конце\n"
  << "-----------------------------------------------\n";
 
  mylist.insert_front( 1 ); mylist.insert_front( 1 );
  mylist.insert_front( 1 );
 
  my1ist.insert_front( 2 ); mylist.insert_front( 3 );
  my1ist.insert_front( 4 );
 
  mylist.display();
 
  int elem_cnt = mylist.remove( 1 );
  cout << "\n" << "Удалено " << elem_cnt
  << " элемент(ов) со значением 1\n";
 
  mylist.display();
 
  mylist.remove_all();
 
  cout << "\n-----------------------------------------------\n"
  << "тест #2: - элементы в начале\n"
  << "-----------------------------------------------\n";
 
  mylist.insert_front( 1 ); mylist.insert_front( 1 );
  mylist.insert_front( 1 );
 
  mylist.display();
 
  elem_cnt = mylist.remove( 1 );
 
  cout << "\n" << "Удалено " << elem_cnt
  << " элемент(ов) со значением 1\n";
  mylist.display();
 
  mylist.remove_all () ;
 
  cout << "\n-----------------------------------------------\n"
  << "тест #3: - элементов нет в списке\n"
  << "-----------------------------------------------\n";
 
  mylist.insert_front( 0 ); mylist.insert_front( 2 );
  mylist.insert_front( 4 );
 
  mylist.display();
 
  elem_cnt = mylist.remove( 1 );
 
  cout << "\n" << "Удалено " << elem_cnt
  << " элемент(ов) со значением 1\n";
  mylist.display();
 
  mylist.remove_all () ;
 
  cout << "\n-----------------------------------------------\n"
  << "тест #4: - элементы в конце и в начале\n"
  << "-----------------------------------------------\n";
  my1ist.insert_front( 1 ); mylist.insert_front( 1 );
  my1ist.insert_front( 1 );
 
  my1ist.insert_front( 0 ); mylist.insert_front( 2 );
  my1ist.insert_front( 4 );
 
  mylist.insert_front( 1 ); my1ist.insert_front( 1 );
  mylist.insert_front( 1 );
 
  mylist.display() ;
 
  elem_cnt = mylist.remove( 1 );
 
  cout << "\n" << "Удалено " << elem_cnt
  << " элемент(ов) со значением 1\n";
  mylist.display();
 }
 Результат работы программы:
 
 -----------------------------------------------
 тест #1: - элементы в конце
 -----------------------------------------------
 
 ( 6 )( 4 3 2 1 1 1 )
 
 Удалено 3 элемент(ов) со значением 1
 
 ( 3 )( 4 3 2 )
 
 -----------------------------------------------
 тест #2: - элементы в начале
 -----------------------------------------------
 
 ( 3 )( 1 1 1 )
 
 Удалено 3 элемент(ов) со значением 1
 
 ( 0 )( )
 
 -----------------------------------------------
 тест #3: - элементов нет в списке
 -----------------------------------------------
 
 ( 3 )( 4 2 0 )
 
 Удалено 0 элемент(ов) со значением 1
 
 ( 3 )( 4 2 0 )
 
 -----------------------------------------------
 тест #4: - элементы в конце и в начале
 -----------------------------------------------
 
 (9 )( 1 1 1 4 2 0 1 1 1 )
 
 Удалено 6 элемент(ов) со значением 1
 

<< Пред.           стр. 21 (из 121)           След. >>

Список литературы по разделу