数据结构（荣誉）实验二跳表 Trie树-阿里云开发者社区

1. 跳表操作

题目描述

实现跳表数据结构，支持增加、查找和删除操作。为保证程序的可复现性，随机生成布尔结果的函数g()定义如下：

假定跳表的第0层存放所有元素。为决定一个不在现有跳表中且待插入的新元素a，可以上升到第h层（h初始值为0），程序反复调用g()，若g()=1，则上升一层，即++h，若g()=0则停止上升; 因此，元素a将位于0,1,…,h层。

输入

注意：符号//及其后为注解，不是输入/输出的内容。整数之间有1个空格分隔

48 45 45 59 89 //1）随机输入初值数据，可能存在重复（重复的元素不插入跳表）

75 48 90 //2）连续插入跳表的3个整数，若跳表中已经有相应元素，则不插入

45 59 30 //3）在2）之后，从跳表中，连续查找的3个整数，对每个待查整数，输出所在各层的严格下界

45 75 87 //4）在3) 之后，从跳表中，连续删除的3个整数

输出

48 //1+)对应输入1)，输出建立的跳表，从最高层到最底层，递增输出每层元素（每层元素不重复）

48 89

45 48 59 89

48 75 //2+)对应2)，输出插入3个新数据后的跳表

48 75 89

45 48 59 75 89 90

N N N N //3+)对于要查找的45，输出每层的严格下界b_i={N,N,N,N}, 满足b_i < 45, N表示无穷小

48 48 48 48 //3+)对于要查找的59，输出b_i={48,48,48,48}, 满足b_i < 59

N N N N

48 //4)删除3个整数之后的跳表。

48 89

48 59 89 90

样例输入

48 45 45 59 89

75 48 90

45 59 30

45 75 87

样例输出

48 89

45 48 59 89

48 75

48 75 89

45 48 59 75 89 90

N N N N

48 48 48 48

N N N N

48 89

48 59 89 90

