Связь и интернет Архив Программирование
   
Сделать стартовойСделать закладку            
   ПОИСК  
   
Главная / Алгоритмы / Структуры данных и хэширование / Введение в абстрактные структуры / Cписки /
8  Perl
8  PHP
8  JavaScript
8  HTML
8  DHTML
8  XML
8  CSS
8  C / C++
8  Pascal и Delphi
8  Турбо Ассемблер
8  MySQL
8  CASE-технологии
8  Алгоритмы
8  Python
8  Обратная связь
8  Гостевая книга
Новости о мире


Реализация кольцевого двухсвязного списка - Программирование от RIN.RU
Реализация кольцевого двухсвязного списка



Изменение списков


Компонентные функции insert, prepend и append используются для включения в список новых элементов. Ни одна из этих трех функций не изменяет позиции окна. Функция insert заносит новый элемент после окна и возвращает указатель на новый элемент:



template T List::insert(T val)
{
win->insert(new ListNode(val) );
++_length;
return val;
}


Компонентные функции prepend и append вставляют новый элемент в начало или в конец списка соответственно и возвращают указатель на новый элемент:


template Т List::prepend(T val)
{
header->insert (new ListNode (val));
++_length;
return val;
}


template Т List::append (T val)
{
header->prev()->insert (new ListNode (val) );
++_length;
return val;
}


Вторая версия компонентной функции append используется для добавления списка 1 в конец текущего списка - первый элемент списка 1 помещается после последнего элемента текущего списка. В процессе выполнения список 1 становится пустым. Возвращается указатель на текущий список:



template List* List::append (List *1)
{
ListNode *a = (ListNode*) header->prev() ;
a->splice(l->header);
_length += l-> _length;
l->header->remove();
l->_length = 0;
l->win = header;
return this;
}


Компонентная функция remove удаляет элемент, находящийся в окне, перемещает окно в предыдущую позицию и возвращает указатель на только что удаленный элемент. Если окно находится в головной позиции, то таких действий не производится:



template T List::remove (void)
{
if (win == header) return NULL;
void *val = win->_val;
win = (ListNode*) win->prev();
delete (ListNode*) win->next()->remove();
-- _length ;
return val;
}




Если вызывается компонентная функция val с именем некоторого элемента v, то происходит замена элемента, находящегося в текущем окне, на элемент v. Если окно находится в головной позиции, то никаких действий не производится.


void List::val (T v)
{
if (win != header)
win->_val = v;
}




Доступ к элементам списка


Если обращение к компонентной функции val происходит без аргументов, то возвращается элемент, находящийся в окне, или нуль NULL, если окно располагается в головной позиции:



template T List::val(void)
{
return win->_val;
}


Компонентные функции next и prev перемещают окно в следующую или предыдущую позиции соответственно. Каждая из них возвращает указатель на элемент, расположенный в новой позиции окна. Заметим, что класс List обеспечивает операцию "заворачивания". Например, если окно находится в последней позиции, то выполнение операции next переместит окно в головную позицию, еще одно обращение к next переместит окно в первую позицию.



template T List::next(void)
{
win = (ListNode*) win->next();
return win->_val;
}


template T List::prev(void)
{
win = (ListNode*) win->prev();
return win->_val;
}


Компонентные функции first и last переносят окно в первую и последнюю позиции соответственно, они не производят никаких действий, если лист пустой. Каждая из этих функций возвращает указатель на элемент, записанный в новом положении окна:



template T List::first (void)
{
win = (ListNode*) header->next();
return win->_val;
}


template T List::last (void)
{
win = (ListNode*) header->prev();
return win->_val;
}




Компонентная функция length возвращает значение длины списка:


template int List::length (void)
{
return _length;
}


Компонентные функции isFirst, isLast и isHead возвращают значение TRUE (истина) только в случаях, если окно находится в первой, последней или головной позициях соответственно.



template bool List::isPirst(void)
{
return ( (win == header->next() ) && (_length > 0) );
}


template bool List::isLast (void)
{
return ( (win == header->prev() ) && (_length > 0) );
}


template>class T> bool List::isHead(void)
{
return (win == header);
}




Примеры списков


Два простых примера иллюстрируют использование списков. В первом примере шаблон функции arrayToList загружает n элементов массива а в список и возвращает указатель на этот список:



template List *arrayToList(Т а[], int n)
{
List *s = new List;
for (int i = 0; i < n; i++)
s->append(a[i]);
return s;
}


Например, если а представляет собой массив строк, то следующий фрагмент программы преобразует массив а в список строк s :



char *a[20];
.
.
// здесь должен быть определен массив а
.
.
List *s = arrayToList(a, 20);




Шаблон функции arrayToList мы будем впоследствии использовать как утилиту в некоторых программах.


В качестве второго примера рассмотрим шаблон функции leastltem, которая возвращает наименьший элемент в списке s. Два элемента сравниваются с помощью функции стр, в результате работы которой возвращаются значения -1, 0 или 1, если первый аргумент соответственно меньше, равен или больше второго аргумента:



template Т leastltem(List &s, int(*cmp) (Т,Т) )
{
int i;
if (s.length() == 0)
return NULL;
Т v = s.first();
for (s.next(); !s.isHeadO; s.next() )
if (cmp(s.val(), v) < 0)
v = s.val();
return v;
}


Для определения, какой из списков строк появляется раньше в алфавитном порядке, следует обратиться к функции leastltem с функцией сравнения strcmp. Это стандартная библиотечная функция языка C++, которая при обработке двух строк выдает значения -1, 0 или 1 в зависимости от того, будет ли первая строка меньше, равна или больше второй строки в алфавитном порядке. Например, в результате работы следующего фрагмента программы будет напечатана строка ant:



List s;
s.append("bat");
s.append("ant");
s.append("cat");
cout << leastltem(s, strcmp);


<<<  Назад
 1  2  3 


 8  Комментарии к статье  8 8  Обсудить в чате

 
  
  
    Copyright ©  RIN 2003 - 2004      * Обратная связь