问题如下 

 回答及笔记如下

#include <iostream>
using namespace std;

struct Node {
    int data;
    string name;
    Node* next;
};

void insert(Node** head, int data,string name) {//接收一个指向“指向Node结构的指针”,即变量“head”是一个指向指针的指针
    Node* newNode = new Node;//创建一个新的node结构,并创建指针“newNode”指向这个结构,注意new出来的是一个地址
    newNode->data = data;
    newNode->name = name;
    newNode->next = *head;//对“head”解除引用,*head是一个“指向Node结构的空指针”
    //1.把新创建的结点加入到原有链表的头部
    //2.如果没有,就在尾部留下一个空指针
    *head = newNode;//更新指向头部结点的指针
}//1.注意这一段代码是在链表头部插入新结点
//2.此处使用Node**是为了直接操作head这个变量
//3.尾部会留下一个空指针

void printList(Node* node) {
    while (node != nullptr) {
        cout << node->data << " "<<node->name<<"\n";
        node = node->next;//从头开始打印
    }
    cout << endl;
}

void sortList(Node** head) {
    const int MAX_VALUE = 100;//注意这个是结点中数据的最大值(问:若数据过大怎么处理)
    Node* index[MAX_VALUE + 1] = { nullptr };//创建一个index指针数组,长度是101,全部初始化为空指针
    Node* current = *head;//指向整个链表的头结点

    while (current != nullptr) {
        Node* next = current->next;//备份当前结点指向下一结点的指针
        current->next = index[current->data];//把当前结点插到data值相同的链表前面,若没有,则将指向下一结点的指针设为空指针
        index[current->data] = current;//把“指向当前结点”的指针加入对应数值的指针数据中
        current = next;//当前结点处理完毕,循环至下一个结点
    }
    //此过程可以理解为把链表拆分为若干结点分别处理,数组存储了所有“带有相同值的结点”形成的链表的头结点
    //在下面的循环中再按顺序把这拆出来的若干链表连成一个链表
    //指针数组中储存的是指向这一系列同值结点链表头结点的一个指针


    *head = nullptr;

    for (int i = MAX_VALUE; i >= 0; i--) {//提问:如果改成(int i=0;i<=MAX_VALUE;i++)是不是降序)
        Node* current = index[i];
        while (current != nullptr) {
            Node* next = current->next;//备份当前结点指向下一结点的指针
            current->next = *head;
            *head = current;
            current = next;//处理下一个
        }
    }
}
//注意这个链表实现的插入永远是插在头部
//大意: A1 A2 A3   B1 B2 B3 --A1 A2 A3   B3 B2 B1--A3 A2 A1 B3 B2 B1
//while处理每一小节链表,for处理储存在数组中的若干链表
//最尾部(B1 B2 B3)链表作为最先处理的链表,可以理解为本体,处理完毕后(B3 B2 B1)处理下一节链表,每个结点被拆出来插到本体的前端(A1 B3 B2 B1--A2 A1 B3 B2 B1--A3 A2 A1 B3 B2 B1)



int main() {
    Node* head = nullptr;//head是一个指向Node结构的空指针,是“指向第一个结点”的
    insert(&head, 1,"a1");//注意到head是一个指针,此处&head传递了一个指针的地址
    insert(&head, 1,"a2");
    insert(&head, 1,"a3");
    insert(&head, 2,"b1");
    insert(&head, 2,"b2");
    insert(&head, 2,"b3");

    cout << "Original List: "<<"\n";
    printList(head);

    sortList(&head);

    cout << "\n"<<"Sorted List :" << "\n";
    printList(head);

    return 0;
}

//问题1:链表中数据在排序后能否保持原有相对顺序

Logo

GitCode 天启AI是一款由 GitCode 团队打造的智能助手,基于先进的LLM(大语言模型)与多智能体 Agent 技术构建,致力于为用户提供高效、智能、多模态的创作与开发支持。它不仅支持自然语言对话,还具备处理文件、生成 PPT、撰写分析报告、开发 Web 应用等多项能力,真正做到“一句话,让 Al帮你完成复杂任务”。

更多推荐