查找 - suzhouzc/Data-Structure GitHub Wiki
-
顺序表查找的实现
tyedef struct{ //查找表的数据结构(顺序表) ElemType *elem; //动态数组基址 int TableLen; //表的长度 }SSTable; //顺序查找1 int Search_Seq(SSTbble ST ,ElemType key ) { int i; for(i=0;i<ST.TableLen && ST.elem[i]!=key;++i); //查找成功,则返回元素下标;查找失败,则返回-1 return i==ST。TableLen? -1 : i; } //顺序查找2(哨兵):0号位置是哨兵,不放置任何元素,元素从顺序表的第1个位置开始放置(优点:无需判断是否越界,效率更高) int Search_Seq(SSTbble ST ,ElemType key ) { ST.elem[0]=key; //"哨兵" int i; for(i=ST.TableLen;ST.elem[i]!=key;--i); //从后往前找 return i; //查找成功,则返回元素下标;查找失败,则返回0 }//查找成功O(n+1/2) 查找失败O(n+1)
-
折半查找(二分查找,仅适用于有序的顺序表–拥有随机访问的特性,链表没有)
//折半查找 int Binary_Search(SSTable L,ElemType key){ int low=0,high=L.TableLen-1,mid; while(low<=high){ mid=(low+hiigh)/2; //取中间位置 if(L.elem[mid]==key) return mid; //查找成功则返回所在位置 else if(L.elem[mid]>key) high=mid-1; //从前半部分继续查找 else low=mid+1; //从后半部分继续查找 } return -1; //查找失败,则返回-1 }
-
分块查找(数据结构)
//索引表 typedef struct{ ElemType maxValue; int low,high; }Index; //顺序表存储的实际元素 ElemType List[100];、
-
二叉排序树结点
typedef etruct BSTNode{ int key; struct BSTNode *lchild,*rchild; }BSTNode,*BSTree;
//在二叉排序树中查找值为key的结点(非递归) 最坏空间复杂度o(1)
BSTNode *BST_Search( BSTree T,int key){ while(T!=NULL&& key!=T->key){ if(key<T->key) T=T->lchild; else T=T->rchiid; } }
//在二叉排序树中查找值为key的结点(递归实现)最坏空间复杂度o(h)
BSTNode *BSTSearch(BSTree T,int key){ if(T==NULL) return NULL; if(key=T->key) return T; else if(key<T->key) return BSTSearch(T->lchild,key); else return BSTSerch(T->rchild,key); }
//在二叉排序树插入关键字为k的新结点(递归实现)最坏空间复杂度o(h)
int BST_Inert(BSTree &T,int k){ if(T==NULL){ T=(BSTree)malloc(sizeof(BSTNode)); T->key=k; T->lchild=T->rchild=NULL; return 1; //返回1插入成功 } else if(k==T->key) //树中存在相同的关键字的结点。插入失败 return 0; else if(k<T->key) return BST_Insert(T-lchild,k); else return BST_Insert(T->rchild,k); }
//非递归
//按照str[]中的关键字序列建立二叉排序树
void Creat_BST(BSTree &T,int str[],int n){ T=NULL; int i=0; while(i<n){ //依次将每个关键字插入到二叉排序树中 BST-Inert(T,str[i]); i++; }
}
-
AVL–平衡二叉树 ASL–平均查找长度
平衡二叉树的结点
typedef struct AVLNode{ int key; //数据域 int balance; //平衡因子 struct AVLNode *lchild, *rchild;
}AVLNode,*AVLTree;
平衡二叉树的最大深度为O(log n),平均查找长度/查找的时间复杂度为O(log n)
-
平衡二叉树的删除
-
比较(BST–二叉排序树 AVL–平衡二叉树)红黑树
用途:1、平衡二叉树:适用于以查为主,很少插入、删除的场景。
2、红黑树:适用于频繁插入、删除的场景,实用性更强。
-
红黑树与普通平衡二叉树的特殊要求(左根右,根叶黑,不红红,黑路同)
-
数据结构
struct RBnode{ //红黑树的结点的定义 int key; //关键字的值 RBnode*parent; //父节点指针 RBnode*lChild; //左孩子指针 RBnode*rChild; //右孩子指针 int color; //结点颜色,如:可用0/1表示 黑/红,也可以使用枚举型enum表示颜色
};
-
红黑树的插入
-
性质:
根节点黑高为h的红黑树,内部结点数(关键字)(null是外部结点)至少有2^h-1个(最少情况是总共h层黑结点的满树形态)
红黑树中左右子树的高度之差小于2倍
-
红黑树
-
红黑树的删除
-
B树
//5叉排序树的结点定义
struct Node{ ElemType keys[4]; //最多4个关键字 struct Node * child[5]; //最多5个孩子 int num; //结点中有几个关键字 };
-
B树的最小高度和最大高度
(2)
-
B树的插入和删除
核心要求:1、对于m阶B树–除根节点外,结点关键字个数向上取整-1<=n<=m-1 2、子树0<关键字1<子树1<关键字2<子树2<……
-
B+树的特点(支持顺序查找)无论查找成功与否,最终一定都要走到最下面一层结点
(3)非叶根结点至少有两颗子树,其他每个分支结点至少有[m/2]向上取整颗子树。!()
-
哈希表(散列表)拉链法
装填因子越大,查找成功的平均查找长度就越大
-
方法(设计目标–让不同关键字的冲突尽可能地少)
-
开放定址法
(1)线性探测法 (2)平方探测法(散列表长度m必须是一个可以表示成4j+3的素数–质数,才能探测到所有的位置)–二次探测法其中k<=m/2
(3)伪随机
(4)再散列法
-
查找长度判断(第一个查找长度为6)
-
删除操作