查找算法集(顺序查找、二分查找、插值查找、动态查找).docx

查找算法集：顺序查找、二分查找、插值查找、动态查找(数组实现、链表实现)/search.cpp:Definestheentrypointfortheconsoleapplication./#includestdafx.h#includeLinkTable.h#defineMAX_KEY500/-数组实现部分-/*/*无序数组顺序查找算法函数nsq_Order_Search参数描述：intarray:被查找数组intn:被查找数组元素个数intkey:被查找的关键值返回值:如果没有找到:nsq_Order_Search=-1否则:nsq_Order_Search=key数组下标*/intnsq_Order_Search(intarray,intn,intkey).inti;arrayn=key;/*/*for循环后面的分号必不可少*/for(i=0;key!=arrayi;i+);return(in?i:-1);/*/*有序数组顺序查找算法函数sq_Order_Search参数描述：intarray:被查找数组intn:被查找数组元素个数intkey:被查找的关键值返回值:如果没有找到:sq_Order_Search=-1否则:sq_Order_Search=key数组下标*/intsq_Order_Search(intarray,intn,intkey).inti;arrayn=MAX_KEY;/*/*for循环后面的分号必不可少*/for(i=0;keyarrayi;i+);if(in&arrayi=key)return(i);elsereturn(-1);/*/*有序数组二分查找算法函数sq_Dichotomy_Search0参数描述：intarray:被查找数组intn:被查找数组元素个数intkey:被查找的关键值返回值:如果没有找到:sq_Dichotomy_Search0=-1否则:sq_Dichotomy_Search0=key数组下标*/intsq_Dichotomy_Search0(intarray,intn,intkey).intlow,high,mid;low=0;high=n-1;while(lowarraymid表明要求查找的值在mid+1,high*/*/*否则,在low,mid-1*/if(keyarraymid)low=mid+1;elsehigh=mid-1;return(-1);/*/*有序数组插值查找算法函数sq_Dichotomy_Search1(插值查找算法是二分查找算法的改进)参数描述：intarray:被查找数组intn:被查找数组元素个数intkey:被查找的关键值返回值:如果没有找到:sq_Dichotomy_Search1=-1否则:sq_Dichotomy_Search1=key数组下标*/intsq_Dichotomy_Search1(intarray,intn,intkey).intlow,high,/二分数组的上,下标pos;/查找码的大致(估算)位置low=0;high=n-1;while(lowarraypos)low=pos+1;elsehigh=pos-1;/*/*没有找到,返回-1*/return(-1);/-数组实现部分-/-链表实现部分-/*/*无序链表顺序查找算法函数nlk_Order_Serach查找思想:遍历链表的所有节点参数描述：Node*head:被查找链表的首指针intkey:被查找的关键值返回值:如果没有找到:nlk_Order_Serach=NULL否则:nlk_Order_Serach=键值为key的节点的指针*/Node*nlk_Order_Serach(Node*head,intkey).for(;head!=NULL&head-data!=key;head=head-link);return(head);/*/*有序链表顺序查找算法函数lk_Order_Serach查找思想:依次遍历链表的节点,发现节点不在key的范围时提前结束查找参数描述：Node*head:被查找链表的首指针intkey:被查找的关键值返回值:如果没有找到:lk_Order_Serach=NULL否则:lk_Order_Serach=键值为key的节点的指针*/Node*lk_Order_Search(Node*head,intkey).for(;head!=NULL&head-datalink);/*/*当遍历指针为NULL或没有找到键值为key的节点,返回NULL(表明没有找到)*/*/*否则,返回head(表明已经找到)*/return(head=NULL|head-data!=key?NULL:head);/*/*有序链表动态查找算法函数lk_Dynamic_Search查找思想:依次遍历链表的节点,发现节点不在key的范围时提前结束查找参数描述：Node*head:被查找链表的首指针Node*p;键值为key的节点的前驱指针(回传参数)Node*q:键值为key的节点指针(回传参数)intkey:被查找的关键值注意:当*p=NULL且*q!=NULL,链表的首节点键值为key当*p!=NULL且*q!=NULL,链表的中间(非首,尾)节点键值为key当*p!=NULL且*q=NULL,链表的尾节点键值为key当*p=NULL且*q=NULL,链表是空链表*/voidlk_Dynamic_Search(Node*head,Node*p,Node*q,intkey).Node*pre,*cur;pre=NULL;cur=head;for(;cur!=NULL&cur-datalink)*p=pre;*q=cur;/*/*有序链表动态插入算法函数lk_Dynamic_Insert参数描述：Node*head:被插入链表的首指针intkey:被插入的关键值返回值:lk_Dynamic_Search=插入键值为key的节点后的链表首指针*/Node*lk_Dynamic_Insert(Node*head,intkey).Node*x,/插入节点的前驱节点*y,/插入节点的后续节点*p;/插入的节点p=(Node*)malloc(sizeof(Node);p-data=key;p-link=NULL;lk_Dynamic_Search(head,&x,&y,key);if(x=NULL).p-link=x;head=p;else.p-link=x-link;x-link=p;ListLinkTable(head,插入节点);return(head);/*/*有序链表动态删除算法函数lk_Dynamic_Delete参数描述：Node*head:被删除链表的首指针intkey:被删除的关键值返回值:lk_Dynamic_Delete=删除键值为key的节点后的链表首指针*/Node*lk_Dynamic_Delete(Node*head,intkey).Node*x,/删除节点的前驱节点*y;/删除的节点lk_Dynamic_Search(head,&x,&y,key);if(x=NULL)/*/*因为x=NLLL时,y指向首指针*/head=y-link;elsex-link=y-link;free(y);ListLinkTable(head,删除节点);return(head);/-链表实现部分-intmain(intargc,char*argv).Node*head;/Node*p,*x,*y;intKEY;intcount,i;/intresult;KEY=11;/PrintArrayValue(TestArray2,DEFAULT_ARRAY_SIZE,原始);/result=sq_Dichotomy_Search1(TestArray2,DEFAULT_ARRAY_SIZE,KEY);/printf(查找结果是：数组%d=%d ,result,TestArray2result);head=CreateLinkTable(DEFAULT_ARRAY_SIZE,TestArray2);ListLinkTable(head,原始);/*/*p=lk_Order_Search(head,KEY);if(p=NULL)printf( 查找结果是：指定链表中没有数据域=%d的节点! ,KEY);elseprintf( 查找结果是：节点.Data=%d 节点.Link=%d 节点.Addr=%d ,p-data,p-link,p);*/printf(输入插入节点的个数： );scanf(%d,&count);for(i=0