分块查找 二叉排序树基本运算

源代码

分块查找 #include<stdio.h> #define MAXL 100 typedef int KeyType; typedef char InfoType; typedef struct { KeyType key; InfoType data; }RecType; void CreateList(RecType R[],KeyType keys[],int n) { for(int i=0;i<n;i++) R[i].key=keys[i]; } void DispList(RecType R[],int n) { for(int i=0;i<n;i++) printf("%d",R[i].key); printf("\n"); } int SeqSearch(RecType R[],int n,KeyType k) { int i=0; while(i<n&&R[i].key!=k) { printf("%d",R[i].key); i++; } if(i>=n) return 0; else { printf("%d",R[i].key); return i+1; } } #define MAXI 20 typedef struct { KeyType key; int link; }IdxType; int IdxSearch(IdxType I[],int b,RecType R[],int n,KeyType k) { int s=(n+b-1)/b; int count1=0,count2=0; int low=0,high=b-1,mid,i; printf("(1)在索引表中折半查找\n"); while(low<=high) { mid=(low+high)/2; printf("第%d次比较：在[%d,%d]中比较元素R[%d]:%d\n",count1+1,low,high,mid,R[mid].key); if(I[mid].key>=k)high=mid-1; else low=mid+1; count1++; } printf("比较%d次，在第%d块中查找元素%d\n",count1,low,k); i=I[high+1].link; printf("(2)在对应块中顺序查找：\n"); while(i<=I[high+1].link+s-1) { printf("%d",R[i].key); count2++; if(R[i].key==k)break; i++; } printf("比较%d次，在顺序表中查找元素%d\n",count2,k); if(i<=I[high+1].link+s-1) return i+1; else return 0; } int main() { RecType R[MAXL]; IdxType I[MAXI]; int n=25,i; int a[]={8,14,6,9,10,22,34,18,19,31,40,38,54,66,46,71,78,68,80,85,100,94,88,96,87}; CreateList(R,a,n); I[0].key=14;I[0].link=0; I[1].key=34;I[1].link=4; I[2].key=66;I[2].link=10; I[3].key=85;I[3].link=15; I[4].key=100;I[4].link=20; printf("关键字序列："); for(i=0;i<n;i++) { printf("M",R[i].key); if(((i+1)%5)==0)printf(" "); if(((i+1))==0)printf("\n\t "); } printf("\n"); KeyType k=46; printf("查找%d的比较过程如下:\n",k); if((i=IdxSearch(I,5,R,25,k))!=-1) printf("元素%d的位置是%d\n",k,i); else printf("元素%d不在表中\n",k); return 1; } 二叉排序树基本运算 #include<stdio.h> #include<malloc.h> #include<stdlib.h> #define MaxSize 100 typedef int KeyType; typedef char InfoType; typedef struct node { KeyType key; InfoType data; struct node *lchild,*rchild; }BSTNode; void DispBST(BSTNode *b); bool InsertBST(BSTNode *&bt,KeyType k) { if(bt==NULL) { bt=(BSTNode *)malloc(sizeof(BSTNode)); bt->key=k; bt->lchild=bt->rchild=NULL; return true; } else if(k==bt->key) return false; else if(k<bt->key) return InsertBST(bt->lchild,k); else return InsertBST(bt->rchild,k); } BSTNode *CreateBST(KeyType A[],int n) { BSTNode *bt=NULL; int i=0; while(i<n) if(InsertBST(bt,A[i])==1) { printf("第%d步，插入%d:",i+1,A[i]); DispBST(bt);printf("\n"); i++; } return bt; } void Delete1(BSTNode *p,BSTNode *&r) { BSTNode *q; if(r->rchild!=NULL) Delete1(p,r->rchild); else { p->key=r->key; p->data=r->data; q=r; r=r->lchild; free(q); } } void Delete(BSTNode *&p) { BSTNode *q; if(p->rchild==NULL) { q=p;p=p->lchild;free(q); } else if(p->lchild==NULL) { q=p;p=p->rchild;free(q); } else Delete1(p,p->lchild); } bool DeleteBST(BSTNode *&bt,KeyType k) { if(bt==NULL)return false; else { if(k<bt->key) return DeleteBST(bt->lchild,k); else if(k>bt->key) return DeleteBST(bt->rchild,k); else { Delete(bt); return true; } } } void SearchBST1(BSTNode *bt,KeyType k,KeyType path[],int i) { int j; if(bt==NULL) return; else if(k==bt->key) { path[i+1]=bt->key; for(j=0;j<=i+1;j++) printf("=",path[j]); printf("\n"); } else { path[i+1]=bt->key; if(k<bt->key) SearchBST1(bt->lchild,k,path,i+1); else SearchBST1(bt->rchild,k,path,i+1); } } int SearchBST2(BSTNode *bt,KeyType k) { if(bt==NULL) return 0; else if(k==bt->key) { printf("=",bt->key); return 1; } else if(k<bt->key) SearchBST2(bt->lchild,k); else SearchBST2(bt->rchild,k); printf("=",bt->key); } void DispBST(BSTNode *bt) { if(bt!=NULL) { printf("%d",bt->key); if(bt->lchild!=NULL||bt->rchild!=NULL) { printf("("); DispBST(bt->lchild); if(bt->rchild!=NULL)printf(","); DispBST(bt->rchild); printf(")"); } } } KeyType predt=-32767; bool JudgeBST(BSTNode *bt) { bool b1,b2; if(bt==NULL) return true; else { b1=JudgeBST(bt->lchild); if(b1==false||predt>=bt->key) return false; predt=bt->key; b2=JudgeBST(bt->rchild); return b2; } } void DestroyBST(BSTNode *bt) { if(bt!=NULL) { DestroyBST(bt->lchild); DestroyBST(bt->rchild); free(bt); } } int main() { BSTNode *bt; int path[MaxSize]; KeyType k=6; int a[]={4,9,0,1,8,6,3,5,2,7},n=10; printf("(1)创建一棵BST树:"); printf("\n"); bt=CreateBST(a,n); printf("(2)BST:");DispBST(bt);printf("\n"); printf("(3)bt%s\n",(JudgeBST(bt)?"是一棵BST":"不是一棵BST")); printf("(4)查找%d关键字(递归，顺序):",k);SearchBST1(bt,k,path,-1); printf("(5)查找%d关键字(非递归，逆序):",k);SearchBST2(bt,k); printf("\n(6)删除操作：\n"); printf("原BST:");DispBST(bt);printf("\n"); printf("删除结点4："); DeleteBST(bt,4);DispBST(bt);printf("\n"); printf("删除结点5："); DeleteBST(bt,5);DispBST(bt);printf("\n"); printf("(7)销毁BST\n");DestroyBST(bt); system("paude"); return 0; }

备注： 有问题可以评论，看到后我会尽力及时回复的，谢谢！