Вставка в односвязный список

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

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

Существует два основных способа построения односвязного списка. Первый способ — помещать новые элементы в конец списка [1] . Второй — вставлять элементы в определенные позиции списка, например, в порядке возрастания. От способа построения списка зависит алгоритм функции добавления элемента. Давайте начнем с более простого способа создания списка путем помещения элементов в конец.

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

Приведенная ниже функция slstore() создает односвязный список путем помещения каждого очередного элемента в конец списка. В качестве параметров ей передаются указатель на структуру типа address , содержащую новую запись, и указатель на последний элемент списка. Если список пуст, указатель на последний элемент должен быть равен нулю.

Несмотря на то, что созданный с помощью функции slstore() список можно отсортировать отдельной операцией уже после его создания, легче сразу создавать упорядоченный список, вставляя каждый новый элемент в нужное место в последовательности. Кроме того, если список уже отсортирован, имеет смысл поддерживать его упорядоченность, вставляя новые элементы в соответствующие позиции. Для вставки элемента таким способом требуется последовательно просматривать список до тех пор, пока не будет найдено место нового элемента, затем вставить в найденную позицию новую запись и переустановить ссылки.

При вставке элемента в односвязный список может возникнуть одна из трех ситуаций: элемент становится первым, элемент вставляется между двумя другими, элемент становится последним. На рис. 22.3 показана схема изменения ссылок в каждом случае.

Рис. 22.3. Вставка элемента new в односвязный список (в котором info — поле данных)

Следует помнить, что при вставке элемента в начало (первую позицию) списка необходимо также изменить адрес входа в список где-то в другом месте программы. Чтобы избежать этих сложностей, можно в качестве первого элемента списка хранить служебный сторожевой элемент [2] . В случае упорядоченного списка необходимо выбрать некоторое специальное значение, которое всегда будет первым в списке, чтобы начальный элемент оставался неизменным. Недостатком данного метода является довольно большой расход памяти на хранение сторожевого элемента, но обычно это не столь важно.

Следующая функция, sls_store() , вставляет структуры типа address в список рассылки, упорядочивая его по возрастанию значений в поле name . Функция принимает указатели на указатели на первый и последний элементы списка, а также указатель на вставляемый элемент. Поскольку первый или последний элементы списка могут измениться, функция sls_store() при необходимости автоматически обновляет указатели на начало и конец списка. При первом вызове данной функции указатели first и last должны быть равны нулю.

Последовательный перебор элементов связанного списка осуществляется очень просто: начать с начала и следовать указателям. Обычно фрагмент кода перебора настолько мал, что его вставляют в другую процедуру — например, функцию поиска, удаления или отображения содержимого. Так, приведенная ниже функция выводит на экран все имена из списка рассылки:

При вызове функции display() параметр start должен быть указателем на первую структуру в списке. После этого функция переходит к следующему элементу, на который указывает указатель в поле next . Процесс прекращается, когда next равно нулю.

Для получения элемента из списка нужно просто пройти по цепочке ссылок. Ниже приведен пример функции поиска по содержимому поля name :

Поскольку функция search() возвращает указатель на элемент списка, содержащий искомое имя, возвращаемый тип описан как указатель на структуру address . При отсутствии в списке подходящих элементов возвращается нуль ( NULL ).

Удаление элемента из односвязного списка выполняется просто. Так же, как и при вставке, возможны три случая: удаление первого элемента, удаление элемента в середине, удаление последнего элемента. На рис. 22.4 показаны все три операции.

Рис. 22.4. Удаление элемента из односвязного списка

Ниже приведена функция, удаляющая заданный элемент из списка структур address .

Функции sldelete() необходимо передавать указатели на удаляемый элемент, предшествующий удаляемому, а также на первый и последний элементы. При удалении первого элемента указатель на предшествующий элемент должен быть равен нулю ( NULL ). Данная функция автоматически обновляет указатели start и last , если один из них ссылается на удаляемый элемент.

У односвязных списков есть один большой недостаток: односвязный список невозможно прочитать в обратном направлении. По этой причине обычно применяются двусвязные списки.

[1] Не забывайте, что у односвязного списка, как и у веревки, два конца: начало и конец.

[2] Часто называется еще сигнальной меткой .

Введение

В стандартную библиотеку C++ входит немало основных структур данных. Среди которых вы найдете списки, стеки, очереди, множества и другие. Но чтобы эффективно пользоваться ими, вы должны хорошо представлять особенности их работы. Речь пойдет об одной из базовых структур: односвязном списке.

Реклама

Односвязные списки в теории

Чтобы понять, как строится односвязный список, представьте себе цепь. У цепи есть начало и конец, а также звенья, которые последовательно соединяются друг с другом. Вы легко можете пройти от начала цепи до ее конца, переходя последовательно от одного звена к другому:

