207年程序设计类课程实验报告20p

1、国脉信息学院（程序设计类课程） 实验报告课程名称：算法与数据结构姓名：系：张三计算机科学与技术专 业:年 级:学 号:指导教师：李小林职称：副教授2012年11 月日实验项目列表序号实验项目名称成绩指导教师1第七章检索及基本算法23456789101112福建农林大学计算机与信息学院实验报告系：计算机科学与技术专业：年级：姓名：_三学号：实验室号计算机号93实验时间：201261指导教师签字： 成绩：实验七检索一、实验目的和要求1) 掌握检索的不同方法，并能用高级语言实现检索算法。2) 熟练掌握顺序表和有序表的检索方法，以及静态检索树的构造方法 和检索算法，理解静态检索树的折半检索方法。3)

2、熟练掌握二叉排序树的构造和检索方法。4) 熟悉各种存储结构的特征以及如何应用树结构解决具体问题。二、实验内容和原理实验内容：1) 编程实现在二叉检索树中删除一个结点的算法。2) 编程实现Fibonacci检索算法。实验原理：1)构造排序树，每输入一个数就进行排序，选择插入的结点，删除结点, 没删除一个节点就返回到构造排序树的方法。2) Fibonacci 数的定义为 fO=O,f1=1,fi二f(i-1)+f(i-2)(i> 2)。由此得Fibonacci 数列为 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,设数组F中元素按关键字值从小到大顺

3、序排列，并假定元素个数n比某个Fibonacci树fi小1,即n=fi-1。第一次用待查关键字k与Ff (i-1 ), 若 k=Ff(i-1),Key 若 k<Ff(i-1),Key 长度为f(i-1)。 若 k>Ff(i-1),KeyKey比较，其算法描述如下:，贝叶佥索成功，Ff(i-1) 为k所在记录。，则下一次的检索范围为下标1到f(i-1)，序列，则下一次的检索范围为下标f(i+1)+1到fi-1 :序列长度为(fi-1 ) - (f(i-1)+1)+1= fi-f(i-1)- 1=f(i-2)-1设F是顺序存储的线性表且满足F1 , key<F2 , key<

4、;-< Fnkey,k是已知的关键字值，在F中检索关键字值为k的记录。若找到返回 其下标值，否则返回0.三、实验环境Win dows XP 系统visual C+6.0四、算法描述及实验步骤实验习题一：#include "stdio.h"#include "malloc.h"struct BTnodeint data;struct BT node *lchild,*rchild;*root;typedef struct BTnode Node,*Nodep;void createtree( int data)Node *no de,*p,*q;no

