就是要你考上研究生!
01

400-050-3680

01

2016计算机考研:数据结构常用算法精析(8)

    第九章 查找
  查找分成静态查找和动态查找,静态查找只是找,返回查找位置。而动态查找则不同,若查找成功,返回位置,若查找不成功,则要返回新记录的插入位置。也就是说,静态查找不改变查找表,而动态查找则会有插入操作,会改变查找表的。
  不同的查找所采用的存储结构也不同,静态查找采用顺序表,而动态查找由于经常变动,所以用二叉排序树,二叉平衡树、B-和B+。
  静态查找有,顺序查找,折半查找,分块查找(索引顺序查找)
  顺序查找(Sequential Search)是最简单的一种查找方法。
  算法思路
  设给定值为k,在表(R1 R2……Rn)中,从Rn即最后一个元素开始,查找key=k的记录。若存在一个记录Ri(l≤i≤n)的key为k,则查找成功,返回记录序号i;否则,查找失败,返回0。
  算法描述
  int sqsearch(sqlist r,keytype k) //对表r顺序查找的算法//
  { int i;
  r.data[0].key=k; //k存入监视哨//
  i=r.len; //取表长//
  while(r.data[i].key!=k)
  i--; //顺序查找//
  return(i);
  }
  算法用了一点技巧:先将k存入监视哨,若对某个i(≠0)有r.data[i].key=k,则查找成功,返回i;若i从n递减到1都无记录的key为k,i再减1为0时,必有r.data[0].key=k,说明查找失败,返回i=0。
  平均查找成功长度ASL= ,而查找失败时,查找次数等于n+l。
  折半查找算法及分析
  当记录的key按关系≤或≥有序时,不管是递增的还是递减的,只要有序且采用顺序存储。
  算法描述
  int Binsearch(sqlist r,keytype k) //对有序表r折半查找的算法//
  { int low,high,mid;
  low=1;high=r.len; //上下界初值//
  while(low<=high) //表空间存在时//
  { mid=(low+high)/2; //求当前mid//
  if (k==r.data[mid].key)
  return(mid); //查找成功,返回mid//
  if (k
  high=mid-1; //调整上界,向左部查找//
  else
  low=mid+1; //调整下界,向右部查找//
  }
  return(0); //low>high,查找失败//
  }
  判定树:用来描述二分查找过程的二叉树。n个结点的判定树的深度和n个结点的完全二叉树深度相同= 。但判断树不一定是完全二叉树,但他的叶子结点所在层次之差不超过1。所以,折半查找在查找成功时和给定值进行比较的关键字个数至多为
  ASL=
  分块查找算法及分析
  分块查找(Blocking Search),又称索引顺序查找(Indexed Sequential Search),是顺序查找方法的一种改进,目的也是为了提高查找效率。
  1.分块
  设记录表长为n,将表的n个记录分成b= 个块,每块s个记录(最后一块记录数可以少于s个),即:
  且表分块有序,即第i(1≤i≤b-1)块所有记录的key小于第i+1块中记录的key,但块内记录可以无序。
  2.建立索引
  每块对应一索引项:
  KeymaxLink
  其中Keymax为该块内记录的最大key;link为该块第一记录的序号(或指针)。
  3.算法思路 分块索引查找分两步进行:
  (1)由索引表确定待查找记录所在的块;(可以折半查找也可顺序因为索引表有序)
  (2)在块内顺序查找。(只能用顺序查找,块内是无序的)
    5.算法分析
  分块查找算法的时间复杂度为:
  二叉排序树:对二叉排序树中序遍历,得到的肯定是递增的有序序列。所以插入和删除都要保证二叉排序树这一性质。
  1.二叉排序树的建立
  typedef struct Bsnode; //二叉排序树结点//
  { Retype data; //结点数据//
  struct Bsnode *Lchild,*Rchild;
  }BSN,*BSP; //结点及指针说明符//
  BSP createBst( ) //从键盘文件读入记录,建立二叉排序树的算法//
  { BSP T,S; keytype key;
  T=NULL; //置空树,T为二叉排序树根结点指针//
  scanf("%d",&key); //读入第一个记录的key//
  while(key!=0) //设key以0为结束符//
  { S=(BSP)malloc(sizeof(BSN)); //申请结点//
  S->data.key=key; //存入key//
  S->Lchild=S->Rchild=NULL; //置S结点左、右子树为空//
  T=BSTinsert(T,S); //将S结点插入到当前的二叉排序树T中//
  scanf("%d",&key); //读下一记录的key//
  }
  return(T); //返回根指针//
  }
  2.二叉排序树的插入新结点
  BSP BSTinsert(BSP T,BSP S)
  //二叉排序树的插入算法,T、S分别为根结点和待插入结点的指针//
  { BSP q, p;
  if (T==NULL)
  return(S); //树为空时,以S为根//
  p=T; q=NULL; //q为p的父结点指针//
  while(p) //寻找插入位置//
  { q=p;
  if(S->data.key==p->data.key)
  { free(S);
  return(T);
  } //S结点已存在,返回//
  if(S->data.keydata.key)
  p=p->Lchild; //向左找//
  else
  p=p->Rchild; //向右找//
  }
  if(S->data.keydata.key)
  q->Lchild=S; //S为q的左子插入//
  else
  q->Rchild=S; //S为q的右子插入//
  return(T);
  }
      3.二叉排序树的删除结点
  (1)算法思路:设指针p指向待删除结点,q为p的父结点指针,分两种情况讨论如下:
  ①当p结点无左子树时,如图
  PR
  q
  P
  p=q->Lchild
  PR
  q
  P
  p=q->Rchild
  其中PR为p结点的右子树(PR=空时,P为叶结点)。此时删除操作只要令:
  q->Lchild=p->Rchild; 或 q->Rchild=p->Rchild;
  ②当p结点的左子树PL存在时,有两种删除方法。
  删除前:
  其一是 直接删除P,再将P的右子树接到新子树的最后下脚
  另一种:将P被最右下的元素替换而不用删除结点(用中序前驱替换)需要掌握的
  (2)算法描述
  Status BSTdelete(BSP t,keytype k)
  //在根指针为t的二叉排序树中,删除key=k的结点的算法//
  { BSP p,q,f,h;
  p=t;q=NULL; //q为p的父结点指针//
  while(p) //寻找被删除结点//
  { if(p->data.key==k)
  break; //找到被删p结点,退出//
  q=p;
  if(kdata.key)
  p=p->Lchild; //向左找//
  else
  p=p->Rchild; //向右找//
  }
  if(p==NULL)
  return(t); //若k不在树中,返回//
  if(p->Lchild==NULL) //p无左子树时//
  { if(q==NULL)
  t=p->Rchild; //p为根,删除后,其右子为根//
  else if(q->Lchild==p) //p为q之左子时//
  q->Lchild=p->Rchild;
  else
  q->Rchild=p->Rchild; //p为q之右子时//
  free(p);
  }
  else //p的左子树存在//
  { f=p;h=p->Lchild; //寻找p在中序下的直接前驱h//
  while(h->Rchild)
  { f=h;
  h=h->Rchild;
  }
  p->data=h->data; //以h结点代替p结点,即删除p结点//
  if(f!=p)
  f->Rchild=h->Lchild;
  else
  f->Lchild=h->Lchild;
  free(h);
  }
  return(t);
  }
    二叉排序树查找算法描述
  BSP BSTSearch(BSP t,keytype k) //在二叉排序树t中,查找key=k的结点//
  { BSP p=t;
  while(p)
  { if(p->data.key==k)
  break; //查找成功,退出循环//
  if(kdata.key)
  p=p->Lchild; //向左找//
  else
  p=p->Rchild; //向右找//
  }
  return(p);
  } //查找成功时返回的是对应的位置,不成功时是插入位置。
  平衡二叉树(AVL)
  平衡因子BF(Balance Factor):BF=HL-HR
  Lchild BFdataRchild
  树的结点形式:
  平衡二叉排序树 :若在构造二叉排序树的同时,使其始终保持为AVL树,则此时的二叉排序树为平衡的二叉排序树。
  4中调整方法:设指针a是失去平衡的最小子树根。
  1 B
  BL
  h-1
  1
  BR
  h-1
  AR
  h-1
  LL型调整
  0 B
  0 A
  BL
  h-1
  1
  BR
  h-1
  AR
  h-1
  2 A
  (1)单向右旋平衡处理:由于在a的左子树根结点的左子树插入结点,a的平衡因子由1增至2,致使以a为根的子树失去平衡,则需要进行一次向右的顺时针旋转操作。(LL)
  -1 B
  BR
  h-1
  1
  BL
  h-1
  AL
  h-1
  RR型调整
  0 B
  0 A
  AL
  h-1
  BL
  h-1
  BR
  h-1
  1
  -2 A

    (2)单向左旋平衡处理:由于在a的右子树根结点的右子树插入结点,a的平衡因子由-1变成-2,致使以a为根结点的子树失去平衡,则需要一次向左的逆时针旋转操作。(RR)
  (3)先左后右平衡处理:由于在a的左子树根结点的右子树上插入结点,a的平衡因子由1增至2,致使以a为根结点的子树失去平衡,需要进行两次旋转(先左旋后右旋)操作(LR)
  -1 B
  BL
  h-1
  CL
  h-2
  1
  AR
  h-1
  LR型调整
  0 C
  -1 A
  BL
  h-1
  CR
  h-2
  AR
  h-1
  2 A
  1 C
  CR
  h-2
  0 B
  CL
  h-2
  1
  1 B
  CL
  h-2
  1
  BR
  h-1
  AL
  h-1
  RL型调整
  0 C
  0 A
  AL
  h-1
  CL
  h-2
  1
  BR
  h-1
  -2 A
  1 C
  CR
  h-2
  -1 B
  CR
  h-2
    (4)先向右后向左平衡处理:由于在a的右子树根结点的左子树上插入结点,a的平衡因子由-1变成-2,致使以a为根结点的子树失去平衡,则需要进行两次旋转(先向右再向左)操作。
  B-树:是一种平衡的多路查找树。一棵M阶的B-树,或者为空树,或满足
  (1)树中的每个结点至多有M棵子树;
  (2)若根结点不是叶子结点,则至少有两颗子树
  (3)除根之外的所有非终端结点至少有 棵子树。
  (4)所有结点的关键字的个数比他的子树个数少1
  一棵3阶B-树(又称2-3树)。
  掌握B-树的插入与删除
  哈希表:处理冲突的方法
  1.开放地址法
  (1)di=1,2,3,……(m-1)——称为线性探查法;
  (2)di= , , , ……——称为二次探查法。
  2.链地址法
  发生冲突时,将各冲突记录链在一起,即同义词的记录存于同一链表。
  装填因子定义:α= ,
  一般,设Hash表的装填因子为α,采用线性、二次探查法及链地址法解决冲突时,查找成功的平均查找长度分别用公式表示如下:
  线性探查法:
  二次探查法:
  链地址法:
   
   
发布与修改日期:2014-08-18
责任编辑:凯程教育

02
  • 01 2019考研群:237188588
  • 01 2019考研公共课群:237188588
  • 01 2018考研复试群:101691756
  • 01 2019金融硕士考研群:258085328
  • 01 2019金融硕士考研群:158221493
  • 01 五道口考研群:101152837
  • 01 2019北大经院金融硕士考研:182454587
  • 01 2019人大金融硕士考研:158221787
  • 01 2019贸大金融硕士考研:113123906
  • 01 2019中财金融硕士考研群:258082886
  • 01 2019MPACC考研群:100618105
  • 01 2019会计专硕群:263915365
  • 01 2019中传考研群:72490860
  • 01 2019中传艺术硕士MFA考研:53732843
  • 01 2019中传新闻传播MJC群:512768938
  • 01 2019名校法学考研群:139789968
  • 01 2019名校法硕考研群:512548111
  • 01 2019翻译硕士考研:512460703
  • 01 2019教育专硕群:277767052
  • 01 2019教育学考研群:8192231
  • 01 2019经济学考研群:512623371
  • 01 2019医学考研qq群:279243253

微信公众号

  • 凯程官方微信
    微信公众号
  • 微信
    kckaoyan

联系我们

  • 咨询电话:400-050-3680
  • QQ服务号:800016820
  • 手机号:13121163112
  • 在线客服: