C语言单链表排序与动态分配：大数据量适配问题求助

Let's break down the issues with your current code and fix them to handle large (MB-scale) text files efficiently:

Critical Problems Holding You Back #

Your current implementation works for small datasets, but it falls apart with large files due to three big issues:

1. Bubble Sort's Terrible Scalability: Bubble sort runs in O(n²) time. For a 5MB text file (which could have 100k+ words), this will be painfully slow—like waiting minutes instead of milliseconds.
2. Wasteful Memory Usage & Leaks:
   • Your MakeLowerCase function allocates new memory every time you compare words, but never frees it. This will leak gigabytes of memory with large files.
   • InsertWordsToStruct does redundant memory copies: you malloc a copied string, then pass it to AddElementToWord which mallocs another copy. Double the work, double the memory overhead.
3. Broken File Opening Logic: You initialize input_file to NULL and immediately check if it's not NULL—this block will never run! You need to actually open the file first.
4. Inefficient Swap: Swapping word contents (instead of linked list nodes) means copying strings over and over, which adds unnecessary overhead.

Step-by-Step Fixes for Large File Handling #

1. Replace Bubble Sort with an Efficient Algorithm #

For large datasets, we need an O(n log n) algorithm. I'll show two options: switching to a dynamic array (easiest) or optimizing the linked list with merge sort.

Option A: Dynamic Array + qsort (Fastest & Simplest)

Linked lists are terrible for sorting because they don't support random access. A dynamic array lets us use the standard library's optimized qsort function.

First, define a dynamic array structure:

typedef struct {
    char** words;
    size_t count;
    size_t capacity;
} WordArray;

Add helper functions for the array:

void initWordArray(WordArray* arr) {
    arr->words = NULL;
    arr->count = 0;
    arr->capacity = 0;
}

void addWordToArray(WordArray* arr, char* word) {
    // Expand capacity when needed (start at 8, double each time)
    if (arr->count >= arr->capacity) {
        size_t new_cap = (arr->capacity == 0) ? 8 : arr->capacity * 2;
        char** new_words = realloc(arr->words, new_cap * sizeof(char*));
        if (!new_words) {
            perror("Failed to expand word array");
            exit(EXIT_FAILURE);
        }
        arr->words = new_words;
        arr->capacity = new_cap;
    }
    arr->words[arr->count++] = word;
}

// Case-insensitive comparison for qsort
int compareWords(const void* a, const void* b) {
    const char* word1 = *(const char**)a;
    const char* word2 = *(const char**)b;
    size_t i = 0;
    while (word1[i] && word2[i]) {
        char c1 = tolower((unsigned char)word1[i]);
        char c2 = tolower((unsigned char)word2[i]);
        if (c1 != c2) return c1 - c2;
        i++;
    }
    // Handle shorter words coming first
    return strlen(word1) - strlen(word2);
}

void freeWordArray(WordArray* arr) {
    for (size_t i = 0; i < arr->count; i++) {
        free(arr->words[i]);
    }
    free(arr->words);
    arr->words = NULL;
    arr->count = arr->capacity = 0;
}

Option B: Linked List Merge Sort (If You Must Keep Linked Lists)

Merge sort is O(n log n) and works well with linked lists (no random access needed). Here's the implementation:

// Find middle of linked list (slow-fast pointer trick)
Word* findMiddle(Word* head) {
    if (!head || !head->pNext) return head;
    Word* slow = head;
    Word* fast = head->pNext;
    while (fast && fast->pNext) {
        slow = slow->pNext;
        fast = fast->pNext->pNext;
    }
    return slow;
}

// Merge two sorted linked lists
Word* merge(Word* left, Word* right) {
    if (!left) return right;
    if (!right) return left;

    Word* result = NULL;
    int cmp = 0;
    size_t i = 0;

    // Case-insensitive comparison
    while (left->word[i] && right->word[i]) {
        char c1 = tolower((unsigned char)left->word[i]);
        char c2 = tolower((unsigned char)right->word[i]);
        if (c1 != c2) {
            cmp = c1 - c2;
            break;
        }
        i++;
    }
    if (cmp == 0) cmp = strlen(left->word) - strlen(right->word);

    if (cmp <= 0) {
        result = left;
        result->pNext = merge(left->pNext, right);
    } else {
        result = right;
        result->pNext = merge(left, right->pNext);
    }
    return result;
}

