【数据结构】跳表+Trie树

Alex_Shen
2020-11-24 / 0 评论 / 0 点赞 / 108 阅读 / 8,028 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-04-06,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

问题 A: 跳表操作

题目描述

实现跳表数据结构,支持增加、查找和删除操作。为保证程序的可复现性,随机生成布尔结果的函数g()定义如下:
g() = 0 if X_t < 8; g() = 1 if X_t >= 8, for all t >= 1,
其中 X_t = (X_t-1 * a + c) % m, X_0 = 7, a=5, c=37, m=19
假定跳表的第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
48 89
45 48 59 89
48 75 //2+)对应2),输出插入3个新数据后的跳表
48 75 89
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 89
48 59 89 90

样例输入

48 45 45 59 89
75 48 90
45 59 30
45 75 87

样例输出

48
48 89
48 89
45 48 59 89
48 75
48 75 89
48 75 89
45 48 59 75 89 90
N N N N
48 48 48 48
N N N N
48
48 89
48 89
48 59 89 90

题解
参考代码链接

#include<iostream>
#include<vector>
#define INFINITY 99999
using namespace std;

const int Max=10;

struct node
{
    int key;
    node* forward[Max];
};

class skiplist
{
public:
    node* head;
    skiplist()
    {
        head = new node();
        head->key = -1;
        node* temp = new node();
        temp->key = INFINITY;
        for (int i = 0; i < Max; i++) {
            head->forward[i] = temp;
            temp->forward[i] = NULL;
        }
    }
    bool g()
    {
        static int x = 7;
        x = (x * 5 + 37) % 19;
        return x >= 8;
    }
    int randomX()
    {
        int sum = 0;
        while (g())
            sum++;
        return sum;
    }
    void add()
    {
        vector<int> v;
        int x;
        while (cin >> x) {
            v.push_back(x);
            if (cin.get() == '\n')
                break;
        }
        for (int i = 0; i < v.size(); i++) {
            insert(v[i]);
        }
    }
    void insert(int key)
    {
        node* p = head;
        node* data[Max];
        for (int i = Max - 1; i >= 0; i--) {
            while (p->forward[i]->key < key)
                p = p->forward[i];
            data[i] = p;
        }
        if (p->forward[0]->key != key) {
            int newlevel = randomX();
            p = new node();
            p->key = key;
            for (int i = 0; i <= newlevel; i++) {
                p->forward[i] = data[i]->forward[i];
                data[i]->forward[i] = p;
            }
        }
    }
    node* search(int key)
    {
        node* data[Max];
        node* p = head;
        for (int i = Max - 1; i >= 0; i--) {
            while ((p->forward[i]->key < key))
                p = p->forward[i];
            data[i] = p;
        }
        return p;
    }

    void Search()
    {
        vector<int> v;
        int x;
        while (cin >> x) {
            v.push_back(x);
            if (cin.get() == '\n')
                break;
        }
        for (int i = 0; i < v.size(); i++) {
            Print(v[i]);
        }
    }

    void Print(int key)
    {
        node* data[Max];
        node* p = head;
        for (int i = Max - 1; i >= 0; i--) {
            while (p->forward[i]->key < key)
                p = p->forward[i];
            data[i] = p;
        }
        if (p->forward[0]->key != key) {
            cout << "N N N N" << endl;
        }
        else {
            for (int i = 0; i < 4; i++) {
                if (!i) {
                    if (data[i]->key == -1)
                        cout << 'N';
                    else cout << data[i]->key;
                }
                else {
                    if (data[i]->key == -1)
                        cout << ' ' << 'N';
                    else cout << ' ' << data[i]->key;
                }
            }
            cout << endl;
        }
    }
    void print()
    {
        for (int i = Max - 1; i >= 0; i--) {
            bool flag = true;
            for (node* p = head->forward[i]; p->key != INFINITY; p = p->forward[i]) {
                if (p == head->forward[i]) {
                    cout << p->key;
                    flag = false;
                }
                else cout << ' ' << p->key;
            }
            if (!flag)
                cout << endl;
        }
    }
    void Delete() {
        vector<int> v;
        int x;
        while (cin >> x) {
            v.push_back(x);
            if (cin.get() == '\n')
                break;
        }
        for (int i = 0; i < v.size(); i++)
            Delete2(v[i]);
    }
    void Delete2(int key) {
        node* target = search(key)->forward[0];
        if (target->key == key) {
            node* p, * q;
            int i = Max - 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;
        }
    }
    void test() {
        add();
        print();
        add();
        print();
        Search();
        Delete();
        print();
    }
};

