二叉排序树 折半查找 顺序查找 数据结构.doc

二叉排序树 #include c1.h #include stdio.h #include stdlib.h typedef int KeyType; typedef struct node{ KeyType key; struct node *lchild,*rchild; }BiTNode,*BiTree; void InsertBST(BiTree bst,KeyType key) { BiTNode *t; if(bst==NULL) { t=(BiTree)malloc(sizeof(BiTNode)); t-key=key; t-lchild=NULL; t-rchild=NULL; bst=t; } else if(keybst-key) InsertBST(bst-lchild,key); else if(keybst-key) InsertBST(bst-rchild,key); } void CreateBST(BiTree bst) { int i; int n; KeyType key=0; bst=NULL; printf(请输入二叉排序树中元素的个数：); scanf(%d,n); for(i=1;i=n;i++) { printf(请输入二叉排序数中的第%d个元素：,i); scanf(%d,key); InsertBST(bst,key); } } BiTree SearchBST(BiTree bst,KeyType key) { if(!bst) return NULL; else if(bst-key==key) return bst; else if(keybst-key) return SearchBST(bst-lchild,key); else return SearchBST(bst-rchild,key); } int main() { BiTree bst; CreateBST(bst); KeyType temp; printf(请输入你要查找的元素：); scanf(%d,temp); BiTree T; T=SearchBST(bst,temp); if(T==NULL) printf(\n\n查找失败\n); else { printf(\n\n查找成功\n); printf(二叉排序树中查到的元素为：%d\n,T-key); } } 折半查找和顺序查找 #include stdio.h #include stdlib.h #include c1.h #define N 20 typedef struct { int Key; }ElemType; typedef struct SSTable { ElemType *elem; int length; }SSTable; int Search_Seq(SSTable ST,int Key) { int i; ST.elem[0].Key=Key; for(i=ST.length;ST.elem[i].Key!=Key;i--); return i; } int count; int Search_Bin(SSTable ST,int Key) { int low=1; int high=ST.length; int mid; count=0; while(low=high) { count++; mid=(low+high)/2; if(ST.elem[mid].Key==Key) return mid; else if(KeyST.elem[mid].Key) high=mid-1; else low=mid+1; } return 0; } int main() { SSTable ST; ST.elem=(ElemType *)malloc(N*sizeof(ElemType)); if(!ST.elem) exit(0); int len; printf(请输入查找表的长度：); scanf(%d,len); int i; printf(请按顺序输入表中元素：); for(i=1;i=len;i++) scanf(%d,ST.elem[i].Key); ST.length=len; int key=0; while (key!=-1) {printf(请输入你要查找的关键字：); scanf(%d,key); if(key==-1) break;