数据结构与算法实验—— 查找及排序
③ 生成200个在[200, 10000]之间的整数保存数组A中，以此数组元素作为关键字，采用快速排序算法按非递减方式进行排序，给出操作的结果及相应的操作次数；① 生成100个在[200, 1000]之间的整数保存数组A中，以此数组元素作为关键字，采用希尔排序算法按非递减方式进行排序，给出操作的结果及相应的操作次数；④ 生成500个在[200, 10000]之间的整数保存数组A中，以此数组元素作为
HASH表的建立及查找
生成50个在[200, 1000]之间互不相同的整数保存数组A中，以此数组元素作为关键字，设计实现以下操作的程序：
① 建立对应的HASH表并输出所建立的HASH表：HASH函数为h(k)=key% p（p为20以内的某个素数），采用链地址法解决冲突；
② 在所建立的HASH表中查找指定的关键字（输入要查找的整数），给出操作的结论及相应的操作次数；
③ 在所建立的HASH表中删除指定的关键字（输入要删除的整数），给出操作的结论及相应的操作次数；
④ 主函数通过调用函数实现以上操作。
⑴ 所定义的数据结构:
typedef struct MyHash {
int key;
int value;
struct MyHash* next;
}MyHash;
MyHash hash[17];
1
2
3
4
5
6
7
8
⑵ 主要操作算法思想或算法步骤:
#include<stdio.h>
#include<malloc.h>
typedef struct MyHash {
int key;
int value;
struct MyHash* next;
}MyHash;
MyHash hash[17];
//主要操作：
//初始化
void ini(MyHash hash[], int n) {
for (int i = 0; i < n; i++) {
hash[i].key = -1;
hash[i].value = -1;
hash[i].next = NULL;
}
}
//添加。返回1为成功，-1为失败（重复）
int addData(int key, int value) {
int t = key % 17;
if (hash[t].key == -1) {
hash[t].key = key;
hash[t].value = value;
return 1;
}
MyHash* p = (MyHash*)malloc(sizeof(MyHash));
*p = hash[t];
if (p->next == NULL) {
MyHash* h = (MyHash*)malloc(sizeof(MyHash));
h->key = key;
h->value = value;
h->next = NULL;
hash[t].next = h;
return 1;
}
while (p->next != NULL) {
if (p->next->key == key) {
return -1;
}
if (p->next->key ==-1) {
p->next->key = key;
p->next->value = value;
return 1;
}
p = p->next;
}
MyHash* h = malloc(sizeof(MyHash));
h->key = key;
h->value = value;
h->next = NULL;
p->next = h;
return 1;
}
//查找
int search(int key) {
int t = key % 17;
int n = 0;//查找次数
n++;
if (hash[t].key == key) {
printf("查找成功，查找次数为%d次\n", n);
return n;
}
MyHash* p = (MyHash*)malloc(sizeof(MyHash));
*p = hash[t];
n++;
if (p == NULL) {
printf("查找失败，查找次数为%d次\n", n);
return n;
}
while (p != NULL) {
n++;
if (p->key == key) {
printf("查找成功，查找次数为%d次\n", n);
return n;
}
p = p->next;
}
printf("查找失败，查找次数为%d次\n", n);
return n;
}
//删除
int delete(int key) {
int t = key % 17;
int n = 0;//操作次数
n++;
if (hash[t].key == key) {
hash[t].key = -1;
hash[t].value = -1;
n += 2;
printf("删除成功，操作次数为%d次\n", n);
return n;
}
MyHash* p = (MyHash*)malloc(sizeof(MyHash));
*p = hash[t];
n++;
if (p == NULL) {
printf("查找失败，不存在此数，操作次数为%d次\n", n);
return n;
}
while (p != NULL) {
n++;
if (p->key == key) {
hash[t].key = -1;
hash[t].value = -1;
n += 2;
printf("删除成功，操作次数为%d次\n", n);
return n;
}
p = p->next;
n++;
}
printf("查找失败，不存在此数，操作次数为%d次\n", n);
return n;
}
//步骤与测试
main() {
ini(&hash, 17);
int count = 50;
int i;
while (count > 0) {
i = rand();
if (i > 199 && i < 1001) {
if (addData(i, 0) > 0) {
count--;
}
}
}
printf("查找500(500为自定义的数)\n");
search(500);
printf("\n");
printf("查找%d(%d为生成的随机数)\n", i,i);
search(i);
printf("\n");
printf("删除%d\n", i);
delete(i);
}
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
排序
① 生成100个在[200, 1000]之间的整数保存数组A中，以此数组元素作为关键字，采用希尔排序算法按非递减方式进行排序，给出操作的结果及相应的操作次数；
③ 生成200个在[200, 10000]之间的整数保存数组A中，以此数组元素作为关键字，采用快速排序算法按非递减方式进行排序，给出操作的结果及相应的操作次数；
④ 生成500个在[200, 10000]之间的整数保存数组A中，以此数组元素作为关键字，采用堆排序算法按非递减方式进行排序，给出操作的结果及相应的操作次数；
⑤ 主函数通过调用函数实现以上操作。
⑴ 所定义的数据结构:
int A[100];
int count = 0;//计数器
1
2
⑵ 主要操作算法思想或算法步骤:
//主要操作：
//希尔排序
int shell_sort(int array[], int length) {
int i;
int j;
int k;
int step; //分组的步长
int temp; //哨兵
int count = 0;//计算操作数
for (step = length / 2; step > 0; step = step / 2) {
for (i = 0; i < step; i++, count++) {
for (j = i + step; j < length; j = j + step) { //单独一次的插入排序
if (array[j] < array[j - step]) {
temp = array[j]; //哨兵
k = j - step;
while (k >= 0 && array[k] > temp) {
array[k + step] = array[k];
k = k - step;
count += 4;
}
array[k + step] = temp;
count += 5;
}
}
}
}
return count;
}
//快速排序
int quickSort(int* arr, int low, int high) {
int c = 0;
c++;
if (low < high) {
int i = low;
int j = high;
int k = arr[low];
while (i < j) {
c+=5;
while (i < j && arr[j] >= k) { // 从右向左找第一个小于k的数
j--; c++;
}
if (i < j) {
arr[i++] = arr[j];
}
while (i < j && arr[i] < k) { // 从左向右找第一个大于等于k的数
i++; c++;
}
if (i < j) {
arr[j--] = arr[i];
}
}
arr[i] = k;
c += 6;
// 递归调用
c+=quickSort(arr, low, i - 1); // 排序k左边
c+=quickSort(arr, i + 1, high); // 排序k右边
}
return c;
}
//堆排序
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
int percDown(int A[], int i, int N) {
int child;
int temp;
int c=0;
c+=2;
for (temp = A[i]; 2 * i + 1 < N; i = child) {
c+=2;
child = 2 * i + 1; //数组下标是从0开始的
c++;
c++;
if (child != N - 1 && A[child + 1] > A[child]) {
++child; //找到最大的儿子节点
c++;
}
c++;
if (temp < A[child]) {
A[i] = A[child];
c++;
}
else
break;
}
A[i] = temp;
c++;
return c;
}
int heapSort(int A[], int N) {
int i;
int c=0;//操作次数
c+=2;
for (i = N / 2; i >= 0; --i) {
c += 2;
c+=percDown(A, i, N); //构造堆
}
for (i = N - 1; i > 0; --i) {
c += 2;
swap(&A[0], &A[i]); //将最大元素（根）与数组末尾元素交换，从而删除最大元素，重新构造堆
c += 3;
c+=percDown(A, 0, i);
}
return c;
}
//测试函数
main() {
int A[100];
int count = 0;//计数器
while (count<100) {
int num = rand();
if (num >= 200 && num <= 1000) {
A[count] = num;
count++;
}
}
printf("未排序：\n");
for (int i = 0; i < 100; i++)
printf("%d ", A[i], i);
printf("\n\n");
int c=0;//操作次数
//c=shell_sort(A, 100);//希尔排序
//c=quickSort(A, 0, 99);//快速排序
c=heapSort(A, 100);//堆排序
printf("排序后：\n");
for (int i = 0; i < 100; i++)
printf("%d ", A[i]);
printf("\n\n操作次数：%d\n", c);
}
魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。
更多推荐
5
0- 0
已为社区贡献1条内容
所有评论(0)