【BigHereo 48】---DataStructure---查找(六)

DataStructure---查找(六)

 

 

一,【前言】

  

   数据结构中,我们之前通过宏观学习基本的数据结构: 队列, 树, 图,从今天开始, 我们将开始学习对数据结构进行的操作: 查找. 其中查找分为静态查找和动态查找, 下面我们就通过几个简单的问题开始了解一下对数据结构的操作;

   1,对数据结构的操作有静态和动态, 分别是那些?

   2, 二分查找的前提是是什么?

   3,索引顺序表的查找是怎么查找的?

   4,二分, 索引, 顺序等,平均查找长度最好的是哪个?

   5,怎么构造平衡二叉树?

 

 

 

二,【详情】

   1,对数据结构的操作有静态和动态, 分别是那些?

解答:   静态的有: 读操作,也即查;  动态的有插入和删除操作.

 

   2, 二分查找的前提是是什么?

解答: 二分查找前提是所有的记录数据必须是有序的, 且顺序存储在内存中

 

   3,索引顺序表的查找是怎么查找的?

解答:索引查找也叫分块查找, 包含索引表和顺序表, 现在索引表中确定查找范围,再去顺序表中查.

      

   4,二分, 索引, 顺序等,平均查找长度最好的是哪个?

解答:  最好的是二分查找

 

   5,怎么构造平衡二叉树?

 

   6,顺序表查找平均长度是多少?

解答: 查找长的ASL: (n+1)/2

 

   7,顺序表查找的代码怎么写?

int SearchSqTable(SqTable T, KeyTypekey)
{
  T.eleme[0].key=key;//设立岗哨
   i=T.n; while(T.elem[i].key !=key) i--; return i;
}
 

   8,二分查找的平均长度怎么计算?

解答: 平均查找长度ASL: (n+1)/n log2(n+1)-1

 

   9,二分查找平均查找长度代码怎么表示?

intSearchBin(SqTable T,KeyType key){
   int low, high; low=1; high=T.n; //第0个为岗哨
   while(low <=high)
     {
        mid=(low+high)/2;
        if(key==T.elem[mid].key)  return mid;
            else if(key<T.elem[mid].key)high=mid-1;      
                 else low=mid + 1; 
      }
         return 0;
}

 

  10.什么是二叉排序树?

解答: 概念

         (1)小于根; 根小于右; 所有的子树满足前两条--似中序, 键值升

         (2子节点高度差绝对值小于等于 1---平衡二叉树

 

  11, 用代码怎么进行二叉树的遍历?

解答: 写代码前, 必须先宏观的理解要写的逻辑, 这里的逻辑怎么写呢?

           

接下来代码就相当的容易了:

 

typedef struct btnode
{
  keyType key;
  struct btnode *lchild; *rchild;
}BSTNode, *BinTree; BinTree bst;
BinTreeSearchBST(BiTree bst, keyType key)
 {
   if(bst==null) return null;
     else if(key==best->key) return bst;
        else if(key< bst->key) returnSearchBST(bst->lchild. key)
        else return SearchBST(bst->rchild, key);
}
 

 12,二叉排序树平均查找长度怎么算?

解答: 平均查找长度O(log2n)---二叉树

 

  13,什么是平衡二叉树?

解答: 概念

         (1)首先这是二叉树

         (2)每子节点高度差绝对值小于等于 1

 

 

  14,散列表的目的是什么?

解答: 目的

         (1)如何构造"均匀的"散列函数?

         (2)用什么法有效解决冲突?

 

  15,如何构造”均匀的”散列函数?     

      

  16,用什么方法能有效解决冲突呢?

         

 

 

三,【小结】                                          

  

     通过这一博文的总结, 知道了对数据结构操作的查找, 有静态查找和动态查找, 其中静态查找又有顺序表,二分查找和索引表的查找; 动态查找中有二叉排序树, 平衡二叉树和散列表的查找. 这些讲的都是对数据结构操作的一个, 还有一个操作是什么呢?  另一个对数据结构的操作就是 排序, 下一博文中, 我将对排序进行总结,敬请期待.