二分查找和斐波那契查找
#include "Search.h" Search::Search(void) { } Search::~Search(void) { } //二分查找 int Search::Binary_Search(int* a,int n,int key) { //a是按照从小到大排序的数组 int low,high,mid; low = 1; high = n; while (low < high) { mid = (low + high)/2; if (key < a[mid]) high = mid-1; else if (key > a[mid]) low = mid + 1; else return mid; } return 0; } int F[]={0,1,2,3,5,8,13,21,34,55,89,144}; int Search::Fibonacci_Search(int* a,int key) { int low,mid,i,k; low = 1; high = n; k = 0; while (n > F[k]-1) //查找n位于斐波那契数列的位置 k++; for (i = n; i<F[k]-1; i++) a[i] = a[n]; while (low <= high) { mid = low + F[k-1] - 1; //计算当前分隔的下标 if (key < a[mid]) //若查找记录小于当前记录 { high = mid - 1; k = k - 1; } else if (key > a[mid]) { low = mid + 1; k = k - 2; } else { if (mid <= n) { return mid; } else return n; } } return 0; }
二叉查找树
结构定义
//二叉树链表节点定义 typedef struct BiTNode { int data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree;
#include "BinarySearchTree.h" BinarySearchTree::BinarySearchTree(void) { } BinarySearchTree::~BinarySearchTree(void) { } /* 递归查找二叉树中是否存在Key,指针f指向T的双亲 若查找成功则指针p指向该数据元素节点 否则p指向查找路径上访问的最后一个节点并返回失败 */ int BinarySearchTree::SearchBST(BiTree T,int key,BiTree f,BiTree *p) { if (!T) //查找失败 { *p = f; return -1; } else if (key == T->data) //查找成功 { *p = T; return 1; } else if (key < T->data) { return SearchBST(T->lchild,key,T,p); //左子树继续查找 } else { return SearchBST(T->rchild,p); //右子树继续查找 } } /* 如果二叉树中不存在关键字等于key的元素,则插入key并返回 */ int BinarySearchTree::InsertBST(BiTree *T,int key) { BiTree p,s; int result = SearchBST(*T,NULL,&p); if (result == -1) { s = (BiTree)malloc(sizeof(BiTree)); s->data = key; s->lchild = s->rchild = NULL; if (!p) { *T = s; } else if (key < p->data) { p->lchild = s; } else { p->rchild = s; } return 1; } else { return -1; } } /* 从二叉树中删除节点p,并重接他的左或右子树 */ int BinarySearchTree::Delete(BiTree *p) { BiTree q,s ; if ((*p)->rchild == NULL) //右子树空则只需要重接它的左子树 { q = *p; *p = (*p)->lchild; free(q); } else if ((*p)->lchild == NULL) //只需要重新连接它的右子树 { q = *p; *p = (*p)->rchild; free(q); } else //左右子树均不为空 { q = *p; s = (*p)->lchild; while (s->rchild) //转左,然后向右到尽头 { q = s; s = s->rchild; } (*p)->data = s->data; if (q != *p) { q->rchild = s->lchild; } else { q->lchild = s->rchild; } free(s); } return 1; } /* 若二叉排序树T中存在关键字等于key的数据元素时,则删除数据元素节点 */ int BinarySearchTree::DeleteBST(BiTree *T,int key) { if (!*T) return -1; else { if (key == (*T)->data) { return Delete(T); } else if (key < (*T)->data) { return DeleteBST(&(*T)->lchild,key); } else { return DeleteBST(&(*T)->rchild,key); } } }