程序设计类课程实验报告

《程序设计类课程实验报告》由会员分享，可在线阅读，更多相关《程序设计类课程实验报告（24页珍藏版）》请在装配图网上搜索。

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

2、法，理解静态检索树的折半检索方法。3) 熟练掌握二叉排序树的构造和检索方法。4) 熟悉各种存储结构的特征以及如何应用树结构解决具体问题。二、实验内容和原理实验内容：1) 编程实现在二叉检索树中删除一个结点的算法。2) 编程实现Fib on acci检索算法。实验原理：1)构造排序树，每输入一个数就进行排序，选择插入的结点，删除结点，没删除一个节点就返回到构造排序树的方法。2) Fib on acci 数的定义为 f0=0,f1=1,fi=f(i-1)+f(i-2)(i 2)。由此得 Fibo nacci 数列为 0, 1, 1, 2,3, 5，8，13, 21，34, 55, 89, 144,

3、设数组F中元素按关键字值从小到大顺序排列，并假定元素个数n比某个Fibonacci树fi小1,即n=fi-1。第一次用待查关键字k与Ff (i-1) , Key比较，其算法描述 如下： 若k=Ff(i-1),Key，则检索成功，Ff(i-1)为k所在记录。 若kFf(i-1),Key，则下一次的检索范围为下标f(i+1)+1到fi-1，序列长度为(fi-1)-(f(i-1)+1) +1=fi-f(i-1)-1= f(i-2)-1设F是顺序存储的线性表且满足F1, keydata=data;no de-lchild=0;no de-rchild=0;if(root=0)root=no de;re

4、turn;elsep=root;while(p!=0) if(datadata)q=p； p=p-lchild;if(p=0)q-lchild=no de;elseif(datap-data)q=p；p=p-rchild;if(p=0) q-rchild=node;elsebreak;void showtreeStruct BTnode *proot,struct BTnode *m,int space) int i;char b;if(proot!=0)for(i=1;i=0)printf(-);if(proot=root)printf(%dn ,proot-data);elseif(m-d

5、ataproot-data)b=L;elseb=R;prin tf(%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-rchild; free(t); return(p);if(p-lchild!

6、=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(t); return(p);if(p-rchild!=O) q-lchild=p-rchild; elseq-lchild=O;p-rchild=t-rchild;p-lchild=t-lchild;free(t);ret

7、urn(p);elsefree(p);return(O);Nodep deleteBT no dei(nt x)Node *p=root,*q;while(p!=0)q=p;if(p-datax) if(p-lchild) p=p-lchild;elsebreak;elseif(p-datarchild) p=p-rchild;else break if(p-data=x) break;if(p=root)&( p-data=x)root=deletep(p);else if(p=q-lchild )&( p-data=x)q-lchild=deletep(p);elseif(p=q-rchi

8、ld )&( p-data=x) q-rchild=deletep(p);else if(p-data!=x)printf( can not found the data you want to delete,please check itnreturn 0;return root;int mai n()char ch;int data;prin tf(E nter c create tree,E nter d delete a no dg：sca nf%c,&ch);getchar();root=0;while(ch=c|ch= d)if(ch= c)pri ntf( please in p

9、ut the key)sca nf%d，&data);getchar();createtree(data);showtree(root,0,0);elsepri ntf( please in put the key of the node you want de；： sca nf%d，&data);getchar();if(deleteBT node(data)showtree(root,0,0);prin tf(E nter c create tree,E nter d delete a no d$:sca nf%c,&ch);return 0;实验习题二：#include stdio.ht

10、ypedefi nt keytype;typedefi nt datatype;typedefstruct nodeint key;rectype;int fibon acci( nt n)if(n=0) retur n 0;elseif(n=1) retur n 1;elsereturn fibon acci(n-1)+fib on acc i(n-2); void printData(rectype Rnt n)int i;for(i=1; i=n; i+)prin tf(%5d,Ri.key);if(i%8=0) printf(n ); printf(n);int fibsearch(r

11、ectype R,keytype Kt n)int m,i,p,q,t;for(m=0;fib on acci(m) =0 & i=n)if(K = Ri.key) return i; elseif(K Ri.key)i=i+q；p=p-q;q=q-p;return 0;void mai n()int m,i,k ,n;rectype R20;prin tf(E nter k nu m:);sea nf%d,&k);printf(enter R20:);for(i=1;i-1启动时间炖 Z011W9 W：22：341. ill 11 al i h eRiii. 13S t 玄七殂5lL1正在创

12、建“ hbu訥数据结构试验，uii5Uucwn=fulbQi=d r因为己指i AlTasCreate *。；応9叩订电；藪据结枸试验.CPT_1|= Au.srsEpJesklflpigg构数振结构试验燼竝居结构试验.cpp(lT)： trror C2O39: key:不是“n屛严的咸员 亡：血空小hplhM炽数据结构试疏數据结槪it矗燉据结构试验嗨:参见rwW的声明 山讥振鼻5燉据结构i魂谢据结构燼撫结构试验u : userslkp desktop I教据第轲试必1藪魯结松说验h数据结构1式!唸一 .9*八如1矗士七0讥数据结构试验I数揺结构试瞪I数拥结构试验.cpp)：c us4r5hj

13、deskt*pl结枸试噓数据结枸诫猛*数据结构iit釜cppG)蚤见noh”的声明11LLrLc : iiser e.upp (29) : error C2O39 ： 叫即”:不是 %皿的咸员cpp ：蚩见的声明error C2O39 : s(Leyv :不是s Ausir5hpdiEktpl结构i瞬哦据结构试瞌報 1曙菇枸iit验 upp (36) ： *rror C2O39： fi(key；不是ndas,的成闵 L1 c: ViierehpdcsktcpYft据结构i谖數擄结构试瞪邇!摒结构试验上PP (期) ferror C2O39. fiLc :应酊 hpdeEkt &p谶据踣枸鼠验

14、埶据结构i it验燉据结构i瓏-ctp(5):垦见w no de71的声明c： VuserEjkpdeEktop燉捐踣构泣蛤數据结构试強斶I据结构试验5W 蜃久ru(U的声明L1时间 00:00:01,69=fi&jh 0牛9牛防1竹晟肅D金，跳讨u个=:在创建结构体时未定义key.六、实验结果1)成功实现删除二叉检索树上删除结点的算法成功创建二叉检索树：删除结点成功：删除结点失败：2)在Fib on acci数列没有找到关键字的情况:在Fib on acci数列找到关键字的情况：七、总结1）掌握了二叉排序树的构造和检索方法。2）删除二叉检索树的结点时，必须保证删除后的二叉树仍是一棵二叉检索树根 右子树3）二叉检索树很方便查找数据，因为它的排列是有一定顺序的，即左子树4）除此之外，还进一步了解了其他的检索方法。