Однозв’язний лінійний список

Прошу пробачити великодушно за мою настирливість, але дозволю собі позначити ще одне джерело потенційних проблем. Якщо розглядати многопоточную середу виконання, то всі дані функції не мають властивість реєнтерабельним, тобто НЕ потокобезпечна. У тому плані, що процедура скріплення або видалення вузлів списку повинна бути атомарної операцією, тобто код в тій частині, де виконуються маніпуляції над покажчиками і полями даних повинен бути розташований в критичній секції, щось типу

p = lst-> ptr; // збереження покажчика на наступний вузол
lst-> ptr = temp; // попередній вузол вказує на створюваний
temp-> field = number; // збереження поля даних додається вузла
temp-> ptr = p; // створений вузол вказує на наступний елемент

Розглянемо такий приклад. Нехай наш список складається з 3-х елементів:

root => elem1 => elem2 => elem3 => NULL

Припустимо існує два паралельні потоки (завдання, нитки і т.д. на різних платформах це називається по-різному, але суті не міняє), в яких ми хочемо додати елемент в кінець списку (далі псевдокод в порядку його виконання в часі)

// Потік 1
// тут якийсь код
last_element = find_last_elem (root); // Отримуємо покажчик на останній елемент
addelem (last_elem, number); // додаємо новий елемент до кінця списку
// тут якийсь код

// Потік 2
// тут якийсь код
last_element = find_last_elem (root); // Отримуємо покажчик на останній елемент
addelem (last_elem, number); // додаємо новий елемент в кінець списку
// тут якийсь код

нехай в даний момент потік 1 виповнюється і ми отримали покажчик на останній елемент списку, в нашому випадку це елемент 3, а потім викликали функцію addelem (), яка починає виконуватися:

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

Отже, підсумовуючи, ми бачимо. Ми бачимо, що в поле ptr елемента 3 покажчик на елемент 4, доданий в кінець списку в потоці 2, затирається старим значенням в потоке1, а сам він безповоротно втрачається. Крім втрати самого елемента, це створює небезпечну ситуацію витоку пам'яті, тому що покажчик на елемент 4 створений в потоці 2 безповоротно втрачено, і ми ніяк вже не зможемо звільнити пам'ять виділену під нього.

Добрий день. Дякую за гарну статтю. Застосовую Ваш метод перестановки двох ланок, щоб поміняти мінімум і максимум у списку. Для знаходження ланок використовую інші функції. На даний момент все працює, але тільки якщо ланки в середині, тобто не перше і не останнє. Причому неважливо, поруч елементи чи ні. Порадьте, яке умова написати для обох варіантів, щоб все працювало. Заздалегідь дякую.

void switchMinMax (Node * head) Node * prevMax * prevMin * postMax * postMin * tmp;
Node * Max, * Min;
Max = getMax (head);
Min = getMin (head);

prevMax = head;
prevMin = head;
if (prevMax == Max)
prevMax = NULL;
else
while (prevMax-> next! = Max)
prevMax = prevMax-> next;
if (prevMin == Min)
prevMin = NULL;
else
while (prevMin-> next! = Min)
prevMin = prevMin-> next;
postMax = Max-> next;
postMin = Min-> next;
if (Min == postMax)
Min-> next = Max;
Max-> next = postMin;
if (Max! = head)
prevMax-> next = Min;
if (Max == head)
prevMin = NULL;
>
else if (Max == postMin)
Max-> next = Min;
Min-> next = postMax;
if (Min! = head)
prevMin-> next = Min;
if (Min == head)
prevMax == NULL;
>
else
if (Max! = head)
prevMax-> next = Min;
Min-> next = postMax;
if (Min! = head)
prevMin-> next = Max;
Max-> next = postMin;
>
>

Добридень! Може хто допоможе, не виходить ніяк вирішити задачу такого типу, потрібно сформувати стек чисел і занести в новий список до максимуму з першого стека - списку. Моє рішення, все працює, крім копіювання в новий список. ось сама функція запису (стек вже заповнений)

Потрібно в циклі визначити максимальний елемент і запам'ятати його покажчик.

struct Stack * maxelem = begin;
int max = maxelem-> number;
while (temp! = NULL) if ((temp-> number)> max) maxelem = temp;
max = (temp-> number);
>
temp = temp-> next;
>

Тільки після цього, коли ми знаємо максимальний елемент і покажчик на нього, можна формувати новий список.

Велике спасибі за швидку відповідь. напевно, я щось не зрозумів, визначив покажчик на макс елемент, заніс в новий список значення, але на консолі не відображається. Чи не могли б ви подивитися, дуже вдячний вам за допомогу.

Помилка в виділеної сходинці. Ви зациклюватися покажчик на сам елемент. Поле покажчика на наступний елемент потрібно форматувати в момент створення цього «наступного» елемента.

struct Stack * new_list = (struct Stack *) malloc (sizeof (struct Stack));
new_list-> number = begin-> number; // це корінь нового списку
new_list-> next = NULL;
while (temp2! = maxelem) struct Stack * temp3 = new_list;
new_list = (struct Stack *) malloc (sizeof (struct Stack));
new_list-> number = temp2-> number;
temp3-> next = new_list;
new_list-> next = NULL;
temp2 = temp2-> next;
>

У функцію addelem () Ви передаєте покажчик на елемент, після якого необхідно здійснити додавання. Покажчик кореня списку при цьому повинен бути збережений в інший змінної, і виведення списку необхідно здійснювати з кореня.

У цьому випадку потрібна функція, яка буде додавати елемент в початок списку, на зразок цієї

struct list * addroot (list * root, int number) struct list * temp;
temp = (struct list *) malloc (sizeof (list));
temp-> ptr = root; // створюваний вузол на попередній корінь
temp-> field = number; // збереження поля даних додається вузла
return (temp); // повертаємо новий корінь списку
>