数据结构之查找（一）基本内容

一、查找的基本概念

      

        1.查找是数据结构中非常重要的一部分，无论你用的网站、日常生活电话号码、出门的地图、你想获取的信息......这些都要从查找开始。

        

         2.查找常进行的操作：

                                            （1）查询某个特定的元素是否在查找表中；

                                            （2）检索摸某个个数据元素的属性；

                                            （3）添加

                                            （4）删除

 

         3.查找的分类：

                                （1）静态查找 仅包含了操作的1-2

                                （2）动态查找 包含了操作的1-2-3-4

                   

                                  ps:如果只进行操作常用的结构是数组可以直接定位

                                       对于能够进行包含添加删除类的链表是有优势的     

                                       整个问题应用与二叉树的话有链表的性质，又有查找的优势                                 

 

二、静态查找

 

       1.顺序扫描

       2.二分查找，要求先排序的

 static void Main(string[] args)
        {
            int[] temp = new int[] { 9, 8, 7, 6, 5, 4, 3, 2, 1 };
            quickSortRun(temp, 0, temp.Length - 1);
            Console.WriteLine(binarySearch(temp,9,0,temp.Length));
        }

        //create a binary search you must first sort it
        public static int binarySearch(int[] temp, int key, int start, int end) { 
              
            while (start < end)
            {
                int midPosition = (start + end) / 2;

                if (key == temp[midPosition])
                {
                    return midPosition;
                }
                else if (key < temp[midPosition])
                {
                    end = midPosition - 1;
                }
                else
                {
                    start = midPosition + 1;
                }
            }
            return -1;
        }

        //quick sort
        public static int   quickSort(int[] temp, int start, int end) { 
        //decalre a variables of key
            int key = temp[start];
            while (start < end) {

                //first get the position of below the start
                while (start < end && temp[end] > key) {
                    end--;
                }
                temp[start] = temp[end];

                //second get the position of above the start
                while (start < end && temp[start] < key) {
                    start++;
                }
                temp[end] = temp[start];
            }

            //end let the position key
            temp[start] = key;
         return start;
        }

        //quick sort is running
        public static void quickSortRun(int[] temp, int start, int end) {
            if (start < end) {
                int position = quickSort(temp, start, end);
                quickSortRun(temp, start, position - 1);
                quickSortRun(temp, position + 1, end);
                
            }
        }

 

三、动态查找

 

     1.二叉树查找树 基本实现

        （1）左子树不为空，则左子树小于根节点

        （2）右子树不为空，则右子树大于根节点

        （3）左右子树又是一个二叉排序树

 

       =》优点：查找方面，时间的复杂度跟这个二叉树的深度有关系。最坏O(n)

       =》缺点：当出现极端的情况下都是左子树或者右子树，那么意义不大了，纯粹一链表

                       =》平衡树方面：定义|左子树的度-右子树的度|<2 时间复杂度为O(log n)

                              =》红黑树 基本实现

                              =》 AVL 基本实现

 

     2.B树的方面

      =》可以看下索引方面，文件方面的查询

      =》因为前段时间在看LUCENE

      =》这些了解了回过头来继续看下

 

     3.Hash方面

       =》其实我倒现在都还不是太了解这些方面的东西

       =》理解的范围只在于映射

 

     4.TRIE树

      =》对准字典方面的 我前面写的