程序设计类课程实验报告.docx
- 文档编号:10322633
- 上传时间:2023-05-25
- 格式:DOCX
- 页数:15
- 大小:19.65KB
程序设计类课程实验报告.docx
《程序设计类课程实验报告.docx》由会员分享,可在线阅读,更多相关《程序设计类课程实验报告.docx(15页珍藏版)》请在冰点文库上搜索。
程序设计类课程实验报告
国脉信息学院
(程序设计类课程)实验报告
课程名称:
算法与数据结构
姓名:
系:
张三
计算机科学与技术
专业:
年级:
学号:
指导教师:
李小林
职称:
副教授
2012年11月日
实验项目列表
序号
实验项目名称
成绩
指导教师
1
第七章检索及基本算法
2
3
4
5
6
7
8
9
10
11
12
福建农林大学计算机与信息学院实验报告
系:
计算机科学与技术专业:
年级:
姓名:
张三学号:
实验室号计算机号93
实验时间:
201261指导教师签字:
成绩:
实验七检索
一、实验目的和要求
1)掌握检索的不同方法,并能用高级语言实现检索算法。
2)熟练掌握顺序表和有序表的检索方法,以及静态检索树的构造方法和检索算法,理解静态检索树的折半检索方法。
3)熟练掌握二叉排序树的构造和检索方法。
4)熟悉各种存储结构的特征以及如何应用树结构解决具体问题。
二、实验内容和原理
实验内容:
1)编程实现在二叉检索树中删除一个结点的算法。
2)编程实现Fibonacci检索算法。
实验原理:
1)构造排序树,每输入一个数就进行排序,选择插入的结点,删除结点,没删除一个节点就返回到构造排序树的方法。
》2)o由此得
2)Fibonacci数的定义为fO=O,f1=1,fi二f(i-1)+f(i-2)(i
Fibonacci数列为0,1,1,2,3,5,8,13,21,34,55,89,144,
设数组F中元素按关键字值从小到大顺序排列,并假定元素个数n比某个
Fibonacci树fi小
1,即卩n二fi-1。
第一次用待查关键字k与F[f(i-1)],
Key比较,其算法描述
如下:
①若k=F[f(i-1)],Key
,贝叶佥索成功,F[f(i-1)]为k所在记录。
②若k 则下一次的检索范围为下标1到f(i-1),序列长度为 f(i-1)o ③若k>F[f(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是顺序存储的线性表且满足F[1],key key,k 是已知的关键字值,在F中检索关键字值为k的记录。 若找到返回其下标值, 否则返回0. 三、实验环境 WindowsXP系统 visualC++6.0 四、算法描述及实验步骤 实验习题一: #include"stdio.h" #include"malloc.h" structBTnode { intdata;structBTnode*lchild,*rchild; }*root; typedefstructBTnodeNode,*Nodep;voidcreatetree(intdata){ Node*node,*p,*q; node=(Nodep)malloc(sizeof(Node));node->data=data; node->lchild=0; node->rchild=0; if(root==0) { root=node;return; } else {p=root; while(p! =0) { if(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=node; } else break; } } } voidshowtree(structBTnode*proot,structBTnode*m,intspace){ inti; charb; if(proot! =0) { for(i=1;i<=space-3;i++) printf(""); if(space-3>=0) printf("---->"); if(proot==root) printf("%d\n",proot->data); else { if(m->data>proot->data) b='L'; else b='R'; printf("%d(%c)",proot->data,b); printf("\n"); } m=proot; showtree(proot->lchild,m,space+6);showtree(proot->rchild,m,space+6); } } Nodepdeletep(Node*p) { Node*q,*t; t=p; if(p->lchild! =0) { p=p->lchild; q=p; while(p->rchild! =0) { q=p; p=p->rchild; if(p==q) p->rchild=t->rchild; free(t);return(p); } if(p->lchild! =O)q->rchild=p->lchild; else q->rchild=O;p->lchild=t->lchild; p->rchild=t->rchild;free(t); return(p); } else if(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! =0)q->lchild=p->rchild;else q->lchild=0;p->rchild=t->rchild; p->lchild=t->lchild;free(t); return(p); } else { free(p); return(0); NodepdeleteBTnode(intx) { Node*p=root,*q; while(p! =0) { q=p; if(p->data>x) if(p->lchild) p=p->lchild; else break; else if(p->data if(p->rchild) 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); else if((p==q->rchild)&&(p->data==x)) q->rchild=deletep(p); else if(p->data! =x) {printf("cannotfoundthedatayouwanttodelete,pleasecheckit! \n"); return0; } returnroot; } intmain() {charch; intdata; printf("Enter'c'createtree,Enter'd'deleteanode: "); scanf("%c",&ch); getchar(); root=0; while(ch=='c'||ch=='d') {if(ch=='c') {printf("pleaseinputthekey: "); seanf("%d",&data);getchar(); createtree(data);showtree(root,0,0); } else {printf("pleaseinputthekeyofthenodeyouwantdel: "); seanf("%d",&data); getchar(); if(deleteBTnode(data)) showtree(root,0,0); } printf("Enter'c'createtree,Enter'd'deleteanode: "); seanf("%c",&ch); } return0; } 实验习题二: #include"stdio.h" typedef int keytype; typedef int datatype; typedef structnode { int key; }rectype; intfibonacci(intn) { if(n==0)return0;else if(n==1)return1; else returnfibonacci(n-1)+fibonacci(n-2);} voidprintData(rectypeR[],intn) { inti; for(i=1;i<=n;i++) { printf("%5d",R[i].key); if(i%8==0)printf("\n");} printf("\n"); } intfibsearch(rectypeR[],keytypeK,intn) { intm,i,p,q,t; for(m=0;fibonacci(m)<=(n+1);m++){} m--; i=fibonacci(m-1); p=fibonacci(m-2); q=fibonacci(m-3); while(i>=0&&i<=n) { if(K==R[i].key) { returni;} elseif(K { i=i-q; t=p; p=q; q=t-q;}elseif(K>R[i].key) {i=i+q;p=p-q;q=q-p; } } return0; } voidmain() { intm,i,k,n; rectypeR[20]; printf("Enterknum: "); scanf("%d",&k); printf("enterR[20]: "); for(i=1;i<=20;i++) { scanf("%d",&R[i].key); } printData(R,20); m=fibsearch(R,k,20); if(m==0) { printf("Notfound! \n"); } m); else printf("TheKeyhasbeenfoundatR[%d]\n"getchar(); } 五、调试过程 1) 构建二叉排序树: 删除二叉树的节点: 2) LA '—已启动生成: 项昌: 埶揺结枸试验,,裁食: DibngTirdE 1闿成倉动时间対2011/6/916: 22.34o L/'Iijitiali口s; ! ■》正在创逢叮弗口於数揭结构试验.zwucuewMHHmiU",因拘己指定AlwaysCreataM LXJ12 L>l>c: 1> L> l>c: L> L>c; 1> * L> 1>吐a cumpile: 數摇皓枸试验.=pp 3理負蚯皿业询1埶据结构诫轻埶搦结构i或验哦H絃构试验嘶〔⑴: *rrwC203Q: L,ckty": 不昱"rutW的成员 0lx比八hplhMkMiA埶据结构诫翳A加据结构试验I加攥结构试憾.比P15)卷风*f“直列的声明 血I仏血P啾据结构试瞪嵋据结构试验谶松结构试验好dC2V: errwcmg: -key": 不是f皿”的成员 匚: \u5erAhpWeSktOpm据结枸试验I数据结构试验'数攜结梅试验.cppCS): 蜃见丽旅"的芮明_ 皿ersgld■旳ktojA埶据结构试验、数据结翰试验哦拥结构试验c叩⑶);errorC^039: i-key": 不是"iw"的成员 u;也sktojA敎拥结槪睡\数松结构试矗谶攝结构试验SP㈤;転见“册朗'*]声明 \usart\lipUa5ktop\^据结构试洛遢拥结松试甕数拥结构试监注抵): 叱叶C如的;"k歹: 不是‘5"的咸员 cVusers\hpUesktcp\数苗絃构试矗'数据绪构i磁'数霭貓构试瞪■cppW.参见"tw血"俞声明 \u5ars\lip\.AesktopVS据结构试热教塘结柯试验I竅壇姑柯试热叼曲盯《rrorC20轴叫电不是%皿”的咸员 XkplJe士昂讥數据结构: 擞\數据结构i腸'救堀结构试唸,"⑸): 筆见竹磔朕待的肓明 Vile吐匸 c.Vusers 冃时间00: 00: 0109 =====牛应: fsfiiho4半时1金*尿新0金,跚Po个 在创建结构体时未定义key. 六、实验结果 1)成功实现删除二叉检索树上删除结点的算法 成功创建二叉检索树: 删除结点成功: 删除结点失败: 2) 在Fibonacci数列没有找到关键字的情况: 在Fibonacci数列找到关键字的情况: 七、总结 1)掌握了二叉排序树的构造和检索方法。 2)删除二叉检索树的结点时,必须保证删除后的二叉树仍是一棵二叉检索树。 3)二叉检索树很方便查找数据,因为它的排列是有一定顺序的,即左子树<根< 右子树。 4)除此之外,还进一步了解了其他的检索方法。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 程序设计 课程 实验 报告