双链表按访问频度域freq的值的递减序排列

绝地灬酷狼 2022-07-27 14:35 41阅读 0赞

问题及代码：

/*
    *Copyright (c)2016,烟台大学计算机与控制工程学院
    *All rights reserved.
    *文件名称：table.cpp
    *作    者：单昕昕
    *完成日期：2016年3月23日
    *版 本 号：v1.0
    *
    *问题描述：设有一个双链表,每个结点中除有piror,data,next三个域外，还有一个访问频度域freq,
    在链表被起用之前，其值均初始化为零.每当进行LocateNode(h,x)运算时,令元素值为x的结点中freq域的值加1,
    并调整表中结点的次序，使其按访问频度的递减序排列，以便使频繁访问的结点总是靠近表头。
    试写一符合上述要求的LocateNode运算的算法。
    *程序输入：无。
    *程序输出：双链表。
    */
    #include <iostream>
    #include <malloc.h>
    using namespace std;
    
    typedef struct DNode
    {
        int data;
        int freq;
        struct DNode *next;
        struct DNode *prior;
    } DinkList;
    
    DinkList *h;
    void sort(DinkList *&h)//根据freq降序排列，写成一个函数，下面没有调用只是当做测试用，因为作业要求只写一个函数
    {
        DinkList *p,*q,*pre;
        p=h->next->next;
        h->next->next=NULL;
        while(p!=NULL)
        {
            q=p->next;
            pre=h;
            while(pre->next!=NULL&&pre->next->freq>p->freq)//根据freq降序
                pre=pre->next;
            p->next=pre->next;
            if(pre->next!=NULL)
                pre->next->prior=p;
            pre->next=p;
            p->prior=pre;
            p=q;
        }
    }
    
    void LocateNode(DinkList *&h,int x)
    {
        DinkList *p;
        p=h->next;
        int i=0;
        //查找x所在的位置
        while(p!=NULL&&p->data!=x)
        {
            p=p->next;
            ++i;
        }
        p->freq++;//x元素的freq++
        //sort(h);//下面是sort
        DinkList *q,*pre;
        p=h->next->next;
        h->next->next=NULL;
        while(p!=NULL)
        {
            q=p->next;
            pre=h;
            while(pre->next!=NULL&&pre->next->freq>p->freq)
                pre=pre->next;
            p->next=pre->next;
            if(pre->next!=NULL)
                pre->next->prior=p;
            pre->next=p;
            p->prior=pre;
            p=q;
        }
    }
    int main()
    {
        DinkList *s;
        h=(DinkList *)malloc(sizeof(DinkList));
        int a[10];
        int i;
        for(i=0; i<10; ++i)//初始化a数组
            a[i]=i;
        h->prior=h->next=NULL;
        for(i=0; i<10; ++i)//头插法
        {
            s=(DinkList *)malloc(sizeof(DinkList));
            s->data=a[i];
            s->freq=0;
            s->next=h->next;
            if(h->next!=NULL)
                h->next->prior=s;
            h->next=s;
            s->prior=h;
        }//下面是测试代码
        cout<<"原来：";
        DinkList *p;
        p=h->next;
        while(p!=NULL)
        {
            cout<<p->data<<" ";
            p=p->next;
        }
        cout<<endl;
        cout<<"x=3：";
        LocateNode(h,3);
    
        p=h->next;
        while(p!=NULL)
        {
            cout<<p->data<<" ";
            p=p->next;
        }
        cout<<endl;
        cout<<"x=5：";
        LocateNode(h,5);
        p=h->next;
        while(p!=NULL)
        {
            cout<<p->data<<" ";
            p=p->next;
        }
        cout<<endl;
        cout<<"x=3：";
        LocateNode(h,3);
    
        p=h->next;
        while(p!=NULL)
        {
            cout<<p->data<<" ";
            p=p->next;
        }
        cout<<endl;
    
        return 0;
    }

运行结果：

![Center][]

直接根据freq的值用排序做。

[Center]: /images/20220727/db08dd513aed4ca293624f53ce436d21.png