查找排序总结范文.doc

查找排序总结范文 =总结几种常见的查找算法*/静态查找顺序查找*/静态查找索引顺序表，效果比顺序表查找较好，但远不及折半查找*/静态查找折半查找#includestdio.h#define SIZE11int Bsearch(int numSIZE,int number,int low,int high)int mid;while(lownummid)low=mid+1;else high=mid-1;return0;main()int numSIZE,number,index,i;for(i=1;inum0=array-numlow;array-weight0=array-weightlow;while(lownumhigharray-num0)-high;array-numlow=array-numhigh;array-weightlow=array-weighthigh;while(lownumlownum0)+low;array-numhigh=array-numlow;array-weighthigh=array-weightlow;array-numlow=array-num0;array-weightlow=array-weight0;return low;Sort(NUM*array,int low,int high)int mid;if(lownum=array.numi;p-weight=array.weighti;if(i=low)p-lchild=NULL;else CreateTree(p-lchild,sw,array,low,i-1);if(i=high)p-rchild=NULL;else CreateTree(p-rchild,sw,array,i+1,high);return p;main()NUM array;struct Node*p,*head;int i,swSIZE,number;randomize();for(i=1;idata=key;s-lchild=s-rchild=NULL;while(p)printf(p-data:%d,p-data);if(p-data=key)printf(find!);getch();return root;else if(keyp-data)printf(search rightn);getch();pr=p;p=p-rchild;elseprintf(search leftn);getch();pr=p;p=p-lchild;printf(have notthis node!);getch();if(!pr)root=s;printf(create tree!n);getch();return root;elseif(keypr-data)printf(input rightn);pr-rchild=s;getch();elseprintf(input leftn);pr-lchild=s;getch();return root;int Search(struct BitTree*&p,struct BitTree*&pr,int key)while(p)if(p-data=key)return1;else if(keyp-data)pr=p;p=p-rchild;elsepr=p;p=p-lchild;printf(have notthis node!);void Delete(struct BitTree*&p,struct BitTree*&pr)struct BitTree*pt;getch();if(!p-lchild&!p-rchild)pt=NULL;else if(p-lchild&!p-rchild)pt=p-lchild;else if(!p-lchild&p-rchild)pt=p-rchild;elsept=p-lchild;pr=p;while(pt-rchild)pr=pt;pt=pt-rchild;p-data=pt-data;if(pr=p)pr-lchild=pt-rchild;else pr-rchild=pt-rchild;if(pr-lchild=p)pr-lchild=pt;else if(pr-rchild=p)pr-rchild=pt;void Print(struct BitTree*p)if(p)Print(p-lchild);printf(%dn,p-data);Print(p-rchild);main()int quit=0,key;structBitTree*root,*pr,*p;root=NULL;while(!quit)char ch;puts(1Insert);puts(2Delete);puts(3Print);puts(4Exit);ch=getch();switch(ch)case1:printf(Please input:);scanf(%d,&key);root=Insert(root,key);break;case2:printf(Please input:);scanf(%d,&key);p=root;pr=NULL;Search(p,pr,key);Delete(p,pr);break;case3:p=root;Print(p);getch();break;case4:quit=1;break;*/动态查找平衡二叉树#includestdio.h#includeconio.h#define EH0;#define LH1;#define RH-1;#define TRUE1;#define FALSE0;typedef struct BSTNodeint data;int bf;structBSTNode*lchild,*rchild;*BitTree;void R_Rotate(BitTree&p)BitTree lc;lc=p-lchild;p-lchild=lc-rchild;lc-rchild=p;p=lc;void L_Rotate(BitTree&p)BitTree rc;rc=p-rchild;p-rchild=rc-lchild;rc-lchild=p;p=rc;int LeftBalance(BitTree&p)BitTree lc,rd;lc=p-lchild;switch(lc-bf)case1:lc-bf=p-bf=EH;R_Rotate(p);break;case-1:rd=lc-rchild;switch(rd-bf)case1:p-bf=RH;lc-bf=EH;break;case0:p-bf=lc-bf=EH;break;case-1:p-bf=EH;lc-bf=LH;break;rd-bf=EH;L_Rotate(p-lchild);R_Rotate(p);break;int RightBalance(BitTree&p)BitTree rc,ld;rc=p-rchild;switch(rc-bf)case-1:rc-bf=p-bf=EH;L_Rotate(p);break;case1:ld=rc-lchild;switch(ld-bf)case1:p-bf=LH;rc-bf=EH;break;case0:p-bf=rc-bf=EH;break;case-1:p-bf=EH;rc-bf=RH;break;R_Rotate(p-rchild);L_Rotate(p);break;int Insert(BitTree&p,int key,int&taller)if(!p)p=new BSTNode;p-lchild=p-rchild=NULL;p-data=key;p-bf=EH;taller=TRUE;elseif(key=p-data)taller=TRUE;return0;if(keydata)if(!Insert(p-lchild,key,taller)return0;if(taller)switch(p-bf)case1:LeftBalance(p);taller=FALSE;break;case0:p-bf=LH;taller=TRUE;break;case-1:p-bf=EH;taller=FALSE;break;elseif(!Insert(p-rchild,key,taller)return0;if(taller)switch(p-bf)case1:p-bf=EH;taller=FALSE;break;case0:p-bf=RH;taller=TRUE;break;case-1:RightBalance(p);taller=FALSE;break;void Print(BitTree&p)if(p)printf(%d%dn,p-data,p-bf);Print(p-lchild);Print(p-rchild);main()BitTree root,p;int quit=0,key,taller;char ch;root=NULL;while(!quit)puts(1Insert);puts(2Print);puts(3Exit);ch=getch();switch(ch)case1:p=root;printf(Please Input:);scanf(%d,&key);Insert(p,key,taller);root=p;break;case2:p=root;Print(p);getch();break;case3:quit=1;break;*/动态查找B+和B-树，在文件系统中很好用*/哈希表查找（简单的算法描述）#define SIZE100#define DUPLICATE-1/表示已有该元素typedef structint keySIZE;int count;int sizeindex;HashTable;int SearchHash(HashTable H,int keynum,int&position,int&count)position=Hash(key);while(H.keyposition!=0&H.keypostion!=keynum)collision(position,+count);/求下一个探测地址if(keynum=H.keyposition)return1;else return0;int InsertHash(HashTable&H,int e)int count=0,position;if(SearchHash(H,e,position,count)return DUPLICATE;else if(count 最佳的状况时间是1，就是第一个就是待查找的远射，最差的查找状况是O（n），就是最后一个是待查找的元素。 二折半查找折半查找是将待查找的数组元素不断的分为两部分，每次淘汰二分之一，但是有个大前提是，元素必须是有序的，如果是无序的则要先进行排序操作，这种查找的方法，类似于找英文字典的Java，我们可以一下子找到字母J开头的，再仔细找。 最佳的状况时间是1，就是第一次分开就查找到了，最差的查找状态是O（n），便是待查找的数据出现在最后一次。 三费氏查找费氏查找主要是根据费氏数列11235813.来确定范围，然后再进行查找四插补查找插补查找是一种类似折半查找的查找