高位优先字符串排序，补充完整MSDSort(SqList &L, SqList &L2, int l, int r, int d)函数，其他函数不能修改

Question

预计输出排序后所有食材英文名称

#include <bits/stdc++.h>
#define MAXSIZE 10000
using namespace std;
typedef struct{
    char name[100];             // 中文名称
    char sname[100];            // 英文名称
    char health[10000];         // 养生功效
    char nutrition[10000];      // 营养与功效
    char expert[10000];         // 专家提醒
    char link[10000];           // 相关链接
    string recipe[30];          // 养生保健食谱
    int recipe_size = 0;        // 食谱数量
    string therapy[30];         // 食疗验方
    int therapy_size = 0;       // 验方数量
} Food;
typedef struct{
    Food *elem;                 // 指向数组的指针
    int length;                 // 数组的长度
}SqList;

void InitList(SqList &L){
// 使用动态内存分配new进行初始化
L.elem = new Food[MAXSIZE];
L.length = 0;
}

void FreeList(SqList &L){
// 释放内存
if(L.elem!=NULL){
    delete[] L.elem;
}
L.elem = NULL;
L.length = 0;
}

void ReadFile(SqList &L, string filename){
// 从文件中读取食材信息，将其按顺序存入L.elem指向的数组中
ifstream inFile(filename);
    if (!inFile){
        cout << "文件打开失败" << endl;
        return;
    }
    char a[MAXSIZE];
    L.length = 0;
    bool flag = false;
    while(inFile.getline(a, sizeof a, '#'))
    {
        Food food;
        stringstream s(a);
        string b;
        int type = 0;
        if (flag) getline(s, b , '\n');
        flag = true;
        while (getline(s, b , '\n'))
        {
            switch (type)
            {
                case 0: strcpy(food.name, b.substr(15).c_str()); break;
                case 1: strcpy(food.sname, b.substr(15).c_str());    break;
                case 2: strcpy(food.health, b.substr(15).c_str()); break;
                case 3: strcpy(food.nutrition, b.substr(18).c_str()); break;
                case 4: strcpy(food.expert, b.substr(15).c_str()); break;
                case 5: strcpy(food.link, b.substr(15).c_str()); break;
                case 6:
                    {
                        getline(s, b , '\n');
                        string::size_type c = b.find("——");
                        while (c != string::npos && !b.empty())
                        {
                            food.recipe[food.recipe_size++] = b;
                            getline(s, b , '\n');
                            c = b.find("——");
                        }
                    }
                case 7:
                    {
                        getline(s, b , '\n');
                        while(!b.empty())
                        {
                            food.therapy[food.therapy_size++] = b;
                            getline(s, b , '\n');
                        }
                    }
                default: break;
            }
            type++;
        }
        L.elem[++L.length] = food;
    }
    inFile.close();
}
void MSDSort(SqList &L, SqList &L2, int l, int r, int d){
    //L为原始的顺序表，L2为辅助排序开辟的顺序表，l是排序的下界，r是排序的上界
    //d为排序的字母的下标位置，从sname中下标为0的位置开始，往后递归处理
    
}
int main(){
    SqList L, L2;
    InitList(L);
    ReadFile(L, "/data/workspace/myshixun/1.4.6-高位优先字符串排序/food.txt");
    InitList(L2);
    MSDSort(L, L2, 0, L.length-1, 0);
    for (int i = 0; i < L.length; i++)
        cout << L.elem[i].sname << endl;
    FreeList(L);
    FreeList(L2);
    return 0;
}

Answer 1

你好，参考下以下代码：

void MSDSort(SqList &L, SqList &L2, int l, int r, int d) {
    // L为原始的顺序表，L2为辅助排序开辟的顺序表，l是排序的下界，r是排序的上界
    // d为排序的字母的下标位置，从sname中下标为0的位置开始，往后递归处理
    
    if (l >= r || d < 0) {
        // 基本情况：如果范围为空或d小于0，停止递归
        return;
    }

    const int RANGE = 128;  // ASCII码范围

    // 初始化计数数组
    int count[RANGE + 1] = {0};

    // 计算出现次数
    for (int i = l; i <= r; ++i) {
        int idx = L.elem[i].sname[d];
        count[idx + 1]++;
    }

    // 计算累积次数
    for (int i = 1; i < RANGE + 1; ++i) {
        count[i] += count[i - 1];
    }

    // 将元素分配到L2
    for (int i = l; i <= r; ++i) {
        int idx = L.elem[i].sname[d];
        L2.elem[count[idx]++] = L.elem[i];
    }

    // 复制回L
    for (int i = l; i <= r; ++i) {
        L.elem[i] = L2.elem[i - l];
    }

    // 对每个组递归排序
    int start = l;
    for (int i = 0; i < RANGE; ++i) {
        int end = l + count[i] - 1;
        MSDSort(L, L2, start, end, d + 1);
        start = l + count[i];
    }
}