Функция связанного списка?

Question

Итак, я пишу эту функцию, которая делает наименьший узел в конце связанного списка. До сих пор он работает, за исключением последнего элемента. если связанный список создается как узлы, содержащие элементы из 0 ~ 9, список после этой функции равен {1,2,3,4,5,6,7,8,0,9}, а нуль не становится на конец.

Любые идеи, почему?

моя функция;

int connecting(linkk A) 
{ 
    linkk L = A; 
    for (int i = 0; i<sizeof(L);i++) 
    { 
     if (L->item < L->next->item) 
     { 
      int a = L->item; 
      L->item = L->next->item; 
      L->next->item = a; 
      L = L->next; 
     } 
     else{L=L->next;} 
    } 
    return 0; 
} 

Answer 1

Давайте начнем с того, что я думаю, что вы должны делать по-другому:

1. Название вашей функции connecting. Учитывая описание функции, которую вы хотите выполнить, это не хорошее имя.
2. Я могу заключить, что linkk является указателем typedef'ed. Скрывать указатели таким образом не очень хорошая идея, большую часть времени.
3. Ваша функция возвращает int. Это всегда 0. Зачем? Это не имеет никакого смысла.
4. Потому что linkk, вероятно, является указателем на узел, и вы передаете указатель головы по значению (т. Е. Его копию) в функцию, вы не можете справиться с тем случаем, когда глава вашего списка является минимальным. Либо верните «новый» указатель на голову, либо передайте указатель на указатель головы, чтобы иметь возможность изменять указатель на голову.
5. Ваше использование sizeof совершенно неверно, как уже было предложено. sizeof(L) даст вам размер (в char) указателя, таким образом, вероятно, 8 на 64-битной системе или 4 на 32-битной системе.
6. Вы не меняете узлы, а перемещаете значения между узлами. Это нормально, если это то, что вы хотите сделать, но описание вашего алгоритма предполагает, что вы хотите переместить узел вместо этого.
7. Ваша функция делает слишком много, ИМО. Это может быть трудно разделить, но лучше всего будет отделить поиск/извлечение минимума и поместить его в конец списка.
8. Вы изменяете намного больше, чем вы хотели. Рассмотрим список, подобный 1, 2, 3, 0, 4. Используя ваш алгоритм, список будет изменен на 2, 3, 1, 4, 0. Это не только плохо для производительности, но и очень удивительно для вызывающего. Сюрпризы не хороши, когда дело доходит до программирования!

Итак, давайте перейдем к надеемся, хорошей реализации, шаг за шагом:

struct node { 
    int item; 
    struct node * next; 
}; 

Я предполагаю, что вы хотите, чтобы переместить узел, содержащий минимальное значение до конца списка, как в вашем описание. Я также собираюсь сохранить это в единственной функции, получая указатель struct node * head, несмотря на мою точку выше, чтобы приблизиться к исходному коду. Давайте сначала рассмотрим специальные/базовые случаи: перемещение элемента минимума пустого списка, а также списка отдельных элементов тривиально: ничего не делать.

if (head == NULL || head->next == NULL) { 
    return head; 
} 

Я возвращаюсь «новый» голову списка, чтобы позволить абоненту обновить свою собственную голову указатель.(Как уже было сказано, head - это всего лишь копия указателя головы вызывающего, изменение его не будет иметь никакого эффекта на сайте вызова).

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

struct node * follow, * point; 

follow следует непосредственно за point.

Первоначально мы помещаем точку во второй узел списка (мы уже проверили, что в списке есть не менее 2 узлов). follow таким образом указывают на голове:

point = head->next; 
follow = head; 

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

int currentMinimum = head->item; 

Теперь мы готовы перебрать список, чтобы найти узел, содержащий минимум. Но нам нужно не только найти узел, содержащий минимум, но и тот, который был перед ним, и тот, который после него, чтобы иметь возможность легко извлечь его. Итак, 3 указателя:

