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

Question

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

Рейтинг: 1Ответов: 2Опубликовано: 07.12.2014

Есть структура:

typedef struct TSotrudnik {
    //информационные поля
    BigDATA ob;
    TSotrudnik *next; //указатель на след элемент
}TSotrudnik;

На основе структуры был создан односвязный список list на С++, список зацикленный, т.е. последний элемент указывает на первый. Нужно написать процедуру для перестановки элементов списка местами. Подскажите, пожалуйста, как это можно сделать? Я уже запутался, постоянно что-нибудь не учитываю, и процедура работает некорректно. При перестановке нужно не перезаписывать BigDATA, а изменять указатели.

c# алгоритм список

Источник: Stack Overflow на русском

Answer 1

▲ 1

Если у вас есть указатели на ссылку на сотрудника, идущую из предыдущего элемента, покатит такое:

TSotrudnik* remove_by_link(TSotrudnik** pLink)
{
    TSotrudnik* item = *pLink;
    *pLink = item->next;
    item->next = NULL;
    return item;
}

void insert_by_link(TSotrudnik** pLink, TSotrudnik* item)
{
    item->next = *pLink;
    *pLink = item;
}

void swap(TSotrudnik** pFirstLink, TSotrudnik** pSecondLink)
{
    int secondFollwsFirst = pSecondLink == &((*pFirstLink)->next);
    int firstFollowsSecond = pFirstLink == &((*pSecondLink)->next);
    if (secondFollowsFirst && firstFollowsSecond)
        return;
    if (secondFollowsFirst)
        pSecondLink = pFirstLink;
    if (firstFollowsSecond)
        pFirstLink = pSecondLink;

    TSotrudnik* pFirst = remove_by_link(pFirstLink);
    TSotrudnik* pSecond = remove_by_link(pSecondLink);

    insert_by_link(pSecondLink, pFirst);
    insert_by_link(pFirstLink, pSecond);
}

Двойные указатели важны.

(А вообще, TEmployee, а не TSotrudnik, конечно.)

Answer 2

▲ 1

Если все элементы списка разные, то тривиально.

Обходите весь свой циклический список и запоминаете адреса структур у которых next ссылается на элементы, которые надо менять местами.

 swap(TSotrudnik *p1, TSotrudnik *p2) {
   TSotrudnik *pp1 = p1, *pp2 = 0, t1 = p1->next, t2 = p2->next;
   while (pp1->next != p1) {
     if (pp1->next == p2)
       pp2 = pp1;
     pp1 = pp1->next;
   }
   if (pp2) {
     pp1->next = p2; 
     pp2->next = p1;
     p1->next = t2; 
     p2->next = t1;
   }
 }

Не проверял, надеюсь нигде не ошибся.

Update

Спасибо @Vlad, за обнаруженную ошибку. Действительно, приходится рассматривать частные случаи. Вот что получилось.

void  swap(node *p1, node *p2) {
  node *pp1 = p1, *pp2 = 0;

  if (p1 && p2 && // элементы присутствуют
      p1 != p2 && // это разные элементы
      !(p1->next->next == p1)) { // в списке больше двух
    while (pp1->next != p1) {
      if (pp1->next == p2)
        pp2 = pp1;
      pp1 = pp1->next;
    }

    if (pp2) {
      if (p1->next == p2) {
        p1->next = p2->next;
        p2->next = p1;
        pp1->next = p2;
      } else if (p2->next == p1) {
        p2->next = p1->next;
        p1->next = p2;
        pp2->next = p1;
      } else {
        node *t = p1->next;
        p1->next = p2->next; 
        p2->next = t;
        pp1->next = p2; 
        pp2->next = p1;
      }
    } else 
      puts("p2 not in p1 list");
  }

}

Надеюсь, что теперь будет работать правильно.

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

Ответы