博客

题目的具体描述和输入输出要求在截图里：



我是用C++实现的，实现的流程大致如下：

1. 定义双向循环链表（带头结点），初始化开辟头结点的空间
2. 输入并创建链表，写成函数，其中头结点后的第一个结点的pre指向头结点，尾结点的next指向头结点后的第一个结点
3. 以字符数组形式接收输入的被访问的结点的data值，如若被访问的data个数为3，分别为a、b、c，将其写入字符数组char* x
4. 访问并修改结点的访问频度，写成函数，传入参数是char* x 和链表
5. 排序算法，用到的主要变量有r、q、MAX、fmax。其中r用来指向被排序好的最后一个节点（即上一次被排序的结点）；q用来指向r的下一个节点（即被排序好的结点后面的第一个待排序的节点）并循环遍历待比较结点；MAX用来指向比较出来的拥有最大freq的结点（每次执行排序算法时初始化为q）；fmax记录循环遍历中出现的最大freq值

具体代码如下：

#include<iostream>
using namespace std;
//按访问频率排序，采用带头结点的循环链表，末尾元素指向首元素
typedef struct LNode {
    char val;
    LNode* pre, * next;
    int freq;
}DLNode, * DLinkList;

void initList(DLinkList& L) {//带头结点
    L = (DLNode*)malloc(sizeof(DLNode));
    L->next = NULL;
}

//带头结点的循环链表创建(我的方法)
void createList(DLinkList& L, int n) {
    DLNode* r = L, * p;//r指针一开始必须初始化
    for (int i = 0; i < n; i++) {
        p = (DLNode*)malloc(sizeof(DLNode));
        cin >> p->val;
        p->freq = 0;
        p->pre = r;
        r->next = p;
        r = p;
    }
    r->next = L->next;//末尾元素next指向第一个元素，第一个元素pre指向末尾
    //L->next->pre = r;
}

//void createList(DLinkList& L, int n) {
//    for (int i = 0; i < n; i++) {
//        DLNode* p = (DLNode*)malloc(sizeof(DLNode));
//        //if (!p)return ;
//        cin >> p->val;
//        p->freq = 0;
//
//        if (L->next != NULL) {
//            p->next = L->next;
//            p->pre = L;
//            L->next->pre = p;
//            L->next = p;
//        }
//        else {
//            L->next = p;
//            L->pre = p;
//            p->next = L;
//            p->pre = L;
//        }
//    }
//}

void locate(DLinkList& L, char *x) {
    DLNode* p = L;
    int i = 0;
    while (x[i] != NULL) {
        while (p != NULL) {
            if (p->val == x[i]) {
                p->freq++;
                i++;
                break;
            }
            p = p->next;
        }
    }
}

//每次排序操作后都需要修改的变量：fmax,MAX,r,q  关系为：
//每插入（包括假象插入）一个节点,r = r->next
//q = r->next
//MAX = q
//fmax = q->freq
//将双向链表中某结点移动并插入某个位置的操作顺序
//将该节点摘下来，即修改该节点前后节点之间的关系
//建立摘下来的节点的pre和next与待插入位置前后节点的关系
//修改前后节点的next和pre
void orderByFreq(DLinkList& L,int n) {
    DLNode* MAX = L->next, * r = L;//r(rear)指向被排序好的结点中的最后一个
    DLNode* q = r->next;//q用来循环剩余节点，在他们中间比较选出最大频率者
    int fmax = r->next->freq;
    for (int i = 0; i < n-1; i++) {//n-1是因为最后剩余的一个节点必定是最小的
        q = q->next;//q上一步为r的后一个节点，fmax此时为r后第一个结点的频率
        for (int j = 0; j < n - i-1; j++) {
            if (q->freq > fmax) {
                MAX = q;
                fmax = q->freq;
            }
            q = q->next;
        }
        //此时MAX指向拥有最大访问频率的结点，但它可能就是头结点之后的第一个结点本身（即MAX没有移动），此时只需将它假象插入
        if (MAX == r->next) {
            r = r->next;//后移代表插入（其实并没有，因为该MAX就是r下一个，假象插入）一个节点
            fmax = r->next->freq;//更新新的fmax为r后一个结点的频率，因为r已经是被排好序的，接下来从除了r的剩余节点中挑选
            q = r->next;
            MAX = q;
            continue;
        }
        else {
            DLNode* temp = MAX;
            MAX->pre->next = MAX->next;
            MAX->next->pre = MAX->pre;
            temp->pre = r;
            temp->next = r->next;
            r->next->pre->next = temp;//即r->next=MAX
            r->next->next->pre = temp;
            q = r->next->next;//r->next是刚才插入的结点，需要定位的是此节点的下一个节点
            r = r->next;//r指向被排序好的最后一个节点，若有新的待插入结点，则插入r后面
            fmax = q->freq;
            MAX = q;//必须修改新的MAX，假设其为r后面的第一个元素，即q
        }
    }
}

char* createX(int n) {
    char* s = (char*)malloc(sizeof(char)*n);
    int i;
    for (i = 0; i < n; i++) {
        cin >> s[i];
    }
    s[i] = NULL;//字符串有NULL结尾才有效
    return s;
}

void showList(DLinkList L,int n) {
    L = L->next;
    for (int i = 0; i < n; i++) {
        cout << L->val << " ";
        L = L->next;
    }
    cout << endl;
}
int main() {
    int sum, n;
    cin >> sum >> n;
    DLinkList A;
    initList(A);
    createList(A, sum);
    //showList(A,sum);//test_point1
    char* xs = createX(n);//输入被访问元素
    locate(A,xs);//访问节点，增加其访问频率
    //排序
    orderByFreq(A, sum);

    showList(A,sum);
}