[NEFU锐格数据结构]实验七查找有关的操作[NEFU锐格数据结构]实验七查找有关的操作

83 阅读 0 评论 55 点赞

我是靠谱客的博主要减肥板栗，这篇文章主要介绍[NEFU锐格数据结构]实验七查找有关的操作[NEFU锐格数据结构]实验七查找有关的操作，现在分享给大家，希望可以做个参考。

[NEFU锐格数据结构]实验七查找有关的操作

推荐阅读：[数据结构]NEFU 大二上锐格实验参考目录

题目

7083

二分查找统计次数
个人觉得这题统计具体次数意义不大，如果你确保你的二分思想正确那就随他去吧，背个板子完事了。
数据是否重复，二分区间的开闭，mid的上下取整都会影响具体次数。我觉得只要是logN级别的都ok。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<iostream>
#include<algorithm>
using namespace std;
int a[105];
int q=0;
int bs(int l,int r,int x){
while(l<=r){
int mid=(l+r)/2;
q++;
if(a[mid]>x)r=mid-1;
else if(a[mid]==x)return mid;
else l=mid+1;
}
return 0;
}
int main(){
int x=0,n=0;
while(cin>>x&&x)a[++n]=x;
sort(a+1,a+1+n);
int find=0;cin>>find;
cout<<bs(1,n,find)<<" ";
cout<<q;
return 0;
}

7081

二叉排序树BST的创建，插入，查找，删除
建议建议看书，注释还可以

复制代码

#include<bits/stdc++.h>
using namespace std;
typedef struct BSTNode{
int key;
struct BSTNode *left,*right;
}BSTNode,*BSTree;
BSTNode *pre = NULL;
void InOrder(BSTree T){
if(T){
InOrder(T->left);
cout<<T->key<<" ";
InOrder(T->right);
}
}
void InsertBST(BSTree &T,int e){
if(!T){
BSTree S = new BSTNode;
S->key=e;S->left=S->right=NULL;
T=S;
}else if(e<T->key){
InsertBST(T->left,e);
}else{
InsertBST(T->right,e);
}
}
void CreateBST(BSTree &T){
T=NULL;int x;
while(cin>>x,x){
InsertBST(T,x);
}
}
void DeleteBST(BSTree &T,int del){
BSTree p=T,fa=NULL;
while(p){
if(p->key==del)break;
fa=p;
if(p->key>del)p=p->left;
else p=p->right;
}
if(!p)return;
BSTree q=p;
if(p->left&&p->right){
BSTree s=p->left;
while(s->right){q=s;s=s->right;}
p->key=s->key;
if(q!=p)q->right=s->left;
else q->left=s->left;
delete s;
return;
}else if(!p->right){
p=p->left;
}else if(!p->left){
p=p->right;
}
if(!fa)T=p;
else if(q==fa->left)fa->left=p;
else fa->right=p;
delete q;
}
BSTree SearchBST(BSTree T,int e){
if(!T||T->key==e)return T;
else if(e<T->key)return SearchBST(T->left,e);
else return SearchBST(T->right,e);
}
int main(){
BSTree T;
CreateBST(T);
InOrder(T);puts("");
int find;cin>>find;
if(SearchBST(T,find)!=NULL)puts("该数存在");
else puts("该数不存在");
int del;cin>>del;
DeleteBST(T,del);
InOrder(T);
return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<bits/stdc++.h>
using namespace std;
typedef struct BSTNode{
int key;
struct BSTNode *left,*right;
}BSTNode,*BSTree;
BSTNode *pre = NULL;
void InOrder(BSTree T){
if(T){
InOrder(T->left);
cout<<T->key<<" ";
InOrder(T->right);
}
}
void InsertBST(BSTree &T,int e){
if(!T){
BSTree S = new BSTNode;
S->key=e;S->left=S->right=NULL;
T=S;
}else if(e<T->key){
InsertBST(T->left,e);
}else{
InsertBST(T->right,e);
}
}
void CreateBST(BSTree &T){
T=NULL;int x;
while(cin>>x,x){
InsertBST(T,x);
}
}
void DeleteBST(BSTree &T,int del){
BSTree p=T,fa=NULL;
while(p){
if(p->key==del)break;
fa=p;
if(p->key>del)p=p->left;
else p=p->right;
}
if(!p)return;
BSTree q=p;
if(p->left&&p->right){
BSTree s=p->left;
while(s->right){q=s;s=s->right;}
p->key=s->key;
if(q!=p)q->right=s->left;
else q->left=s->left;
delete s;
return;
}else if(!p->right){
p=p->left;
}else if(!p->left){
p=p->right;
}
if(!fa)T=p;
else if(q==fa->left)fa->left=p;
else fa->right=p;
delete q;
}
BSTree SearchBST(BSTree T,int e){
if(!T||T->key==e)return T;
else if(e<T->key)return SearchBST(T->left,e);
else return SearchBST(T->right,e);
}
int main(){
BSTree T;
CreateBST(T);
InOrder(T);puts("");
int find;cin>>find;
if(SearchBST(T,find)!=NULL)puts("该数存在");
else puts("该数不存在");
int del;cin>>del;
DeleteBST(T,del);
InOrder(T);
return 0;
}

7051

插入法构建哈希表，开放地址法：线性探测法处理冲突

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <cstring>
#include <iostream>
using namespace std;
const int N = 105;
const int null = 0x3f3f3f3f;
//规定空指针为 null 0x3f3f3f3f
int h[N];
int m,p;
bool is_prime(int x){//判质数
if(x<2)return 0;
for(int i=2;i*i<=x;i++){
if(x%i==0)return 0;
}
return 1;
}
void get_p(int st){//找<=st的最大质数
while(st){
if(is_prime(st)){
p=st;
return;
}
st--;
}
}
int find(int x) {
int t = (x % p + p) % p;
while (h[t] != null && h[t] != x) {
t++;
if (t == p) {
t = 0;
}
}
return t;
}
int main() {
cin>>m;
get_p(m);
memset(h, 0x3f, sizeof h);
//规定空指针为 0x3f3f3f3f
for(int i=0;i<m;i++)cout<<i<<"
";puts("");
int x;
while(cin>>x,x)h[find(x)]=x;
for(int i=0;i<m;i++){
if(h[i]==null)cout<<0<<"
";
else cout<<h[i]<<"
";
}
return 0;
}

7050

~~（开脸寻址法）~~ 开链寻址法，p固定为13了

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
int m;
struct Node{
int x;
Node *next;
}Hash[15];
void Hashfun(int x){
int h = x % 13;
Node *tmp = new Node;
tmp->x = x;
tmp->next = Hash[h].next;
Hash[h].next = tmp;
}
void Print(int x){
Node *p = Hash[x].next;
while(p){
cout << p->x << " ";
p = p->next;
}
}
int main(){
int x;
while (cin >> x && x)Hashfun(x);
for(int i = 0;i<13;i++){
cout << i << ":"; Print(i);puts("");
}
return 0;
}