链表排序需求：实现支持升降序的sortList函数

原代码问题总结 #

• compare函数错误访问secondName->m_Next，未正确处理空指针，比较逻辑完全偏离需求
• changeListPointers函数无实际交换操作，仅存在无效的逗号表达式
• sortList函数无完整排序逻辑，仅处理了第一个节点的单次比较，未遍历链表完成排序
• newItem中冗余的+4内存分配无意义，可能导致内存浪费

修复后的完整代码 #

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct TItem {
    struct TItem *m_Next;
    char *m_Name;
    char m_Secret[24];
} TITEM;

// 已实现的必填函数，修复冗余内存分配
TITEM *newItem(const char *name, TITEM *next) {
    TITEM *result = (TITEM *)malloc(sizeof(TITEM));
    if (!result) return NULL; // 增加内存分配失败判断
    result->m_Next = next;
    result->m_Name = name ? strdup(name) : NULL; // 处理name为空的情况
    return result;
}

// 修复后的比较函数：直接比较两个节点的m_Name
int compare(TITEM *a, TITEM *b) {
    // 处理空指针情况：空字符串视为小于非空字符串
    if (!a->m_Name && !b->m_Name) return 0;
    if (!a->m_Name) return -1;
    if (!b->m_Name) return 1;
    return strcmp(a->m_Name, b->m_Name);
}

// 重写后的排序函数：使用冒泡排序实现链表排序
TITEM *sortList(TITEM *l, int ascending) {
    if (!l || !l->m_Next) return l; // 空链表或单节点直接返回

    int swapped;
    TITEM *ptr1;
    TITEM *lptr = NULL; // 标记已排序部分的尾部

    do {
        swapped = 0;
        ptr1 = l;

        while (ptr1->m_Next != lptr) {
            int cmp = compare(ptr1, ptr1->m_Next);
            // 根据升序/降序判断是否需要交换
            if ((ascending && cmp > 0) || (!ascending && cmp < 0)) {
                // 交换两个节点的内容（或交换指针，这里交换内容更简单）
                // 交换m_Name
                char *temp_name = ptr1->m_Name;
                ptr1->m_Name = ptr1->m_Next->m_Name;
                ptr1->m_Next->m_Name = temp_name;
                // 交换m_Secret
                char temp_secret[24];
                memcpy(temp_secret, ptr1->m_Secret, sizeof(temp_secret));
                memcpy(ptr1->m_Secret, ptr1->m_Next->m_Secret, sizeof(temp_secret));
                memcpy(ptr1->m_Next->m_Secret, temp_secret, sizeof(temp_secret));
                swapped = 1;
            }
            ptr1 = ptr1->m_Next;
        }
        lptr = ptr1;
    } while (swapped);

    return l;
}

// 已实现的必填函数，补充释放m_Name内存
void freeList(TITEM *src) {
    while (src != NULL) {
        TITEM *next = src->m_Next;
        free(src->m_Name); // 释放strdup分配的内存
        free(src);
        src = next;
    }
}

// 测试用main函数
int main(int argc, char *argv[]) {
    // 构建测试链表
    TITEM *l = newItem("Charlie", NULL);
    l = newItem("Alice", l);
    l = newItem("Bob", l);
    l = newItem("David", l);

    printf("排序前：");
    TITEM *curr = l;
    while (curr) {
        printf("%s ", curr->m_Name);
        curr = curr->m_Next;
    }
    printf("\n");

    // 升序排序
    l = sortList(l, 1);
    printf("升序排序后：");
    curr = l;
    while (curr) {
        printf("%s ", curr->m_Name);
        curr = curr->m_Next;
    }
    printf("\n");

    // 降序排序
    l = sortList(l, 0);
    printf("降序排序后：");
    curr = l;
    while (curr) {
        printf("%s ", curr->m_Name);
        curr = curr->m_Next;
    }
    printf("\n");

    freeList(l);
    return 0;
}

关键修复说明 #

1. compare函数：
   • 直接比较传入的两个节点的m_Name，不再错误访问m_Next
   • 增加空指针处理逻辑，避免空指针引用崩溃
2. sortList函数：
   • 采用冒泡排序逻辑遍历链表，完成完整排序
   • 根据ascending参数决定交换条件：升序时前节点大于后节点则交换，降序时前节点小于后节点则交换
   • 通过交换节点内容（而非指针）简化逻辑，适合小型结构体
3. newItem函数：
   • 移除冗余的+4内存分配，避免不必要的内存浪费
   • 增加内存分配失败的判断，处理name为空的情况
4. freeList函数：
   • 补充释放strdup分配的m_Name内存，避免内存泄漏

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