《数据结构算法——Visual C++ 6.0程序集教学课件 第8章》由会员分享，可在线阅读，更多相关《数据结构算法——Visual C++ 6.0程序集教学课件 第8章（69页珍藏版）》请在金锄头文库上搜索。
1、数据结构算法 Visual C+ 6.0程序集 侯 识 忠 等编著 中国水利水电出版社,第八章 查找,8、0 二分查找法(递归调用) /二分查找法(递归调用)erfenfa1.cpp #include #include #include double a10=1.1,1.3,1.5,1.7,1.9,2.1,2.3,2.5,2.7,2.9; void binsrch(int s,int r,double x) int m; m=(s+r)/2; if(am=x) coutr) coutam) binsrch(m+1,r,x); else binsrch(s,m-1,x); ,单击此处运行程序,v
2、oid main() coutx; cout“查找结果:n“; binsrch(s,r,x); cin.get();cin.get();,8、1 二分查找法(非递归调用),#include #include #include void binsrch(int a,int n,int x) int mid,top=0,bot=n-1,find=0,m=0; do m=m+1; mid=(top+bot)/2; if(amid=x) coutamid) top=mid+1; while(top=bot),单击此处运行程序,void main() coutx; cout“查找结果:n“; binsr
3、ch(b,n,x); cin.get();cin.get();,8、2 二叉排序树的类定义与实现,/二叉排序树BinSortT.cpp #include #include #include /二叉树的链式存储结构表示 typedef struct BinaryTree int data; struct BinaryTree *l; struct BinaryTree *r; *BiTree,BiNode; /二叉树的类定义 class BiSearchT private: BiTree root; public: /构造函数 BiSearchT():root(NULL) /构造二叉链表表示的二
4、叉树T int CreateSubTree(BiTree ,/先序遍历二叉树T int PreOrderTraverse(BiTree t,int (*Visit)(int e); /中序遍历二叉树T int InOrderTraverse(BiTree t,int (*Visit)(int e); /插入算法 int InsertBST(BiTree *t,int e); /在二叉排序树中删除一个节点 void Delete(BiTree *p); /二叉排序树的删除 bool DeleteBST(BiTree *t,int key); /二叉排序树上的查找递归算法 bool SearchB
5、ST(BiTree t,int key,BiTree f,BiTree *p); ; /二叉排序树的类实现 /构造二叉链表表示的二叉树T int BiSearchT:CreateSubTree(BiTree ,if(t=NULL) return 0; t-data=alli; CreateSubTree(t-l,all,2*i); CreateSubTree(t-r,all,2*i+1); /先序遍历二叉树T int BiSearchT:PreOrderTraverse(BiTree t,int (*Visit)(int d) if(t) if(Visit(t-data) if(PreOrde
6、rTraverse(t-l,Visit) if(PreOrderTraverse(t-r,Visit) return 1; return 0; else return 1; /中序遍历二叉树T int BiSearchT:InOrderTraverse(BiTree t,int (*Visit)(int d) if(t) if(InOrderTraverse(t-l,Visit),if(Visit(t-data) if(InOrderTraverse(t-r,Visit) return 1; return 0; else return 1; /二叉排序树上的查找递归算法 bool BiSear
7、chT:SearchBST(BiTree t,int key,BiTree f,BiTree *p) if(!t) *p=f;return false;/递归的终结条件 else if(key=t-data) *p=t;return true; else if(keydata) SearchBST(t-l,key,t,p); else SearchBST(t-r,key,t,p);/继续在右子树中查找 /插入算法 int BiSearchT:InsertBST(BiTree *t,int e) BiTree p; BiTree s; if(!SearchBST(*t,e,NULL,else i
8、f(edata) p-l=s; else p-r=s; return true; else return false; /在二叉排序树中删除一个节点 void BiSearchT:Delete(BiTree *p) BiTree q,s; if(!(*p)-r)/在右子树删除 q=(*p); (*p)=(*p)-l; free(q); else if(!(*p)-l)/在左子树删除 q=(*p); (*p)=(*p)-r; free(q); else q=s=(*p)-l; while(s-r) s=s-r;,s-r=(*p)-r; free(*p); (*p)=q; /二叉排序树的删除 bo
9、ol BiSearchT:DeleteBST(BiTree *t,int key) if(*t!=NULL) if (key=(*t)-data) Delete(t); else if(keydata) DeleteBST( ,/二叉排序树类的测试 void main() cout“BinSortT.cpp运行结果:n“; BiTree root; BiTree sroot=NULL; BiTree croot=NULL; int all16=0,1,2,3,0,0,4,5,0,0,0,0,6,0,0,0; int i,a10=45,23,12,3,33,27,56,90,120,62; in
10、t n=7,b=10,7,6,9,20,12,22; BiSearchT my; my.CreateSubTree(root,all,1); cout“先序遍历(root,all):n“; my.PreOrderTraverse(root,printelem); cout“n中序遍历(root,all):n“; my.InOrderTraverse(root,printelem); for(i=0;i10;i+) my.InsertBST(,单击此处运行程序,for(i=0;i3;i+) my.DeleteBST(,8、3 Fibonacci查找法,/Fibonacci查找法Fibonaci.
11、cpp #include typedef int KeyType; typedef struct RecType KeyType key;RecType; int fib(int n) int i,f,f0=0,f1=1; if(n=0) return 0; if(n=1) return 1; for(i=2;i=n;i+) f=f0+f1; f0=f1; f1=f; return f; int FibSearch(RecType R,int m,KeyType k) int low,high,mid,f1,f2; low=1; high=fib(m); f1=fib(m-1); f2=fib
12、(m-2);,while(lowk) high=mid-1; f2=f1-f2; f1=f1-f2; else low=mid+1; f1=f1-f2; f2=f2-f1; return 0; /Fibonacci查找法测试 void main() cout“Fibonaci.cpp运行结果:n“; int n=7; KeyType k=21;,单击此处运行程序,int a10=5,8,13,21,34,55,89,144,233,377; RecType r10; for(int i=0;i10;i+) ri.key=ai; if(FibSearch(r,n,k) cout“查找成功!n“;
13、 else cout“查找失败!n“; cin.get();,8、4 平衡二叉搜索树类定义与实现,/平衡二叉搜索树类定义与实现AVLTREE.h template class BSTree; /平衡二叉搜索树的结点类型定义 template struct TNode private: TNode *left;/左子树指针 TNode *right;/右子树指针 public: int balance;/平衡因子 T data;/数据域 friend class BSTree; /构造函数 TNode():left(NULL),right(NULL),balance(0) TNode(T ite
14、m,TNode *left1,TNode *right1) :balance(0),data(item),left(left1),right(right1) ; template class BSTree private: int size;,public: /构造函数 BSTree(TNode *,/取根指针 TNode *GetRoot(TNode *,/平衡二叉搜索树的类实现 template void BSTree:DeleteTree(TNode *,(*b)-left=(*a); template void BSTree:LR(TNode *a,TNode *b) TNode *c
15、; c=(*b)-right;/c是插入结点 (*a)-left=c-right; (*b)-right=c-left; c-left=(*b); c-right=(*a); switch(c-balance) case 0:(*a)-balance=0; (*b)-balance=0; break; case 1:(*a)-balance=-1;/插入的结点在c的左子树 (*b)-balance=0; break; case -1:(*a)-balance=0;/插入的结点在c的右子树 (*b)-balance=1; break; c-balance=0;,(*b)=c;/使b指向调整后的子树的根 template void BSTree:RL(TNode *a,TNode *b) TNode *c; c=(*b)-left; /c是插入结点 (*a)-right=c-left; (*b)-left=c-right; c-right=(*b); c-left=(*a); switch(c-balance) case 0:(*a)-balance=0; (*b)-balance=0; break; case 1:(*a)-balance=0;/插入的结点在c的左子树 (*b)-balance=-1; break; case -1:
