归并排序（merge sort）实现员工姓名排序异常求助（附C代码）

问题描述 #

本任务需处理存储员工姓名与年龄的文本文件employee.txt，示例数据如下：

abc 45
xyz 23
pqr 23
xuv 25
tcs 76

要求使用归并排序按姓名对数据排序，并将结果写入新文件sorted_name_employee.txt。

我编写了C语言代码尝试实现，但未得到正确输出。

原代码 #

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

struct employee
{
    char name[10];
    int age;
} emp[20];

void m_sort(struct employee *a, int low, int up);
void merge(struct employee *a, struct employee *temp, int low1, int up1, int low2, int up2);
int total_records(struct employee *a);
void copy(struct employee *a, struct employee *temp, int low, int up);
void write_into_file(struct employee *a, int n);

int main()
{
    int i = 0, n;
    struct employee emp[20];
    n = total_records(emp);
    //printf("n in main:- %d\n", n);
    m_sort(emp, 0, n - 1);
    /*for (i = 0; i <= n; i++)
    {
        printf("%s %d\n", emp[i].name, emp[i].age);
    }*/
    write_into_file(emp, n);
    printf("Data has been written into 'sorted_name_emp.txt'");
}

int total_records(struct employee *a)
{
    int i = 0;
    FILE *fp;
    fp = fopen("employee.txt", "r");
    if (fp == NULL)
    {
        printf("Error!");
        exit(1);
    }
    else
    {
        while (!feof(fp))
        {
            fscanf(fp, "%s %d", a[i].name, &a[i].age);
            i++;
        }
    }
    return (i - 1);
}

void m_sort(struct employee *a, int low, int up)
{
    int mid;
    struct employee temp_emp[20];
    if (low < up)
    {
        mid = (low + up) / 2;
        m_sort(a, low, mid);
        m_sort(a, mid + 1, up);
        merge(a, temp_emp, low, mid, mid + 1, up);
        copy(a, temp_emp, low, up);
    }
}

void merge(struct employee *a, struct employee *temp, int low1, int up1, int low2, int up2)
{
    int i = low1, j = low2, k = low1;
    while ((i <= up1) && (j <= up2))
    {
        if (strcmp(a[i].name, a[j].name) <= 0)
        {
            strcpy(temp[k].name, a[i].name);
            temp[k].age = a[i].age;
            k++;
            i++;
        }
        else
        {
            strcpy(temp[k].name, a[j].name);
            temp[k].age = a[j].age;
            k++;
            j++;
        }
    }
    while (i <= up1)
    {
        strcpy(temp[k].name, a[i].name);
        temp[k].age = a[i].age;
        k++;
        i++;
    }
    while (j <= up2)
    {
        strcpy(temp[k].name, a[j].name);
        temp[k].age = a[j].age;
        k++;
        j++;
    }
}

void copy(struct employee *a, struct employee *temp, int low, int up)
{
    int i = 0;
    for (i = 0; i <= up; i++)
    {
        strcpy(a[i].name, temp[i].name);
        a[i].age = temp[i].age;
    }
}

void write_into_file(struct employee *a, int n)
{
    int i;
    FILE *fp;
    fp = fopen("sorted_name_emp.txt", "w");
    if (fp == NULL)
    {
        printf("Error!");
        exit(1);
    }
    for (i = 0; i <= n; i++)
    {
        fprintf(fp, "%s %d\n", a[i].name, a[i].age);
    }
}

实际错误输出 #

abc 45
pqr 23
xuv 25
xyz 56
tcs 76

错误分析与修复 #

1. copy函数的核心错误 #

copy函数当前从i=0开始复制到up，但归并排序中只需要复制low到up的区间（这部分是刚merge好的内容），复制整个0到up会覆盖前面已经排好的有效数据，甚至引入未初始化的垃圾值。

修复后的copy函数：

void copy(struct employee *a, struct employee *temp, int low, int up)
{
    int i;
    for (i = low; i <= up; i++)
    {
        strcpy(a[i].name, temp[i].name);
        a[i].age = temp[i].age;
    }
}

2. 文件写入的循环条件错误 #

write_into_file中循环条件i <= n会多写一条无效数据（因为记录索引是0到n-1），应改为i < n：

修复后的write_into_file函数：

void write_into_file(struct employee *a, int n)
{
    int i;
    FILE *fp;
    fp = fopen("sorted_name_emp.txt", "w");
    if (fp == NULL)
    {
        printf("Error!");
        exit(1);
    }
    for (i = 0; i < n; i++)
    {
        fprintf(fp, "%s %d\n", a[i].name, a[i].age);
    }
}

3. feof的使用问题（可选优化） #

total_records中用!feof(fp)作为循环条件会导致最后一次循环执行无效读取（fscanf失败但i仍自增），虽然返回i-1修正了数量，但更严谨的写法是直接判断fscanf的返回值：

修复后的total_records函数：

int total_records(struct employee *a)
{
    int i = 0;
    FILE *fp;
    fp = fopen("employee.txt", "r");
    if (fp == NULL)
    {
        printf("Error!");
        exit(1);
    }
    // 直接判断fscanf是否成功读取两个字段
    while (fscanf(fp, "%s %d", a[i].name, &a[i].age) == 2)
    {
        i++;
    }
    fclose(fp); // 补充关闭文件，避免资源泄漏
    return i;
}

4. 全局与局部变量冲突（可选优化） #

全局定义了emp[20]，但main中又定义了同名局部变量，虽然不影响功能，但会造成混淆，建议移除全局变量，只保留局部定义。

修复后正确输出 #

abc 45
pqr 23
tcs 76
xuv 25
xyz 23

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