5、de=(Nodep)malloc( sizeof (Node);no de->data=data;no de->lchild=0;no de->rchild=0;if (root=0)root=no de;return ;elsep=root;while (p!=0)if (data<p->data)q=p;p=p->lchild;if (p=0)q->lchild=node;elseif (data>p->data)q=p； p=p->rchild;if (p=0) q->rchild=no de;elsebreak;void

6、 showtree( struct BTnode *proot, struct BTnode *m, int space) int i;char b;if (proot!=0)for (i=1;i<=space-3;i+)printf("");if (space-3>=0)printf( "->");if (proot=root)printf( "%dn" ,proot->data);elseif (m->data>proot->data)b='L'elseb='R&#

7、39;printf( "%d (%c)" ,proot->data,b);printf( "n");m=proot;showtree(proot->lchild,m,space+6);showtree(proot->rchild,m,space+6);Nodep deletep(Node *p)Node *q,*t;t=p;if (p->lchild!=O)p=p->lchild;q=p； while (p->rchild!=O) q=p； p=p->rchild;if (p=q) p->rchild=t-

8、>rchild; free(t); return (p);if (p->lchild!=O) q->rchild=p->lchild; elseq->rchild=O;p->lchild=t->lchild; p->rchild=t->rchild; free(t); return (p);elseif (p->rchild!=O)p=p->rchild;q=p;while (p->lchild!=O) q=p;p=p->lchild;if (p=q) p->lchild=t->lchild; free(

9、t);return (p);if (p->rchild!=O) q->lchild=p->rchild; elseq->lchild=O;p->rchild=t->rchild;p->lchild=t->lchild;free(t);return (p);elsefree(p);return (0);Nodep deleteBTnode( int x)Node *p=root,*q;while (p!=0)q=p;if (p->data>x)if (p->lchild)p=p->lchild;elsebreak;elsei

10、f (p->data<x)if (p->rchild)p=p->rchild;elsebreak;if (p->data=x)break;if (p=root)&&(p->data=x)root=deletep(p);elseif (p=q->lchild)&&(p->data=x)q->lchild=deletep(p);elseif (p=q->rchild)&&(p->data=x)q->rchild=deletep(p);elseif (p->data!=x)p

11、ri ntf("ca n not found the data you want to delete,pleasecheck it!n");return 0;return root;int main()char ch;int data;printf( "En ter 'c' create tree,E nter 'd' delete a no de:");scanf( "%c",&ch);getchar();root=0;while (ch= 'c' |ch= 'd

12、9;)if (ch='c')pri ntf("please in put the key:" );scanf( "%d",&data);getchar();createtree(data); showtree(root,0,0);elsepri ntf("please in put the key of the node you want del:");scanf( "%d",&data);getchar();if (deleteBTnode(data)showtree(root,0

13、,0);printf( "En ter 'c' create tree,E nter 'd' delete a no de:");scanf( "%c",&ch);return 0;实验习题二：#i nclude "stdio.h"typedef int keytype;typedef int datatype;typedef struct nodeint key;rectype;int fibonacci(int n)if (n=0) return 0;elseif (n=1) return

14、1;elsereturn fibonacci(n-1)+fibonacci(n-2); void printData(rectype R, int n)int i;for (i=1; i<=n; i+)printf( "%5d",Ri.key);if (i%8=0) printf("n" ); printf( "n");int fibsearch(rectype R,keytype K, int n)int m,i,p,q,t;for (m=0;fibonacci(m)<=(n+1);m+) m-;i = fibon ac

15、ci(m-1);p = fibon acci(m-2);q = fibon acci(m-3);while (i>=0 && i<=n)if (K = Ri.key)return i; else if (K < Ri.key)i = i-q;t = p;p = q;q = t-q; else if (K > Ri.key) i=i+q; p=p-q; q=q-p;return 0;void mai n()int m,i,k,n;rectype R20;printf( "En ter k nu m:");scanf("%d&q

16、uot;,&k);printf("en ter R20:");for (i=1;i<=20;i+)scanf( "%d",&Ri.key);prin tData(R,20);m=fibsearch(R,k,20);if (m = 0)printf( "Not fou nd!n");elseprintf( "The Key has bee n found at R%dn",m);getchar();五、调试过程1)构建二叉排序树：删除二叉树的节点：已直动生咸-顷目：數搦结构试验配畫.De lug

17、 liriSZ匕成启动时间対2011/8l&：22：34cIni 11 Oi z.eBuildSt 自t口s :正在创律 b4£ ®el-ag数据结构|克鲨一 un£ w" s; wfullmii 1 d ",因为已扌AlwayECTeaiLeoICornjile；靱据詰掏试验.CPP皿纽MVhpl仏瞅麻期s结构试聆城据结构试验邇据结构试骑.叱代C20C39 "鹼汕：不昱f 皿"的爾員 c：结枸试噓I勤掘结枸试噓I數捐结枸试髓.占“陌：參见H 的声他:皿叱如仏kt环频辭构數堆结构i溜数堀结构i谨® 住厂：e

18、rror C2K39: -key11 :不昙f 皿"的成员 二狂址to讪救拐结枸试验燉協结枸试验燉瞬枸试骚一 TPCS)：参见的声明_;也曲11班仏15伽1数据结构1沆验1数据结构I丑验燼I据结构加：error C2Q39: "key"不是的感员 =；usershpdeskt&p数損结枸试盛5数捐括枸试诫'数1S结枸试验山丹；善见*4寸'的声朋八11 wNhp也Ekt °F、数据结构试怒数据唐碱罐燼塘结畅i罐Cfp(36)- *rror 02030: kay"不是、皿砂的咸员 c Aus*rshpUftiktopSffi®W试胚燼捐括枸试唸'數揭站枸试验"PP：参见"朕”的声明:皿叱血也皿低曦据结构试血哦据结称亦I数垢结爾试验注：wrwr C2tX3g：叫甲不是皿利的粛員 c! user3hpdesktoptiti£tlE结箱i式婭I教吉惭式猛” cpp国：参闪0捷"的靑明，用时间 00:00