<iframe align="top" marginwidth="0" marginheight="0" src="http://www.zealware.com/csdnblog01.html" frameborder="0" width="728" scrolling="no" height="90"></iframe>
//search.cpp:Definestheentrypointfortheconsoleapplication.
//
#include"stdafx.h"
#include"LinkTable.h"
#defineMAX_KEY500
//------------------------------数组实现部分----------------------------------
/**//*
无序数组顺序查找算法函数nsq_Order_Search
参数描述:
intarray[]:被查找数组
intn:被查找数组元素个数
intkey:被查找的关键值
返回值:
如果没有找到:nsq_Order_Search=-1
否则:nsq_Order_Search=key数组下标
*/
intnsq_Order_Search(intarray[],intn,intkey)
...{
inti;
array[n]=key;
/**//*for循环后面的分号必不可少*/
for(i=0;key!=array[i];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;
array[n]=MAX_KEY;
/**//*for循环后面的分号必不可少*/
for(i=0;key>array[i];i++);
if(in&&array[i]==key)
return(i);
else
return(-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(lowhigh)
...{
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
(插值查找算法是二分查找算法的改进)
参数描述:
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(lowhigh)
...{
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:被查找链表的首指针
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->datakey;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的节点指针(回传参数)
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->datakey;pre=cur,cur=cur->link)
*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;
else
x->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,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;icount;i++)
...{
printf("输入插入节点的数据域: ");
scanf("%d",&KEY);
lk_Dynamic_Insert(head,KEY);
}
do
...{
printf("输入删除节点的数据域: ");
scanf("%d",&KEY);
lk_Dynamic_Delete(head,KEY);
}while(head!=NULL);
printf(" 应用程序正在运行...... ");
return0;
}
Trackback: http://tb.blog.csdn.net/TrackBack.aspx?PostId=935672
分享到:
相关推荐
顺序查找、二分查找、插值查找、动态查找(数组实现、链表实现)
5.4.2 链表结构中的查找算法 148 5.4.3 树结构中的查找算法 151 5.4.4 图结构中的查找算法 152 5.5 小结 153 第6章 基本数学问题 154 6.1 判断闰年 154 6.2 多项式计算 156 6.2.1 —维多项式求值 156 6.2.2...
有序数组的二分查找 插值查找 模糊二分查找 散列表 支持插入、删除、查找的散列表 分离链接法处理散列表中的冲突 线性探查法处理散列表中的冲突 二叉树 二叉树的前、中、后序以及层次遍历 支持插入、删除、查找的...
并根据自己的理解重新进行了整理本文持续更新中本文收录于一、计算机基础1、数据结构(1)基本数据结构数据结构基本概念(时间复杂度和空间复杂度的计算方法)数组链表集合队列栈关联数组跳表倒排索引BitSet(2)树...
我的算法我的算法学习笔记数据结构叠放队列链表BinarySearchTree 组地图eep 段树特里联合查找AVL树红黑树哈希表图形演算法分类气泡分选选择排序插入排序贝壳分类快速分类合并排序堆排序计数排序桶分类基数排序搜索二...
顺序查找、二分查找、插值查找、斐波那契查找、树表查找、分块查找、哈希查找 系统设计题 LeetCode 常见题目标签 其他 题解(剑指 Offer) 模板 题目:**剑指 Offer 29. 顺时针打印矩阵** 题目描述:输入一个矩阵,...
范例1-94 顺序表的查找 273 ∷相关函数:Search_Seq函数 1.6.2 静态树表的查找 276 范例1-95 静态树表的查找 276 ∷相关函数:Search_SOSTree函数 1.6.3 二叉排序树的基本操作 280 范例1-96 二叉排序树的基本...
范例1-94 顺序表的查找 273 ∷相关函数:Search_Seq函数 1.6.2 静态树表的查找 276 范例1-95 静态树表的查找 276 ∷相关函数:Search_SOSTree函数 1.6.3 二叉排序树的基本操作 280 范例1-96 二叉排序树的基本...
范例1-94 顺序表的查找 273 ∷相关函数:Search_Seq函数 1.6.2 静态树表的查找 276 范例1-95 静态树表的查找 276 ∷相关函数:Search_SOSTree函数 1.6.3 二叉排序树的基本操作 280 范例1-96 二叉排序树的基本...
4.1.5 名称查找 4.2 包含文件 4.2.1 包含标准库文件 4.2.2 用户自定义头文 4.2.3 条件包含指令 4.2.4 文件包含 4.3 源文件和连接 4.3.1 独立编译 4.3.2 外部连接和内部连接 4.3.3 与其他...
为实现静态编译,易语言编译器、核心支持库、集成开发环境(IDE)等均有重大更新,支持库开发架框有扩展性调整,绝大多数官方支持库都已针对静态编译完成自身改造并提供静态库。 目前绝大多数官方支持库均已支持...