我正在尝试使用合并排序对字符串进行排序

Question

问题陈述

在这个问题中我们给出了一个文本文档employee.txt，其中存储了员工姓名和年龄，例如以下数据：

abc 45
xyz 23
pqr 23
xuv 25
tcs 76

我们必须使用合并排序对字符串（即姓名）进行排序，并将它们存储到名为 sorted_name_employee.txt 的新文本文档中。

我尝试过一些方法，但这没有给出适当的输出。

#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);
    }
}

sorted_name_emp.txt中的实际输出：

abc 45
pqr 23
xuv 25
xyz 56
tcs 76

Answer 1

存在多个问题：

• 如果

  n

  是记录数，则

  for (i = 0; i <= n; i++)

  迭代一次太多。您应该使用

  i < n

  而不是

  i <= n

  。

• while (!feof(fp))

  读取和解析文件总是错误的。用这个代替：

    while (fscanf(fp, "%s %d", a[i].name, &a[i].age) == 2) {
        i++;
    }
  

• total_records

  返回

  i - 1

  ，比较麻烦而且容易出错。您应该返回

  i

  并在其他地方修复代码以将

  n

  处理为记录数。

• m_sort(emp, 0, n - 1);

  似乎不正确，但是您的

  m_sort()

  实现确实假设最后一个参数是最后一个元素的索引。因此，如果

  n

  是元素的数量，那么这是正确的，但由于您在

  i - 1

  中返回

  total_records

  ，实际上您将索引传递给了最后一个元素之前的元素，所以这就是最后一个元素未排序的原因正确。

• mid = (low + up) / 2;

  对于少数记录不会造成问题，但如果对大型数组进行排序，

  low + up

  可能会超出

  int

  类型的范围并导致未定义的行为。你应该写

  mid = low + (up - low) / 2;

• 函数

  copy

  中的循环从

  i=0

  开始迭代，而它应该从

  i = low

  开始。

• 您忘记用

  total_records

   关闭 

  write_into_file

   和 

  fclose(fp)
  中的文件

• struct employee emp[20];

  中定义的

  main

  实际上隐藏了在全局范围内定义的同名全局数组

  emp[20]

  。

• 无需单独复制每个结构体成员，直接使用

  temp[k] = a[i];

  ...
  复制结构体即可

将索引传递给最后一个元素很容易出错。将索引传递给超过切片末尾的元素进行排序在 C 中更惯用，并且更不容易出错。这避免了繁琐和混乱的

+1

/

-1

调整。

这是修改后的版本：

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

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

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, int max_index, const char *filename);
void copy(struct employee *a, struct employee *temp, int low, int up);
void write_into_file(struct employee *a, int n, const char *filename);

int main(void) {
    struct employee emp[20];
    int n = total_records(emp, 20, "employee.txt");
    m_sort(emp, 0, n);
    write_into_file(emp, n, "sorted_name_emp.txt");
    printf("Data has been written into 'sorted_name_emp.txt': %d lines\n", n);
    return 0;
}

int total_records(struct employee *a, int max_index, const char *filename) {
    int i = 0;
    FILE *fp = fopen(filename, "r");
    if (fp == NULL) {
        printf("Cannot open %s: %s\n", filename, strerror(errno));
        exit(1);
    }

    while (i < max_index && fscanf(fp, "%9s %d", a[i].name, &a[i].age) == 2) {
        i++;
    }
    fclose(fp);
    return i;
}

void m_sort(struct employee *a, int low, int up) {
    if (up - low > 1) {
        struct employee temp_emp[20];
        int mid = low + (up - low) / 2;
        m_sort(a, low, mid);
        m_sort(a, mid, up);
        merge(a, temp_emp, low, mid, mid, 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) {
            temp[k++] = a[i++];
        } else {
            temp[k++] = a[j++];
        }
    }
    while (i < up1) {
        temp[k++] = a[i++];
    }
    while (j < up2) {
        temp[k++] = a[j++];
    }
}

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

void write_into_file(struct employee *a, int n, const char *filename) {
    FILE *fp = fopen(filename, "w");
    if (fp == NULL) {
        printf("Cannot open %s: %s\n", filename, strerror(errno));
        exit(1);
    }
    for (int i = 0; i < n; i++) {
        fprintf(fp, "%s %d\n", a[i].name, a[i].age);
    }
    fclose(fp);
}

输出文件内容：

abc 45
pqr 23
tcs 76
xuv 25
xyz 23