c - 排序简单链表 - C

Question

[最后更新了答案]我尝试了很多方法，但我仍然不知道如何使用简单的链接列表进行任何排序。它应该按照每个节点上保存的数字从低到高的顺序进行排序。我能做些什么？当我保存在列表中时，不允许我对数字进行排序。排序必须在列表完成后进行。

代码尚未完全准备好

#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <string.h>
#define pi 3.14159265359
#define N 50

typedef struct lista{
    char palavra[N];
    int repeticao;
    struct lista *prox;
    } Lista;

Lista* lista_cria(){
    return NULL;
}

    int vazia(Lista *LISTA){
    if(LISTA->prox == NULL) return 1;
    else return 0;
}


void insere(Lista **lis, char *s){
    Lista* novo = (Lista*) malloc (sizeof(Lista));
    strcpy(novo->palavra, s);
    novo->prox = NULL;

    while (*lis)
        lis = &(*lis)->prox;
        *lis = novo;
}

Lista* retira(Lista* lis, char *s){
    Lista* ant = NULL;
    Lista* p = lis;

    while(p != NULL && (strcmp(s, p->palavra) != 0)){
        ant = p;
        p = p->prox;
    }

    if(p == NULL) return lis;
    if(ant == NULL) lis = p->prox;
    else ant->prox = p->prox;

    free(p);
    return lis;
}

void imprimir_lista(Lista* lis){
        Lista* p;
        for(p = lis; p != NULL; p = p->prox)
            printf("%s ", p->palavra);
    printf("\n \n");
}

int busca(Lista* lis, char *s){
        Lista *p;
    int cont = 0;

        for(p = lis; p != NULL; p = p->prox){
        if(strcmp(p->palavra, s) == 0) cont++;
    }

        return cont;
}

Lista* repeticao(Lista* lis, int i){
    Lista *p;
char s[50];
int cont;
printf("\n \n Doc%d", i);
    for(p = lis; p != NULL; p = p->prox){
    strcpy(s, p->palavra);
    cont = busca(p, s);
    printf(" \n\t %s: %d ", s, cont);
    p->repeticao = cont;
}

    return lis; /* return p*/
}

void liberar_lista(Lista *lis){
    Lista *aux = lis;
while (aux != NULL) {
    Lista *aux2 = aux->prox;
    free(aux);
    aux = aux2;
}
}

float produto_escalar (Lista *lis1, Lista *lis2) {
Lista *aux1 = lis1, *aux2 = lis2;
float resultado=0;
while (aux1 != NULL) {
    while (aux2 != NULL) {
        if (strcmp(aux1->palavra, aux2->palavra) == 0 ) {
            resultado+=(aux1->repeticao*aux2->repeticao);
            aux2 = aux2->prox;
            break;
        }
        else {
            aux2 = aux2->prox;
        }
    }
aux1 = aux1->prox;
aux2 = lis2;
}
return resultado;
}

float formula (Lista *lis1, Lista *lis2){
float resultado;
resultado = acos(produto_escalar(lis1, lis2)/(sqrt(produto_escalar(lis1, lis1))*sqrt(produto_escalar(lis2, lis2))));
resultado = (((resultado *50)*4)/pi)-100;
    if (resultado<0){
        resultado*=-1;
    }
return resultado;
}

void checa_plagio (float resultado) {
if (resultado>=50) {
    printf("\n O arquivo foi plagiado. \n\t Arquivo é %.3f%% parecido.", resultado);
}
else
    printf("\n O arquivo não foi plagiado \n\t Arquivo é %.3f%% parecido.", resultado);

}


