浙江省高考成绩排名程序：快速排序算法实现

本程序使用快速排序算法对50万条浙江省高考成绩数据进行排序，并计算每位考生的名次和同名次人数，最终输出考生信息到文本文件。

问题描述:

有一个文本文件保存了浙江省2021年高考成绩。为了使问题简单，假设高考分数都是整数，没有小数。满分为750分。在数据文件里，每行保存一位考生的信息。先准考证号后高考成绩。现在要求编写一程序，确定每位考生的名次。最后以如下格式保存考生的信息：

准考证号 总分 名次 同名次人数 （同分情况下按准考证号大小排序）

输入:

330327969978 704
330783413356 443
330483550396 326
330726567225 215
330326613747 394
331021766290 704

输出:

输出一个文本文件(命名方式同之前实验)，每行一位考生的信息，包括准考证号，成绩，名次和同名次人数。

330327969978 704 1 2
331021766290 704 1 2
330783413356 443 3 1
330326613747 394 4 1
330483550396 326 5 1
330726567225 215 6 1

代码实现:

#include <iostream>
#include <fstream>
#include <cstdlib>

using namespace std;

typedef struct Node {
    int score;
    long long id;
    int same_rank;
    struct Node* next;
} Node, * Nodelink;

int mycompare(Nodelink x, Nodelink z) {
    if (x->score != z->score) {
        if (x->score < z->score)
            return 1;
        else
            return 0;
    }
    else {
        x->same_rank++;
        z->same_rank++;
        if (x->id < z->id) {
            return 1;
        }
        else
            return 0;
    }
}

Node* createNode(long long id, int score) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->id = id;
    newNode->score = score;
    newNode->same_rank = 0;
    newNode->next = NULL;
    return newNode;
}

Nodelink quicksort(Nodelink head, Nodelink end) {
    if (head == end)
        return head;
    Nodelink ret = createNode(0, 0);
    ret->next = head;
    Nodelink x = head->next, px = head, z = head, p;
    while (x != end) {
        if (mycompare(x, z)) {
            x = x->next;
            p = ret->next;
            ret->next = px->next;
            px->next->next = p;
            px->next = x;
        }
        else {
            px = px->next;
            x = x->next;
        }
    }
    ret->next = quicksort(ret->next, z);
    z->next = quicksort(z->next, end);
    return ret->next;
}

int main() {
    long long id;
    int x;
    ifstream ifs("C:\\Users\\86139\\Desktop\\P03_TextData500.in");
    if (!ifs.is_open()) {
        cout << "Failed to open file" << endl;
        return 1;
    }

    ofstream ofs("C:\\Users\\86139\\Desktop\\P03_TextData500.txt");
    if (!ofs.is_open()) {
        cout << "Failed to open file" << endl;
        return 1;
    }

    Nodelink ret = createNode(0, 0), head;
    while (ifs >> id && ifs >> x) {
        head = createNode(id, x);
        if (!ret->next) {
            ret->next = head;
        }
        else {
            head->next = ret->next;
            ret->next = head;
        }
    }

    Nodelink end = ret;
    while (end->next) {
        end = end->next;
    }

    head = quicksort(ret->next, end);
    int RANK = 1;
    while (head) {
        cout << head->id << " " << head->score << " " << RANK << " " << head->same_rank << endl;
        ofs << head->id << " " << head->score << " " << RANK << " " << head->same_rank << endl;
        RANK++;
        head = head->next;
    }

    ifs.close();
    ofs.close();

    return 0;
}

代码说明:

使用链表结构存储考生信息，每个节点包含准考证号、成绩、同名次人数和指向下一个节点的指针。
使用快速排序算法对链表进行排序，排序依据为成绩，同分情况下按准考证号大小排序。
计算每个考生的名次，并记录同名次人数。
将排序后的考生信息输出到文本文件。

使用方法:

将高考成绩数据文件命名为P03_TextData500.in，并将文件放到程序所在目录下。
运行程序。
程序会生成一个名为P03_TextData500.txt的文本文件，其中包含了每个考生的信息。

注意事项:

请确保输入文件路径和输出文件路径正确。
该程序仅供参考，实际应用中可能需要根据具体需求进行调整。

代码优化:

可以使用std::vector代替链表，提高内存管理效率。
可以使用更高级的排序算法，例如归并排序，提高排序效率。
可以使用STL中的std::pair存储考生信息，简化代码。

其他:

本程序仅用于学习和研究目的，不得用于任何商业用途。

本程序的版权归作者所有，任何人不得擅自复制、传播或使用本程序。

联系方式:

如有任何疑问，请联系作者。