Именно так и работают односвязные списки. Начало списка называют головным элементом, а звенья — узлами. Конец списка определяется с помощью специального узла ( NULL ). При этом на каждый узел "вешают" значение, чтобы структура была полезной:

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

Реклама

Интерфейс класса односвязного списка

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

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

Узел определяется с помощью структуры Node , которая содержит два поля: m_t — значение, привязанное к узлу, и m_next — указатель на следующий узел.

Изначально список пуст, поэтому головной элемент указывает на NULL :

Добавление элемента в односвязный список

Добавление узла в односвязный список осуществляется в самое начало. Добавленный узел сам станет новым головным элементом списка:

Удаление элемента из односвязного списка

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

Список является динамической структурой. При добавлении новых узлов выделяется память из кучи, которую нужно освободить, чтобы не создавать утечек памяти. Имея функцию удаления элементов, реализовать деструктор односвязного списка совсем не сложно:

Итератор односвязного списка

Функциональность для добавления/удаления узлов в список лучше не смешивать с задачей его обхода. Для этого существуют итераторы. Создадим итератор односвязного списка в стиле C++. Вернемся к его определению, которое ранее пропустили:

В качестве итераторов для начала и конца списка вернем следующее:

Теперь список легко можно обойти от начала до конца. Но не забудем про функцию для вычисления его длины. Воспользуемся механизмом итераторов, чтобы упростить задачу:

Заключение

Учитывайте, что рассмотренный пример является лишь краткой демонстрацией принципов работы с односвязным списком в C++. В реальных программах практически всегда лучше использовать стандартную библиотечную реализацию списка и любой другой структуры данных. Тогда вам не только потребуется делать меньше работы, но вы получите в распоряжение хорошо отлаженную и оптимизированную версию, которой сможете смело пользоваться.

Каждый узел однонаправленного (односвязного) линейного списка (ОЛС) содержит одно поле указателя на следующий узел. Поле указателя последнего узла содержит нулевое значение (указывает на NULL).

Узел ОЛС можно представить в виде структуры

Основные действия, производимые над элементами ОЛС:

• Инициализация списка
• Добавление узла в список
• Удаление узла из списка
• Удаление корня списка
• Вывод элементов списка
• Взаимообмен двух узлов списка

Инициализация ОЛС

Инициализация списка предназначена для создания корневого узла списка, у которого поле указателя на следующий элемент содержит нулевое значение.

Добавление узла в ОЛС

Функция добавления узла в список принимает два аргумента:

• Указатель на узел, после которого происходит добавление
• Данные для добавляемого узла.

Процедуру добавления узла можно отобразить следующей схемой:

Добавление узла в ОЛС включает в себя следующие этапы:

• создание добавляемого узла и заполнение его поля данных;
• переустановка указателя узла, предшествующего добавляемому, на добавляемый узел;
• установка указателя добавляемого узла на следующий узел (тот, на который указывал предшествующий узел).

Таким образом, функция добавления узла в ОЛС имеет вид:

Возвращаемым значением функции является адрес добавленного узла.

Удаление узла ОЛС

В качестве аргументов функции удаления элемента ОЛС передаются указатель на удаляемый узел, а также указатель на корень списка.
Функция возвращает указатель на узел, следующий за удаляемым.

Удаление узла может быть представлено следующей схемой:

Удаление узла ОЛС включает в себя следующие этапы:

• установка указателя предыдущего узла на узел, следующий за удаляемым;
• освобождение памяти удаляемого узла.

Удаление корня списка

Функция удаления корня списка в качестве аргумента получает указатель на текущий корень списка. Возвращаемым значением будет новый корень списка — тот узел, на который указывает удаляемый корень.

Вывод элементов списка

В качестве аргумента в функцию вывода элементов передается указатель на корень списка.
Функция осуществляет последовательный обход всех узлов с выводом их значений.

Взаимообмен узлов ОЛС

В качестве аргументов функция взаимообмена ОЛС принимает два указателя на обмениваемые узлы, а также указатель на корень списка. Функция возвращает адрес корневого элемента списка.

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

• заменяемые узлы являются соседями;
• заменяемые узлы не являются соседями, то есть между ними имеется хотя бы один элемент.

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

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

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

Функция взаимообмена узлов списка выглядит следующим образом:

#include
#include
using namespace std;

struct node
<
double value;
node *next = NULL ;
>;

struct stack
<
node *head = NULL ;
> stck;

void add( double value)
<
node *n = new node();
n->value = value;
n->next = stck.head;
stck.head = n;
>
double get()
<
if (stck.head)
<
double output = stck.head->value;
stck.head = stck.head->next;
return output;
>
else
return 0;
>

