Список — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 29: Строка 29:
  
 
===Поиск===
 
===Поиск===
  Search()
+
  Search()//ищем элемент
 
     {
 
     {
 
         node = head;
 
         node = head;
 
         while ((node != NULL) && (we_are_looking_not_for(node)))
 
         while ((node != NULL) && (we_are_looking_not_for(node)))
 
             node = node->next;
 
             node = node->next;
 +
        return node;
 
     }
 
     }
 
===Удаление===
 
===Удаление===
  Удаление первого элемента
+
  removeHead()//удаление головы
 +
    {
 +
        if (head != NULL)
 +
        {
 +
            tmp = head;
 +
            head = head->next;
 +
            delete tmp;
 +
        }
 +
    }
 +
 
 
   
 
   
  Удаление элемента после определенного элемента списка
+
  removeAfter(this_element)
 +
    {
 +
        if ((this_element != NULL)&&(this_element->next != NULL))
 +
        {
 +
            tmp = this_element->next;
 +
            this_element->next = this_element->next->next;
 +
            delete tmp;
 +
        }
 +
    }
 
==См.также==
 
==См.также==
 
[[Массив с увеличением/уменьшением размера]]
 
[[Массив с увеличением/уменьшением размера]]

Версия 10:34, 7 июня 2011

Связный список - структура данных, состоящая из узлов, содержащих помимо собственных данных ссылки на следующий и/или предыдущий узел списка. С помощью списков можно реализовать такие структуры данных как стек и очередь.

Односвязный список

Простейшай реализация списка. В узлах хранятся данные и указатель на следующий элемент в списке.

Single linked list-1-.png

Двусвязный список

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

Doubly linked list.png

XOR-связный список

XOR-связный список — структура данных, похожая на обычный двусвязный список, однако в каждом элементе хранящая только один адрес — результат выполнения операции XOR над адресами предыдущего и следующего элементов списка. Для того, чтобы перемещаться по списку, необходимо взять два последовательных адреса и выполнить над ними операцию XOR, которая и даст реальный адрес следующего элемента.

Циклический список

Первый элемент является следующим для последнего элемента списка.

Circurlar linked list.png (872×241).png

Операции на списке

Рассмотрим базовые операции на примере односвязного списка.

Вставка

insert(new_head)// вставка в голову  списка
    {
        new_head->next = head;
        head = new_head;
    }
insertAfter(this_element, that_element)// вставка после this_element
    {
        that_element->next = this_element->next; 
        this_element->next = that_element;
    }

Поиск

Search()//ищем элемент
    {
        node = head;
        while ((node != NULL) && (we_are_looking_not_for(node)))
            node = node->next;
        return node;
    }

Удаление

removeHead()//удаление головы
    {
        if (head != NULL)
        {
            tmp = head;
            head = head->next;
            delete tmp;
        }
    }


removeAfter(this_element)
    {
        if ((this_element != NULL)&&(this_element->next != NULL))
        {
            tmp = this_element->next;
            this_element->next = this_element->next->next;
            delete tmp;
        }
    }

См.также

Массив с увеличением/уменьшением размера

Ссылки

http://en.wikipedia.org/wiki/Linked_list Linked list

Литература

  • Т. Кормен, Ч. Лейзерсон, Р. Ривест: Алгоритмы: построение и анализ глава 11.2
  • Д. Кнут: Искусство программирования том 1 глава 2.2