各种查找的Java实现代码

happy熊 贡献于2014-01-05

作者 MC SYSTEM  创建于2009-04-22 03:07:00   修改者MC SYSTEM  修改于2009-04-22 16:58:00字数10115

文档摘要:一、线性查找  在一列给定的值中进行搜索,从一端开始逐一检查很个元素,直到找到所需元素的过程。 线性查找又称为顺序查找。 二分查找二分查找又称折半查找,它是一种效率较高的查找方法。【二分查找要求】:1.必须采用顺序存储结构2.必须按关键字大小有序排列。 【优缺点】折半查找法的优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难。
关键词:

一、 线性查找   在一列给定的值中进行搜索,从一端开始逐一检查很个元素,直到找到所需元素的过程。   线性查找又称为顺序查找。 public class LSearch { public static int[] Data = { 12, 76, 29, 22, 15, 62, 29, 58, 35, 67, 58, 33, 28, 89, 90, 28, 64, 48, 20, 77 }; // 输入数据数组 public static int Counter = 1; // 查找次数计数变量 public static void main(String args[]) { int KeyValue = 22; // 调用线性查找 if (Linear_Search((int) KeyValue)) { // 输出查找次数 System.out.println(""); System.out.println("Search Time = " + (int) Counter); } else { // 输出没有找到数据 System.out.println(""); System.out.println("No Found!!"); } } // --------------------------------------------------- // 顺序查找 // --------------------------------------------------- public static boolean Linear_Search(int Key) { int i; // 数据索引计数变量 for (i = 0; i < 20; i++) { // 输出数据 System.out.print("[" + (int) Data[i] + "]"); // 查找到数据时 if ((int) Key == (int) Data[i]) return true; // 传回true Counter++; // 计数器递增 } return false; // 传回false } } 运行结果: [12][76][29][22] Search Time = 4 二、 二分查找 二分查找又称折半查找,它是一种效率较高的查找方法。 【二分查找要求】:1.必须采用顺序存储结构 2.必须按关键字大小有序排列。   【优缺点】折半查找法的优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难。因此,折半查找方法适用于不经常变动而查找频繁的有序列表。   【算法思想】首先,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。   重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。 public class BSearch { public static int Max = 20; public static int[] Data = { 12, 16, 19, 22, 25, 32, 39, 48, 55, 57, 58, 63, 68, 69, 70, 78, 84, 88, 90, 97 }; // 数据数组 public static int Counter = 1; // 计数器 public static void main(String args[]) { int KeyValue = 22; // 调用折半查找 if (BinarySearch((int) KeyValue)) { // 输出查找次数 System.out.println(""); System.out.println("Search Time = " + (int) Counter); } else { // 输出没有找到数据 System.out.println(""); System.out.println("No Found!!"); } } // --------------------------------------------------- // 二分查找法 // --------------------------------------------------- public static boolean BinarySearch(int KeyValue) { int Left; // 左边界变量 int Right; // 右边界变量 int Middle; // 中位数变量 Left = 0; Right = Max - 1; while (Left <= Right) { Middle = (Left + Right) / 2; if (KeyValue < Data[Middle]) // 欲查找值较小 Right = Middle - 1; // 查找前半段 // 欲查找值较大 else if (KeyValue > Data[Middle]) Left = Middle + 1; // 查找后半段 // 查找到数据 else if (KeyValue == Data[Middle]) { System.out.println("Data[" + Middle + "] = " + Data[Middle]); return true; } Counter++; } return false; } } 运行结构: Data[3] = 22 Search Time = 5 二叉查找树 二叉查找树(Binary Search Tree),或者是一棵空树,或者是具有下列性质的二叉树:   若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;   若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;   它的左、右子树也分别为二叉排序树。   二叉排序树的查找过程和次优二叉树类似,通常采取二叉链表作为二叉排序树的存储结构。中序遍历二叉排序树可得到一个关键字的有序序列,一个无序序列可以通过构造一棵二叉排序树变成一个有序序列,构造树的过程即为对无序序列进行排序的过程。每次插入的新的结点都是二叉排序树上新的叶子结点,在进行插入操作时,不必移动其它结点,只需改动某个结点的指针,由空变为非空即可。搜索,插入,删除的复杂度等于树高,O(log(n)).   目录   1 二叉排序树的查找算法   2 在二叉排序树插入结点的算法   3 在二叉排序树删除结点的算法   二叉排序树的查找算法:   在二叉排序树b中查找x的过程为:   若b是空树,则搜索失败,否则:   若x等于b的根结点的数据域之值,则查找成功;否则:   若x小于b的根结点的数据域之值,则搜索左子树;否则:查找右子树。   向一个二叉排序树b中插入一个结点s的算法:   过程为:   若b是空树,则将s所指结点作为根结点插入,否则:   若s->data等于b的根结点的数据域之值,则返回,否则:   若s->data小于b的根结点的数据域之值,则把s所指结点插入到左子树中,否则:   把s所指结点插入到右子树中。   在二叉排序树删除结点的算法:   在二叉排序树删去一个结点,分三种情况讨论:   若*x结点为叶子结点,即xL(左子树)和xR(右子树)均为空树。由于删去叶子结点不破坏整棵树的结构,则只需修改其双亲结点的指针即可。   若*x结点只有左子树xL或右子树xR,此时只要令xL或xR直接成为其双亲结点*parent的左子树或者右子树即可,作此修改也不破坏二叉排序树的特性。   若*x结点的左子树和右子树均不空。在删去*x之后,为保持其它元素之间的相对位置不变,可按中序遍历保持有序进行调整,可以有两种做法:其一是令*x的左子树为*parent的左子树,*xsucc为*f左子树的最右下的结点,而*x的右子树为*xsucc的右子树;其二是令*x的直接前驱(或直接后继)替代*x,然后再从二叉排序树中删去它的直接前驱(或直接后继)。   中序后继结点替换要删除的节点:从x的右儿子开始,一直靠左往下走,最后到达的节点就是所需的后继结点,程序中用xsucc指向这个后继结点,现在只需删除xsucc指向的节点,可以根据情况1或者是情况2中的方法来删除它。 实现上先形成树型结构,在进行查找。 查找: --------------------------- 顺序查找 说明:顺序查找适合于存储结构为顺序存储或链接存储的线性表。 int SequelSearch(elemtype s[],keytype Key,int n) /*在s[0]-s[n-1]中顺序查找关键字为Key的记录*/ /*查找成功时返回该记录的下标序号;失败时返回-1*/ { int i; i=0; while(ihigh) return -1; mid=(low+high)/2; if(x==a[mid]) return mid; if(xls[i].Key)i++; if(i>=m)return -1; else { /*在顺序表中顺序查找*/ j=ls[i].Links; while(Key!=s[j].Key&&j-ls[i].Linkdata==x) return(b); if(xdata) return(search(b->left)); else return(search(b->right)); } } b、递归算法: bsnodetype *Search(bsnodetype *bt,keytype Key) /*在二叉树bt中查找元素为Key的元素*/ { bsnodetype *p; if(bt==NULL) return(bt); p=bt; while(p->Key!=Key) { if(KeyKey) p=p->Lchild; else p=p->Rchild; if(p==NULL)break; } return(p); } 2、二叉树的生成 a、向一个二叉树b中插入一个结点s的函数如下: void insert(b,s) btree *b,*s; { if(b==NULL) b=s; else if(s->data==b->data) return(); else if(s->datadata) insert(b->left,s); else if(s->data>b->data) insert(b->right,s); } b、生成二叉树 void create(btree *b) { int x; btree 8s; b==NULL; do { scanf("%d",&x); s=(bnode *)malloc(sizeof(bnode)); s->data=x; s->left=NULL; s->right=NULL; insert(b,s); }while(x!=-1); } c、从二叉树中删除一个结点 bsnodetype *Delete(bsnodetype *bt,keytype Key) /*在bt为根结点的二叉树中删除值为Key的结点*/ { bsnodetype *p,*q; if(bt->Key==Key) { /*bt的左右子树均为空*/ if(bt->Lchild==NULL&&bt->Rchild==NULL) { free(bt); /*删除叶结点*/ return(NULL); } else if(bt->Lchild==NULL)/*bt的左子树为空*/ { p=bt->Rchild; free(bt); return(p); } else if(bt->Rchild==NULL)/*bt的右子树为空*/ { p=bt->Lchild; free(bt); return(p); } else { p=q=bt->Rchild; while(p->Lchild!=NULL)p=p->Lchild; p->Lchild=bt->Lchild; free(bt); return(q); } } /*在bt->Lchild为根结点的二叉树中删除值为Key的结点*/ if(bt->Key>Key&&bt->Lchild!=NULL) bt->Lchild=Delete(bt->Lchild,Key); /*在bt->Rchild为根结点的二叉树中删除值为Key的结点*/ if(bt->KeyRchild!=NULL) bt->Rchild=Delete(bt->Rchild,Key); return(bt); } 遍历概念:   所谓遍历(Traversal)是指沿着某条搜索路线,依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问 题。   遍历是二叉树上最重要的运算之一,是二叉树上进行其它运算之基础。   遍历方案:   1.遍历方案   从二叉树的递归定义可知,一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此,在任一给定结点上,可以按某种次序执行三个操作:   (1)访问结点本身(N),   (2)遍历该结点的左子树(L),   (3)遍历该结点的右子树(R)。   以上三种操作有六种执行次序:   NLR、LNR、LRN、NRL、RNL、RLN。   注意:   前三种次序与后三种次序对称,故只讨论先左后右的前三种次序。   2.三种遍历的命名   根据访问结点操作发生位置命名:   ① NLR:前序遍历(PreorderTraversal亦称(先序遍历))   ——访问结点的操作发生在遍历其左右子树之前。   ② LNR:中序遍历(InorderTraversal)   ——访问结点的操作发生在遍历其左右子树之中(间)。   ③ LRN:后序遍历(PostorderTraversal)   ——访问结点的操作发生在遍历其左右子树之后。   注意:   由于被访问的结点必是某子树的根,所以N(Node)、L(Left subtree)和R(Right subtree)又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。   遍历算法   1.中序遍历的递归算法定义:   若二叉树非空,则依次执行如下操作:   (1)遍历左子树;   (2)访问根结点;   (3)遍历右子树。   2.先序遍历的递归算法定义:   若二叉树非空,则依次执行如下操作:   (1) 访问根结点;   (2) 遍历左子树;   (3) 遍历右子树。   3.后序遍历得递归算法定义:   若二叉树非空,则依次执行如下操作:   (1)遍历左子树;   (2)遍历右子树;   (3)访问根结点。   4.中序遍历的算法实现   用二叉链表做为存储结构,中序遍历算法可描述为:   void InOrder(BinTree T)   { //算法里①~⑥是为了说明执行过程加入的标号   ① if(T) { // 如果二叉树非空   ② InOrder(T->lchild);   ③ printf("%c",T->data); // 访问结点   ④ InOrder(T->rchild);   ⑤ }   ⑥ } // InOrder   遍历序列   1.遍历二叉树的执行踪迹   三种递归遍历算法的搜索路线相同(如下图虚线所示)。   具体线路为:   从根结点出发,逆时针沿着二叉树外缘移动,对每个结点均途径三次,最后回到根结点。   2.遍历序列   A   / \   B C   / / \   D E F   图   (1) 中序序列(inorder traversal)   中序遍历二叉树时,对结点的访问次序为中序序列   【例】中序遍历上图所示的二叉树时,得到的中序序列为:   D B A E C F   (2) 先序序列(preorder traversal)   先序遍历二叉树时,对结点的访问次序为先序序列   【例】先序遍历上图所示的二叉树时,得到的先序序列为:   A B D C E F   (3) 后序序列(postorder traversal)   后序遍历二叉树时,对结点的访问次序为后序序列   【例】后序遍历上图所示的二叉树时,得到的后序序列为:   D B E F C A   (4)层次遍历(level traversal)二叉树的操作定义为:若二叉树为空,则退出,否则,按照树的结构,从根开始自上而下,自左而右访问每一个结点,从而实现对每一个结点的遍历   注意:   (1)在搜索路线中,若访问结点均是第一次经过结点时进行的,则是前序遍历;若访问结点均是在第二次(或第三次)经过结点时进行的,则是中序遍历(或后序遍历)。只要将搜索路线上所有在第一次、第二次和第三次经过的结点分别列表,即可分别得到该二叉树的前序序列、中序序列和后序序列。   (2)上述三种序列都是线性序列,有且仅有一个开始结点和一个终端结点,其余结点都有且仅有一个前趋结点和一个后继结点。为了区别于树形结构中前趋(即双亲)结点和后继(即孩子)结点的概念,对上述三种线性序列,要在某结点的前趋和后继之前冠以其遍历次序名称。   【例】上图所示的二叉树中结点C,其前序前趋结点是D,前序后继结点是E;中序前趋结点是E,中序后继结点是F;后序前趋结点是F,后序后继结点是A。但是就该树的逻辑结构而言,C的前趋结点是A,后继结点是E和F。   二叉链表的构造   1. 基本思想   基于先序遍历的构造,即以二叉树的先序序列为输入构造。   注意:   先序序列中必须加入虚结点以示空指针的位置。   【例】   建立上图所示二叉树,其输入的先序序列是:ABD∮∮∮CE∮∮F∮∮。   2. 构造算法   假设虚结点输入时以空格字符表示,相应的构造算法为:   void CreateBinTree (BinTree *T)   { //构造二叉链表。T是指向根指针的指针,故修改*T就修改了实参(根指针)本身   char ch;   if((ch=getchar())=='') *T=NULL; //读人空格,将相应指针置空   else{ //读人非空格   *T=(BinTNode *)malloc(sizeof(BinTNode)); //生成结点   (*T)->data=ch;   CreateBinTree(&(*T)->lchild); //构造左子树   CreateBinTree(&(*T)->rchild); //构造右子树   }   }   注意:   调用该算法时,应将待建立的二叉链表的根指针的地址作为实参。   【例】   设root是一根指针(即它的类型是BinTree),则调用CreateBinTree(&root)后root就指向了已构造好的二叉链表的根结点。   二叉树建立过程见http://student.zjzk.cn/course_ware/data_structure/web/flashhtml/erchashujianli.htm   下面是关于二叉树的遍历、查找、删除、更新数据的代码(递归算法):   [code]   #include   using namespace std;   typedef int T;   class bst{   struct Node{   T data;   Node* L;   Node* R;   Node(const T& d, Node* lp=NULL, Node* rp=NULL):data(d),L(lp),R(rp){}   };   Node* root;   int num;   public:   bst():root(NULL),num(0){}   void clear(Node* t){   if(t==NULL) return;   clear(t->L);   clear(t->R);   delete t;   }   ~bst(){clear(root);}   void clear(){   clear(root);   num = 0;   root = NULL;   }   bool empty(){return root==NULL;}   int size(){return num;}   T getRoot(){   if(empty()) throw "empty tree";   return root->data;   }   void travel(Node* tree){   if(tree==NULL) return;   travel(tree->L);   cout << tree->data << ' ';   travel(tree->R);   }   void travel(){   travel(root);   cout << endl;   }   int height(Node* tree){   if(tree==NULL) return 0;   int lh = height(tree->L);   int rh = height(tree->R);   return 1+(lh>rh?lh:rh);   }   int height(){   return height(root);   }   void insert(Node*& tree, const T& d){   if(tree==NULL)   tree = new Node(d);   else if(ddata)   insert(tree->L, d);   else   insert(tree->R, d);   }   void insert(const T& d){   insert(root, d);   num++;   }   Node*& find(Node*& tree, const T& d){   if(tree==NULL) return tree;   if(tree->data==d) return tree;   if(ddata)   return find(tree->L, d);   else   return find(tree->R, d);   }   bool find(const T& d){   return find(root, d)!=NULL;   }   bool erase(const T& d){   Node*& pt = find(root, d);   if(pt==NULL) return false;   combine(pt->L, pt->R);   Node* p = pt;   pt = pt->R;   delete p;   num--;   return true;   }   void combine(Node* lc, Node*& rc){   if(lc==NULL) return;   if(rc==NULL) rc = lc;   else combine(lc, rc->L);   }   bool update(const T& od, const T& nd){   Node* p = find(root, od);   if(p==NULL) return false;   erase(od);   insert(nd);   return true;   }   };   int main()   {   bst b;   cout << "input some integers:";   for(;;){   int n;   cin >> n;   b.insert(n);   if(cin.peek()=='\n') break;   }   b.travel();   for(;;){   cout << "input data pair:";   int od, nd;   cin >> od >> nd;   if(od==-1&&nd==-1) break;   b.update(od, nd);   b.travel();   }   } [/code] 哈希查找   哈希查找是通过计算数据元素的存储地址进行查找的一种方法。   哈希查找的操作步骤:   ⑴用给定的哈希函数构造哈希表;   ⑵根据选择的冲突处理方法解决地址冲突;   ⑶在哈希表的基础上执行哈希查找。   建立哈希表操作步骤:   step1 取数据元素的关键字key,计算其哈希   函数值(地址)。若该地址对应的存储   空间还没有被占用,则将该元素存入;   否则执行step2解决冲突。   step2 根据选择的冲突处理方法,计算关键字   key的下一个存储地址。若下一个存储地   址仍被占用,则继续执行step2,直到找   到能用的存储地址为止。   哈希查找步骤为:   设哈希表为HST[0~M-1],哈希函数取H(key),解决冲突的方法为R(x);   Step1 对给定k值,计算哈希地址 Di=H(k);若HST为空,则查找失败;   若HST=k,则查找成功;否则,执行step2(处理冲突)。   Step2 重复计算处理冲突的下一个存储地址 Dk=R(Dk-1),直到HST[Dk]为   空,或HST[Dk]=k为止。若HST[Dk]=K,则查找成功,否则查找失败。

下载文档到电脑,查找使用更方便

文档的实际排版效果,会与网站的显示效果略有不同!!

需要 3 金币 [ 分享文档获得金币 ] 0 人已下载

下载文档