数据结构实验五---查找的实现.doc

实验五 查找得实现
一、 实验内容
　 1、建立一个线性表,对表中数据元素存放得先后次序没有任何要求.输入待查数据元素得关键字进行查找。为了简化算法,数据元素只含一个整型关键字字段,数据元素得其余数据部分忽略不考虑.建议采用前哨得作用，以提高查找效率。
2、查找表得存储结构为有序表,输入待查数据元素得关键字利用折半查找方法进行查找.此程序中要求对整型量关键字数据得输入按从小到大排序输入。
二、 源代码与执行结果
1、
＃inclｕｄｅ〈ｉoｓtreａm>
ｕsiｎg namespace stｄ ；
＃defｉne MAX １０0
＃deｆinｅ KｅyTｙpe iｎｔ
typｅｄef stｒuct
{
ＫｅｙＴｙpe key ；
｝DataTｙpe　；
typedef struｃt
{
ﻩDaｔaＴyｐｅ elem[ＭAX］ ;
iｎｔ　length ；
}SeqTａble ， ＊PSeｑTable ；
PSeｑTable Ｉniｔ_SｅqＴable（)
{
ﻩＰSｅqTable p ＝ （ＰＳｅｑTable）malｌoc(ｓizeof（SeｑTable)) ;
ﻩiｆ（p ！＝ ＮULＬ）
｛
p->lｅｎgtｈ = 0 ；
ﻩｒｅｔｕrn　ｐ　；
}
ﻩelsｅ
｛
ﻩ ｃｏｕt〈<"Ouｔ ｏf space!”〈〈endl ；
ﻩ rｅtuｒn NＵＬL　;
ﻩ}
｝
int　insert＿SeqTable（PSeｑTable　p　,KeｙType x)
{
ｉｆ(ｐ-＞length　〉= ＭＡX）
ﻩ｛
ﻩcｏｕt〈<”ｏverｆｌow！"<<endl ;
ﻩreｔuｒn 0 ；
ﻩ}
ｐ—>ｅlem[ｐ—＞leｎgｔh］、key　＝ x ;
p-〉ｌｅｎｇtｈ　+＋ ；
reｔurｎ 1 ;
｝
iｎｔ SｅqSｅarch（SｅqTａble　s ,KｅｙTypｅ　k)
{
ﻩｉnt　n ， i = ０　；
ﻩn = s、ｌength ；
s、eleｍ［n］、ｋeｙ =　ｋ ;
ﻩwhilｅ（s、eｌem[i］、key ！= k）
ﻩﻩi ＋+ ;
ﻩif(i == n）
retｕrn —1 ；
else
ﻩﻩrｅturn i ;
}
ｖoid　ｍain（）
｛
PSeｑTabｌe ｐ ;
int　ｉ , ｎ ；
ﻩKeyＴype a ;
p =　Ｉnit_ＳｅqTaｂｌｅ（） ；
ﻩｃout<〈"请输入数据个数：" ;
ｃin＞>n ；
couｔ〈＜＂请输入数据：”＜〈endｌ ;
fｏr(ｉ = 0 ; ｉ　＜ n ;　ｉ ＋+）
ﻩ{
ﻩciｎ〉＞a ；
ﻩ insert_SｅqTaｂle（p , a） ；
｝
ﻩcｏut＜＜"请输入要查找得数据，输入3２76７结束：” ；
cin〉〉ａ ;
ﻩwｈiｌｅ（a ！= ３27６７)
ﻩ｛
i =SｅｑSearcｈ(*p　， a) ；
ｉf（i == -１）
{
ﻩﻩﻩcｏｕt＜＜”无此数据!请重新输入：＂<〈ｅｎｄl ；
ﻩ ﻩcin＞＞a ；
ﻩ｝
ﻩﻩeｌｓe
ﻩﻩ｛
ﻩ cout＜〈"该数据得位置就是：＂〈<i+1<<enｄｌ ；
ﻩ couｔ〈＜＂请输入要查找得数据：" ；
ﻩ ﻩｃiｎ〉〉ａ　；
ﻩ }
ﻩ｝
｝

2、
＃incｌｕde<iosｔream>
usinｇ naｍespace　stｄ ；
#defｉne MAX 100
＃dｅfine　KeyTyｐe ｉｎt
ｔyｐedef　sｔruct
{
KeyTｙpe key ；
｝ＤataTypｅ ；
typedeｆ stｒuｃt
｛
ﻩDataType ｅｌem［MAX] ；
ﻩinｔ length ；
}BinTａbｌe ,　＊PBｉnＴabｌe ;
PBinTabｌｅ Iniｔ_BiｎTablｅ（）
｛
ﻩPBinＴable p = (PBiｎTabｌe)mａlloｃ（sizeof(ＢinTable）) ;
if(p ！= ＮULＬ)
｛
p->length　= ０ ；
ﻩﻩｒeturn p ；
ﻩ}
eｌse
ﻩ{
ﻩｃout〈<＂Ｏｕt ｏｆ spａｃe！"〈＜endl ;
rｅturｎ NUＬL ;
ﻩ｝
｝
int iｎsｅｒt＿BinTａble（PBinTａble p ，ＫｅyTｙpe x）
{
ｉf（p—〉ｌｅnｇth ＞＝ MAX)
｛
ﻩ ｃoｕt<＜"ｏｖerflow!”<〈ｅnｄl ;
ﻩ return 0 ;
ﻩ}
ﻩp－〉ｅlｅm［p—＞lｅngtｈ］、key =　x ;
ｐ->ｌengtｈ ++ ；
ﻩreturn １ ；
}
int ＢinSearｃh（BinTable　s ，KeyTｙpe k）
｛
ﻩint lｏw　,　mid , ｈiｇｈ ；
ﻩloｗ = 0 ；
high = s、lｅngth-1 ;
ｗｈile（low ＜= hiｇh）
{
ﻩﻩmid　＝　(ｌow+higｈ）／2 ；
ﻩ if(s、ｅlｅm［mｉd]、kｅy　== k)
ﻩﻩﻩretｕrｎ　ｍiｄ　;
ﻩ ｅlse ｉｆ（s、elem[mｉd］、ｋｅy ＞ ｋ）
ﻩﻩ hiｇh　＝ mｉｄ － 1 ;
ﻩﻩｅlｓe
ﻩlow = mid +1 ；
ﻩ｝
ﻩrｅturn —1　；
}
ｖoiｄ main（)
｛
PBinTablｅ p ；
ﻩint　ｉ ,　n ；
ﻩKeyType ａ　;
p ＝　Iｎit＿BinＴable（）　;
ｃｏuｔ<<”请输入数据个数：”　;
ｃｉn〉＞n　；
ﻩｃout<〈"请按从小到大得顺序输入数据：”〈<ｅndｌ　；
fｏr(i = 0 ；　ｉ 〈 n　; i ++）
ﻩ｛
ｃin>〉a　;
ﻩ insert_BinTable（ｐ ，　a）　;
｝
ﻩcout＜<＂请输入要查找得数据,输入32767结束：” ;
ﻩcin〉＞ａ ;
whilｅ（a　！= 3２767)
{
ﻩi =BｉｎSeaｒｃh（*p , ａ） ；
iｆ（ｉ =＝ -1）
ﻩ{
ﻩﻩcｏut〈〈＂无此数据！请重新输入:＂〈〈ｅndl ;
ｃiｎ>>a　;
ﻩ}
ﻩelｓe
{
ﻩcout＜<"该数据得位置就是：”〈<i+1〈＜ｅndl ；
ﻩﻩﻩｃｏut＜〈”请输入要查找得数据:" ；
cin＞〉a ;
}
ﻩ}
｝