首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

我被困在如何在双向链表中使用C++中的人的名字和姓氏进行排序的算法

在双向链表中使用C++进行人名排序的算法可以采用冒泡排序或插入排序的方式实现。下面是一个示例的排序算法:

代码语言:txt
复制
#include <iostream>
#include <string>
using namespace std;

// 双向链表节点定义
struct Node {
    string firstName;
    string lastName;
    Node* prev;
    Node* next;
};

// 在双向链表中插入节点
void insertNode(Node** head, string firstName, string lastName) {
    Node* newNode = new Node();
    newNode->firstName = firstName;
    newNode->lastName = lastName;
    newNode->prev = nullptr;
    newNode->next = nullptr;

    if (*head == nullptr) {
        *head = newNode;
    } else {
        Node* current = *head;
        while (current->next != nullptr) {
            current = current->next;
        }
        current->next = newNode;
        newNode->prev = current;
    }
}

// 交换两个节点的数据
void swapNodes(Node* a, Node* b) {
    string tempFirstName = a->firstName;
    string tempLastName = a->lastName;
    a->firstName = b->firstName;
    a->lastName = b->lastName;
    b->firstName = tempFirstName;
    b->lastName = tempLastName;
}

// 使用冒泡排序对双向链表进行排序
void bubbleSort(Node* head) {
    if (head == nullptr || head->next == nullptr) {
        return;
    }

    bool swapped;
    Node* current;
    Node* last = nullptr;

    do {
        swapped = false;
        current = head;

        while (current->next != last) {
            if (current->firstName > current->next->firstName) {
                swapNodes(current, current->next);
                swapped = true;
            } else if (current->firstName == current->next->firstName && current->lastName > current->next->lastName) {
                swapNodes(current, current->next);
                swapped = true;
            }
            current = current->next;
        }
        last = current;
    } while (swapped);
}

// 打印双向链表
void printList(Node* node) {
    while (node != nullptr) {
        cout << node->firstName << " " << node->lastName << endl;
        node = node->next;
    }
}

int main() {
    Node* head = nullptr;

    // 插入节点
    insertNode(&head, "John", "Doe");
    insertNode(&head, "Alice", "Smith");
    insertNode(&head, "Bob", "Johnson");
    insertNode(&head, "Charlie", "Brown");

    // 打印排序前的链表
    cout << "Before sorting:" << endl;
    printList(head);

    // 使用冒泡排序对链表进行排序
    bubbleSort(head);

    // 打印排序后的链表
    cout << "After sorting:" << endl;
    printList(head);

    return 0;
}

这个算法使用冒泡排序对双向链表中的节点按照人名进行排序,首先定义了双向链表节点的结构体,包含了名字和姓氏的字符串以及前后指针。然后通过insertNode函数向链表中插入节点。接下来,使用bubbleSort函数对链表进行排序,通过比较节点的名字和姓氏来确定节点的顺序。最后,使用printList函数打印排序前后的链表。

这个算法的时间复杂度为O(n^2),其中n是链表中节点的数量。在实际应用中,可以根据具体需求选择更高效的排序算法,如快速排序或归并排序。

页面内容是否对你有帮助?
有帮助
没帮助

相关·内容

  • 算法与数据结构(一) 线性表的顺序存储与链式存储(Swift版)

    温故而知新,在接下来的几篇博客中,将会系统的对数据结构的相关内容进行回顾并总结。数据结构乃编程的基础呢,还是要不时拿出来翻一翻回顾一下。当然数据结构相关博客中我们以Swift语言来实现。因为Swift语言是面向对象语言,所以在相关示例实现的时候与之前在大学学数据结构时C语言的实现有些出入,不过数据结构还是要注重思想,至于实现语言是面向对象的还是面向过程的影响不大。 接触过数据结构的小伙伴应该都知道程序 = 数据结构 + 算法。数据结构乃组织组织数据的结构,算法就是对这些结构中的数据进行操作,可见数据结构的重

    07
    领券