int main()
{
    skiplist list;
    list.test();
    return 0;
}



问题 B: 点名

题目描述

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

输入

第一行一个整数n,表示班上人数。
接下来 nn 行,每行一个字符串表示其名字(互不相同,且只含小写字母,长度不超过 5050)。
第 n+2n+2 行一个整数 mm,表示教练报的名字个数。
接下来 mm 行,每行一个字符串表示教练报的名字(只含小写字母,且长度不超过50)。

输出

对于每个名字,输出一行。
如果该名字正确且是第一次出现,输出 OK ;如果该名字错误,输出 WRONG;如果该名字正确但不是第一次出现,输出 REPEAT 。

样例输入

5
a
b
c
ad
acd
3
a
a
e

样例输出

OK
REPEAT
WRONG

题解

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;


struct Node {
	char data;
	Node* next[26];
};

class TrieTree {
public:
	Node* root;
	int get_num(struct Node* t);
	void level_print(struct Node* t);
};

int main() {
	TrieTree t;
	t.root = new Node[26];
	for (int i = 0; i < 26; i++) {
		t.root[i].data = NULL;
		for (int j = 0; j < 26; j++)
			t.root[i].next[j] = NULL;
	}
	char str[10000];
	int num = 0;
	while ((str[num] = getchar()) != '\n') {
		num++;
	}
	for (int i = 0; i < num; i++) {
		string string;
		while (str[i] != ' ' && i < num) {
			string += str[i];
			i++;
		}
		struct Node* p = &t.root[string[0] - 'a'];
		p->data = string[0];
		for (int j = 1; j < string.length(); j++)
		{
			if (p->next[string[j] - 'a'] != NULL)
			{
				p = p->next[string[j] - 'a'];
				continue;
			}
			struct Node* temp = new Node;
			temp->data = string[j];
			for (int k = 0; k < 26; k++)
				temp->next[k] = NULL;
			p->next[string[j] - 'a'] = temp;
			p = p->next[string[j] - 'a'];
		}
	}
	t.level_print(t.root);
	int n;
	cin >> n;
	string s;
	for (int i = 0; i < n; i++)
	{
		cin >> s;        //输入前缀
		struct Node* temp = &t.root[s[0] - 'a'];
		for (int j = 1; j < s.length(); j++)
		{
			temp = temp->next[s[j] - 'a'];
			if (temp == NULL)
				break;
		}
		if (temp == NULL)
			cout << 0 << endl;
		else
		{
			int coun = t.get_num(temp);
			cout << coun << endl;
		}
	}
	return 0;
}

int TrieTree::get_num(Node* t)
{
	int count = 0;
	for (int i = 0; i < 26; i++)
	{
		if (t->next[i] != NULL)
		{
			count += get_num(t->next[i]);
		}
	}
	if (count == 0)
		return 1;
	else
		return count;

}

