Skip to content

11051: 【原1051】静态查找表

题目

题目描述

author: yepyao 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1051

Description

如果一个用单链表存储的无序表中各个节点的查找概率不等,则可以用如下策略提高查找效率:若找到了指定节点,则让它移到链表的第一个位置,使得经常被查找的节点尽量靠近表头。

请用程序模拟这个过程。最后输出按此策略查找指定数据一共做了多少次比较。

Input Format

第一行:一个整数n ,表示静态查找表中一共n个元素。

之后的n行,每行一个整数,按顺序给出了静态查找表中的元素,其中可能有重复元素。

之后的一行:一个整数m,表示即将查找元素。

之后的m行,每行一个整数,表示查找的元素。

Output Format

一个整数,表示一共进行了多少次比较。

Hint

题目中的\(n,m \leq 10000\) 元素均小于10^9

Hint:你的程序只能判断两个整数是相等或是不相等,也就是说,认为静态查找表中的元素是无序的!

Sample Input

3
1
3
4
3
2
1
4

Sample Output

7

FineArtz's solution

/* 静态查找表 */
#include <iostream>
using namespace std;

class Node{
public:
    Node *pred = nullptr, *succ = nullptr;
    int data = 0;
};

int main(){
    Node *head = new Node, *p = head;
    int n, m, cnt = 0;
    cin >> n;
    for (int i = 1; i <= n; ++i){
        Node *t = new Node;
        cin >> t->data;
        p->succ = t;
        t->pred = p;
        p = t;
    }
    cin >> m;
    while (m--){
        int x;
        cin >> x;
        p = head->succ;
        while (p){
            ++cnt;
            if (p->data == x)
                break;
            p = p->succ;
        }
        if (p){
            p->pred->succ = p->succ;
            if (p->succ)
                p->succ->pred = p->pred;
            p->pred = head;
            p->succ = head->succ;
            if (p->succ)
                p->succ->pred = p;
            head->succ = p;
        }
    }
    p = head;
    Node *q = head;
    while (p){
        q = p->succ;
        delete p;
        p = q;
    }
    cout << cnt << endl;
    return 0;
}

ligongzzz's solution

#include "iostream"
using namespace std;

class myList {
public:
    class node {
    public:
        int data;
        node* next = nullptr;
    };

    node* head;
    node* rear;
    myList() {
        head = new node;
        rear = head;
    }

    ~myList() {
        for (auto p = head; p!= nullptr;) {
            auto temp = p;
            p = p->next;
            delete temp;
        }
    }

    int find(int num) {
        int ans = 0;
        auto p = head;
        for (; p->next != nullptr; p = p->next,ans++) {
            if (p->next->data == num) {
                ans++;
                break;
            }
        }
        //移动
        if (head != p&&p->next!=nullptr) {
            auto temp = head->next;
            head->next = p->next;
            p->next = head->next->next;
            head->next->next = temp;
        }
        return ans;
    }

    void insert(int num) {
        auto p = head;
        bool flag = true;
        /*for (; p->next != nullptr; p = p->next)
            if (p->next->data == num) {
                flag = false;
                break;
            }*/

        if (flag) {
            rear->next = new node;
            rear = rear->next;
            rear->data = num;
        }
    }
};

int main() {
    ios::sync_with_stdio(false);

    int n, m;
    cin >> n;

    myList newList;

    for (; n > 0; n--) {
        int temp;
        cin >> temp;
        newList.insert(temp);
    }

    cin >> m;

    long long ans = 0;
    for (; m > 0; m--) {
        int temp;
        cin >> temp;
        ans += newList.find(temp);
    }

    cout << ans;

    return 0;
}

Neight99's solution

#include <iostream>

using namespace std;

int compare = 0;

class sLinkList {
   private:
    struct Node {
        int data;
        Node *next;

        Node() : data(0), next(NULL) {}
        Node(int d, Node *n = NULL) : data(d), next(n) {}
        ~Node() {}
    };
    Node *head;
    int Length;