// Merge sort for linked lists
Word* mergeSort(Word* head) {
    if (!head || !head->pNext) return head;

    Word* middle = findMiddle(head);
    Word* nextToMiddle = middle->pNext;
    middle->pNext = NULL;

    Word* left = mergeSort(head);
    Word* right = mergeSort(nextToMiddle);

    return merge(left, right);
}

2. Fix Memory Waste & Leaks #

• Remove redundant copies in InsertWordsToStruct:

  void InsertWordsToStruct(Word** pH, FILE* input_file) {
      char one_line[8192];
      while(fgets(one_line, 8192, input_file)) {
          char* one_word = strtok(one_line, " \t\n");
          while(one_word != NULL) {
              if(IsLegitWord(one_word)) {
                  size_t len = strlen(one_word);
                  char* copied = malloc(len + 1);
                  if (!copied) {
                      perror("Failed to allocate word memory");
                      RemoveWordList(pH);
                      exit(EXIT_FAILURE);
                  }
                  strcpy(copied, one_word);
                  AddElementToWord(pH, copied);
                  // Don't free copied here—we need it in the linked list!
              }
              one_word = strtok(NULL, " \t\n");
          }
      }
  }
  

• Delete MakeLowerCase: We now do case-insensitive comparisons on the fly without allocating new memory, eliminating leaks.
• Fix RemoveWordList: The final free(current) is unnecessary (current is already NULL):

  void RemoveWordList(Word** pH){
      Word* current = *pH;
      while (current != NULL){
          Word* next = current->pNext;
          free(current->word);
          free(current);
          current = next;
      }
      *pH = NULL;
  }
  

3. Fix File Handling & Add Output #

For Dynamic Array Implementation

int main() {
    WordArray arr;
    initWordArray(&arr);

    // Open input file
    FILE* input_file = fopen("input.txt", "r");
    if(!input_file){
        perror("Failed to open input file");
        return EXIT_FAILURE;
    }

    // Read words into array
    char one_line[8192];
    while(fgets(one_line, 8192, input_file)) {
        char* one_word = strtok(one_line, " \t\n");
        while(one_word != NULL) {
            if(IsLegitWord(one_word)) {
                size_t len = strlen(one_word);
                char* copied = malloc(len + 1);
                if (!copied) {
                    perror("Failed to allocate word memory");
                    freeWordArray(&arr);
                    fclose(input_file);
                    return EXIT_FAILURE;
                }
                strcpy(copied, one_word);
                addWordToArray(&arr, copied);
            }
            one_word = strtok(NULL, " \t\n");
        }
    }
    fclose(input_file);

    // Sort the array
    qsort(arr.words, arr.count, sizeof(char*), compareWords);

    // Write to output file
    FILE* output_file = fopen("output.txt", "w");
    if(!output_file){
        perror("Failed to open output file");
        freeWordArray(&arr);
        return EXIT_FAILURE;
    }
    for(size_t i = 0; i < arr.count; i++) {
        fprintf(output_file, "%s ", arr.words[i]);
    }
    fclose(output_file);

    // Cleanup
    freeWordArray(&arr);
    return EXIT_SUCCESS;
}

For Linked List Implementation

int main() {
    Word* s_words = NULL;

    // Open input file (fixed logic!)
    FILE* input_file = fopen("input.txt", "r");
    if(input_file != NULL){
        InsertWordsToStruct(&s_words, input_file);
        fclose(input_file);
    } else{
        perror("Failed to open input file");
        RemoveWordList(&s_words);
        return EXIT_FAILURE;
    }

    // Sort with merge sort instead of bubble sort
    s_words = mergeSort(s_words);

    // Write to output file
    FILE* output_file = fopen("output.txt", "w");
    if(!output_file){
        perror("Failed to open output file");
        RemoveWordList(&s_words);
        return EXIT_FAILURE;
    }
    Word* current = s_words;
    while(current != NULL){
        fprintf(output_file, "%s ", current->word);
        current = current->pNext;
    }
    fclose(output_file);

    // Cleanup
    RemoveWordList(&s_words);
    return EXIT_SUCCESS;
}

4. Bonus Optimizations for Extra Large Files #

• Use getline instead of fgets: It automatically allocates enough memory for long lines, avoiding truncation.
• Increase buffer size: Bump one_line from 8192 to 65536 (64KB) to reduce the number of I/O calls.
• Batch writes: Collect words in a buffer and write to disk in chunks instead of one word at a time.

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