登 录
查找<span class='wp_keywordlink'><a href="http://www.xuebuyuan.com/category/%E7%AE%97%E6%B3%95" title="算法" target="_blank">算法</a></span>集：顺序查找、二分查找、插值查找、动态查找(数组实现、链表实现)(转)<br /> 关键字: 查找算法 </p> <p>// search.cpp : Defines the entry point for the console application.<br /> // </p> <p>#include "stdafx.h"<br /> #include "LinkTable.h"<br /> #define MAX_KEY 500 </p> <p>//------------------------------数组实现部分----------------------------------<br /> /**//*<br /> 无序数组顺序查找算法函数nsq_Order_Search<用数组实现><br /> 参数描述：<br /> int array[] :被查找数组<br /> int n :被查找数组元素个数<br /> int key :被查找的关键值<br /> 返回值:<br /> 如果没有找到: nsq_Order_Search = -1<br /> 否则: nsq_Order_Search = key数组下标<br /> */<br /> int nsq_Order_Search(int array[],int n,int key)<br /> ...{<br /> int i;<br /> array[n] = key;<br /> /**//*for循环后面的分号必不可少*/<br /> for(i=0;key!=array[i];i++);<br /> return(i<n?i:-1);<br /> }<br /> /**//*<br /> 有序数组顺序查找算法函数sq_Order_Search<用数组实现><br /> 参数描述：<br /> int array[] :被查找数组<br /> int n :被查找数组元素个数<br /> int key :被查找的关键值<br /> 返回值:<br /> 如果没有找到: sq_Order_Search = -1<br /> 否则: sq_Order_Search = key数组下标<br /> */<br /> int sq_Order_Search(int array[],int n,int key)<br /> ...{<br /> int i;<br /> array[n] = MAX_KEY;<br /> /**//*for循环后面的分号必不可少*/<br /> for(i=0;key>array[i];i++);<br /> if(i<n && array[i] == key)<br /> return(i);<br /> else<br /> return(-1);<br /> }<br /> /**//*<br /> 有序数组二分查找算法函数sq_Dichotomy_Search0<用数组实现><br /> 参数描述：<br /> int array[] :被查找数组<br /> int n :被查找数组元素个数<br /> int key :被查找的关键值<br /> 返回值:<br /> 如果没有找到: sq_Dichotomy_Search0 = -1<br /> 否则: sq_Dichotomy_Search0 = key数组下标<br /> */<br /> int sq_Dichotomy_Search0(int array[],int n,int key)<br /> ...{<br /> int low,high,mid;<br /> low = 0;<br /> high = n - 1; </p> <p> while(low<=high)<br /> ...{<br /> mid = (high+low)/2;<br /> if(array[mid] == key)<br /> return(mid);<br /> /**//*key>array[mid] 表明要求查找的值在[mid+1,high]*/<br /> /**//*否则,在[low,mid-1]*/<br /> if(key > array[mid])<br /> low = mid + 1;<br /> else<br /> high = mid - 1;<br /> }<br /> return(-1);<br /> }<br /> /**//*<br /> 有序数组插值查找算法函数sq_Dichotomy_Search1<用数组实现><br /> (插值查找算法是二分查找算法的改进)<br /> 参数描述：<br /> int array[] :被查找数组<br /> int n :被查找数组元素个数<br /> int key :被查找的关键值<br /> 返回值:<br /> 如果没有找到: sq_Dichotomy_Search1 = -1<br /> 否则: sq_Dichotomy_Search1 = key数组下标<br /> */<br /> int sq_Dichotomy_Search1(int array[],int n,int key)<br /> ...{<br /> int low,high, //二分数组的上,下标<br /> pos; //查找码的大致(估算)位置<br /> low = 0;<br /> high = n-1;<br /> while(low <= high)<br /> ...{<br /> pos = (key-array[low])/(array[high]-array[low])*(high-low)+low;<br /> /**//*找到关键值,中途退出*/<br /> if(key == array[pos])<br /> return(pos);<br /> if(key > array[pos])<br /> low = pos + 1;<br /> else<br /> high = pos - 1;<br /> }<br /> /**//*没有找到,返回-1*/<br /> return(-1);<br /> }<br /> //------------------------------数组实现部分----------------------------------<br /> //------------------------------链表实现部分----------------------------------<br /> /**//*<br /> 无序链表顺序查找算法函数nlk_Order_Serach<用链表实现><br /> [查找思想:遍历链表的所有节点]<br /> 参数描述：<br /> Node *head :被查找链表的首指针<br /> int key :被查找的关键值<br /> 返回值:<br /> 如果没有找到: nlk_Order_Serach = NULL<br /> 否则: nlk_Order_Serach = 键值为key的节点的指针<br /> */<br /> Node *nlk_Order_Serach(Node *head,int key)<br /> ...{<br /> for(;head!=NULL && head->data != key;head = head->link);<br /> return(head);<br /> }<br /> /**//*<br /> 有序链表顺序查找算法函数lk_Order_Serach<用链表实现><br /> [查找思想:依次遍历链表的节点,发现节点不在key的范围时提前结束查找]<br /> 参数描述：<br /> Node *head :被查找链表的首指针<br /> int key :被查找的关键值<br /> 返回值:<br /> 如果没有找到: lk_Order_Serach = NULL<br /> 否则: lk_Order_Serach = 键值为key的节点的指针<br /> */<br /> Node *lk_Order_Search(Node *head,int key)<br /> ...{<br /> for(;head!=NULL && head->data < key;head=head->link);<br /> /**//*当遍历指针为NULL或没有找到键值为key的节点,返回NULL(表明没有找到)*/<br /> /**//*否则,返回head(表明已经找到)*/<br /> return(head==NULL || head->data != key ? NULL : head);<br /> }<br /> /**//*<br /> 有序链表动态查找算法函数lk_Dynamic_Search<用链表实现><br /> [查找思想:依次遍历链表的节点,发现节点不在key的范围时提前结束查找]<br /> 参数描述：<br /> Node *head: 被查找链表的首指针<br /> Node **p; 键值为key的节点的前驱指针(回传参数)<br /> Node **q: 键值为key的节点指针(回传参数)<br /> int key : 被查找的关键值<br /> 注意:<br /> 当 *p == NULL 且 *q != NULL,链表的首节点键值为key<br /> 当 *p != NULL 且 *q != NULL,链表的中间(非首,尾)节点键值为key<br /> 当 *p != NULL 且 *q == NULL,链表的尾节点键值为key<br /> 当 *p == NULL 且 *q == NULL,链表是空链表<br /> */<br /> void lk_Dynamic_Search(Node *head,Node **p,Node **q,int key)<br /> ...{<br /> Node *pre,*cur;<br /> pre = NULL;<br /> cur = head;<br /> for(;cur != NULL && cur->data < key;pre = cur,cur = cur->link)<br /> *p = pre;<br /> *q = cur;<br /> }<br /> /**//*<br /> 有序链表动态插入算法函数lk_Dynamic_Insert<用链表实现><br /> 参数描述：<br /> Node *head: 被插入链表的首指针<br /> int key : 被插入的关键值<br /> 返回值:<br /> lk_Dynamic_Search = 插入键值为key的节点后的链表首指针<br /> */<br /> Node *lk_Dynamic_Insert(Node *head,int key)<br /> ...{<br /> Node<br /> *x, //插入节点的前驱节点<br /> *y, //插入节点的后续节点<br /> *p; //插入的节点<br /> p = (Node *)malloc(sizeof(Node));<br /> p->data = key;<br /> p->link = NULL;<br /> lk_Dynamic_Search(head,&x,&y,key);<br /> if(x==NULL)<br /> ...{<br /> p->link = x;<br /> head = p;<br /> }<br /> else<br /> ...{<br /> p->link = x->link;<br /> x->link = p;<br /> }<br /> ListLinkTable(head,"插入节点");<br /> return(head);<br /> }<br /> /**//*<br /> 有序链表动态删除算法函数lk_Dynamic_Delete<用链表实现><br /> 参数描述：<br /> Node *head: 被删除链表的首指针<br /> int key : 被删除的关键值<br /> 返回值:<br /> lk_Dynamic_Delete = 删除键值为key的节点后的链表首指针<br /> */<br /> Node *lk_Dynamic_Delete(Node *head,int key)<br /> ...{<br /> Node *x, //删除节点的前驱节点<br /> *y; //删除的节点<br /> lk_Dynamic_Search(head,&x,&y,key);<br /> if(x==NULL)<br /> /**//*因为x=NLLL时,y指向首指针*/<br /> head = y->link;<br /> else<br /> x->link = y->link;<br /> free(y);<br /> ListLinkTable(head,"删除节点");<br /> return(head);<br /> }<br /> //------------------------------链表实现部分----------------------------------<br /> int main(int argc, char* argv[])<br /> ...{<br /> Node *head;<br /> //Node *p,*x,*y;<br /> int KEY;<br /> int count,i;<br /> //int result;<br /> KEY = 11;<br /> //PrintArrayValue(TestArray2,DEFAULT_ARRAY_SIZE,"原始");<br /> //result = sq_Dichotomy_Search1(TestArray2,DEFAULT_ARRAY_SIZE,KEY);<br /> //printf("查找结果是：数组[%d] = %d ",result,TestArray2[result]);<br /> head = CreateLinkTable(DEFAULT_ARRAY_SIZE,TestArray2);<br /> ListLinkTable(head,"原始");<br /> /**//*<br /> p = lk_Order_Search(head,KEY);<br /> if(p==NULL)<br /> printf(" 查找结果是：指定链表中没有[数据域 = %d]的节点! ",KEY);<br /> else<br /> printf(" 查找结果是：节点.Data = %d 节点.Link = %d 节点.Addr = %d ",p->data,p->link,p);<br /> */<br /> printf("输入插入节点的个数： ");<br /> scanf("%d",&count);<br /> for(i=0;i<count;i++)<br /> ...{<br /> printf("输入插入节点的数据域： ");<br /> scanf("%d",&KEY);<br /> lk_Dynamic_Insert(head,KEY);<br /> }<br /> do<br /> ...{<br /> printf("输入删除节点的数据域： ");<br /> scanf("%d",&KEY);<br /> lk_Dynamic_Delete(head,KEY);<br /> }while(head!=NULL);<br /> printf(" 应用程序正在运行...... ");<br /> return 0;<br /> }<br />
抱歉!评论已关闭.