查找算法
#include<stdio.h> #include<stdlib.h> typedef struct BiTNode{ int data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; int SequentialSearch(int arr[],int length,int key); void QuickSort(int arr[],int low,int high); int Partition(int arr[],int low,int high); int BinarySearch(int arr[],int length,int key); int CreateBST(BiTree *T,int arr[],int n); int InsertBST(BiTree *T,int k); BiTNode * SearchBST(BiTree T,int key,BiTNode *p); void MiddleOrder(BiTree T); int main() { int n=8; int k=0; int A[]={ 6,5,9,1,4,11,80,3,10 }; BiTree T=NULL; BiTNode *bstresult=NULL; BiTNode *p=NULL; for(k=0;k<9;k++) { printf("%d\t",A[k]); } printf("\n"); CreateBST(&T,A,9); printf("\n"); int result=BinarySearch(A,n,80); bstresult=SearchBST(T,80,p); if(bstresult!=NULL) { printf("%d",bstresult->data); } MiddleOrder(T); return 0; } int SequentialSearch(int arr[],int length,int key) { int i=0; arr[0]=key; for(i=length;arr[i]!=key;--i); return i+1; } int Partition(int arr[],int low,int high) { int pivot=arr[low]; while(low<high) { while(low<high&&arr[high]>=pivot)--high; arr[low]=arr[high]; while(low<high&&arr[low]<=pivot)++low; arr[high]=arr[low]; } arr[low]=pivot; return low; } void QuickSort(int arr[],int low,int high) { if(low<high) { int pivotpos=Partition(arr,low,high); QuickSort(arr,low,pivotpos-1); QuickSort(arr,pivotpos+1,high); } } int BinarySearch(int arr[],int length,int key) { int mid; int low=0; int high=length; while(low<high) { mid=(low+high)/2; if(arr[mid]==key) { return mid+1; } else { if(arr[mid]>key) { high=mid-1; } else { low=mid+1; } } } return 0; } BiTNode * SearchBST(BiTree T,int key,BiTNode *p) { p=NULL; while(T!=NULL&&key!=T->data) { p=T; if(key<T->data) { T=T->lchild; } else { T=T->rchild; } } return T; } int InsertBST(BiTree *T,int k) { if((*T)==NULL) { (*T)=(BiTree)malloc(sizeof(BiTNode)); (*T)->data=k; (*T)->lchild=NULL; (*T)->rchild=NULL; return 1; } else if(k==(*T)->data) { return 0; } else if(k<(*T)->data) { return InsertBST((&(*T)->lchild),k); } else { return InsertBST((&(*T)->rchild),k); } } int CreateBST(BiTree *T,int arr[],int n) { (*T)=NULL; int i=0; while(i<n) { InsertBST(T,arr[i]); printf("The %d\n",i); i++; } } int DeleteBST(BiTree *T,int key) { if(!(*T)) { return 0; } if(key==(*T)->data) { return Delete(T); } else if(key<(*T)->data) { return DeleteBST(&(*T)->lchild,key); } else { return DeleteBST(&(*T)->rchild,key); } } int Delete(BiTree *p) { BiTree s; BiTree q; if(!(*p)->rchild) { q=(*p); (*p)=(*p)->lchild; free(q); } else if(!(*p)->lchild) { q=(*p); (*p)=(*p)->rchild; free(q); } else { q=(*p); s=(*p)->lchild; while(s->rchild) { q=s; s=s->rchild; } (*p)->data=s->data; if(q!=(*p)) { q->rchild=s->lchild; } else { q->lchild=s->lchild; } free(s); } return 1; } void MiddleOrder(BiTree T) { if(T!=NULL) { MiddleOrder(T->lchild); printf("%d\t",T->data); MiddleOrder(T->rchild); } }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。