C++按访问频度排序双链表结点

题目描述

编写程序实现一个双链表h,每个结点中除了有 ptior、 data和next几个域外,还有一个访问频度域feq·在链表被启用之前,其初始值都为0,设计并实现 LocateNode Ch,)运算,每当进行该运算时,令元素值为×的结点中feq域的值加1,并调整表中结点的次序,使其按访问平度的递减次序排列,以便使短繁访问的结点总是靠近表头。

源代码

#include <iostream>

using namespace std;

// 双链表结点
struct Node {
    int data; // 数据域
    int feq;  // 访问频度域
    Node* prior; // 指向前驱结点的指针
    Node* next;  // 指向后继结点的指针

    Node(int d = 0, int f = 0) : data(d), feq(f), prior(nullptr), next(nullptr) {}
};

// 双链表类
class DoubleLinkedList {
public:
    DoubleLinkedList() {
        head = new Node(); // 初始化头结点
        tail = new Node(); // 初始化尾结点
        head->next = tail; // 头结点的后继结点为尾结点
        tail->prior = head; // 尾结点的前驱结点为头结点
    }

    // 在表头插入结点
    void insertToHead(int data, int feq) {
        Node* node = new Node(data, feq);
        node->next = head->next;
        head->next->prior = node;
        head->next = node;
        node->prior = head;
    }

    // 删除结点
    void deleteNode(Node* node) {
        node->prior->next = node->next;
        node->next->prior = node->prior;
        delete node;
    }

    // 查找元素为data的结点，并将其访问频度加1
    Node* locateNode(int data) {
        Node* p = head->next;
        while (p != tail) {
            if (p->data == data) { // 找到目标结点
                p->feq++; // 访问频度加1
                // 调整结点位置，使其按访问频度的递减次序排列
                while (p->prior != head && p->feq > p->prior->feq) {
                    // 交换p和p->prior的位置
                    Node* q = p->prior;
                    Node* r = p->next;
                    q->next = r;
                    r->prior = q;
                    p->next = q;
                    q->prior = p;
                    p->prior = q->prior;
                    q->next = p;
                }
                return p;
            }
            p = p->next;
        }
        return nullptr; // 没有找到目标结点
    }

private:
    Node* head; // 头结点
    Node* tail; // 尾结点
};

int main() {
    DoubleLinkedList list;
    list.insertToHead(3, 0);
    list.insertToHead(2, 0);
    list.insertToHead(1, 0);

    Node* p = list.locateNode(2);
    if (p != nullptr) {
        cout << "Find node with data " << p->data << ", feq = " << p->feq << endl;
    } else {
        cout << "Cannot find node with data 2" << endl;
    }

    return 0;
}

在上面的代码中，我们定义了一个双链表类DoubleLinkedList，包括了插入结点、删除结点和查找结点的操作。其中，查找结点的操作实现了题目要求的LocateNode函数。

在查找结点时，我们首先遍历整个链表，找到元素值为data的结点。如果找到了目标结点，就将其访问频度加1，并调整结点位置，使其按访问频度的递减次序排列。具体来说，我们从目标结点开始，向前遍历链表，如果前驱结点的访问频度小于目标结点的访问频度，就交换这两个结点的位置。这样，就可以保证访问频度高的结点总是靠近表头。

运行截图