void TrieTree::level_print(Node* t)
{
	queue<struct Node*> q1;
	for (int i = 0; i < 26; i++)
	{
		if (t[i].data != '\0')
		{
			q1.push(&t[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;

}

方法二:字典树
参考代码网址

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
struct Node{
    int son[27],f,vis;
}N[500010];
int n,m,cnt=1;
char name[55];
void insert(char name[]){
    int now=1;
    for(int i=0;name[i]!='\0';i++){
        if(N[now].son[name[i]-'a']) now=N[now].son[name[i]-'a'];
        else{N[now].son[name[i]-'a']=++cnt; now=cnt;}
    }
    N[now].f=1;
}
int find(char name[]){
    int now=1;
    for(int i=0;name[i]!='\0';i++){
        if(!N[now].son[name[i]-'a']) return -1;
        else now=N[now].son[name[i]-'a'];
    }
    if(N[now].f){
        if(N[now].vis) return 0;
        else{
            N[now].vis=1;
            return 1;
        }
    }
    else return -1;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%s",name);
        insert(name);
    }
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        scanf("%s",name);
        int pd=find(name);
        if(pd==-1) printf("WRONG\n");
        else if(pd==0) printf("REPEAT\n");
        else printf("OK\n");
    }
    return 0;
}

问题 C: 公共前缀

题目描述

输入一组单词,创建Trie树。输入字符串,计算以该字符串为公共前缀的单词数。
(提示:树结点有26个指针,指向单词的下一字母结点。)

输入

测试数据有多组,每组测试数据格式为:
第一行:一行单词,单词全小写字母,且单词不会重复,单词的长度不超过10
第二行:测试公共前缀字符串数量t
后跟t行,每行一个字符串

输出

每组测试数据输出格式为:
第一行:创建的Trie树的层次遍历结果
第2~t+1行:对每行字符串,输出树中以该字符串为公共前缀的单词数。

样例输入

abcd abd bcd efg hig
3
ab
bc
abcde

样例输出

abehbcficddggd
2
1
0

题解

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;


struct Node {
	char data;
	Node* next[26];
};

class TrieTree {
public:
	Node* root;
	int get_num(struct Node* t);
	void level_print(struct Node* t);
};

int main() {
	TrieTree t;
	t.root = new Node[26];
	for (int i = 0; i < 26; i++) {
		t.root[i].data = NULL;
		for (int j = 0; j < 26; j++)
			t.root[i].next[j] = NULL;
	}
	char str[10000];
	int num = 0;
	while ((str[num] = getchar()) != '\n') {
		num++;
	}
	for (int i = 0; i < num; i++) {
		string string;
		while (str[i] != ' ' && i < num) {
			string += str[i];
			i++;
		}
		struct Node* p = &t.root[string[0] - 'a'];
		p->data = string[0];
		for (int j = 1; j < string.length(); j++)
		{
			if (p->next[string[j] - 'a'] != NULL)
			{
				p = p->next[string[j] - 'a'];
				continue;
			}
			struct Node* temp = new Node;
			temp->data = string[j];
			for (int k = 0; k < 26; k++)
				temp->next[k] = NULL;
			p->next[string[j] - 'a'] = temp;
			p = p->next[string[j] - 'a'];
		}
	}
	t.level_print(t.root);
	int n;
	cin >> n;
	string s;
	for (int i = 0; i < n; i++)
	{
		cin >> s;        //输入前缀
		struct Node* temp = &t.root[s[0] - 'a'];
		for (int j = 1; j < s.length(); j++)
		{
			temp = temp->next[s[j] - 'a'];
			if (temp == NULL)
				break;
		}
		if (temp == NULL)
			cout << 0 << endl;
		else
		{
			int coun = t.get_num(temp);
			cout << coun << endl;
		}
	}
	return 0;
}

int TrieTree::get_num(Node* t)
{
	int count = 0;
	for (int i = 0; i < 26; i++)
	{
		if (t->next[i] != NULL)
		{
			count += get_num(t->next[i]);
		}
	}
	if (count == 0)
		return 1;
	else
		return count;

}

void TrieTree::level_print(Node* t)
{
	queue<struct Node*> q1;
	for (int i = 0; i < 26; i++)
	{
		if (t[i].data != '\0')
		{
			q1.push(&t[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;

}


0

评论区