分享
 
 
 

查找算法集:顺序查找、二分查找、插值查找、动态查找(数组实现、链表实现)

王朝other·作者佚名  2007-09-27
窄屏简体版  字體: |||超大  

// 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;

}

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有