可以通过更改引用来对链表进行排序吗？

Question

我正在尝试通过更改节点的引用，使用冒泡排序算法对链表进行排序。我翻了很多书和在互联网上搜索，但我只找到了从节点之间的信息部分更改值的排序方法。我想要做的是通过更改列表的移动顺序而不是它们之间的值来排序。这是我的代码。 PS: 排序算法不起作用。它不是合并排序列表的副本，因为它完全是另一种算法。

#include <stdio.h>
#include <malloc.h>
#include <string.h>
#include <stdlib.h>
#define LINESIZE 128
struct Student {
    float medie;
    char nrMatricol[10];
    char *nume;
    char facltate[6];
};
struct Nod{
    Student stud;
    Nod* next;
};
Nod* inserareNodEnd(Nod *l,Student st)
{
    Nod *nou = (Nod*)malloc(sizeof(Nod));
    nou->next = NULL;//NOU->NEXT=0
    nou->stud = st;
    if (!l) {
        //lista este goala
        return nou;
    }
    else
    {
     //lista contine un nod
        Nod *t = l;
        while (t->next) {
            t = t->next;
        }
        t->next = nou;
        return l;
    }

}
float medieStudenti(Nod *lista) {
    float suma=0;
    int i=0;
    Nod *aux=lista;
    while (aux->next) {
        aux = aux->next;
        suma += aux->stud.medie;
        i++;
    }
    return suma/i;
}
Nod *stergerePrimulNodLista(Nod *l,Student *st) {
    if (l) {
        Nod *aux = l;
        l = l->next;
        aux->next = NULL;
        *st = aux->stud;
        //aux->next = NULL;
        free(aux);

    }
        return l;
}
Nod* sortareLista(Nod *l) {
    Nod *i=l;
    Nod *j=l;
    Nod *aux=l;
    Nod *min=l;
    min = i;
    while (i->next) {

        if (i->stud.medie < min->stud.medie) {
            min = i;
        }
        i = i->next;

    }
    i = l;
    int n = 0;
    while (i->next) {
        j = i->next;
        while (j->next) {
            if (i->stud.medie > j->stud.medie) {
                aux = i->next;
                i->next = j->next;
                j->next = aux;
            }
            j = j->next;
        }
        i = i->next;
    }

    return min;
    //return l;
}
void dezalocare(Nod *lista) {
    Nod *aux;
    aux = lista;
    while (aux->next) {
        lista = aux->next;
        free(aux->stud.nume);
        free(aux);
        aux = lista;
    }
}
void main()
{
    FILE *f;
    Student s;
    Nod *list=NULL;
    f = fopen("fisier.txt", "r");
    char fileBuff[LINESIZE], SEPARATORI[] = { "," };
    char *token;
    while (fgets(fileBuff, LINESIZE, f)) {
        token = strtok(fileBuff, SEPARATORI);
        strcpy(s.nrMatricol, token);
        //extragere token nume student din aceeasi linie
        //salvata in file Buff
        token = strtok(NULL, SEPARATORI);
        s.nume = (char*)malloc(sizeof(char)*strlen(token) + 1);
        strcpy(s.nume, token);
        token = strtok(NULL, SEPARATORI);
        strcpy(s.facltate, token);
        //extragere tokeni medie si conversia tokenului la float
        token = strtok(NULL, SEPARATORI);
        s.medie = atof(token);
        list = inserareNodEnd(list, s);
        printf("%s %s \n", s.nrMatricol, s.nume);
    }
    Nod *tmp = list;
    while (tmp) {
        printf("\nSe afiseaza din lista");
        printf("%s %s \n", tmp->stud.nrMatricol, tmp->stud.nume);
        tmp = tmp->next;
    }

    fclose(f);
    //determinarea mediei pentru studentii din lista
    float media = medieStudenti(list);
    printf("\nMedia este %.2f", media);
    //sortare lista dupa medie(cu modificarea adreselor de legatura)

    //tema dezalocare lista
    //tema dezalocari la nivel de aplicatie
    printf("\nAcesta este Ionel %s %s \n", s.nrMatricol, s.nume);
//  list = stergerePrimulNodLista(list, &s);
    tmp = list;
    while (tmp) {
        printf("\nSe afiseaza din lista");
        printf("%s %s \n", tmp->stud.nrMatricol, tmp->stud.nume);
        tmp = tmp->next;
    }

     tmp = list;
    while (tmp) {
        printf("\nSe afiseaza  lista sortata");
        printf("%s %s \n", tmp->stud.nrMatricol, tmp->stud.nume);
        tmp = tmp->next;
    }
    dezalocare(list);
  }