    Node *move(int) const;

   public:
    sLinkList();
    ~sLinkList();
    void push_back(const int &);
    void push_first(const int &);
    void clear();
    void remove(const int &);
    int find(const int &);
    void moveToFirst(const int &);
    int visit(const int &);
};

typename sLinkList::Node *sLinkList::move(int i) const {
    Node *p = head;
    while (i-- >= 0) {
        p = p->next;
    }

    return p;
}

sLinkList::sLinkList() {
    head = new Node;
    Length = 0;
}

sLinkList::~sLinkList() {
    clear();
    delete head;
}

void sLinkList::clear() {
    Node *p = head->next, *q;
    head->next = NULL;
    while (p != NULL) {
        q = p->next;
        delete p;
        p = q;
    }
    Length = 0;
}

void sLinkList::push_back(const int &x) {
    Node *p = move(Length - 1);
    p->next = new Node(x, p->next);
    ++Length;
}

void sLinkList::push_first(const int &x) {
    Node *p = head;
    p->next = new Node(x, p->next);
    ++Length;
}

void sLinkList::remove(const int &i) {
    if (i == -1) {
        return;
    } else {
        Node *p, *q;
        p = move(i - 1);
        q = p->next;
        p->next = q->next;
        delete q;
        --Length;
    }
}

int sLinkList::find(const int &x) {
    int n = 0;
    Node *p = head->next;
    while (p != NULL) {
        compare++;
        if (p->data == x) {
            return n;
        } else {
            p = p->next;
            n++;
        }
    }

    return -1;
}

int sLinkList::visit(const int &x) { return move(x)->data; }

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, m, tmp, pos;
    sLinkList lists;

    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> tmp;
        lists.push_back(tmp);
    }

    cin >> m;
    for (int i = 0; i < m; i++) {
        cin >> tmp;
        pos = lists.find(tmp);
        if (pos != -1) {
            lists.remove(pos);
            lists.push_first(tmp);
        }
    }

    cout << compare;

    return 0;
}

satgo1546's solution

#include <cstdio>
using namespace std;

int n;
// 不使用此数组中的第0个元素以零next作为表尾
struct {
    int x, next;
} a[100007];
int head;
int s;

void search(int x) {
    int i = head;
    int prev = 0;
    while (i) {
        s++;
        if (a[i].x == x) {
            if (prev) {
                a[prev].next = a[i].next;
                a[i].next = head;
                head = i;
            }
            return;
        }
        prev = i;
        i = a[i].next;
    }
}

int main(int argc, char **argv) {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i].x);
        a[i].next = i + 1;
    }
    head = 1;
    a[n].next = 0;
    scanf("%d", &argc);
    while (argc--) {
        int x;
        scanf("%d", &x);
        search(x);
    }
    printf("%d\n", s);
    return 0;
}

WashSwang's solution

#include <iostream>
using namespace std;
int ans,n,x,m,nex[20000],v[20000],last;
int main() {
    cin>>n;
    for (int i=1;i<=n;++i)
    {
        cin>>v[i];
        nex[i-1]=i;
    }
    cin>>m;
    for (int i=0;i<m;++i)
    {
        cin>>x;
        last=0;
        for (int j=nex[0];j;j=nex[j]){
            ans++;
            if (v[j]==x){
                nex[last]=nex[j];
                nex[j]=nex[0];
                nex[0]=j;
                break;
            }
            last=j;
        }
    }
    cout<<ans;
    return 0;
}

yyong119's solution

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;
const int MAXN = 10001;

int main() {

    int n, m;
    long times = 0;
    int a[MAXN];
    memset(a, 0, sizeof(a));
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    scanf("%d", &m);
    while (m) {
        scanf("%d", &a[0]);
        for (int i = 1; i <= n; ++i) {
            ++times;
            if (a[i] == a[0]) {
                for (int j = i; j >= 1; --j) a[j] = a[j - 1];
                break;
            }
        }
        --m;
    }
    printf("%d\n", times);
}