int main () {
char arquivo1[] = "doc1.txt", arquivo2[] = "doc2.txt";
char string[50];
double resposta;
FILE *fp1, *fp2;
Lista *lista1, *lista2;

lista1 = lista_cria();
lista2 = lista_cria();

fp1 = fopen (arquivo1, "r+") ;

if (fp1 == NULL) {
    printf("\nErro. Não foi possível abrir o arquivo.\n");
    return EXIT_FAILURE;
}

while(!feof(fp1)){
    fscanf(fp1, "%s[A-Z a-z]", string);
    insere(&lista1, string);
}

fclose(fp1);

fp2 = fopen (arquivo2, "r+") ;

if (fp2 == NULL) {
    printf("\nErro. Não foi possível abrir o arquivo.\n");
    return EXIT_FAILURE;
}

while(!feof(fp2)){
    fscanf(fp2, "%s[A-Z a-z]", string);
    insere(&lista2, string);
}

fclose(fp2);

/*imprimir_lista(lista1);
imprimir_lista(lista2);*/

lista1 = repeticao(lista1, 1);
lista2 = repeticao(lista2, 2);

resposta = formula (lista1, lista2);
checa_plagio(resposta);


liberar_lista(lista1);
liberar_lista(lista2);

return EXIT_SUCCESS;
}

[已更新答案]我用来排序的代码:

#define N 50
#include <stdlib.h>
#include <stdio.h>

typedef struct lista{
    char palavra[N];
    int repeticao;
    struct lista *prox;
} Lista;

Lista* sort (Lista *lis) {
    Lista *temp, *empurra;
    Lista *aux1, *aux2;
    Lista *guarda;

    aux1 = NULL;
    for (temp = lis; temp != NULL; temp = temp->prox){
        aux2 = temp;
        for (empurra=temp->prox; empurra != NULL; empurra = empurra->prox){
            if (empurra->repeticao < temp->repeticao){
                guarda = temp->prox;
                temp->prox = empurra->prox;
                if(guarda == empurra)
                    empurra->prox = temp;
                else
                    empurra->prox = guarda;
                if(aux2 != temp)
                    aux2->prox = temp;
                if(aux1)
                    aux1->prox = empurra;
                else
                lis = empurra;
                guarda = temp;
                temp = empurra;
                empurra = guarda;
            }
            aux2 = empurra;
        }
        aux1 = temp;
    }
return lis;
}

int main (){
return 0;
}

Answer 1

我认为你可以采取的最有效的学习方法就是认为链表是一个数组。通过这种方法，您可以简单地访问数组的元素并应用排序算法(如冒泡排序)，然后使用指向元素的指针交换元素。这样，只需将指针重定向(指向下一个元素)即可找到正确的元素。

此外，请注意排序的特殊情况(在本例中为列表的开头和结尾)。

这是一个例子:

假设我们有链表的结构:

typedef struct list{
        int n;
        struct list *next;
        } List;

我们想使用 int n 对链表进行排序，代码示例如下:

void sort (List * begin) {
    List *currentElement, *previousElement;
    int swapped = 1;
    while (swapped) {
        swapped = 1;
        while (swapped != 0) {
            swapped = 0;
            currentElement = begin;
            previousElement = NULL; //No previous element in the beginning of the list
            while(currentElement->next != NULL) { //Has another element, it's not the end of the list
                List *nextElement = currentElement->next;
                if(currentElement->n > nextElement->n) {
                    //swapping the elements
                    if (previousElement == NULL) { //is the first element
                        List *auxPtr = nextElement->next;
                        nextElement->next = currentElement;
                        currentElement->next = auxPtr;
                        begin = nextElement; //nextElement is the first element of the list now
                    }
                    else {
                        previousElement->next = nextElement;
                        currentElement->nextElement->next;
                        nextElement->next = currentElement;
                    }
                    previousElement = nextElement; //The nextElement is 'behind' the currentElement so it should be the previousElement
                    swapped = 1; // a swap was made
                    //The elements where swapped so currentElement is already in the 'position' of the next element, there is no need to upload it value
                }
                else { // there is no need to swap, just walk foward in the list
                    previousElement = currentElement;
                    currentElement = nextElement;
                }
            }
        }
    }
}

我使用了简单的冒泡排序来进行排序