如何在带表头的C语言双向链表中按姓氏排序？

一、改造双向链表存储字符串 #

你原来的链表存整数，现在要存姓氏字符串，得从结构体开始改：

1. 修改结构体定义 #

把整数字段换成字符串指针，C里用char*存字符串：

typedef struct elemento{ 
    char *sobrenome;  // 存储姓氏
    struct elemento *ant; 
    struct elemento *prox;
}Elem;

typedef struct elemento* Lista;

2. 调整插入函数 #

插入时要给字符串分配内存，用strdup（自动分配内存并复制字符串）最方便，也可以用malloc加strcpy：

// 插入开头的修改版
int Inserir_Inicio(Lista *Lista_Nomes, const char *sobrenome){
    if(Lista_Nomes == NULL || sobrenome == NULL) 
        return 0;
        
    Elem *no = (Elem*)malloc(sizeof(Elem)); 
    if(no == NULL) 
        return 0;
    
    // 给字符串分配内存并复制内容
    no->sobrenome = strdup(sobrenome);
    if(no->sobrenome == NULL){ // 字符串分配失败就释放节点
        free(no);
        return 0;
    }
    
    no->ant = NULL; 
    no->prox = (*Lista_Nomes); 
    
    if (*Lista_Nomes != NULL) 
        (*Lista_Nomes)->ant = no; 
    *Lista_Nomes = no; 
    
    return 1; 
}

插入结尾的函数同理，只需要替换字符串处理部分。

3. 调整打印函数 #

打印时直接输出字符串，还要修改Printagem_Dinamica来适配字符串长度：

// 适配字符串的打印辅助函数
void Printagem_Dinamica(int margem, const char *str){ 
    int q_char = strlen(str);
    
    char *t = (char*)malloc((q_char + 1)*sizeof(char));
    if(t == NULL) return;
    
    int i=0;
    while(i < q_char){ 
        t[i]='-';
        i++;
    }
    t[q_char]='\0'; 
    
    if(margem == 1)
        printf(" ,_.--%s--.  ", t); 
    if(margem == 2)
        printf("   `--%s--´  ", t); 
    free(t); // 记得释放临时内存
}

// 修改打印链表的函数
void Printar_Elemento(Lista *Lista_Nomes){
    int br[3];
    Lista aux1, aux2, aux3;
    aux1 = aux2 = aux3 = (*Lista_Nomes);
    
    printf("NULL\n"); 
    do{
        br[0]=0;
        while(aux1 != NULL){
            Printagem_Dinamica(1, aux1->sobrenome); 
            aux1 = aux1->prox;
            
            br[0]++;
            if(br[0] % ELEM_LINHA == 0)
                break;
        }
        printf("\n");
        
        br[1]=0;
        while(aux2 != NULL){
            printf(" ` || %s ||->", aux2->sobrenome); // 这里改成输出字符串
            aux2 = aux2->prox;
            
            br[1]++;
            if(br[1] % ELEM_LINHA == 0)
                break;
        }
        
        br[2]=0;
        printf("\n");
        while(aux3 != NULL){
            Printagem_Dinamica(2, aux3->sobrenome); 
            aux3 = aux3->prox;
            
            br[2]++;
            if(br[2] % ELEM_LINHA == 0)
                break;
        }
        
        if(br[0] < ELEM_LINHA) 
            printf("NULL"); 
        printf("\n\n");
        
    }while(aux3 != NULL); 
}

4. 新增内存释放函数 #

因为存了字符串，要先释放字符串再释放节点，避免内存泄漏：

void Liberar_Lista(Lista *Lista_Nomes){
    if(Lista_Nomes == NULL) return;
    Elem *aux = *Lista_Nomes;
    while(aux != NULL){
        Elem *prox = aux->prox;
        free(aux->sobrenome); // 先释放字符串
        free(aux); // 再释放节点
        aux = prox;
    }
    free(Lista_Nomes);
}

二、按姓氏字母排序双向链表 #

用冒泡排序最简单，直接交换节点里的字符串指针就行：

#include <string.h> // 要包含这个头文件用strcmp

void Ordenar_Lista(Lista *Lista_Nomes){
    if(Lista_Nomes == NULL || *Lista_Nomes == NULL) return;
    
    int trocou;
    Elem *atual;
    Elem *fim = NULL;
    
    do{
        trocou = 0;
        atual = *Lista_Nomes;
        
        while(atual->prox != fim){
            // strcmp返回正数表示前者字母顺序靠后，需要交换
            if(strcmp(atual->sobrenome, atual->prox->sobrenome) > 0){
                // 直接交换两个节点的字符串指针，比交换节点本身简单
                char *temp = atual->sobrenome;
                atual->sobrenome = atual->prox->sobrenome;
                atual->prox->sobrenome = temp;
                trocou = 1;
            }
            atual = atual->prox;
        }
        fim = atual;
    }while(trocou);
}

如果要支持葡萄牙语带重音的姓氏，把strcmp换成strcoll，配合你代码里的setlocale(LC_ALL, "portuguese")就能按本地化规则排序。

整合后的主函数示例 #

int main(void){
    setlocale(LC_ALL, "portuguese");
    char sobrenome[50];
    Lista *Lista_Nomes = Criar_Lista();
    
    printf("Digite sobrenomes (digite 'sair' para parar):\n");
    while(1){
        printf("Informe um sobrenome: ");
        scanf("%s", sobrenome);
        if(strcmp(sobrenome, "sair") == 0) break;
        
        if(!Inserir_Final(Lista_Nomes, sobrenome)){
            printf("Erro de memória!\n");
            break;
        }
        system("CLS");
        Printar_Elemento(Lista_Nomes);
    }
    
    // 排序后打印
    printf("\nLista ordenada por sobrenome:\n");
    Ordenar_Lista(Lista_Nomes);
    Printar_Elemento(Lista_Nomes);
    
    Liberar_Lista(Lista_Nomes);
    return 0;
}

内容的提问来源于stack exchange，提问作者Otacir