[笔记] 数据结构-第九章-检索

线性表的检索

二分法检索

递归

给定的顺序表l

int BinSearch(seqlist *l,int x,int left,int right){if(left>right){return 0;}int mid=(left+right)/2;if(l->a[mid]==x)return mid;if(l->a[mid]>x)return BinSearch(l,x,left,mid-1);elsereturn BinSearch(l,x,mid+1,right);
}

非递归

int BinSearch(seqlist *l,int x,int left,int right){int count=0; //计数while(left <= right){count++;int mid=(left+right)/2;if(l->a[mid]==x){printf("\n查找成功次数: %d \n",count);return mid;}if(l->a[mid]>x)right=mid-1;elseleft=mid+1;}printf("\n查找失败次数: %d\n",count);return -1;
}

二叉排序树

二叉排序树结构体

typedef struct k{int data;struct k* left;struct k* right;
}btree;

判断是否是二叉排序树

中序遍历的角度

利用中序遍历: 在中序遍历中，二叉排序树的节点值是严格递增的

int isBSTree(btree *t) {static btree *pre = NULL; // 静态变量，用于记录中序遍历的前驱节点if (t == NULL) return 1; // 空树是BSTif (isBSTree(t->l) == 0) return 0; // 检查左子树if (pre != NULL && pre->data > t->data) return 0; // 检查当前节点是否满足条件, 当前节点与前驱点比较pre = t; // 更新前驱节点return isBSTree(t->r); // 检查右子树
}

定义的角度

// 找二叉树中的最大值
btree* findMax(btree *t){if(t==NULL)return NULL;btree* max=t;btree* LM=findMax(t->left);btree* RM=findMax(t->right);if(LM!=NULL && LM->data>max->data)max=LM;if(RM!=NULL && RM->data>max->data)max=RM;return max;
}// 找二叉树中最小值
btree* findMin(btree *t){if(t==NULL)return NULL;btree* min=t;btree* Lm=findMin(t->left);btree* Rm=findMin(t->right);if(Lm!=NULL && Lm->data<min->data)min=Lm;if(Rm!=NULL && Rm->data<min->data)min=Rm;return min;
}//判断是否是二叉树(递归)
int isBST(btree *t){if(t==NULL)return 1; //空数为二叉树btree* L_max=findMax(t->left);   //找左子树的最大值btree* R_min=findMin(t->right); //找右子树的最小值// 如果左子树的最大值大于当前节点的值，或者右子树的最小值小于当前节点的值，则不是二叉排序树if((t->left!=NULL && t->data<=L_max->data) || (t->right!=NULL && t->data >= R_min->data) )return 0;//递归遍历左右子树是否是二叉排序树if( isBST(t->left) && isBST(t->right) )return 1;return 0;
}

这个方法效率比较低下且看起来也比较复杂, 但感觉比较容易理解一点
改进的代码(GTP改进的)

int isBSTWithRange(btree *t, int min, int max) {if (t == NULL) return 1; // 空树是BSTif (t->data <= min || t->data >= max) return 0; // 当前节点不符合范围// 递归检查左右子树，左子树的值必须小于当前节点值，右子树的值必须大于当前节点值return isBSTWithRange(t->left, min, t->data) &&isBSTWithRange(t->right, t->data, max);
}int isBST(btree *t) {return isBSTWithRange(t, INT_MIN, INT_MAX); // 初始范围为整型的最小值到最大值
}

二叉排序树–插入结点

递归

btree *InsertBSTree(btree *t, int x){btree *q;if(t==NULL){q=(btree *)malloc(sizeof(btree));q->data=x;q->left=NULL;q->right=NULL;return q;}if(x<=t->data)//x小就递归遍历左子树,否则就右子树t->left=InsertBSTree(t->left,x);elset->right=InsertBSTree(t->right,x);return t;
}

非递归

btree *InsertBSTree(btree *t, int x){btree *p,*pre,*q;q=(btree *)malloc(sizeof(btree));q->data=x;q->left=NULL;q->right=NULL;if(t==NULL)return q;p=t;pre=NULL;while(p!=NULL){//查找插入点pre=p;if(x<=p->data) p=p->left;elsep=p->right;}if(x<=pre->data)//x小就插入到左边, 否则插入到右边pre->left=q;elsepre->right=q;	return t;
}

建树(基于插入操作建树)

// 2.2输入一组数据，基于上面插入操作建树(非递归)
void BuildTree(btree **t,int a[], int n){for(int i=0;i<n;i++){*t=InsertBSTree(*t,a[i]);}
}

二叉排序树中查找元素x

递归

btree *Find(btree *t,int x){if(t==NULL || t->data==x)return t;if(x<t->data)return Find(t->left,x);elsereturn Find(t->right,x);return NULL;//未找到返回NULL
}

非递归

btree *Find2(btree *t,int x){while(t!=NULL){if(t->data==x)return t;if(x<t->data)t=t->left;elset=t->right;}return NULL;
}

散列检索

创建hash表

//hash散列表, 取key的十位数作哈希地址，采用线性探测法作为冲突处理方法
void hash(int num[],int h[],int size){//初始化for(int i=0;i<10;i++) //hash表存10个数据h[i]=-1;//填入数据for(int i=0;i<size;i++){int pos=(num[i]/10)%10;//取十位数为hash的keywhile(h[pos]!=-1){//冲突处理pos++;if(pos==10)pos=0;}h[pos]=num[i];	}}

查找值x

//查找 ,线性探测法作为冲突处理方法
void search(int h[],int x){int pos,count=0;pos=(x/10)%10;//hash的keywhile(h[pos]!=x){if(h[pos]==-1){printf("找不到值 %d,查找次数 %d",x,count+1);return;}pos++;if(pos==10)//数组大小为10pos=0;count++;}printf("找到值%d ,查找次数为%d",x,count+1);
}

平均查找长度

void avgCount(int h[],int num[],int size){int i,j,pos,count=0,totalCount=0,notFoundTotalCount=0;for(i=0;i<size;i++){pos=(num[i]/10)%10;count=1;while(h[pos]!=num[i]){pos++;if(pos==10) pos=0;count++;}totalCount+=count;}for(i=0;i<10;i++){pos=i;count=1;while(h[pos]!=-1){pos++;if(pos==10) pos=0;count++;}notFoundTotalCount+=count;}printf("平均查找长度（找到）：%f",(float)totalCount/size);printf("（找不到）：%f\n",(float)notFoundTotalCount/10);
}