用c语言写一个顺序查找的代码void SeqSearch(SqTable R, RecType k, int& i, int& j) {}
时间: 2023-12-10 15:41:27 浏览: 100
好的,下面是用C语言实现顺序查找的代码:
```
typedef struct {
// 定义记录类型
int key; // 关键字
// 其他数据项...
} RecType;
typedef struct {
// 定义顺序表类型
RecType *elem; // 数据元素存储空间基址
int length; // 当前长度
} SqTable;
void SeqSearch(SqTable R, RecType k, int& i, int& j) {
// 顺序查找
for (i = 1; i <= R.length; i++) {
if (R.elem[i].key == k.key) { // 找到关键字
j = i;
return;
}
}
j = 0; // 未找到关键字
}
```
其中,`SeqSearch`函数用于顺序查找关键字为`k.key`的记录,它的输入参数包括一个顺序表`R`和一个记录`k`,输出参数包括两个整型变量`i`和`j`。其中`i`表示查找过程中扫描到的元素位置,`j`表示查找到的记录位置,如果未找到则`j=0`。
相关问题
补全下面代码:#include "stdio.h" #include "iostream.h" #include "stdlib.h" #include "time.h" const int size=1000; typedef long RecType; typedef struct { RecType rec[size+1]; int n; } SqTable; //顺序查找 void SeqSearch(SqTable R,RecType k,int &i,int &j) { } void print(SqTable R,int n) { } //排序 void sort(SqTable &R,int n) { } //折半查找 int BinSearch(SqTable R,RecType k,int &j) { } void main() { SqTable R,A; RecType x; int i,j,n; int k; do { printf("\n\n\n\n"); printf("\t\t 查找子系统\n"); printf("\t\t*****************************\n"); printf("\t\t* 1----产生数据 *\n"); printf("\t\t* 2----顺序查找 *\n"); printf("\t\t* 3----二分查找 *\n"); printf("\t\t* 4----打印数据 *\n"); printf("\t\t* 0----返 回 *\n"); printf("\t\t*****************************\n"); printf("\t\t 请选择菜单项(0-4):"); scanf("%d",&k); switch(k) { case 1://随机产生数据 printf("请输入要产生随机数的个数(n<=%d)n= ",size); scanf("%d",&n); srand((unsigned)time( NULL )); for (i=1;i<=n;i++) A.rec[i]=R.rec[i]=rand(); A.n=R.n=n; break; case 2://顺序查找 printf("请输入要查找的关键字:"); scanf("%ld",&x); SeqSearch(R,x,i,j); if (i==0) printf("没有此数据!!!"); else printf("在 %d 个下标,第 %d 次找到。",i,j); break; case 3://二分查找 sort(A,n); print(A,n); printf("请输入要查找的关键字:"); scanf("%ld",&x); j=0; i=BinSearch(A,x,j); if (i==0) printf("没有此数据!!!"); else printf("在 %d 个下标,第 %d 次找到。",i,j); break; case 4: print(A,n); } }while (k!=0); }
这是一个简单的顺序查找和折半查找的程序,补全代码如下:
```c
#include "stdio.h"
#include "iostream.h"
#include "stdlib.h"
#include "time.h"
const int size = 1000;
typedef long RecType;
typedef struct {
RecType rec[size+1];
int n;
} SqTable;
//顺序查找
void SeqSearch(SqTable R, RecType k, int &i, int &j) {
i = 1;
while (i <= R.n && R.rec[i] != k) {
i++;
j++;
}
if (i <= R.n) {
j++;
} else {
i = 0;
}
}
void print(SqTable R, int n) {
for (int i = 1; i <= n; i++) {
printf("%d ", R.rec[i]);
}
printf("\n");
}
//排序
void sort(SqTable &R, int n) {
int i, j;
RecType temp;
for (i = 1; i < n; i++) {
for (j = n; j >= i+1; j--) {
if (R.rec[j] < R.rec[j-1]) {
temp = R.rec[j];
R.rec[j] = R.rec[j-1];
R.rec[j-1] = temp;
}
}
}
}
//折半查找
int BinSearch(SqTable R, RecType k, int &j) {
int low = 1, high = R.n, mid;
while (low <= high) {
mid = (low + high) / 2;
j++;
if (R.rec[mid] == k) {
return mid;
} else if (R.rec[mid] > k) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return 0;
}
void main() {
SqTable R, A;
RecType x;
int i, j, n;
int k;
do {
printf("\n\n\n\n");
printf("\t\t 查找子系统\n");
printf("\t\t*****************************\n");
printf("\t\t* 1----产生数据 *\n");
printf("\t\t* 2----顺序查找 *\n");
printf("\t\t* 3----二分查找 *\n");
printf("\t\t* 4----打印数据 *\n");
printf("\t\t* 0----返 回 *\n");
printf("\t\t*****************************\n");
printf("\t\t 请选择菜单项(0-4):");
scanf("%d", &k);
switch(k) {
case 1://随机产生数据
printf("请输入要产生随机数的个数(n<=%d)n= ",size);
scanf("%d",&n);
srand((unsigned)time(NULL));
for (i = 1; i <= n; i++) {
A.rec[i] = R.rec[i] = rand();
}
A.n = R.n = n;
break;
case 2://顺序查找
printf("请输入要查找的关键字:");
scanf("%ld",&x);
SeqSearch(R,x,i,j);
if (i == 0) {
printf("没有此数据!!!");
} else {
printf("在 %d 个下标,第 %d 次找到。", i, j);
}
break;
case 3://二分查找
sort(A,n);
print(A,n);
printf("请输入要查找的关键字:");
scanf("%ld",&x);
j = 0;
i = BinSearch(A,x,j);
if (i == 0) {
printf("没有此数据!!!");
} else {
printf("在 %d 个下标,第 %d 次找到。", i, j);
}
break;
case 4:
print(A,n);
}
} while (k != 0);
}
```
数据结构顺序查找和折半查找代码中增加在顺序表中查找关键字最大值最小值的函数,并调用测试: void MaxMin(SSTable ST,int &min, int &max){}
以下是增加了查找最大值和最小值功能的顺序查找和折半查找的代码:
顺序查找:
```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;
}
```
阅读全文