LOCATE操作（严2.38）

Time Limit: 3000ms, Memory Limit: 10000KB, Accepted: 265, Total Submissions: 768

Description

设有一个双向循环链表，每个结点中除有pre，data和next三个域外，还增设了一个访问频度域freq。在链表被起用之前，频度域freq的值均初始化为零，而每当对链表进行一次LOCATE（L,x）的操作后，被访问的结点（即元素值等于x的结点）中的频度域freq的值便增1，同时调整链表中结点之间的次序，使其按访问频度非递增的次序排列，以便始终保持被频繁访问的结点总是靠近表头结点。试编写符合上述要求的LOCATE操作的程序。

Input

第一行输入双向循环链表的节点数m和被访问的节点数n，
第二行输入双向循环链表各节点的值，
第三行依次输入被访问的节点。

Output

输出符合上述要求的双向循环链表。
输出经过n次LOCATE后的链表。

样例

7 1
a b c d e f g
d

输出

d a b c e f g

思路

• 先找到每次需要操作的结点，给这个结点的fre+1
• 再找到它该在的位置，方法是只需要查找前面的元素，如果该结点的fre值比他大就放在他的前面，这样确保了每次都可以按照要求排序

代码

006.cpp

#include<iostream>
using namespace std;


struct Node{
    char data;
    Node* next;
    Node* prev;
    int fre;

};

typedef struct Node *node;
node Init_List(){
    node L=new Node;
    L->next=L->prev=L;
    L->fre=0;
    
    return L;
}
node Create_List(int n,char A[]){
    
    node L=Init_List();
    node r=L;
    int i;
    for(i=0;i<n;i++){
        node s=Init_List();
        s->fre=0;
        s->data=A[i];
        r->next=s;
        s->prev=r;
        s->next=L;
        r=s;

    }
    return L;
}

void Print_List(node L){
    node p=L->next;
    while(p!=L){
        // cout<<p->data<<" "<<p->fre<<endl;
        cout<<p->data<<" ";
        p=p->next;
        
    }
    cout<<endl;
}
/**
 * @brief Locate 操作，由于题目要求每一次操作后同时进行调整次序，
 * 故思路可以为先找到元素，取出来，再遍历比较，如果大于某个元素，就插入他前面
 * 
 * @param L 
 * @param x 
 */
void Locate(node L,char x){
    //第一步，先找到那个结点
    node p=L->next;
    while(p->data!=x){
        p=p->next;
    }
    p->fre++;

    node q=L->next;
    
    while(q!=p){
        // 第二步，把这个结点取出来，再插入到合适的位置
        if(q->fre<=p->fre){
            p->prev->next=p->next;
            p->next->prev=p->prev;
            p->next=q;
            p->prev=q->prev;
            q->prev->next=p;
            q->prev=p;
            return ;

        }
        else{
            return ;//找不到，说明本身就应该在那个位置
        }
    }

    

}


int main(){
    freopen("in006.txt", "r", stdin);
    int n,m;
    char A[1001],B[1001];
    cin>>n>>m;
    int i;
    for(int i=0;i<n;i++){
        cin>>A[i];
    }
    for(int i=0;i<m;i++){
        cin>>B[i];
    }
    node L=Create_List(n,A);
    for(i=0;i<m;i++){
        Locate(L,B[i]);
    }
    Print_List(L);
    return 0;

}

in006.txt

7 7
a b c d e f g
d b d b a a 

输出

a b d c e f g