实验五-查找和排序实验报告(共4页)

1、精选优质文档-倾情为你奉上实验五 查找和排序1、实验目的1. 掌握顺序查找的基本方法2. 掌握简单排序和二分法查找的算法。2能运用线性表的查找方法解决实际问题。2、实验内容1、给出在一个无序表A，采用顺序查找算法查找值为x的元素的算法2、给出一个无序表B，采用简单排序方法使该表递增有序，并采用二分查找算法查找值为x的元素的算法。3、实验步骤（1）仔细分析实验内容，给出其算法和流程图；（2）用C语言实现该算法；（3）给出测试数据，并分析其结果；（4）在实验报告册上写出实验过程。4、实验报告要求实验报告要求书写整齐，步骤完整，实验报告格式如下：1、实验目的2、实验设备3、实验步骤4、实验内容5、实

2、验结果(结论)1.折半查找算法描述如下： int Search_Bin(SSTable ST,KeyType key) low=1;high=ST.length; while(low<=high) mid=(low+high)/2; if EQ(key,ST.elemmid.key) return mid; else if LT(key,ST.elemmid.key) high=mid -1;else low=mid +1 ; return 0; /Search_Bin; 2.顺序查找算法描述如下：typedef struct ElemType *elem;int length;SSTa

3、ble; 顺序查找：从表中最后一个记录开始，逐个进行记录的关键字和给定值的比较，若某个记录的关键字和给定值比较相等，则查找成功，找到所查记录；反之，查找不成功。int Search_Seq(SSTable ST,KeyType key)ST.elme0.key=key; for(i=ST.length; !EQ(ST.elemi.key,key); -i); return i; (3)写出源程序清单（加适当的注释）。#include "stdio.h"typedef struct BiTNode int data; struct BiTNode *lchild,*rchil

4、d;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 (

5、bt->lchild);printf("%5d",bt->data);ZXBL (bt->rchild);BiTree select (BiTree bt,int key) /在二叉排序树bt中查找关键字等于给定值的结点是否存在if(bt=NULL) return NULL;else if(bt->data=key) return bt;else if(key<bt->data) return select (bt->lchild,key);else return select (bt->rchild,key);void ma

6、in() char ch;int key;BiTree s,bt=NULL;int i=0; /建立一个二叉树，元素从键盘输入，直到回车为止printf("n请输入要一列整数,以空格隔开,回车结束. n");while(ch!='n')scanf("%d",&key);s=(BiTree)malloc(sizeof(BiTNode);s->data=key;s->lchild=s->rchild=NULL;insert (&bt,s);ch=getchar();printf("n排序后: n&q

7、uot;); ZXBL (bt);/中序遍历while(1)printf("n输入你要查找的关键字: ");scanf("%d",&key);s=select(bt,key);if(s!=NULL) printf("%d 查找成功!",s->data);else printf("未发现你输入的数!");printf("n再次查找?(Y/N): ");ch=getch();if(ch!='y'&&ch!='Y') return 0;(4

8、)调试说明。包括上机调试的情况、调试所遇到的问题是如何解决的，并对调试过程中的问题进行分析，对执行结果进行分析。1,问题: malloc无法识别.解决: 百度得知缺少头文件,导入stdlib.h后解决.2,问题: 输入后程序无响应.解决: scanf中缺少&,添加后解决.3,问题: 结果显示不正确,为ASCII码解决: 输出改为”%c”.(5)测试结果及说明。对完成所要执行的功能情况分析。（1）（2）五实验体会： 通过本次排序和查找的练习，初步掌握了其基本概念和操作。查找的基本概念： 查找表： 是由同一类型的数据元素（或记录）构成的集合。 查找表的操作： 1、查询某个“特定的”数据元素是否在查找表中。 2、检索某个“特定的”数据元素的各种属性。 3、在查找表中插入一个数据元素； 4、从查找表中刪去某个数