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