[结尾有答案]我尝试了很多方法，但我仍然不知道如何使用简单的链表进行排序。它应该按照每个节点上保存的数字从低到高的顺序进行排序。我能做什么？当我保存在列表中时，不允许对数字进行排序。排序必须在列表完成后进行。
代码还没有完全准备好
#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(" nt %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. nt Arquivo é %.3f%% parecido.", resultado);
}
else
printf("n O arquivo não foi plagiado nt 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;
}
我认为你能采取的最具学习性的方法是认为链表是一个数组。使用这种方法，您可以简单地访问数组的元素，并应用排序算法（如气泡排序），以及在使用指向元素的指针交换元素时。这样只需要将指针（指向下一个元素）重定向到正确的元素。
此外，还要注意排序的特殊情况（在这种情况下是列表的开头和结尾）。
这里有一个例子：
假设我们有链表的结构：
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;
}
}
}
}
}
我使用了一个简单的气泡排序来排序