《数据结构》实验指导书 - 图文(6)

实验七 查找的基本操作

一、

实验目的：

1. 掌握顺序查找的算法； 2. 掌握二分查找法；

3. 掌握二叉排序树的基本操作。

二、 实验内容：

1. 验证二分查找法；

2. 验证二叉排序树的基本操作。

三、 实验要求：

1. 认真阅读、掌握和上机运行本实验的程序； 2. 记录程序的运行结果，并结合程序进行分析； 3. 参照示例程序，完成相应功能的C程序设计编写。

四、 五、

实验学时：2学时 实验步骤：

1． 实验准备：

(1)完成教材第八章课后编程项目1-3题； (2)阅读源程序； (3)编写有关程序。

2． 拓展练习：阅读下列程序，写出各子函数功能和程序运行结果，再上机调试运行。

typedef struct {int elem[100]; int length; } SSTable;

int Searchs(SSTable s,int key) {int i;

s.elem[0]=key;

for(i=s.length;s.elem[i]!=key;i--); return(i); }

int Search_Bin( SSTable ST, int key) {int low, high,mid;

low=1; high=ST.length; while(low<=high) { mid=(low+high)/2;

if(ST.elem[mid]==key) return (mid);

else if( key

{SSTable x; int I,y,k; clrscr();

printf(\请输入线性表的长度\ scanf(\

printf(\请输入线性表的各个元素\\n\ for(I=1;I<=x.length;I++) scanf(\ printf(\所建立的线性表为:\\n\ for(I=1;I<=x.length;I++) printf(\

printf(\请输入待查找的元素\ scanf(\ y=Searchs(x,k);

if (y)printf(\有值为%d的元素，下标为%d\ else printf(\没有值为%d的元素\

printf(\以下验证折半查找，请建立一个有序表，输入线性表的长度\ scanf(\ for(I=1;I<=x.length;I++) x.elem[I]=I*4;

printf(\所建立的线性表为?\\n\for(I=1;I<=x.length;I++)

printf(\printf(\请输入待查找的元素\ scanf(\ y=Search_Bin(x,k);

if (y)printf(\有值为%d的元素,下标为%d\ else printf(\没有值为%d的元素!\}

3． 拓展练习：阅读下列二叉排序树的程序，写出各函数的功能及程序运行结果，再上

机调试运行。 #include typedef struct bnode {int data;

struct bnode *left,*right; } bitree;

void output(t) bitree *t; {

if (t!=NULL) {

output(t->left);

printf(\ output(t->right);} return; }

bitree *insert(bitree *t,bitree *s) {bitree *p=t,*q;

if (t==NULL) return s; while(p!=NULL) {q=p;

if (s->data==p->data) return t; else

{if (s->data>p->data) p=p->right;

else

p=p->left; } }

if(s->data>q->data) q->right=s; else q->left=s; return t; }

bitree *creat() { bitree *t,*s; int k,i,n,dat; t=NULL;

/*scanf(\n=5;

for(i=1;i<=n;i++) {scanf(\

s=(bitree *)malloc(sizeof(bitree)); s->left=NULL;s->right=NULL; s->data=dat; t=insert(t,s); }

return t; }

int delete(bitree *t,int x) {bitree *p=t,*q=NULL; while(p!=NULL)

{if(p->data==x) break; else if(p->data>x) {q=p;p=p->left;} else

{q=p;p=p->right;} }

if(p==NULL) return 0;

if((p->left==NULL)&&(p->right==NULL)) {if(p==t) t=NULL;

else if(p==q->left) q->left=NULL; else q->right=NULL; free(p); } else

if((p->left==NULL)||(p->right==NULL)) {if(p==t) {if(p->left==NULL) t=p->right; else t=p->left;} else

{if((p==q->left)&&(p->left!=NULL)) q->left=p->left; else if(p==q->left&&p->right!=NULL) q->left=p->right; else if(p==q->right&&p->left!=NULL) q->right=p->left; else if(p==q->right&&p->right!=NULL) q->left=p->right; free(p); } } …… 此处隐藏：357字，全部文档内容请下载后查看。喜欢就下载吧 ……