C++链表快速排序：设置空的头指针

本文将介绍如何使用C++实现链表的快速排序，并重点讲解如何设置一个空的头指针来简化代码逻辑。

问题背景

在对链表进行快速排序时，通常需要维护一个指向链表头部的指针。然而，当链表为空时，这个头指针应该指向哪里呢？为了处理这种情况，我们可以初始化一个指向NULL的头指针。

代码实现

下面是使用空的头指针实现链表快速排序的C++代码：c++#include #include #include

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 = NULL; // 设置为空的头指针 Nodelink x = head->next, px = head, z = head, p; while (x != end) { if (mycompare(x, z)) { x = x->next; p = ret; ret = px->next; px->next = x; ret->next = p; } else { px = px->next; x = x->next; } } ret = quicksort(ret, z); z->next = quicksort(z->next, end); return ret;}

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 = NULL, head; // ret初始化为空的头指针    while (ifs >> id && ifs >> x) {        head = createNode(id, x);        if (!ret) { // 当ret为空时，直接赋值            ret = head;        }        else { // 否则插入到ret前面            head->next = ret;            ret = head;        }    }

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

head = quicksort(ret, 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;}

代码解释

quicksort函数: - Nodelink ret = NULL;: 将ret初始化为空指针，用于存储排序后的链表。 - 在遍历链表的过程中，根据比较结果将节点插入到ret的头部或尾部。2. main函数: - Nodelink ret = NULL, head;: ret初始化为空指针，用于存储最终排序后的链表。 - 在读取数据时： - 当ret为空时，说明链表为空，直接将新节点赋值给ret。 - 否则，将新节点插入到ret的前面，保持链表按插入顺序排序。

总结

通过设置一个空的头指针，我们可以简化链表快速排序的代码逻辑，使其更易于理解和维护。同时，这种方法也适用于其他需要处理空链表情况的场景。