数据结构第五次上机代码

发表于 更新于 分类于 ， 阅读次数： Waline： 本文字数： 11k 阅读时长 ≈ 10 分钟
线性查找：顺序查找、折半查找、分块查找（感觉有问题） 二叉排序树 哈希查找
报告

线性查找

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<malloc.h>
#include<math.h>
using namespace std;
#define OK 1 
#define ERROR 0  
#define LIST_INIT_SIZE 10
#define LISTINCREMRNT 10 
typedef int Status; 
typedef int ElemType; 
typedef struct
{
	ElemType* elem;//储存空间基址
	int length;//当前长度
	int listsize;//当前分配的存储容量
}SqList;
//初始化一个空的表
Status InitList(SqList* L)
{
	L->elem = (ElemType*)__vcrt_malloc_normal(LIST_INIT_SIZE * sizeof(ElemType));
	if (!(L->elem))
		exit(OVERFLOW);//分配失败
	L->length = 0;//长度
	L->listsize = LIST_INIT_SIZE;//容量
	return OK;
}
//插入
Status ListInsert(SqList* L, int i, ElemType e)
{
	if (i<1 || i>L->length + 1)
		return ERROR;
	ElemType* q = &(L->elem[i - 1]), *p = NULL;// q为插入位置
	for (p = &(L->elem[L->length - 1]); p >= q; --p)
		* (p + 1) = *p;// 插入位置及之后的元素后移
	*q = e;// 插入e
	++(L->length);// 表长增加1
	if (L->length == L->listsize) {
		ElemType*  newbase = (ElemType*)realloc(L->elem, (L->listsize + LISTINCREMRNT) * sizeof(ElemType));
		if (!newbase)
			exit(OVERFLOW);
		L->elem = newbase;// 新基址
		L->listsize += LISTINCREMRNT;// 增加存储容量
	}
	return OK;
}
//遍历表
Status myPrintf(SqList* L)
{
	for (int i = 0; i < L->length; i++) {
		cout << "第" << i + 1 << "个值------------" << (L->elem[i]) << "\n";
	}
	return OK;
}
//顺序查找
int Search_SS(SqList* L,ElemType e)
{
	for (int i =0 ; i<L->length ; i++)
	{
		if (L->elem[i]==e)
		{
			return i + 1;
		}
	}
	return -1;
}
//顺序查找所有
Status Search_SS_ALL(SqList* L, ElemType e)
{
	int k = 0;
	for (int i = 0; i<L->length; i++)
	{
		if (L->elem[i] == e)
		{
			k++;
			cout << i+1 << " ";
		}
	}
	if (k == 0)cout << -1;
	return OK;
}
//折半查找
int Search_Bin(SqList* L, ElemType e)
{
	int low = 0, high = L->length - 1,mid=0;
	while(low<=high)
	{
		mid = (int)floor(low*0.5 + high*0.5);
		if (L->elem[mid]==e)
		{
			return mid + 1;
		}
		else if (L->elem[mid]>e)
		{
			high = mid - 1;
		}
		else
		{
			low = mid + 1;
		}
	}
	return -1;
}
//分块查找
int Search_BS(SqList* L, ElemType e)
{
	int high = L->length-1, low = 0;
	int mid = 0;
	int n = L->length;
	int k = (int)sqrt(L->length);
	for (int i = 0; i < k; i++)
	{
		if (e==L->elem[0+i*k])
		{
			return 0 + i*k + 1;
		}
		else if (e>L->elem[0+i*k])
		{
			low = 0 + i*k;
			high = 0 + (i + 1)*k - 1 > L->length - 1 ? L->length - 1 : 0 + (i + 1)*k - 1;
		}
	}
	while (low <= high)
	{
		mid = (int)floor(low*0.5 + high*0.5);
		if (L->elem[mid] == e)
		{
			return mid + 1;
		}
		else if (L->elem[mid]>e)
		{
			high = mid - 1;
		}
		else
		{
			low = mid + 1;
		}
	}
	return -1;
}
//清空缓冲区的一行
void myclear()
{
	cin.clear();
	cin.ignore(numeric_limits<std::streamsize>::max(), '\n');
}
//排序
Status mysort(SqList* L)
{
	for (int i = 0; i < L->length; i++)
	{
		for (int k = 0; k < L->length-i-1; k++)
		{
			if (L->elem[k] > L->elem[k + 1])
			{
				L->elem[k] = L->elem[k]^L->elem[k+1];
				L->elem[k + 1] = L->elem[k] ^ L->elem[k + 1];
				L->elem[k] = L->elem[k] ^ L->elem[k + 1];;
			}
		}
	}
	return OK;
}
int main(void)
{
	SqList* L = (SqList*)__vcrt_malloc_normal(sizeof(SqList));
	InitList(L);
	cout << "输入插入个数" << endl;
	int n = 0;
	cin >> n;
	myclear();
	cout << "输入元素" << endl;
	ElemType e = NULL;
	for (int i = 0; i < n; i++)
	{
		cin >> e;
		ListInsert(L, i+1, e);
	}
	myclear();
	cout << "输入结果为:" << endl;
	myPrintf(L);
	cout << "输入查找元素" << endl;
	cin >> e;
	myclear();
	cout << "顺序查找到元素位置 " << Search_SS(L, e)<< endl;
	cout << "顺序查找到元素位置有 "; Search_SS_ALL(L, e);
	cout << endl;
	cout << "输入查找元素" << endl;
	cin >> e;
	myclear();
	cout << "顺序查找到元素位置 " << Search_SS(L, e) << endl;
	cout << "顺序查找到元素位置有 "; Search_SS_ALL(L, e);
	cout << endl;
	cout << "折半查找需有序,排序后:" << endl;
	mysort(L);
	myPrintf(L); 
	cout << "输入查找元素" << endl;
	cin >> e;
	myclear();
	cout << "折半查找到元素位置 " << Search_Bin(L, e) << endl;
	cout << "分块查找到元素位置 " << Search_BS(L, e) << endl;
	cout << "输入查找元素" << endl;
	cin >> e;
	myclear();
	cout << "折半查找到元素位置 " << Search_Bin(L, e) << endl;
	cout << "分块查找到元素位置 " << Search_BS(L, e) << endl;
	system("pause");
	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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <limits.h>
using namespace std;
//结构
typedef int DataType;
typedef struct BST_Node {
	DataType data;
	struct BST_Node *lchild, *rchild;
}BST_T, *BST_P;
/*//插入
void InsertBST(BST_T *T, DataType data)
{
	if (!T)
	{
		BST_P S = new BST_Node;
		S->data = data;
		S->lchild = S->rchild = NULL;
		T = S;
	}
	else if (data<T->data)
	{
		InsertBST(T->lchild, data);
	}
	else if (data>T->data)
	{
		InsertBST(T->rchild, data);
	}
}*/
//查找
BST_P Search_BST(BST_P root, DataType key)
{
	if (root == NULL)
		return NULL;
	if (key > root->data) //查找右子树  
		return Search_BST(root->rchild, key);
	else if (key < root->data) //查找左子树  
		return Search_BST(root->lchild, key);
	else
		return root;
}
void Insert_BST(BST_P *root, DataType data)
{
	//初始化插入节点
	BST_P p = (BST_P)malloc(sizeof(struct BST_Node));
	if (!p) return;
	p->data = data;
	p->lchild = p->rchild = NULL;
	//空树时，直接作为根节点
	if (*root == NULL)
	{
		*root = p;
		return;
	}
	//是否存在，已存在则返回，不插入
	if (Search_BST(*root, data) != NULL) return;
	//进行插入，首先找到要插入的位置的父节点
	BST_P tnode = NULL, troot = *root;
	while (troot)
	{
		tnode = troot;
		troot = (data < troot->data) ? troot->lchild : troot->rchild;
	}
	if (data < tnode->data)
		tnode->lchild = p;
	else
		tnode->rchild = p;
}
//创建
void CreateBST(BST_P *T, int a[], int n)
{
	int i;
	for (i = 0; i < n; i++)
	{
		Insert_BST(T, a[i]);
	}
}
//中序遍历
void MidOrderTraverse(BST_P T)
{
	if (T)
	{
		MidOrderTraverse(T->lchild);
		cout << T->data << " ";
		MidOrderTraverse(T->rchild);
	}
}
int main(void)
{
	int arr[] = { 17,12,19,10,15,18,25,8,11,13,16,22 };
	BST_P root = NULL;
	cout << "数据为: ";
	for (int i = 0; i < 12; i++)
		cout << arr[i] << " ";
	cout << endl;
	CreateBST(&root, arr, 12);
	cout << "创建后中序遍历: ";
	MidOrderTraverse(root);
	int data = 0;
	cout << "\n输入查找元素: ";
	cin >> data;
	BST_P result = Search_BST(root, data);
	if (result)
	{
		cout << "数据为: " << result->data << "地址为: " << result << endl;
	}
	else
	{
		cout << "未查询到,插入后遍历:" ;
		Insert_BST(&root, data);
		MidOrderTraverse(root);
	}
	cout << endl;
	cout << "\n输入查找元素: ";
	cin >> data;
	 result = Search_BST(root, data);
	if (result)
	{
		cout << "数据为: " << result->data << "地址为: " << result << endl;
	}
	else
	{
		cout << "未查询到,插入后遍历:" ;
		Insert_BST(&root, data);
		MidOrderTraverse(root);
	}
	cout << endl;
	system("pause");
	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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include<malloc.h>
using namespace std;
typedef int Status;
#define SUCCESS 1
#define UNSUCCESS 0
#define HASHSIZE 12  //定义哈希表长为数组的长度
#define NULLKEY -32768
//定义
typedef struct
{
	int *elem;  //数据元素存储的基址，动态分配数组
	int count;
}HashTable;
int m = 0;
//初始化
Status InitHashTable(HashTable *H)
{
	int i;
	m = HASHSIZE;
	H->count = m;
	H->elem = (int *)malloc(m * sizeof(int));
	for (i = 0; i < m; i++)
		H->elem[i] = NULLKEY;
	return SUCCESS;
}
//hash函数
int Hash(int key)
{
	return key % m; 
}
//插入
void InsertHash_1(HashTable *H, int key)
{
	int addr = Hash(key); 
	while (H->elem[addr] != NULLKEY) 
		addr = (addr + 1) % m;
	H->elem[addr] = key;
}
//插入
void InsertHash_2(HashTable *H, int key)
{
	int k = 2;
	int i = 0;
	int addr = Hash(key);
	while (H->elem[addr] != NULLKEY)
	{
		if (i%2==0)
		{
			addr = (addr + (int)pow((int)(k/2),2)) % m;
		}
		else
		{
			addr = (addr - (int)pow((int)(k / 2), 2)) % m;
		}
		++i;
		++k;
	}
	H->elem[addr] = key;
}
//查找
Status SearchHash_1(HashTable H, int key, int *addr)
{
	*addr = Hash(key);  
	while (H.elem[*addr] != key) 
	{
		*addr = (*addr + 1) % m;  
		if (H.elem[*addr] == NULLKEY || *addr == Hash(key))
			return UNSUCCESS;
	}
	return SUCCESS;
}
//查找
Status SearchHash_2(HashTable H, int key, int *addr)
{
	int k = 2;
	int i = 0;
	*addr = Hash(key);
	while (H.elem[*addr] != key)
	{
		if (i % 2 == 0)
		{
			*addr = (*addr + (int)pow((int)(k / 2), 2)) % m;
		}
		else
		{
			*addr = (*addr - (int)pow((int)(k / 2), 2)) % m;
			if (*addr<0)
			{
				*addr = abs(*addr);
			}
		}
		++i;
		++k;
		if (H.elem[*addr] == NULLKEY || *addr == Hash(key))
			return UNSUCCESS;
	}
	return SUCCESS;
}
int main(void)
{/*
	HashTable H;
	HashTable HH;
	int key=0;
	int addr = 0;
	InitHashTable(&H);
	InitHashTable(&HH);
	cout << "线性探测处理冲突"<<endl;
	cout << "输入12个数:" << endl;
	for (int i = 0; i < 12; i++)
	{
		cin >> key;
		InsertHash_1(&H, key);
	}
	cout << "插入结果:" << endl;
	for (int i = 0; i < 12; i++)
	{
		cout << H.elem[i] << " ";
	}cout << endl;
	cout << "输入查找元素:";
	cin >> key;
	printf("%s", SearchHash_1(H, key, &addr) == SUCCESS ? "查找成功\n" : "查找不成功\n");
	cout << "输入查找元素:";
	cin >> key;
	printf("%s", SearchHash_1(H, key, &addr) == SUCCESS ? "查找成功\n" : "查找不成功\n");
	cout << "------------------------------------------" << endl;
	cout << "二次探测处理冲突" << endl;
	cout << "输入12个数:" << endl;
	for (int i = 0; i < 12; i++)
	{
		cin >> key;
		InsertHash_2(&HH, key);
	}
	cout << "插入结果:" << endl;
	for (int i = 0; i < 12; i++)
	{
		cout << HH.elem[i] << " ";
	}cout << endl;
	cout << "输入查找元素:";
	cin >> key;
	printf("%s", SearchHash_2(HH, key, &addr) == SUCCESS ? "查找成功\n" : "查找不成功\n");
	cout << "输入查找元素:";
	cin >> key;
	printf("%s", SearchHash_2(HH, key, &addr) == SUCCESS ? "查找成功\n" : "查找不成功\n");*/
	int a[5] = { 0 };
	cout << *(a-1);
	system("pause");

	return 0;
}