Изменение списков Компонентные функции 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  Обсудить в чате