查找算法比较.docVIP

数据结构课程设计 计算机学院 李敬球 查找算法的比较 #includeiostream #includestdlib.h #includetime.h using namespace std; templateclass T int Find_s(T data[], int n,T key,int icmp) //顺序查找(从n维数组中查找key,并且给出比较的次数icmp { icmp=0; for(int i=0;in;i++) { icmp++; if(data[i]==key) return i; } return -1; } templateclass T int Find_t(T data[], int n,T key,int icmp) //二分查找(从n维数组中查找key,并且给出比较的次数icmp { int i=0,j=n-1; icmp=0; while(data[(i+j)/2]!=keyi=j) { icmp++; if(data[(i+j)/2]key) j=(i+j)/2-1; else i=(i+j)/2+1; } if(ij) return -1; return (i+j)/2; } ///以下是二叉查找树查找法 templateclass T class BintreeNode { public: T data; BintreeNode* left; BintreeNode*right; BintreeNode():left(0),right(NULL){} BintreeNode(T item):data(item),left(NULL),right(NULL){} ~BintreeNode(){ if(left!=0) delete left; if(right!=0) delete right; } }; templateclass T class Bintree { public: int num; BintreeNodeT* root; BintreeNodeT* Find_bt(T key,int icmp,int itype=0)//一个二叉树查找算法，itype=1时有插入功能（不同的值时） { icmp=0; if(root==0) { icmp++; if(itype==0) return NULL; else { num++; return root=new BintreeNodeT(key); } } else { BintreeNodeT* ptr=root,*p; while(ptr!=NULL) { icmp++; p=ptr; if(ptr-data==key) return ptr; else { if(ptr-datakey) ptr=ptr-left; else ptr=ptr-right; } } if(itype) { num++; if(p-datakey) return p-left=new BintreeNodeT(key); else return p-right=new (BintreeNodeT)(key); } return NULL; }//else }//Find_bt Bintree():root(0),num(0){} ~Bintree(){delete root;} }; int compare(const void* a,const void* b) { return *(int *)a-*(int *)b; } templateclass T class Link { public: T data; LinkT* next; LinkT():next(0){} LinkT(T item):data(item),next(0){} ~LinkT(){if(next) delete next;} }; templateclass T class LinkList { public: LinkT* first; LinkListT():first(0){} ~LinkListT(){if(first)delete first;} LinkT* Find_hash(T key,int icmp,int