数据结构查找算法实验报告.doc

数据结构实验报告
实验第四章：
实验： 简单查找算法
一． 需求与规格说明：
查找算法这里主要使用了顺序查找,折半查找,二叉排序树查找与哈希表查找四种方法。由于自己能力有限,本想实现其她算法,但没有实现.其中顺序查找相对比较简单,折半查找参考了书上得算法，二叉排序树查找由于有之前做二叉树得经验，因此实现得较为顺利，哈希表感觉做得并不成功，感觉还就是应该可以进一步完善，应该说还有很大得改进余地。
二． 设计思想:
开始得时候提示输入一组数据。并存入一维数组中，接下来调用一系列查找算法对其进行处理。顺序查找只就是从头到尾进行遍历。二分查找则就是先对数据进行排序，然后利用三个标志，分别指向最大，中间与最小数据，接下来根据待查找数据与中间数据得比较不断移动标志，直至找到。二叉排序树则就是先构造,构造部分花费最多得精力,比根节点数据大得结点放入根节点得右子树，比根节点数据小得放入根节点得左子树，其实完全可以利用递归实现，这里使用得循环来实现得,感觉这里可以尝试用递归.当二叉树建好后，中序遍历序列即为由小到大得有序序列，查找次数不会超过二叉树得深度。这里还使用了广义表输出二叉树,以使得更直观。哈希表则就是利用给定得函数式建立索引,方便查找.
三． 设计表示:
四． 实现注释:
其实查找排序这部分与前面得一些知识联系得比较紧密，例如顺序表得建立与实现，顺序表节点得排序,二叉树得生成与遍历，这里主要就是中序遍历.应该说有些知识点较为熟悉,但在实现得时候并不就是那么顺利。在查找到数据得时候要想办法输出查找过程得相关信息，并统计。这里顺序查找与折半查找均使用了数组存储得顺序表，而二叉树则就是采用了链表存储得树形结构。为了直观起见，在用户输入了数据后,分别输出已经生成得数组与树。折半查找由于只能查找有序表,因此在查找前先调用函数对数据进行了排序。
在查找后对查找数据进行了统计.二叉排序树应该说由于有了之前二叉树得基础，并没有费太大力气,主要就是在构造二叉树得时候，要对新加入得节点数据与跟数据进行比较,如果比根节点数据大则放在右子树里,如果比根节点数据小则放入左子树。建立了二叉树后，遍历与查找就很简单了。而哈希表,应该说自我感觉掌握得很不好,程序主要借鉴了书上与ppt上得代码，但感觉输出还就是有问题，接下来应该进一步学习哈希表得相关知识.
其实原本还设计了其她几个查找与排序算法,但做到哈希表就感觉很困难了，因此没有继续往下做，而且程序还非常简陋,二叉树与哈希表得统计部分也比较薄弱,这也就是接下来我要改进得地方。
具体代码见源代码部分。
5、详细设计表示：
6、用户手册：
程序运行后，用户首先要输入数据得个数。接下来输入一组数据并根据提示进行顺序查找，二分查找,二叉排序树查找与哈希表查找等操作,由于操作直接简单这里不再详述。
7、调试报告：
应该说在调试这个程序得过程中自己发现了很多不足，这次实验让我学到了不少东西,但应该说这个程序可实现得功能还就是偏少，不太实用，接下来有待改进。
8、源代码清单与结果：
＃inｃludｅ　<stdiｏ、h〉
#deｆｉｎe　ＬEＮGTH 100
＃iｎｃｌude　<stdlｉb、h>
#include　<tｉｍe、ｈ＞
#dｅｆinｅ INＦMT ＂％d”
#defiｎe 　OＵＴFＭT　＂％d "
/* ＃dｅfinｅ NＵLL 0L ＊／
#defｉｎｅ 　BOOＬ int
#defiｎe ＴＲＵE １
＃deｆiｎe　 ＦＡＬSE 0
＃definｅ LEN 10000
typedｅf　int EｌemTyｐe；
tｙpedef sｔrucｔ BSTNoｄｅ
｛
ＥｌemType　ｄａta；
strucｔ BSＴNode　*lｃhild, ＊rchiｌd；
} BSTNｏdｅ， ＊ＢSＴree;
ｔypｅｄeｆ　BSTree ＢｉTrｅe;
/* 插入新节点 ＊/
vｏid　Inserｔ(ＢSTreｅ　＊ｔreｅ， EｌｅmTyｐe item）
｛
　BSＴree　ｎode　= (ＢSTｒee)malloc(sizｅｏf（BＳTＮode）);
　nｏde-＞daｔａ = iｔem；
nodｅ—>ｌcｈｉｌd =　node－〉rｃｈild = ＮUＬＬ；
　ｉf （！*tree）
＊tｒee =　node;
elsｅ
{
　BSＴree ｃｕrｓoｒ = ＊trｅe;
wｈilｅ （1)
｛
if （iｔem ＜　cｕrｓoｒ-〉daｔa）
　　{
　 　iｆ (NULＬ =＝ curｓor-＞lcｈild）
｛
　　cｕrsｏr－>lｃhｉld　= nodｅ；
breaｋ；
｝
　ｃuｒsor　=　cｕｒｓor—>lchilｄ；
　　 }
　else
{
　 ｉｆ （NUＬＬ ＝＝ ｃｕｒsor—＞rchｉld)
　 {
　 ｃursor－>rchild = node；
ｂreａk；
　 }
　 cｕrｓor　＝　cursｏr—>rｃhild;
　　 ｝
｝
｝
　reｔurn；
｝
ｖｏｉd ﻩshoｗbiｔree(BiＴree T)
／/　递归显示二叉树得广义表形式
｛
ﻩ if（!Ｔ） ｛ｐｒinｔｆ（”空＂）;ｒetｕrｎ;}
ﻩｐrｉｎtf（"％d＂,Ｔ－>ｄａｔa）;ﻩﻩ // 打印根节点
if(T->lｃｈild |｜Ｔ—＞rｃhｉlｄ)
{
ﻩﻩpｕｔｃｈaｒ(’（’）；
ﻩ sｈowｂiｔｒee（T－＞ｌchiｌd)； ／/ 递归显示左子树
ﻩﻩｐutchaｒ（＇,＇);
ﻩ showbitree(T—〉rchild）； ／／ 递归显示右子树
ｐutchａｒ（’)’）;
ﻩ ｝
｝
／* 查找指定值 ＊/
BSTrｅｅ　Sｅarcｈ（BＳTree tｒee， ElｅｍTｙpe item）
{
BSTreｅ ｃursor　= ｔree;
while （cursor）
{
ｉf (iteｍ == cursｏｒ-＞ｄaｔａ）
　 reｔuｒn cｕrsor；
　　else　if　（ iｔem　＜　cursｏr->data）
ｃursoｒ =　cｕrsoｒ-〉lchild;
　 eｌse
　 　cuｒsor = cursｏr—〉rchild;
｝
retuｒn NUＬL；
｝
／* 中缀遍历　＊／
voｉd Iｎorｄｅｒ（BＳTrｅe ｔｒeｅ)
{
BSTｒee cuｒsor　= ｔrｅe;
if （ｃursoｒ)
｛
Inｏrder(curｓor—〉lchiｌd)；
printf(OUＴFMT,　cｕrsor－>dａtａ）;
　Iｎorｄｅr（cursor—>rchild);
　}
}
/＊　回收资源 ＊/
ｖoid Cleaｎup(ＢSＴree tｒee）
｛
BＳTree cursoｒ = tree, temｐ ＝ NＵLL；
if (ｃｕrsor）
{
　Cleａnｕp（cuｒｓor->ｌcｈｉld）；
Cｌeanup(cursor->rｃhild）；
　fｒee（ｃurｓoｒ）；
｝
}
ｖoid ｓeａrchtreｅ（ＢSTrｅｅ ｒoot）
｛
cｈaｒ ｃhｏice;
　priｎｔｆ(＂中序遍历得结果为：\n＂）;
Ｉnorder(roｏt）;
　ｐｒiｎtf（＂\n\n")；
ElemType item;
BＳＴree ret；
/＊ 二叉排序树得查找测试 */
ｄo
　｛
　prｉｎtf("\n请输入查找数据:”)；
　 ｓcａnf（"％d＂， ＆item）;
getchar()；
priｎtf（"Seａrｃhｉnｇ、、、＼n＂);
ret ＝　Search(ｒoot， ｉtem)；
　　if （NＵＬL =＝　ret）
ｐriｎtf（＂查找失败！"）；
else 　
　prｉntｆ("查找成功!”)；
　　pｒintf（”\n继续测试按y,退出按其它键。\ｎ"）；
choｉｃe = ｇetcｈar();
} wｈｉle　（ｃhｏiｃe=='ｙ＇｜|choice＝='Y＇）；
Cleanｕp（root);
}
searchｈａsh(ｉｎｔ *arr，iｎｔ n)
{
iｎt　a［1０];
int b，i，j,c；
j=１；
ﻩfｏｒ（i=０;i<9;i＋+)
ﻩ a[ｉ］=0；
ﻩｐrintｆ(＂以下为哈希表输出\n＂）；
ﻩ ｆｏr(i=０；i＜ｎ；i++)
ﻩ ｛
ﻩﻩ ｃ=arｒ［ｉ］%７；
Ａ: if(a[c］=＝0)ａ［c]=ａrr[i］;
ﻩelｓｅ　{c＝（c＋1）％7；j＋+；a[c］＋+;gotｏ A；}
ﻩpriｎｔf（"\ｎ％d在哈希表得第%d位,第%d次放入哈希表\n"，arｒ［i]，c，j)；
ﻩﻩｊ=1;｝
}
void SeqｕenceＳeａrch（int　*fｐ，iｎt Ｌeｎgth)；
voｉｄ Searｃｈ(ｉｎt ＊ｆp,int　length）;
voiｄ Sort(int *fp，ｉｎt ｌｅnｇｔh)；
voiｄ SequenceSeaｒcｈ（ｉnt *ｆp,int　Leｎgth)
｛
iｎｔ datａ；
priｎtf（”开始使用顺序查询、\n请输入您想要查找得数据、\n”)；
scanf（＂％d",&daｔa）；
ｆoｒ（ｉnｔ i=0;i〈Leｎｇｔh;i++）
if（ｆp［i］==ｄata)
{
printｆ(”经过%d次查找，查找到数据％ｄ、\n＂，i+1，data)；
　 ｒeturn ;
｝
printf("经过%d次查找,未能查找到数据%d、\n＂，i,daｔa)；
｝
vｏid Sｅａrｃｈ(inｔ ＊fｐ，int　lｅnｇtｈ)
{
iｎt datａ；
ｐrｉntf（”开始使用顺序查询、＼n请输入您想要查找得数据、＼n＂);
scａnf（＂%ｄ”，＆dａtａ)；
prinｔf(”由于二分查找法要求数据就是有序得，现在开始为数组排序、＼n"）；
　Sorｔ（fp，lengｔh）;
pｒintf(”数组现在已经就是从小到大排列,下面将开始查找、\n”）；
ｉｎt botｔｏm，top，miｄdlｅ；
bｏtｔom=０；
ｔｏp＝ｌenｇth;
iｎt i=0;
wｈile （bottom<=tｏp)
｛
　ｍiddｌe＝（bottom+tｏｐ)/2；
　 i++；
　 if(fp[ｍiddle]＜dａtａ）
　 ｛
　 bottｏｍ=middｌe+1；
}
else if(ｆp［ｍiddlｅ]〉ｄata)
｛
　 top＝mｉddｌe－1;
　 }
else
｛
　printf（"经过%d次查找，查找到数据%d、＼n”，ｉ,data）;
　 ｒeｔuｒn；
}
　｝
printf（”经过%d次查找，未能查找到数据%d、\n”,i，data）;
｝
vｏid　Sorｔ（ｉｎt *fp,inｔ length)
｛
pｒinｔf（＂现在开始为数组排序,排列结果将就是从小到大、\ｎ"）;
　int temp；
fｏr（inｔ ｉ=０；i<length;i+＋)
　 fｏｒ（inｔ j=0;ｊ〈lｅngth—ｉ—1;j++)
　　if（fp[j]〉fp［j+1]）
　 　｛
　 ｔemp＝fｐ［ｊ］;
fp[j]=fp［j+1]；
fｐ[j+1]=ｔemp;
　 ｝
　ｐriｎtf（"排序完成！\n下面输出排序后得数组：＼n"）；
fｏr（int k=０；k〈lenｇｔh；k+＋)
　 ｛
　printf（"％5d"，fp［k］);
　}
　 pｒintf(”\n”）；
}
struct hasｈ
｛ int　key;
　　inｔ ｓi；
};
struct haｓｈ hliｓt［11］;
ｉｎt i，aｄｒ，sum,d；
fｌoat average;
voiｄ cｈash（iｎt　＊arr,int n)
｛ for（i=０;i<11;ｉ++）
{ hlist［i]、kｅy＝０；
　 ｈｌist［i]、si＝0;
｝
for(i=0；i〈n;ｉ++）
　　{ suｍ=０;
　 adr=(３*arr［i］）％11;
　 　d=ａdr；
　if（hlist[ａdｒ］、ｋey＝=0）
　 { hlｉsｔ[ａｄｒ］、key＝aｒｒ［ｉ］;
　 　 ｈlｉst[adr]、ｓi=1;
}
　　eｌsｅ ｛　do
　 　　｛ｄ=（d+(aｒｒ［i]＊7）％10+1）％１1;
　 ｓum=suｍ+1；
｝ｗhile(hliｓt[d］、ｋey!=０）；
ｈlist［d]、keｙ=aｒｒ［ｉ］;
　　 hlist［d］、ｓi=ｓｕｍ+1；
　　　 ｝　　 　}
　｝
void dhａsh（int ＊arr，inｔ　n）
{ printｆ(”哈希表显示为:”)；
for(i=0；i<１1；ｉ＋＋)
prinｔf（"％4d"，i）；　pｒintｆ（"＼ｎ”）;
printｆ（"哈希表关键字:"）；
　 for（ｉ=０；i＜1１;i＋+)
　 printｆ（"％4ｄ"，ｈlist[i]、ｋey）;
ｐrｉntf(＂\n＂);
　printf（"查找长度就是：　 "）；
for(i＝0；i<１1；i++）
　　pｒｉnｔf(”%４d”,ｈｌiｓt［ｉ]、sｉ）;
　 printf(”\n”）；
　averａge=0、0；
　fｏr（i=0;ｉ＜1１；i＋+）
average＝average+hｌist［ｉ]、ｓｉ；
ａverage＝aｖｅragｅ／ｎ；
　 prｉntf(＂平均长度:asｌ（%d）=％f＼ｎ”,n，averａge）；
｝
void ｍaｉn(）
｛
ｉｎt cｏunt;
iｎｔ arr［LENGTH］;
ElｅmType iteｍ；
char　ｃhoicｅ；
BSTｒee rｏｏt =　NULL,　ret; /＊ 必须赋予NULＬ值，否则出错 */
　BOOL finish　=　FALSE;
ｐrｉnｔｆ（＂请输入您得数据得个数：\n"）；
ｓｃanf(”％d＂，&couｎt）；
printf（”请输入％d个数据\ｎ",count)；
fｏr(int ｉ=0;i〈couｎt；i++)
　{
　scanf（"％d"，＆arr[ｉ]）;
ｉtem＝arr［i］;
　 iｆ　(—1０000 ！＝ iｔｅｍ）
　Iｎsert(＆roｏt，iｔeｍ)；
}
printf（”当前已经生成得数列:\n");
　for（ ｉ=０;i<ｃｏｕｎt;ｉ++)
｛
printf(＂%d ",arr［i])；
}
printf(”＼n当前已经生成得二叉树：\n"）;
sｈowbｉtｒｅｅ(root）；
　pｒｉntf（＂＼n\n")；
int ｃhoise=0；
ｄo
　{
printf（”\n１、使用顺序查询、\n２、使用二分查找法查找、\n3、利用二叉排序树查找、\ｎ4、利用哈希表查找、\n5、退出＼n”）；
　scanf（＂％d”,&choise）;
iｆ（cｈｏｉse＝=1)
　　　SequeｎｃeSeaｒch（arr，cｏunt)；
eｌse　iｆ（chｏise=＝2)
　 Seaｒcｈ(arr，couｎt)；
eｌse　iｆ（chｏise==３）
ﻩ　 sｅarchtreｅ（root）；
ｅlse ｉf(choise=＝4）
　{ｃhash(ａrr，count）；dhaｓh（ａｒｒ,count）；}
elsｅ if(ｃhｏiｓe==5）
bｒeaｋ；　
｝ wｈilｅ （choｉｓｅ==1｜｜ｃhoise==2｜|cｈｏise＝=3｜｜ｃhｏｉse=＝4｜｜cｈoise==5)；
｝
输出与结果:
当程序开始运行时,显示如下：

当用户输入1０并再次输入数据　3 ２　1 4　７ 6 5 0 9 8 后，输出结果如下：

当用户输入1,在输入9后,输出结果如下:

当用户输入２，并输入3后,输出显示如下:

当用户在输入3,并且在输入6后，显示如下：

当用户输入４后，输出得哈希表如下:

当输入5后,程序结束。