内容发布更新时间 : 2024/5/24 16:50:15星期一 下面是文章的全部内容请认真阅读。

实验八 查找

8.1 实验目的：

（1） 熟悉掌握各种查找方法，深刻理解各种查找算法及其执行的过程； （2） 学会分析各种查找算法的性能。

8.2 实验要求：

（1） 复习课本中有关查找的知识；

（2） 用C语言完成算法和程序设计并上机调试通过；

（3） 撰写实验报告，给出算法思路或流程图和具体实现（源程序）、算法分析结果（包括

时间复杂度、空间复杂度以及算法优化设想）、输入数据及程序运行结果（必要时给出多种可能的输入数据和运行结果）。

8.3 基础实验

[实验1] 顺序查找的设计与实现

实验内容与要求:

编写一个程序实现在顺序表｛7，8，34，5，9，12，10，2，4｝中查找9的过程。

分析：

算法思想参照课本。

参考程序：

#include #define MAXL 100 /*定义表中最多记录个数*/ typedef int KeyType;

typedef char InfoType[10]; typedef struct { KeyType key; /*KeyType为关键字的数据类型*/ InfoType data; /*其他数据*/ } NodeType;

typedef NodeType SeqList[MAXL]; /*顺序表类型*/ int SeqSearch(SeqList R,int n,KeyType k) /*顺序查找算法*/ {

int i=0;

while (i

if (i>=n)

1

return -1; else { printf(\ return i; } }

void main() { SeqList R; int n=10; KeyType k=9; int a[]={7,8,34,5,9,12,10,2,4},i; for (i=0;i

[实验2] 折半查找的设计与实现

实验内容与要求：

编写一个程序，实现对顺序表｛2，4，6，8，10，12，14，16｝进行折半查找关键字14的过程。 分析：

算法思想参照课本。

参考程序：

#include #define MAXL 100 /*定义表中最多记录个数*/ typedef int KeyType;

typedef char InfoType[10]; typedef struct { KeyType key; /*KeyType为关键字的数据类型*/ InfoType data; /*其他数据*/ } NodeType;

typedef NodeType SeqList[MAXL]; /*顺序表类型*/ int BinSearch(SeqList R,int n,KeyType k) /*二分查找算法*/ {

2

}

void main() { SeqList R; KeyType k=14; int a[]={2,4,6,8,10,12,14,16},i,n=10; for (i=0;i

int low=0,high=n-1,mid,count=0; while (low<=high) { mid=(low+high)/2;

printf(\第%d次查找:在[%d,%d]中查找到元素R[%d]:%d\\n\

++count,low,high,mid,R[mid].key); if (R[mid].key==k) /*查找成功返回*/ return mid; if (R[mid].key>k) /*继续在R[low..mid-1]中查找*/ high=mid-1; else low=mid+1; /*继续在R[mid+1..high]中查找*/ }

return -1;

8.4 提高实验

[实验1] 二叉排序树的设计与实现。

实验内容与要求：

编写一个程序实现二叉排序树的基本运算，并在此基础上完成如下功能：

（1） 由｛4，9，0，1，8，6，3，5，2，7｝创建一棵bt并以括号表示法输出； （2） 判断bt是否为一棵二叉排序树；

（3） 采用递归和非递归两种方法查找关键字为6的结点，并输出其查找路径； （4） 分别删除bt中的关键字为4和5的结点，并输出删除后的二叉排序树。

分析：

二叉排序树的查找过程如下：即当二叉排序树不为空的时候，首先将给定值和根结点的关键字比较，若相等，则查找成功，否则将依据给定值和根结点的关键字之间的大小关系，分

3