1.顺序查找
#pragma once
#include
using namespace std;
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define INFEASIBLE -1
#define MAXSIZE 100
typedef int Status;
typedef int KeyType;
typedef int InfoType;
//数据元素类型定义
struct ElemType
{
KeyType Key;
InfoType otherinfo;
};
//顺序表结构类型定义
struct SSTable //Sequential Search Table
{
ElemType* R;//表基址
int length; //表长
};
//顺序查找
int Search_Seq(SSTable& ST, const KeyType& k)
{
for (auto i = ST.length; i >= 1; --i)
{
if (ST.R[i].Key == k)
{
return i;
}
}
return 0;
}
//改进,增加监视哨
int Search_Seq2(SSTable& ST, const KeyType& k)
{
ST.R[0].Key = k;//监视哨
auto i = ST.length;
for (; ST.R[i].Key != k; --i);
return i;
}
2.折半查找
int Search_Bin(SSTable& S, const KeyType& k)
{
int low = 1;
int high = S.length;
while (low <= high)
{
auto mid = (low + high) / 2;
if (S.R[mid].Key == k)
{
return mid;
}
else if (S.R[mid].Key < k)
{
low = mid + 1;
}
else
{
high = mid - 1;
}
}
return 0;
}
3.折半查找——递归算法
int Search_Bin2(SSTable& S, const KeyType& k, int low, int high)
{
if (low > high)
{
return 0;
}
auto mid = (low + high) / 2;
if (k == S.R[mid].Key)return mid;
else if (k < S.R[mid].Key)
{
return Search_Bin2(S, k, low, mid - 1);
}
else
{
return Search_Bin2(S, k, mid +1, high);
}
}
4.二叉排序树的递归查找
//二叉树的存储结构
typedef struct BSTnode
{
ElemType data;
struct BSTnode* lchild, * rchild;
}BSTnode, *BSTree;
//二叉排序树的递归查找
BSTree SearchBST(BSTree& T, const KeyType& e)
{
if ((!T) || e == T->data.Key)
{
return T;
}
else if (e < T->data.Key)
{
return SearchBST(T->lchild, e);
}
else
{
return SearchBST(T->rchild, e);
}
}
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)