题解

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
#define MAXLENGTH 9999999
#define MAXLEVEL 10
class Node {
public:
    int data;
    Node *forward[MAXLEVEL];
};
class SkipList {
public:
    Node *head;
    SkipList() {
        head = new Node();
        head->data = -1;
        Node *p = new Node();
        p->data = MAXLENGTH;
        for (int i = MAXLEVEL - 1; i >= 0; --i) {
            head->forward[i] = p;
            p->forward[i] = NULL;
        }
    }
    void ope() {
        Add();
        Print();
        Add();
        Print();
        Search();
        Delete();
        Print();
    }
    bool g() {
        static int x = 7;
        x = (x * 5 + 37) % 19;
        return x >= 8;
    }
    int getRandom() {
        int count = 0;
        while (g()) {
            count++;
        }
        return count;
    }
    void Add() {
        vector<int> temp;
        int b;
        while (cin >> b) {
            temp.push_back(b);
            if (cin.get() == '\n') {
                break;
            }
        }
        for (int i : temp) {
            Insert(i);
        }
    }
    void Insert(int key) {
        Node *p = head;
        Node *update[MAXLEVEL];
        for (int i = MAXLEVEL - 1; i >= 0; i--) {
            while ((p->forward[i]->data < key)) {
                p = p->forward[i];
            }
            update[i] = p;
        }
        if (p->forward[0]->data != key) {
            int newlevel = getRandom();
            p = new Node();
            p->data = key;
            for (int i = 0; i <= newlevel; i++) {
                p->forward[i] = update[i]->forward[i];
                update[i]->forward[i] = p;
            }
        }
    }
    Node *search(int key) {
        Node *update[MAXLEVEL];
        Node *p = head;
        for (int i = MAXLEVEL - 1; i >= 0; i--) {
            while ((p->forward[i]->data < key)) {
                p = p->forward[i];
            }
            update[i] = p;
        }
        return p;
    }
    void Search() {
        vector<int> s1;
        int b;
        while (cin >> b) {
            s1.push_back(b);
            if (cin.get() == '\n') {
                break;
            }
        }
        for (int i : s1) {
            searchPrint(i);
        }
    }
    void searchPrint(int key) {
        Node *update[MAXLEVEL];
        Node *p = head;
        for (int i = MAXLEVEL - 1; i >= 0; i--) {
            while ((p->forward[i]->data < key)) {
                p = p->forward[i];
            }
            update[i] = p;
        }
        if (p->forward[0]->data != key) {
            cout << "N N N N" << endl;
        } else {
            for (int i = 0; i < 4; i++) {
                if (!i) {
                    if (update[i]->data == -1) {
                        cout << 'N';
                    } else {
                        cout << update[i]->data;
                    }
                } else {
                    if (update[i]->data == -1) {
                        cout << ' ' << 'N';
                    } else {
                        cout << ' ' << update[i]->data;
                    }
                }
            }
            cout << endl;
        }
    }
    void Print() {
        for (int i = MAXLEVEL - 1; i >= 0; i--) {
            bool flag = true;
            for (Node *p = head->forward[i]; p->data != MAXLENGTH; p = p->forward[i]) {
                if (p == head->forward[i]) {
                    cout << p->data;
                    flag = false;
                } else {
                    cout << ' ' << p->data;
                }
            }
            if (!flag) {
                cout << endl;
            }
        }
    }
    void Delete() {
        vector<int> temp;
        int b;
        while (cin >> b) {
            temp.push_back(b);
            if (cin.get() == '\n') {
                break;
            }
        }
        for (int i : temp) {
            DeleteItem(i);
        }
    }
    void DeleteItem(int key) {
        Node *target = search(key)->forward[0];
        if (target->data == key) {
            Node *p, *q;
            int i = MAXLEVEL - 1;
            while (i >= 0) {
                p = q = head;
                while (p && p != target) {
                    q = p;
                    p = p->forward[i];
                }
                if (p) {
                    q->forward[i] = p->forward[i];
                }
                i--;
            }
            delete target;
        }
    }
};
int main() {
    SkipList task;
    task.ope();
    return 0;
}

2. 点名

题目描述

XS中学化学竞赛组教练是一个酷爱炉石的人。他会一边搓炉石一边点名以至于有一天他连续点到了某个同学两次。校长任命你为特派探员，每天记录他的点名。校长会提供化学竞赛学生的人数和名单，而你需要告诉校长他有没有点错名。

输入

第一行一个整数n，表示班上人数。

接下来 n 行，每行一个字符串表示其名字（互不相同，且只含小写字母，长度不超过 50）。

第 n+2 行一个整数 m，表示教练报的名字个数。

接下来 m 行，每行一个字符串表示教练报的名字（只含小写字母，且长度不超过50）。

输出

对于每个名字，输出一行。

如果该名字正确且是第一次出现，输出 OK ；如果该名字错误，输出 WRONG；如果该名字正确但不是第一次出现，输出 REPEAT 。

样例输入

acd

样例输出

REPEAT

WRONG

题解

#include <iostream>
using namespace std;
class status {
public:
    string name;
    bool check = false;
};
int main() {
    int n;
    cin >> n;
    status *s = new status[n];
    for (int i = 0; i < n; i++) {
        string temp;
        cin >> temp;
        s[i].name = temp;
    }
    int t;
    cin >> t;
    for (int i = 0; i < t; i++) {
        string ope;
        cin >> ope;
        bool flag = false;
        for (int i = 0; i < n; i++) {
            if (s[i].name == ope) {
                flag = true;
                if (s[i].check) {
                    cout << "REPEAT" << endl;
                } else {
                    cout << "OK" << endl;
                }
                s[i].check = true;
                break;
            }
        }
        if (!flag) {
            cout << "WRONG" << endl;
        }
    }
    return 0;
}

3.公共前缀

题目描述

