[数据结构与算法]数据结构算法——1015. 查词典

题目

输入
3 7
1 2 1 5 4 4 1
输出
5

思路

队列题，先进先出，为了减少删除插入时间用链表队

代码

#include<iostream>
using namespace std;

struct list
{
    int data;
    list* next;
    list()
    {
        data = 0;
        next = NULL;
    }

};

struct LQue
{
    list* head;
    int cap;
    int size;
    int search_times;

    LQue(int n )
    {
        head = new list;
        cap = n;
        size = search_times = 0;
    }

    void buf_trans(int data)
    {
        if(head->next == NULL)
        {
            head->next = new list;
            head->next->data = data;
            size++;
            search_times++;
            return;
        }
        else
        {
            list* search = head->next;
            while(search->next)
            {
                if(search->data == data)
                {
                    return;
                }
                search = search->next;
            }
            if(search->data == data)
                return;


            list*temp = head->next;

            
            search->next = new list;
            search->next->data = data;
            if(cap == size)
            {
                head->next = temp->next;
                delete temp;
            }
            else if(cap > size)
            {
                size++;
            }
            search_times++;
        }

        
    }

    void p()
    {
        list* a = head->next;
        while(a)
        {
            cout << a->data << " ";
            a = a->next;
        }
        cout << endl;
    }
};
int main()
{
    int n,t;
    cin >> n >> t;
    int times = 0;
    LQue Q(n);

    for(int i = 0; i < t; i++)
    {
        
        int c;
        cin >> c;
        Q.buf_trans(c);
        //Q.p();
    }
    
    cout << Q.search_times << endl;
    return 0;
}