r[i].total=r[i].politics+r[i].Chinese+r[i].English+r[i].math+r[i].physics+r[i].chemistry+r[i].biology; Creat_Seq(st,N);printf(\"准考证号 姓名 政治 语文 外语 数学 物理 化学 生物 总分\\n\"); Traverse(st,print);
printf(\"请输入待查找人的总分\"); scanf(\"%d\ i=Search_Seq(st,s);
6
if(i)
print(*(st.elem+i));
else
print(\"没找到\\n\");
Destroy(st);}
2、有序表查找，同一个文件夹中建立如下五个文件c1.h;c9.h;c9-1.h;bo9-1.cpp;algo9-2.cpp;对于algo9-2.cpp进行编译、构建和运行；
建立文件algo9-2.cpp并利用实验一的文件编译 #include\"c1.h\" #define N 11 typedef int KeyType; struct ElemType {
KeyType key; int others;
}r[N]={{5,1},{13,2},{19,3},{21,4},{37,5},{56,6},{,7},{75,8},{80,9},{88,10},{92,11}}; #include\"c9.h\" #include\"c9-1.h\" #include\"bo9-1.cpp\" void print(ElemType c) {
printf(\"(%d %d)\}
7
void main() {
SSTable st; int i; KeyType s; Creat_Ord(st,N); Traverse(st,print); printf(\"\\n\");
printf(\"请输入待查找值的关键字\")； scanf(\"%d\i=Search_Bin(st,s); if(i)
printf(\"(%d %d)%d是第%d个记录的关键字\\n\else
printf(\"没有找到\\n\"); Destroy(st); }
3、树在同一个文件夹中建立如下五个文件c1.h;c6-2.h;bo9-2.cpp;algo9-4.cpp;对于algo9-1.cpp进行编译、构建和运行；
建立c6-2.h放二叉树的二叉链表存储表示 typedef struct BiTNode {
TElemType data; BiTNode *lchild,*rchild; }BiTNode,*BiTree;
建立文件bo9-2.cpp存储动态查找表的基本操作 typedef ElemType TElemType #include\"c6-2.h\"
8
Status InitDSTable(BiTree &DT) {
DT=NULL; return OK; }
void DestroyDSTable(BiTree &DT) { if(DT) {
if(DT->lchild)
DestroyDSTable(DT->lchild); if(DT->rchild)
DestroyDSTable(DT->rchild); free(DT); DT=NULL; } }
BiTree SearchBST(BiTree T,KeyType key) {
if(!T)||EQ(key,T->data.key)
return T;
else if LT(key,T->data.key)
return SearchBST(T->lchild,key);
else }
9
return SearchBST(T->rchild,key);
void SearchBST(BiTree &T,KeyType key,BiTree f,BiTree &p,Status &flag) { if(!T) { p=f; flag=FALSE; }
else if EQ(key,T->data.key) { p=T; }
else if LT(key,T->data.key)
SearchBST(T->lchild,key,T,p,flag); flag=TRUE;
else }
Status InsertBST(BiTree &T,ElemType e) {
BiTree p,s; Status flag;
SearchBST(T,e.key,NULL,p,flag); if(!flag) {
s=(BiTree)malloc(sizeof(BiTNode)); s->data=e;
s->lchild=s->rchild=NULL; if(!p)
10
SearchBST(T->rchild,key,T,p,flag);
T=s;
else if LT(e.key,p->data.key)
p->lchild=s;
else
p->rchild=s;
return TRUE; } else return FALSE;
}
void Delete(BiTree &p) {
BiTree q,s; if(!p->rchild) { q=p; p=p->lchild; free(q); }
else if(!p->lchild) { q=p; p=p->rchild; free(q); } else { q=p; s=p->lchild;
11
while(s->rchild) { q=s; s=s->rchild; }
p->data=s->data; if(q!=p)
q->rchild=s->lchild;
else
q->lchild=s->lchild;
free(s); } }
Status DeleteBST(BiTree &T,KeyType key)
{//若二叉排序树T中存在关键字等于key的数据元素时，则删除该数据元素结点， }
12
//并返回TRUE；否则返回FALSE。算法9.7 if(!T)//不存在关键字等于key的数据元素
return FALSE;
else { }
if EQ(key,T->data.key)//找到关键字等于key的数据元素
Delete(T);
else if LT(key,T->data.key)
DeleteBST(T->lchild,key);
else
DeleteBST(T->rchild,key);
return TRUE;
void TraverseDSTable(BiTree DT,void(*Visit)(ElemType))
{//初始条件：动态查找表DT存在，Visit是对结点操作的应用函数
//操作结果：按关键字的顺序对DT的每一个结点调用函数Visit（）一且至
多一次 }
建立algo9-4.cpp检验bo9-2.cpp的程序 //alog9-4.cpp的程序 #include\"c1.h\" #define N 10 typedef int KeyType; struct ElemType { };
#include\"c9.h\" #include\"bo9-2.cpp\" void print(ElemType c) { }
13
if(DT) { }
TraverseDSTable(DT->lchild,Visit); Visit(DT->data);
TraverseDSTable(DT->rchild,Visit);
KeyType key; int others;
printf(\"(%d,%d)\
void main() {
BiTree dt,p; int i; KeyType j; ElemType
r[N]={{45,1},{12,2},{53,3},{3,4},{37,5},{24,6},{100,7},{61,8},{90,9},{78,10}};
InitDSTable(dt); for(i=0;iInsertBSTable(dt,r[i]);TraverseDSTable(dt,print); printf(\"请输入待查找的值：\\n\");
scanf(\"%d\
p=SearchBST(dt,j); if(p) {
printf(\"表中存在此值:\"); DeleteBST(dt,j); printf(\"删除此值后:\\n\");
TraverseDSTable(dt,print); printf(\"\\n\"); }
14
} else
printf(\"表中不存在此值\\n\");
DestroyDSTable(dt);
四、实验结果：
1、顺序表查找
2、有序表查找
3、二叉查找树
15
五、实验心得
通过本次试验，让我对课堂所学的知识进行了巩固和提高，对顺序表、有序表和二叉树等知识进行了进一步的学习，并学会了设计查找算法。
尽管这个程序很长，但进过我们小组同学的认真思考、讨论，以及分工合作，终于完成了实验，也让我们意识到，平时的学习不光要学会书本上的知识，还应以实践为主，只有付诸实践才能体现出程序设计的重要性。
16