输入一组单词，创建Trie树。输入字符串，计算以该字符串为公共前缀的单词数。

（提示：树结点有26个指针，指向单词的下一字母结点。）

输入

测试数据有多组，每组测试数据格式为：

第一行：一行单词，单词全小写字母，且单词不会重复，单词的长度不超过10

第二行：测试公共前缀字符串数量t

后跟t行，每行一个字符串

输出

每组测试数据输出格式为：

第一行：创建的Trie树的层次遍历结果

第2~t+1行：对每行字符串，输出树中以该字符串为公共前缀的单词数。

样例输入

abcd abd bcd efg hig

abcde

样例输出

abehbcficddggd

题解

#include <iostream>
#include <queue>
#include <string>
using namespace std;
struct Node
{
    char data;
    struct Node *next[26];
};
int count(struct Node *node)
{
    int num = 0;
    for (int i = 0; i < 26; i++)
    {
        if (node->next[i] != NULL)
        {
            num += count(node->next[i]);
        }
    }
    if (num == 0)
    {
        return 1;
    }
    else
    {
        return num;
    }
}
int main()
{
    Node *tree = new Node[26];
    //初始化
    for (int i = 0; i < 26; i++)
    {
        tree[i].data = '0';
        for (int j = 0; j < 26; j++)
        {
            tree[i].next[j] = NULL;
        }
    }
    //读入每个单词
    char str[10000];
    int num = 0;
    while ((str[num] = getchar()) != '\n')
    {
        num++;
    }
    for (int i = 0; i < num; i++)
    {
        string t;
        while ((str[i] != ' ') && i < num)
        {
            t += str[i];
            i++;
        }
        Node *father = &tree[t[0] - 'a'];
        father->data = t[0];
        for (int j = 1; j < t.length(); j++)
        {
            if (father->next[t[j] - 'a'] != NULL)
            {
                father = father->next[t[j] - 'a'];
                continue;
            }
            struct Node *temp = new Node;
            temp->data = t[j];
            for (int k = 0; k < 26; k++)
            {
                temp->next[k] = NULL;
            }
            father->next[t[j] - 'a'] = temp;
            father = father->next[t[j] - 'a'];
        }
    }
    //层次遍历
    queue<struct Node *> q1;
    for (int i = 0; i < 26; i++)
    {
        if (tree[i].data != '0')
        {
            q1.push(&tree[i]);
        }
    }
    while (!q1.empty())
    {
        struct Node *t = q1.front();
        q1.pop();
        cout << t->data;
        for (int i = 0; i < 26; i++)
        {
            if (t->next[i] != NULL)
            {
                q1.push(t->next[i]);
            }
        }
    }
    cout << endl;
    //测试公共前缀字符串数量
    int n;
    cin >> n;
    while (n--)
    {
        string temp;
        cin >> temp;
        struct Node *father = &tree[temp[0] - 'a'];
        for (int j = 1; j < temp.length(); j++)
        {
            father = father->next[temp[j] - 'a'];
            if (father == NULL)
            {
                break;
            }
        }
        if (father == NULL)
            cout << 0 << endl;
        else
        {
            cout << count(father) << endl;
        }
    }
    return 0;
}

数据结构（荣誉）实验二跳表 Trie树

1. 跳表操作

题目描述

输入

输出

样例输入

样例输出

题解

2. 点名

题目描述

输入

输出

样例输入

样例输出

题解

3.公共前缀

题目描述

输入

输出

样例输入

样例输出

题解

热门文章

最新文章

相关课程

相关电子书

数据结构（荣誉）实验二 跳表 Trie树

1. 跳表操作

题目描述

输入

输出

样例输入

样例输出

题解

2. 点名

题目描述

输入

输出

样例输入

样例输出

题解

3.公共前缀

题目描述

输入

输出

样例输入

样例输出

题解

热门文章

最新文章

相关课程

相关电子书

数据结构（荣誉）实验二跳表 Trie树