数据结构B上机实验五查找和排序.docx
《数据结构B上机实验五查找和排序.docx》由会员分享，可在线阅读，更多相关《数据结构B上机实验五查找和排序.docx（23页珍藏版）》请在冰点文库上搜索。
数据结构B上机实验五查找和排序
数据结构上机实验五
实验内容:
查找表和内部排序的基本算法
实验要求:
1）基本操作要作为函数被调用，做到模块化.
2）基本上实现每个实验题目的要求.
分组要求：
可单独完成，也可两人一组。
实验目的:
1）熟悉C/C++基本编程,培养动手能力.
2）通过实验,加深对查找算法的理解.
评分标准：
1）只完成第一和第二题，根据情况得4，5-分；
2）完成前3题，根据情况得5，6分；
3）在2）基础上，选做四）中题目，根据情况得6，7分。
题目:
一）顺序表与有序表的查找
（1）建立一个顺序表，利用教材9.1.1的顺序查找算法进行查找；
（2）建立一个有序表，利用折半法进行查找；
（3）试将把
（2）中的折半法改用递归算法实现；
二）二叉排序树的一些基本操作
（1）利用二叉链表的存储形式，从键盘输入建立一棵二叉排序树；
（2）对
（1）中建立的二叉排序树进行中序遍历并打印；
（3）编写算法，判断一棵二叉树是否为二叉排序树。
（4）在
（1）建立的二叉排序树中，查找一个树中不存在的关键字后并插入，之后打印该树；
三）排序
（1）插入排序——已知序列{17，18，60，40，7，32，73，65，85}
建立一个顺序表，采用插入排序算法的实现升序排序，打印排序结果；
（2）交换排序——已知序列{503，87，512，61，908，170，897，275，652，462}
（1）建立一个顺序表，采用冒泡排序法实现升序排序，并打印每趟排序结果；
（2）建立一个顺序表，采用快速排序法实现升序排序，并打印每趟排序结果，与
（1）做比较；
（3）选择排序——已知序列{42，13，24，91，23，16，05，88}
利用简单选择排序，实现上述序列的降序排序；
四）选作题
（1）试构造一个算法，从键盘输入一组关键字，按哈希函数H（key）=keyMOD13和链地址法处理冲突构来造哈希表,能对关键字进行查找并显示。
如（19,14,23,1,68,20,84,27,55,11,10,79,33）.
（2）已知序列{503，87，512，61，908，170，897，275，652，462}，采用基数排序法对其作升序排序，打印每一趟的结果。
（3）归并排序——已知序列{10，18，4，3，6，12，1，9，15，8}，采用归并排序法对其作升序排序，打印每一趟的结果。
（4）堆排序——已知序列{42，13，24，91，23，16，05，88}
按照从小到大，建立“大”顶堆，并打印完全二叉树及其存储结果的变化情况；
一）顺序表与有序表的查找
（1）建立一个顺序表，利用教材9.1.1的顺序查找算法进行查找；
（2）建立一个有序表，利用折半法进行查找；
（3）试将把
（2）中的折半法改用递归算法实现；
#include
#include
#include
#defineOK1
#defineERROR0
intr[10];
#defineEQ（a,b）（（a）==（b））
#defineLT（a,b）（（a）<（b））
typedefintKeyType;
typedefintStatus;
typedefstruct
{
KeyTypekey;
}ElemType;
typedefstruct
{
ElemType*elem;
intlength;
}SSTable;
/*构造一个含n个数据元素的静态顺序查找表ST（数据来自全局数组r）*/
StatusCreat_Seq（SSTable&ST,intn）
{
inti;
ST.elem=（ElemType*）calloc（n+1,sizeof（ElemType））;
if（!
ST.elem）
returnERROR;
for（i=1;i<=n;i++）
ST.elem[i].key=r[i-1];
ST.length=n;
returnOK;
}
/*重建静态查找表为按关键字非降序排序*/
voidAscend（SSTable&ST）
{
inti,j,k;
for（i=1;i{
k=i;
ST.elem[0]=ST.elem[i];
for（j=i+1;j<=ST.length;j++）
ifLT（ST.elem[j].key,ST.elem[0].key）
{
k=j;
ST.elem[0]=ST.elem[j];
}
if（k!
=i）
{
ST.elem[k]=ST.elem[i];
ST.elem[i]=ST.elem[0];
}
}
}
/*构造一个含n个数据元素的静态按关键字非降序查找表ST*/
StatusCreat_Ord（SSTable&ST,intn）
{
Statusf;
f=Creat_Seq（ST,n）;
if（f）
Ascend（ST）;
returnf;
}
/*在顺序表ST中顺序查找其关键字等于key的数据元素。
若找到，则函数值为该元素在表中的位置，否则为0*/
intSearch_Seq（SSTableST,KeyTypekey）
{
inti;
ST.elem[0].key=key;
for（i=ST.length;!
EQ（ST.elem[i].key,key）;--i）;
returni;
}
/*在有序表ST中折半查找其关键字等于key的数据元素。
若找到，则函数值为该元素在表中的位置，否则为0。
算法9.2*/
intSearch_Bin（SSTableST,KeyTypekey）
{
intlow,high,mid;
low=1;
high=ST.length;
while（low<=high）
{
mid=（low+high）/2;
ifEQ（key,ST.elem[mid].key）
returnmid;
elseifLT（key,ST.elem[mid].key）
high=mid-1;
else
low=mid+1;
}
return0;
}
intSearch_Bin_R（SSTableST,KeyTypekey,intlow,inthigh）
{
intmid;
if（low>high）return0;
mid=（low+high）/2;
ifEQ（key,ST.elem[mid].key）returnmid;
elseifLT（key,ST.elem[mid].key）
returnSearch_Bin_R（ST,key,low,mid-1）;
else
returnSearch_Bin_R（ST,key,mid+1,high）;
}
intmain（）
{
inti=0,low,high,len;
SSTableST;
KeyTypekey;
printf（"\n请输入n个数据:
\n"）;
scanf（"%d",&r[i++]）;
while（r[i-1]!
=999）
scanf（"%d",&r[i++]）;
len=i-1;
Creat_Ord（ST,len）;
printf（"%d个数据非降序排序后为：
\n",len）;
for（i=1;i<=len;i++）
printf（"%d",ST.elem[i]）;
printf（"\n请输入要查找的关键字：
"）;
scanf（"%d",&key）;
i=Search_Seq（ST,key）;
printf（"顺序查找所得元素位置为：
%d\n",i）;
i=Search_Bin（ST,key）;
printf（"折半查找所得元素位置为：
%d\n",i）;
low=1;
high=len;
i=Search_Bin_R（ST,key,low,high）;
printf（"折半查找的递归算法所得元素位置为：
%d\n",i）;
while（scanf（"%d",&i）!
=EOF）;
}
二）二叉排序树的一些基本操作
（1）利用二叉链表的存储形式，从键盘输入建立一棵二叉排序树；
（2）对
（1）中建立的二叉排序树进行中序遍历并打印；
（3）编写算法，判断一棵二叉树是否为二叉排序树。
（4）在
（1）建立的二叉排序树中，查找一个树中不存在的关键字后并插入，之后打印该树；
#include
#include
#include
#defineTRUE1
#defineFALSE0
#defineOK1
#defineERROR0
#defineEQ（a,b）（（a）==（b））
#defineLT（a,b）（（a）<（b））
typedefintKeyType;
typedefintStatus;
typedefstruct
{
KeyTypekey;
}ElemType;
typedefstructBTNode
{
ElemTypedata;
structBTNode*lchild;
structBTNode*rchild;
}BTNode,*BTree;
/*操作结果:
构造一个空的动态查找表DT*/
StatusInitDSTable（BTree&DT）
{
DT=NULL;
returnOK;
}
//在根指针T所指二叉排序树中递归地查找其关键字等于key的数据元素，若查找成功，则指针p指向该数据元素结点，并返回TRUE，
//否则指针p指向查找路径上访问的最后一个结点并返回FALSE,指针f指向T的双亲，其初始调用值为NULL
voidSearchBST（BTree&T,KeyTypekey,BTreef,BTree&p,Status&flag）/*算法9.5（b）改*/
{
if（!
T）
{
p=f;
flag=FALSE;
}
elseifEQ（key,T->data.key）
{
p=T;
flag=TRUE;
}
elseifLT（key,T->data.key）
SearchBST（T->lchild,key,T,p,flag）;
else
SearchBST（T->rchild,key,T,p,flag）;
}
//当二叉排序树T中不存在关键字等于e.key的数据元素时，插入e并返回TRUE，否则返回FALSE。
算法9.6（改）
StatusInsertBST（BTree&T,ElemTypee）
{
BTreep,s;
Statusflag;
SearchBST（T,e.key,NULL,p,flag）;
if（!
flag）
{
s=（BTree）malloc（sizeof（BTNode））;
s->data=e;
s->lchild=s->rchild=NULL;
if（!
p）
T=s;
elseifLT（e.key,p->data.key）
p->lchild=s;
else
p->rchild=s;
returnTRUE;
}
else
returnFALSE;
}
voidVisit（ElemTypee）
{
printf（"%d",e.key）;
}
//按关键字的顺序对DT的每个结点调用函数Visit（）一次且至多一次
voidTraverseDSTable（BTreeDT,void（*Visit）（ElemType））
{
if（DT）
{
TraverseDSTable（DT->lchild,Visit）;
Visit（DT->data）;
TraverseDSTable（DT->rchild,Visit）;
}
}
//判断二叉树是否是二叉排序树
voidJudgeBTree（BTree&T,int&flag）
{
if（T）
{
if（T->lchild）
{
if（T->data.keylchild->data.key）
flag=FALSE;
}
if（T->rchild）
{
if（T->data.key>T->rchild->data.key）
flag=FALSE;
}
JudgeBTree（T->lchild,flag）;
JudgeBTree（T->rchild,flag）;
}
}
intmain（）
{
inti,j,flag;
BTreeDT;
ElemTypee;
InitDSTable（DT）;
printf（"\n请依次输入二叉树的结点:
\n"）;
for（j=0;;j++）
{
scanf（"%d",&e.key）;
if（e.key==999）break;
InsertBST（DT,e）;
}
printf（"中序遍历此二叉排序树为：
"）;
TraverseDSTable（DT,Visit）;
printf（"\n"）;
flag=TRUE;
JudgeBTree（DT,flag）;
if（flag==FALSE）
printf（"\n此二叉树不是二叉排序树!
!
!
\n"）;
else
printf（"\n此二叉树是二叉排序树!
!
!
\n"）;
printf（"\n请输入要插入的关键字：
"）;
scanf（"%d",&e.key）;
InsertBST（DT,e）;
printf（"中序遍历此二叉排序树为：
"）;
TraverseDSTable（DT,Visit）;
printf（"\n"）;
while（scanf（"%d",&i）!
=EOF）;
}
（1）插入排序——已知序列{17，18，60，40，7，32，73，65，85}
建立一个顺序表，采用插入排序算法的实现升序排序，打印排序结果；
#include
#include
#include
#defineTRUE1
#defineFALSE0
#defineOK1
#defineERROR0
#defineOVERFLOW-2
#defineEQ（a,b）（（a）==（b））
#defineLT（a,b）（（a）<（b））
#defineLQ（a,b）（（a）<=（b））
#defineMAXSIZE20
typedefintKeyType;
typedefintStatus;
typedefstruct
{
KeyTypekey;
}RedType;
typedefstruct
{
RedTyper[MAXSIZE+1];/*r[0]闲置或用作哨兵单元*/
intlength;
}SqList;
voidPrint（SqListL）
{
inti;
for（i=1;i<=L.length;i++）
printf（"%d",L.r[i].key）;
printf（"\n"）;
}
/*对顺序表L作直接插入排序。
算法10.1*/
voidInsertSort（SqList&L）
{
inti,j;
for（i=2;i<=L.length;++i）
{
ifLT（L.r[i].key,L.r[i-1].key）
{
L.r[0]=L.r[i];
for（j=i-1;LT（L.r[0].key,L.r[j].key）;--j）
L.r[j+1]=L.r[j];
L.r[j+1]=L.r[0];
}
printf（"插入第%d个排序：
",i）;
Print（L）;
}
}
intmain（）
{
SqListL;
inti,r[MAXSIZE]={17,18,60,40,7,32,73,65,85};
printf（"原序列为:
\n{17,18,60,40,7,32,73,65,85}\n"）;
for（i=0;i<9;i++）
L.r[i+1].key=r[i];
L.length=9;
InsertSort（L）;
printf（"插入排序后的升序排序为：
\n"）;
Print（L）;
while（scanf（"%d",&i）!
=EOF）;
}
（2）交换排序——已知序列{503，87，512，61，908，170，897，275，652，462}
（1）建立一个顺序表，采用冒泡排序法实现升序排序，并打印每趟排序结果；
（2）建立一个顺序表，采用快速排序法实现升序排序，并打印每趟排序结果，与
（1）做比较；
#include
#include
#include
#defineTRUE1
#defineFALSE0
#defineOK1
#defineERROR0
#defineOVERFLOW-2
#defineEQ（a,b）（（a）==（b））
#defineLT（a,b）（（a）<（b））
#defineLQ（a,b）（（a）<=（b））
#defineMAXSIZE20
typedefintInfoType;
typedefintKeyType;
typedefintStatus;
typedefstruct
{
KeyTypekey;
}RedType;
typedefstruct
{
RedTyper[MAXSIZE+1];
intlength;
}SqList;
voidPrint（SqListL）
{
inti;
for（i=1;i<=L.length;i++）
printf（"%d",L.r[i].key）;
printf（"\n"）;
}
/*冒泡排序*/
voidBubbleSort（SqList&L）
{
inti,j,change,temp,k=1;
for（i=L.length,change=TRUE;i>1&&change;--i）
{
change=FALSE;
for（j=1;jif（L.r[j].key>L.r[j+1].key）
{
temp=L.r[j].key;
L.r[j].key=L.r[j+1].key;
L.r[j+1].key=temp;
change=TRUE;
}
printf（"第%d趟排序为：
",k++）;
Print（L）;
}
}
/*交换顺序表L中子表r[low..high]的记录，枢轴记录到位，并返回其所在位置，此时在它之前（后）的记录均不大（小）于它。
*/
intPartition（SqList&L,intlow,inthigh,int&t）
{
KeyTypepivotkey;
L.r[0]=L.r[low];
pivotkey=L.r[low].key;
while（low{
while（low=pivotkey）
--high;
L.r[low]=L.r[high];
while（low++low;
L.r[high]=L.r[low];
}
L.r[low]=L.r[0];
printf（"第%d趟排序为：
",t++）;
Print（L）;
returnlow;
}
//对顺序表L中的子序列L.r[low..high]作快速排序。
inti=1;
voidQSort（SqList&L,intlow,inthigh）
{
intpivotloc;
if（low{
pivotloc=Partition（L,low,high,i）;
QSort（L,low,pivotloc-1）;
QSort（L,pivotloc+1,high）;
}
}
//对顺序表L作快速排序。
算法10.8
voidQuickSort（SqList&L）
{
QSort（L,1,L.length）;
}
intmain（）
{
SqListL;
inti,r[MAXSIZE]={503,87,512,61,908,170,897,275,652,462};
for（i=0;i<10;i++）
L.r[i+1].key=r[i];
L.length=10;
printf（"原序列为：
\n{503,87,512,61,908,170,897,275,652,462}\n"）;
printf（"\n冒泡排序：
\n"）;
BubbleSort（L）;
for（i=0;i<10;i++）
L.r[i+1].key=r[i];
printf（"\n快速排序：
\n"）;
QuickSort（L）;
while（scanf（"%d",&i）!
=EOF）;
}
（3）选择排序——已知序列{42，13，24，91，23，16，05，88}
利用简单选择排序，实现上述序列的降序排序；
#include
#include
#include
#defineTRUE1
#defineFALSE0
#defineOK1
#defineERROR0
#defineOVERFLOW-2
#defineEQ（a,b）（（a）==（b））
#defineLT（a,b）（（a）<（b））
#defineLQ（a,b）（（a）<=（b））
#defineMAXSIZE20
typedefintKeyType;
typedefintStatus;
typedefstruct
{
KeyTypekey;
}RedType;
typedefst
升级会员 