void parse_string(string str)
<
int i = 0;
string tmp = "" ;
while (str[i] != ‘’)
<
if (str[i] != ‘ ‘)
<
switch (str[i])
<
case ‘+’:
add(get() + get());
break ;
case ‘-‘:
add(get() — get());
break ;
case ‘*’:
add(get() * get());
break ;
case ‘/’:
add(get() / get());
break ;
default:
tmp += str[i];
break ;
>
>
else if (tmp != "" )
<
add(stod(tmp.c_str()));
tmp = "" ;
>
i++;
>
printf( "Answer is: %f
" , get());
>
int main()
<
string str;
while (true)
<
stck.head = NULL ;
cout "Enter exspression (‘E’ to exit)
" ;
getline (cin, str);
if (str[0] == ‘E’)
return 0;
else
<
parse_string(str);
>
>
return 0;
>

struct Elem
<
int key;
Elem *next;
>;

bool AddtoTail( int key, Elem **list)
<
Elem *ptr = new Elem;
if (ptr)
<
ptr->key = key;
ptr->next = NULL ;
if (list == NULL )
<
*list = ptr;
return true;
>
else
<
Elem *p = new Elem;
p = *list;
while (p->next)
p = p->next;
p->next = ptr;
return true;
>
>
return false;
>

struct Node <
Node* next;
int data;
>;

void push_back(Node **head, Node **last, int data) <
Node *node = new Node;
node->next = NULL ;
node->data = data;
if (*last != NULL )
(*last)->next = node;
*last = node;
if (*head == NULL )
*head = *last;
>

void print(Node *head) <
while (head != NULL ) <
std::cout int main() <
Node *head = NULL , *last = NULL ;
for ( int i = 0; i return 0;
>

#include "stdafx.h"
#include "stdio.h"
#include "locale.h"
#include "stdlib.h"
typedef struct Node <
int value;
struct Node *next;
>Node;

void push( struct Node** head, int num)
<
struct Node* current = *head;
Node *newNode = (Node*)malloc( sizeof ( struct Node));
newNode->value = num;
newNode->next = NULL ;
if (current == NULL ) <
*head = newNode;
>

else <
while (current->next != NULL ) <
current = current->next;
>
current->next = newNode;
>
>

void printFromHead( const Node* list) <
if (list) <
printf( "%d " , list->value);
printFromHead(list->next);
>
>
void main()
<
setlocale(LC_ALL, "ukr" );
int x, z;
Node *head = NULL ;
printf( "Вкажiть розмiр списку — " );
if ((scanf( "%d" , &x)) != 1) <
printf( "Неверное введенное значение" );
>
printf( "
" );
for ( int i = 0; i "
" );
printFromHead(head);
printf( "
" );
system( "pause" );
>

Enter_Critical();
p = lst->ptr; // сохранение указателя на следующий узел
lst->ptr = temp; // предыдущий узел указывает на создаваемый
temp->field = number; // сохранение поля данных добавляемого узла
temp->ptr = p; // созданный узел указывает на следующий элемент

//Поток 1
// тут какой-то код
last_element = find_last_elem(root); // Получаем указатель на последний элемент
addelem(last_elem, number); // добавляем новый элемент в конец списка
// тут какой-то код

//Поток 2
// тут какой-то код
last_element = find_last_elem(root); // Получаем указатель на последний элемент
addelem(last_elem, number); // добавляем новый элемент в конец списка
// тут какой то код

//Поток 1
temp = ( struct list*)malloc( sizeof (list));
p = lst->ptr; // сохранение указателя на следующий узел, в нашем случае он последний p = NULL

// Уупс! Исполнение переключилось на поток 2 никто не гарантирует, что этого не может случиться именно в этом месте

// поток 2 — теперь мы в потоке 2

// нашли последний элемент списка — это (какая неожиданность !!) элемент 3, т.к. мы просто не успели переназначить //указатели
// теперь мы вошли в функцию addelem() повторно

temp = ( struct list*)malloc( sizeof (list));
p = lst->ptr; // сохранение указателя на следующий узел, это NULL
lst->ptr = temp; // предыдущий узел указывает на создаваемый, теперь это элемент 4
temp->field = number; // сохранение поля данных добавляемого узла
temp->ptr = p; // созданный узел указывает на следующий элемент, в нашем случае NULL
return (temp);

// вернулись в функцию потока 2
// у нас должен быть следующий список root => elem1 => elem2 => elem3 => elem4 => NULL
// выполняем какой-то код потока 2
// упс. опять переключение на поток 1.

// Поток 1
// Продолжаем с того места на котором прервались

// lst у нас по-прежнему указывает на element 3, хотя это уже не последний элемент списка.
lst->ptr = temp; // предыдущий узел указывает на создаваемый, но это не элемент 4 добавленный в потоке 2
// таким образом указатель на элемент 4, созданный в потоке 2 затирается
temp->field = number; // сохранение поля данных добавляемого узла
temp->ptr = p; // созданный узел указывает на следующий элемент
return (temp);

// возврат в функцию потока 1, выполняем какой-то код потока 1