Answer 1

应楼主的要求，链表冒泡排序的例子。

更新 - 删除swap，改为使用 pnEnd（指向未排序列表末尾的指针）。

/* bubble sort linked list */

NODE * SortList(NODE *pHead)    /* pHead used as local ptr to start of list */
{
NODE *pEnd = NULL;              /* ptr to end of unsorted part of list */
NODE *pnEnd;                    /* pEnd for next pass */
NODE *pNext;                    /* ptr to next node */
NODE **ppCurr;                  /* ptr to ptr to curr node */
    if(pHead == NULL)           /* return if empty list */
        return pHead;
    do{
        ppCurr = &pHead;        /* set ppCurr to start of list */
        pnEnd = pHead->next;    /* set pnEnd to 2nd node */
        while((pNext = (*ppCurr)->next) != pEnd){
            if((*ppCurr)->data > pNext->data){ /* if out of order swap */
                (*ppCurr)->next = pNext->next;
                pnEnd = pNext->next = *ppCurr;
                *ppCurr = pNext;
            }
            ppCurr = &(*ppCurr)->next;
        }
        pEnd = pnEnd;           /* update pEnd since rest of list is sorted */
    }while(pEnd != pHead->next);
    return pHead;
}

Answer 2

第一：冒泡排序很糟糕。对于链表，就更可怕了…… ["natural" 对链表进行排序的方法是合并排序，因为压缩合并两个已排序的链表很容易]

对于冒泡排序，基本操作是：

{ 比较两个相邻节点，并可能交换它们}
重复此操作，直到没有任何变化。
这意味着最后的通道总是什么都不做。

#include <stdio.h>

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

struct node nodes[] =
{{ nodes+1, 9}
,{ nodes+2, 5}
,{ nodes+3, 0}
,{ nodes+4, 1}
,{ nodes+5, 4}
,{ nodes+6, 7}
,{ nodes+7, 2}
,{ nodes+8, 3}
,{ nodes+9, 8}
,{ NULL   , 6}
        };

void node_printlist(struct node *p) {
for (   ;p; p=p->next) {
        printf("%d\n", p->value);
        }
}

unsigned node_bubblepass(struct node **pp)
{
struct node *one, *two;
unsigned swaps;

for (swaps=0 ; one = *pp; pp=&(*pp)->next) {
        two = one->next;
        if(!two) break;
        if(two->value >= one->value) continue;
                /* wrong order: swap them*/
        one->next = two->next;
        two->next = one;
        *pp = two;
        swaps++;
        }
return swaps;
}

void node_bubblesort(struct node **pp)
{
unsigned swaps;
do      {
        swaps = node_bubblepass(pp);
        } while (swaps);
}

int main(void){
struct node *root =nodes;

printf("Original:\n");
node_printlist(root);

node_bubblesort(&root);

printf("Result:\n");
node_printlist(root);

return 0;
}

UPDATE（感谢@rcgldr）在内循环中，当我们碰到一个之前已经冒泡过的项目时，我们可以停止冒泡。

struct node * node_bubblepass_2(struct node **pp, struct node *end)
{
struct node *one, *two;

for ( ; one = *pp; pp=&(*pp)->next) {
        two = one->next;
        if(two == end) break;
        if(two->value >= one->value) continue;
                /* wrong order: swap them*/
        one->next = two->next;
        two->next = one;
        *pp = two;
        }
return one;
}

void node_bubblesort_2(struct node **pp)
{
 struct node *end = NULL;
do      {
        end = node_bubblepass_2(pp, end);
        } while (*pp != end);
}

可以通过更改引用来对链表进行排序吗？

Can a linked list be sorted by changing the references?

c

sorting

linked-list

bubble-sort