【2016-d-二-1】双链表结点按照访问的频度递减排序

/**
    算法思想：1.从头至尾遍历双链表，找到data值为x的节点
              2.将此节点频度加一，将此节点在链表中删除
              3.从右至左找到第一个频度比他大的节点，插入到此节点后面
**/
typedef struct DLNode
{
    int data;
    int freq;
    struct DLNode *prior;
    struct DLNode *next;
}DLNode;

void locate( DLNode *l,int x)
{
    DLNode *p,*q;
    p=l->next;//l即为头结点
    while(p!=l)
    {
        if(p->data == x)
        {
            q=p;//p指针暂存查找到的这个节点
            q->freq = q->freq+1;//访问频度加一
                                           
            //先将q在原位置删除，因为我们要从后往前找到插入点，
            //必须先删除，避免他位置不变，重复插入的情况
            q->prior->next=q->next;
            q->next->prior=q->prior;
            
            //从这个点开始，向表头方向查找q的插入点
            while(p!=l)
            {
                if(q->freq<p->freq)//从右至左找到第一个比q的频度大的结点
                {                   
                    //将q插入到此位置的后面
                    q->next = p->next;
                    p->next->prior=q;
                    p->next=q;
                    q->prior=p;
                    
                }
                p=p->prior;//p指针前移
            }
        }
        p=p->next;
    }
}