struct node * предшественник, * минимальный, * преемник;

Как мы установили currentMinimum к head s деталь, мы должны также установить указатели соответственно:

predecessor = NULL; // Nothing preceding the head 
minimum = head; 
successor = head->next; 

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

while (point != NULL) { 
    // to be continued 
    follow = point; 
    point = point->next; 
} 
// when we're here, follow will point to the last node 

в каждой итерации, мы должны проверить, если мы нашли меньшее значение, чем текущий минимум, и в конечном счете помните узел, содержащий его:

if (point->item < currentMinimum) { 
    predecessor = follow; 
    minimum = point; 
    successor = point->next; 
    currentMinimum = point->item; 
} 

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

• minimum указывает на узел, содержащий минимум.
• follow указывает на последний узел списка.
• Два вышеуказанных могут быть одинаковыми, что является особым случаем!
• predecessor все еще может быть NULL, который является другим особым случаем!

Учитывая первый случай minimum = follow: В этом случае минимум уже в конце списка, так что прибыль! В противном случае, нам нужно «вырезать» узел в minimum из списка и добавить его в последний узел, на который указывает follow:

if (follow != minimum) { 
    if (predecessor != NULL) { 
    predecessor->next = successor; // Cut out 
    minimum->next = NULL; // will be the last node 
    follow->next = minimum; // append at end 
    } else { 
    // to be continued 
    } 
} 

Как вы можете видеть, есть второй частный случай для рассмотрения: Если predecessor по-прежнему NULL, тогда ни один товар не был меньше head s item.(Поэтому мы могли бы также проверить на minimum == head) Таким образом, первый узел списка будет перенесен в конец. Об этом нужно сообщить об этом!

head = head->next; // Second node is now the first one, though this is not all we need to do, see further down! 
minimum->next = NULL; // Will be the last node 
follow->next = minimum; // Append at end 

Поскольку назначение head только изменил параметр функции (который является копией указателя, с которой функция была вызвана), мы должны вернуть (возможно, модифицированную!) Указатель головы, давая абоненту возможность обновить свой собственный указатель головы:

return head; 

абонент, таким образом, использовать эту функцию следующим образом:

struct node * head = get_a_fancy_list(); 
head = move_minimum_to_end(head); // This is our function being called! 

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

Перемещение элемента вместо узла, содержащего элемент, значительно проще. Прежде всего, мы должны следить за минимальной (значение, а также узел):

Для итерацию, мы снова будем использовать два указателя. Это может быть сделано с одним, но кодом будет более удобным для чтения таким образом:

struct node * point, * follow; 

Мы начнем с тем же начальным состоянием:

minimum = head; 
currentMinimum = head->item; 
follow = head; 
point = head->next; 

Итерация похожа на другой реализация, как это шаг итерации:

while (point != NULL) { 
    if (point->item < currentMinimum) { 
    minimum = point; 
    currentMinimum = point->item; 
    } 
    follow = point; 
    point = point->next; 
} 
// follow points to the last node now 

Теперь, делая то же самое, как предыдущую реализацию, мы можем поменять местами пункты последнего узла и узел с минимальным:

minimum->item = follow->item; 
follow->item = currentMinimum; // contains minimum->item 

Там нет смысла в проверке follow != minimum, как и в предыдущем подходе: Вы могли бы это сделать, но замена элемента узла с его собственным пунктом не будет никакого вреда. OTOH, добавив if, добавит ветку и, следовательно, возможную штрафную санкцию.

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

return head; 

Хорошо, это есть немного долго теперь, но, надеюсь, это легко понять!

Answer 2

Попробуйте эту функцию

int connecting(linkk A) 
{ 
linkk L = A; 
    while(L->next!=NULL) 
    { 
    if (L->item < L->next->item) 
    { 
     int a = L->item; 
     L->item = L->next->item; 
     L->next->item = a; 

    } 

    L=L->next; 
    } 
    return 0; 
}