内容发布更新时间 : 2024/11/15 17:17:16星期一 下面是文章的全部内容请认真阅读。
实验五 查找和排序
1、实验目的
1. 掌握顺序查找的基本方法
2. 掌握简单排序和二分法查找的算法。
2．能运用线性表的查找方法解决实际问题。
2、实验内容
1、给出在一个无序表A，采用顺序查找算法查找值为x的元素的算法
2、给出一个无序表B，采用简单排序方法使该表递增有序，并采用二分查找算法查找值为x的元素的算法。
3、实验步骤
（1）仔细分析实验内容，给出其算法和流程图； （2）用C语言实现该算法；
（3）给出测试数据，并分析其结果； （4）在实验报告册上写出实验过程。
4、实验报告要求
实验报告要求书写整齐，步骤完整，实验报告格式如下： 1、［实验目的］ 2、［实验设备］ 3、［实验步骤］ 4、［实验内容］
5、［实验结果(结论)］
1
1.折半查找算法描述如下：
int Search_Bin(SSTable ST,KeyType key) low=1;high=ST.length; 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_Bin;
2.顺序查找算法描述如下： typedef struct { ElemType *elem; int length; }SSTable; 顺序查找：
从表中最后一个记录开始，逐个进行记录的关键字和给定值的比较，若某个记录的 关键字和给定值比较相等，则查找成功，找到所查记录；反之，查找不成功。 int Search_Seq(SSTable ST,KeyType key){ ST.elme[0].key=key; for(i=ST.length;
!EQ(ST.elem[i].key,key); --i); return i; }
(3)写出源程序清单（加适当的注释）。 #include \
typedef struct BiTNode { int data;
struct BiTNode *lchild,*rchild; }BiTNode,*BiTree;
void insert(BiTree *bt,BiTree s){ //在二叉树中插入一个新节点,并将较大数至于右子树,较小数至于左子树 if (*bt==NULL) *bt=s; else if (s->data<=(*bt)->data) insert(&((*bt)->lchild),s); else if (s->data>(*bt)->data) insert(&((*bt)->rchild),s); }
void ZXBL(BiTree bt) { //中序遍历,二叉树已排好顺序 if(bt!=NULL){ ZXBL (bt->lchild); printf(\ ZXBL (bt->rchild); } }
2
void main() {
char ch; int key; BiTree s,bt=NULL; int i=0; //建立一个二叉树，元素从键盘输入，直到回车为止 printf(\请输入要一列整数,以空格隔开,回车结束. \\n\ while(ch!='\\n'){ scanf(\ s=(BiTree)malloc(sizeof(BiTNode)); s->data=key; s->lchild=s->rchild=NULL; insert (&bt,s); ch=getchar(); } printf(\排序后: \\n\ ZXBL (bt);//中序遍历 while(1) { printf(\输入你要查找的关键字: \
BiTree select (BiTree bt,int key) //在二叉排序树bt中查找关键字等于给定值的结点是否存在 { if(bt==NULL) return NULL; else if(bt->data==key) return bt; else if(key
}
}
scanf(\s=select(bt,key);
if(s!=NULL) printf(\查找成功!\else printf(\未发现你输入的数!\printf(\再次查找?(Y/N): \ch=getch();
if(ch!='y'&&ch!='Y') return 0;
(4)调试说明。包括上机调试的情况、调试所遇到的问题是如何解决的，并对调试过程中的问题进行分析，对执行结果进行分析。
1,问题: malloc无法识别.
解决: 百度得知缺少头文件,导入stdlib.h后解决. 2,问题: 输入后程序无响应. 解决: scanf中缺少&,添加后解决. 3,问题: 结果显示不正确,为ASCII码 解决: 输出改为”%c”.
(5)测试结果及说明。对完成所要执行的功能情况分析。
（1）
（2）
五．实验体会：
通过本次排序和查找的练习，初步掌握了其基本概念和操作。 查找的基本概念：
查找表： 是由同一类型的数据元素（或记录）构成的集合。 查找表的操作：
1、查询某个“特定的”数据元素是否在查找表中。 2、检索某个“特定的”数据元素的各种属性。
3