Каждый узел однонаправленного (односвязного) линейного списка (ОЛС) содержит одно поле указателя на следующий узел. Поле указателя последнего узла содержит нулевое значение (указывает на NULL).
Узел ОЛС можно представить в виде структуры
{
int field; // поле данных
struct list *ptr; // указатель на следующий элемент
};
Основные действия, производимые над элементами ОЛС:
- Инициализация списка
- Добавление узла в список
- Удаление узла из списка
- Удаление корня списка
- Вывод элементов списка
- Взаимообмен двух узлов списка
Инициализация ОЛС
Инициализация списка предназначена для создания корневого узла списка, у которого поле указателя на следующий элемент содержит нулевое значение.
2
3
4
5
6
7
8
9
{
struct list *lst;
// выделение памяти под корень списка
lst = (struct list*)malloc(sizeof(struct list));
lst->field = a;
lst->ptr = NULL; // это последний узел списка
return(lst);
}
Добавление узла в ОЛС
Функция добавления узла в список принимает два аргумента:
- Указатель на узел, после которого происходит добавление
- Данные для добавляемого узла.
Процедуру добавления узла можно отобразить следующей схемой:
Добавление узла в ОЛС включает в себя следующие этапы:
- создание добавляемого узла и заполнение его поля данных;
- переустановка указателя узла, предшествующего добавляемому, на добавляемый узел;
- установка указателя добавляемого узла на следующий узел (тот, на который указывал предшествующий узел).
Таким образом, функция добавления узла в ОЛС имеет вид:
2
3
4
5
6
7
8
9
10
{
struct list *temp, *p;
temp = (struct list*)malloc(sizeof(list));
p = lst->ptr; // сохранение указателя на следующий узел
lst->ptr = temp; // предыдущий узел указывает на создаваемый
temp->field = number; // сохранение поля данных добавляемого узла
temp->ptr = p; // созданный узел указывает на следующий элемент
return(temp);
}
Возвращаемым значением функции является адрес добавленного узла.
Удаление узла ОЛС
В качестве аргументов функции удаления элемента ОЛС передаются указатель на удаляемый узел, а также указатель на корень списка.
Функция возвращает указатель на узел, следующий за удаляемым.
Удаление узла может быть представлено следующей схемой:
Удаление узла ОЛС включает в себя следующие этапы:
- установка указателя предыдущего узла на узел, следующий за удаляемым;
- освобождение памяти удаляемого узла.
2
3
4
5
6
7
8
9
10
11
12
{
struct list *temp;
temp = root;
while (temp->ptr != lst) // просматриваем список начиная с корня
{ // пока не найдем узел, предшествующий lst
temp = temp->ptr;
}
temp->ptr = lst->ptr; // переставляем указатель
free(lst); // освобождаем память удаляемого узла
return(temp);
}
Удаление корня списка
Функция удаления корня списка в качестве аргумента получает указатель на текущий корень списка. Возвращаемым значением будет новый корень списка - тот узел, на который указывает удаляемый корень.
2
3
4
5
6
7
{
struct list *temp;
temp = root->ptr;
free(root); // освобождение памяти текущего корня
return(temp); // новый корень списка
}
Вывод элементов списка
В качестве аргумента в функцию вывода элементов передается указатель на корень списка.
Функция осуществляет последовательный обход всех узлов с выводом их значений.
2
3
4
5
6
7
8
9
{
struct list *p;
p = lst;
do {
printf("%d ", p->field); // вывод значения элемента p
p = p->ptr; // переход к следующему узлу
} while (p != NULL);
}
Взаимообмен узлов ОЛС
В качестве аргументов функция взаимообмена ОЛС принимает два указателя на обмениваемые узлы, а также указатель на корень списка. Функция возвращает адрес корневого элемента списка.
Взаимообмен узлов списка осуществляется путем переустановки указателей. Для этого необходимо определить предшествующий и последующий узлы для каждого заменяемого. При этом возможны две ситуации:
- заменяемые узлы являются соседями;
- заменяемые узлы не являются соседями, то есть между ними имеется хотя бы один элемент.
При замене соседних узлов переустановка указателей выглядит следующим образом:
При замене узлов, не являющихся соседними переустановка указателей выглядит следующим образом:
При переустановке указателей необходима также проверка, является ли какой-либо из заменяемых узлов корнем списка, поскольку в этом случае не существует узла, предшествующего корневому.
Функция взаимообмена узлов списка выглядит следующим образом:
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
{
// Возвращает новый корень списка
struct list *prev1, *prev2, *next1, *next2;
prev1 = head;
prev2 = head;
if (prev1 == lst1)
prev1 = NULL;
else
while (prev1->ptr != lst1) // поиск узла предшествующего lst1
prev1 = prev1->ptr;
if (prev2 == lst2)
prev2 = NULL;
else
while (prev2->ptr != lst2) // поиск узла предшествующего lst2
prev2 = prev2->ptr;
next1 = lst1->ptr; // узел следующий за lst1
next2 = lst2->ptr; // узел следующий за lst2
if (lst2 == next1)
{ // обмениваются соседние узлы
lst2->ptr = lst1;
lst1->ptr = next2;
if (lst1 != head)
prev1->ptr = lst2;
}
else
if (lst1 == next2)
{
// обмениваются соседние узлы
lst1->ptr = lst2;
lst2->ptr = next1;
if (lst2 != head)
prev2->ptr = lst2;
}
else
{
// обмениваются отстоящие узлы
if (lst1 != head)
prev1->ptr = lst2;
lst2->ptr = next1;
if (lst2 != head)
prev2->ptr = lst1;
lst1->ptr = next2;
}
if (lst1 == head)
return(lst2);
if (lst2 == head)
return(lst1);
return(head);
}
