数据结构顺序查找和折半查找代码中增加在顺序表中查找关键字最大值最小值的函数,并调用测试: void MaxMin(SSTable ST,int &min, int &max){}
时间: 2024-01-21 15:16:13 浏览: 96
10 查找_wantms3_顺序查找_分块查找_数据结构_折半查找分块查找_
以下是增加了查找最大值和最小值功能的顺序查找和折半查找的代码:
顺序查找:
```c++
#include <iostream>
using namespace std;
const int MAXSIZE = 100;
typedef struct {
int key;
// 其他数据项
} ElemType;
typedef struct {
ElemType *elem;
int length;
} SSTable;
// 初始化顺序表
void InitList(SSTable &ST, int length) {
ST.elem = new ElemType[length];
ST.length = length;
for (int i = 0; i < length; i++) {
ST.elem[i].key = i + 1;
}
}
// 查找最大值和最小值
void MaxMin(SSTable ST, int &min, int &max) {
min = ST.elem[0].key;
max = ST.elem[0].key;
for (int i = 1; i < ST.length; i++) {
if (ST.elem[i].key > max) {
max = ST.elem[i].key;
}
if (ST.elem[i].key < min) {
min = ST.elem[i].key;
}
}
}
// 顺序查找
int SeqSearch(SSTable ST, int key) {
ST.elem[0].key = key; // 哨兵
int i;
for (i = ST.length; ST.elem[i].key != key; i--);
return i;
}
int main() {
SSTable ST;
InitList(ST, MAXSIZE);
int min, max;
MaxMin(ST, min, max);
cout << "最小值:" << min << endl;
cout << "最大值:" << max << endl;
int key = 56;
int pos = SeqSearch(ST, key);
if (pos != 0) {
cout << "查找成功,位置为:" << pos << endl;
} else {
cout << "查找失败" << endl;
}
return 0;
}
```
折半查找:
```c++
#include <iostream>
using namespace std;
const int MAXSIZE = 100;
typedef struct {
int key;
// 其他数据项
} ElemType;
typedef struct {
ElemType *elem;
int length;
} SSTable;
// 初始化顺序表
void InitList(SSTable &ST, int length) {
ST.elem = new ElemType[length];
ST.length = length;
for (int i = 0; i < length; i++) {
ST.elem[i].key = i + 1;
}
}
// 查找最大值和最小值
void MaxMin(SSTable ST, int &min, int &max) {
min = ST.elem[0].key;
max = ST.elem[0].key;
for (int i = 1; i < ST.length; i++) {
if (ST.elem[i].key > max) {
max = ST.elem[i].key;
}
if (ST.elem[i].key < min) {
min = ST.elem[i].key;
}
}
}
// 折半查找
int BinarySearch(SSTable ST, int key) {
int low = 0, high = ST.length - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (ST.elem[mid].key == key) {
return mid;
} else if (ST.elem[mid].key < key) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return 0;
}
int main() {
SSTable ST;
InitList(ST, MAXSIZE);
int min, max;
MaxMin(ST, min, max);
cout << "最小值:" << min << endl;
cout << "最大值:" << max << endl;
int key = 56;
int pos = BinarySearch(ST, key);
if (pos != 0) {
cout << "查找成功,位置为:" << pos << endl;
} else {
cout << "查找失败" << endl;
}
return 0;
}
```
阅读全文