-
-可编辑修改-
-
-可编辑修改 -
实验五 查找和排序
1、实验目的掌握顺序查找的基本方法
掌握简单排序和二分法查找的算法。
2．能运用线性表的查找方法解决实际问题。
2 、实验内容
1、给出在一个无序表A,采用顺序查找算法查找值为x的元素的算法
2、给出一个无序表B,采用简单排序方法使该表递增有序，并采用二分查找算法查找值为 x的元素的算法。
3、实验步骤
（1 ）仔细分析实验内容,给出其算法和流程图；
（2） 用 C 语言实现该算法；
（3） 给出测试数据,并分析其结果；
（4） 在实验报告册上写出实验过程。
4、实验报告要求
实验报告要求书写整齐,步骤完整,实验报告格式如下：
1 、［实验目的］
2、 ［实验设备］
3、 ［实验步骤］
4、 ［实验内容］
5、 ［实验结果 （结论 ）］
排序创建二叉捌
L 「
1?折半查找算法描述如下：
int Search_Bin(SST able ST,KeyType key) low=1;high=ST .len gth;
while(low<=high){
mid=(low+high)/2;
if EQ(key,ST.elem[mid].key) return mid;
else if LT(key,ST.elem[mid].key) high=mid -1;
else low=mid +1 ;
}
return 0;
}//Search_B in;
2.顺序查找算法描述如下： typedef struct {
ElemType *elem;
int len gth;
}SSTable;
顺序查找：
从表中最后一个记录开始，逐个进行记录的关键字和给定值的比较，若某个记录的关键字和给定值比较相等，则查找成功，找到所查记录；反之，查找不成功。
int Search_Seq(SST able ST,KeyType key){
ST.elme[O].key=key;
for(i=ST.Ie ngth;
!EQ(ST.elem[i].key,key); --i);
return i; }
(3)写出源程序清单(加适当的注释)。
#i nclude "stdio.h"
void mai n()
typedef struct BiTNode {
{
char ch;
int data;
int key;
struct BiTNode *lchild,*rchild;
BiTree s,bt=NULL;
}BiTNode,*BiTree;
int i=0; //建立一个二叉树，元素从键盘输入，
直到回车为止
void insert(BiTree *bt,BiTree s){ // 在二叉树中插
printf("\n 请输入要一列整数，以空格隔开，回车结
入一个新节点，并将较大数至于右子树，较小数至于左子
束.\n");
树
while(ch!='\n'){
if (*bt==NULL) *bt=s;
scan f("%d", &key);
else if (s->data<=(*bt)->data)
s=(BiTree)malloc(sizeof(BiTNode));
in sert(&((*bt)->lchild),s);
s->data=key;
else if (s->data>(*bt)->data)
s->lchild=s->rchild=NULL;
in sert(&((*bt)->rchild),s);
in sert (&bt,s);
}
ch=getchar();
void
ZXBL（BiTree bt） { //中序遍历，二叉树已排好顺
}
序
printf("\n 排序后：\n”)；
if(bt!=NULL){
ZXBL (bt);//中序遍历
ZXBL (bt->lchild);
while(1)
prin tf("%5d",bt->data);
{
ZXBL (bt->rchild);
prin tf（"\n 输入你要查找的关键字：”）；
}
scan f("%d", &key);
}
s=select(bt,key);
BiTree select (BiTree bt,int key) // 在一叉排序树 bt
if(s!=NULL) prin tf("%d 查 找 成
中查找关键字等于给定值的结点是否存在
功!",s->data);
{
else prin tf（"未发现你输入的数！"）；
if(bt==NULL) retur n NULL;
printf("\n 再次查找?(Y/N):");
else if(bt->data==key)
ch=getch();
return bt;
if(ch!='y'&&ch!='Y') return 0;
else if(key<bt->data)
}
return select (bt->lchild,key);
}
}
else return select (bt->rchild,key);
-
-可编辑修改 -
(4)
(4)调试说明。包括上机调试的情况、调试所遇到的问题是如何解决的，并对调试过程中的问题进行分析，对执
-
-可编辑修改-
行结果进行分析。
1,问题：malloc无法识别
解决：百度得知缺少头文件，导入stdlib.h后解决.
2,问题：输入后程序无响应
解决:scanf中缺少&添加后解决
3,问题：结果显示不正确，为ASCII码
解决：输岀改为” %c
(5)测试结果及说明。对完成所要执行的功能情况分析。
(1 )
请输入要一列整数，以空格隔开，回车结束.
12 刖 55 23 55 78 121 31
非序后：
12 23 91 34 FE E5 78 121
输入你晏査找的关键字：阴
2S査我旗I加
冃次查找？(Y/W :
输入像要查戏的关键字：4
未发现你输入的数！
再玄查W?(V/N):
(2)
谴输入要一列整数,以空格隔开,回车结束.
31 121 111 11L 435 5 5 5
排疼后:
5 5 12 12
12
12
12 31 31 31 31 35 111 111 121
435
输入你要査找的关键字；& 5查找成功！ 再次查我*?(Y/N):
五?实验体会:
通过本次排序和查找的练习，初步掌握了其基本概念和操作。
查找的基本概念： 查找表： 是由同一类型的数据元素（或记录）构成的集合。
查找表的操作：
1、查询某个“特定的”数据元素是否在查找表中。
2、检索某个“特定的”数据元素的各种属性。
3、在查找表中插入一个数据元素；
4、从查找表中刪去某个数据元素。
排序：将一个数据元素的无序序列重新排列成一个按关键字有序的序列 内部排序：待排序记录存放在计算机随机存储器中进行的排序过程； 外部排序：待排序记录的数量很大，以致内存一次不能容纳全部记录，
在排序过程中尚需对外存进行访问的排序过程。