Поменять место в одиночном списке в C

Question

Мне дано задание создать различные методы для связанного списка в C. Я застрял в методе подкачки, который, кажется, испортил весь связанный список. Есть ли у кого-нибудь совет, где я ошибаюсь? Ура!

Вот мой код.

int main(int argc, char* argv[]) 
{ 
    // A list of pointers to Reminders 
    const int MAX_ENTRIES = 10; 
    int numOfEntries = 0 ; 
    reminder_t* pFirst = (reminder_t*) malloc (sizeof(reminder_t)); 
    reminder_t* pSecond = (reminder_t*) malloc (sizeof(reminder_t)); 
    reminder_t* pThird = (reminder_t*) malloc (sizeof(reminder_t)); 
    reminder_t* pStart = NULL; 
    if (pFirst != NULL) 
    { 
     strcpy(pFirst->message, "Mikes Birthday"); 
     pFirst->dateOfEvent.day= 1; 
     pFirst->dateOfEvent.month= 1; 
     pFirst->dateOfEvent.year= 2013; 
     pFirst->pNext = NULL; 
    } 

    if (pSecond != NULL) 
    { 
     strcpy(pSecond->message, "Als Soccer Match"); 
     pSecond->dateOfEvent.day= 2; 
     pSecond->dateOfEvent.month= 2; 
     pSecond->dateOfEvent.year= 2013; 
     pSecond->pNext = NULL; 
    } 

    if (pThird != NULL) 
    { 
     strcpy(pThird->message, "School Concert"); 
     pThird->dateOfEvent.day= 3; 
    pThird->dateOfEvent.month= 3; 
    pThird->dateOfEvent.year= 2013; 
    pThird->pNext = NULL; 
} 

pFirst->pNext = pSecond; 
pSecond->pNext = pThird; 
pThird->pNext = NULL; 
pStart = pFirst; 

printf("\n------Before------\n"); 
listEntries(pStart); 
swapPositonOf(pFirst,pThird); 

printf("\n------After-aa-----\n"); 
listEntries(pStart); 

getchar(); 
return 0; 
} 

void listEntries(reminder_t * pList) 
{ 
    printf("\n"); 
    while (pList != NULL) 
    { 
      printf("%s\n", pList->message); 
     pList = pList->pNext; 
    } 
} 

void swapPositonOf(reminder_t* first , reminder_t* second) 
{ 
    reminder_t* pFirst = (reminder_t*) first; 
reminder_t* pSecond = (reminder_t*) second; 
reminder_t* temp = second->pNext; 

pSecond->pNext = pFirst->pNext; 
pFirst->pNext = temp; 
temp = pSecond; 
pSecond = pFirst; 
pFirst = temp; 
} 

Ожидаемый результат:

------Before------ 

Mikes Birthday 
Als Soccer Match 
School Concert 

------After-aa----- 
School Concert 
Als Soccer Match  
Mikes Birthday 

Выход:

------Before------ 

Mikes Birthday 
Als Soccer Match 
School Concert 

------After-aa----- 

Mikes Birthday 

Answer 1

Если вы хотите поменять содержание из список узлов, то это не сложно: вы можете просто сделать своп для полей message и dateOfEvent в двух узлах.

Но если вы хотите поменять позиции этих узлы (как имя функции предполагает), то вы должны обратить внимание на член pNext данных.
На самом деле, просто менять указатели узлов недостаточно.
Вы должны найти положение узлов перед темfirst и last, и сделать что-то вроде:

/* reminder_t* beforeFirst, reminder_t* beforeSecond */ 
beforeFirst->pNext = second; 
beforeSecond->pNext = first; 

и обмена first->pNext и second->pNext.

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

Answer 2

Вы не изменяя pNext указатель для узлов непосредственно перед first и second узлы.

Вам необходимо указать pNext узла, предшествующего «first узел», на «second узел» и наоборот.

Пусть связанный список:

Node_A -> Node_B -> Node_C -> Node_D -> Node_E

Вы должны поменять Node_B и Node_D:
Всего ссылки на сломаться и форму:

1. Старой ссылка: Node_A -> Node_B .... Новой Ссылка: Node_A -> Node_D
2. Старая ссылка: Node_B -> Node_C .... Новая ссылка: Node_D -> Node_C
3. Старая Ссылка: Node_C -> Node_D .... New Link: Node_C -> Node_B
4. Старая Ссылка: Node_D -> Node_E .... New Link: Node_B -> Node_E

Также помните, угловые случаи, как NULL указателей и последовательные узлы.

Answer 3

Вы не меняете его правильно, а как насчет узла ПЕРЕД первым узлом и узлом ПЕРЕД вторым узлом?

Answer 4

С односвязным списком вы не можете напрямую найти элемент списка, предшествующий элементу, который хотите поменять местами. У вас есть первое, второе, и вы можете напрямую манипулировать ими, но у вас нет first.prev и second.prev.

Вам необходимо пройти ваш список и найти узлы, которые предшествуют двум узлам, которые вы хотите поменять местами (first_previous, second_previous). Затем вам необходимо заменить swap на следующий из этих предыдущих узлов.

reminder_t* first_prev, *second_prev; 
first_prev = second_prev = pStart; 
reminder_t* iter; 
for(iter = pStart; iter; iter=iter->next) 
{ 
    if(iter->next == first) first_prev = iter; 
    if(iter->next == second) second_prev = iter; 
} 

Вам нужно будет исправить выше обрабатывать пустой список, один список элементов, и проходит первый или второй в главе списка ...