数据结构实验2 查找算法的实现和应用

 实验目的

1. 熟练掌握静态查找表的查找方法； 2. 熟练掌握动态查找表的查找方法; 3. 掌握hash表的技术.  实验内容

1. 用二分查找法对查找表进行查找； 2. 建立二叉排序树并对该树进行查找；

3. 确定hash函数及冲突处理方法，建立一个hash表并实现查找。

1.二分查找

#include

using namespace std;

#define INVALID_INDEX -100

int IntCompare(const int& a, const int& b, void* param) {

return a - b; }

template

int BinarySearch(const T1* theArray, int length, const T2& key, int (*compare)(const T1&, const T2&, void* param), void *param) {

int indexRet = INVALID_INDEX; int mid = length / 2;

int cmp = compare(theArray[mid], key, param);

if (cmp == 0) {

indexRet = mid; }

else if (length != 1) {

if (cmp < 0 && length != 1) {

indexRet = BinarySearch(theArray + mid, length - mid, key, compare,param); if (indexRet != INVALID_INDEX) {

indexRet += mid; } } else {

indexRet = BinarySearch(theArray, mid, key, compare, param); } }

return indexRet; }

int main() {

int length = 0; int i = 0; int key = 0;

int index = INVALID_INDEX;

cout <<\"请输入元素的个数：\"<> length;

int* aArray = new int[length];

cout<<\"请输入要输入的元素：\"<cin >> aArray[i]; }

cout<<\"要查找的元素：\"<> key&&key != 'F'){

index = BinarySearch(aArray, length, key, IntCompare, NULL); if (index == INVALID_INDEX) {

cout << \"The element is not exist.\" << endl; } else {

cout << \"The element position is \" << index << \".\" << endl; } delete aArray; } return 0; }

2 二叉排序树 #include #include #include using namespace std;

typedef int keyType; typedef struct Node {

keyType key; struct Node* left; struct Node* right; struct Node* parent; }Node,*PNode;

void inseart(PNode* root, keyType key) {

PNode p = (PNode)malloc(sizeof(Node)); p -> key = key;

p -> left = p -> right = p -> parent = NULL; if((*root) == NULL) {

*root = p; return ; }

if((*root)->left == NULL && (*root)->key > key) {

p->parent=(*root); (*root)->left=p; return; }

if((*root)->right == NULL && (*root)->key < key) {

p->parent=(*root); (*root)->right=p; return; }

if((*root) -> key > key) {

inseart(&(*root) -> left, key); }

else if((*root) -> key < key) {

inseart(&(*root) -> right, key); } else

return ; }

PNode search(PNode root,keyType key) {

if(root == NULL) {

return NULL; }

if(key > root -> key) {

return search(root -> right, key); }

else if(key < root -> key) {

return search(root -> left, key);

} else

return root; }

void create(PNode* root, keyType* keyArray, int length) {

int i;

for(i = 0; i < length; i++) {

inseart(root, keyArray[i]); } }

int main() {

int i;

PNode root = NULL; int a[100]; int n;

scanf(\"%d\ for(i = 0; i < n; i++) {

scanf(\"%d\ }

create(&root, a,n); int m;

while(~scanf(\"%d\ if(search(root,m) ->key){ printf(\"YES\\n\"); } }

return 0; }

3 hash

#include //#include #include

using namespace std;

enum Result{ ok = 2,

success = 1, unsuccess = 0, duplicate = -1, fail = -2, };

typedef int elemtype; typedef struct{

elemtype* elem; int count; int sizeindex; }hashTable;

void Inithash(hashTable &H, int n){ H.elem = new elemtype[n]; H.count = 0; H.sizeindex = n;

for(int i = 0; i < n; i++) {

H.elem[i] = 0; } }

int hash(elemtype K, int sizeindex) {

int count = H.count;

int haAddr = K % sizeindex; return haAddr; }

int SearchHash(hashTable &H, elemtype K, int &haAddr, int &c) {

int d = 1;

int sizeindex = H.sizeindex; haAddr = hash(K, sizeindex);

while(H.elem[haAddr] != NULL && H.elem[haAddr] != K) {

haAddr = (K % sizeindex + d) % sizeindex; d++; c++;

cout<<\"产生冲突，解决中…………\"< H.sizeindex - 2) {

cout<<\"冲突次数过多，重新建立哈希表\"<if(K == H.elem[haAddr]) {

cout<<\"chenggong\"<cout<<\"fail\"<int InsertHash(hashTable &H, elemtype e) {

int collision = 0; int haAddr = -1;

if(SearchHash(H, e, haAddr, collision) == success) {

cout<<\"存在该元素！！！\"<else if(collision < H.sizeindex - 2) {

H.elem[haAddr] = e; H.count++;

cout<<\"插入成功！！！\"<cout<<\"冲突次数过多，重新建立哈希表\"<int hashsearch(hashTable &H, elemtype e) {

int p = 0;

for(int i = 0; i < H.sizeindex; i++) {

if(H.elem[i] == e) {

//H.elem[i] == 0; p = 1;

cout <<\"hashaddress = \"<return unsuccess; else

return success; } } }

void PrintHash(hashTable H) {

int num = 1;

cout<<\"哈希表为……！\"<if(num % 10 == 0) cout <cout <else continue; }

cout <void Performance(hashTable &H){ //hashTable H; int sizeindex;

cout <<哈希表容量为……！<>sizeindex;

Inithash(H, sizeindex); int e = 1;

cout<<\"输入插入元素，否则输入＇０＇\"<>ｅ; while(e != 0) {

InsertHash(H, e);

cout<<\"输入插入元素，否则输入＇０＇\"<>e; }

PrintHash(H); int k = 1;

cout<<\"输入要查找元素：\"; //int k; cin>>k;

hashsearch(H,k);

int status = hashsearch(H,K); if(!status)

cout<<\"该元素不存在\"<int main() {

hashTable H; Performance(H); cin.get(); cin.get();

return 0; }