数据结构实验_1.pdf

《数据结构实验_1.pdf》由会员分享，可在线阅读，更多相关《数据结构实验_1.pdf（14页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、精品文档 1欢迎下载 数据结构实验报告 、实验目的及要求 1进一步掌握指针变量、动态变量的含义。2、掌握二叉树的结构特征，以及各种存储结构的特点及适用范围 3、掌握用指针类型描述、访问和处理二叉树的运算。4、掌握用二叉树前序、中序、后序、层次遍历的方法。、实验设备(环境)及要求 微型计算机；wi ndows操作系统；Microsoft Visual Studio 6.0 三、实验内容与步骤 2.根据 P129 的方法，将 a*b-(c+d*e/f)+g)转化为表达式二叉树(绘图)，并写出表达式学 号 姓 名 专业、班 实验地点 指导教师 实验时间 实验序号：6 实验项目名称：树和二叉树的操作

2、集成开发环境。1.根据下图中的树回答问题-。列出所有的叶子结点；K,L,F,M,H,I,J 列出 G 结点的双亲；B 列出 E 结点的孩子；K 丄 列出 I 结点所有的堂兄弟；E,F,G,H 列出 B 结点所有的子孙；E,F,G,K,L,M 结点 E 的度是多少；2 树的度是多少；3 结点 E 的层次是多少；3 树的深度是多少；4 精品文档 2欢迎下载 二叉树的前序、中序和后序遍历顺序。先序：-*ab+c/*defg 中序：a*b-c+d*e/f+g 后序：ab*cde*f/+g+-精品文档 3欢迎下载 4.链式表表示和实现二叉排序树如下:#i nclude#in elude typedef

3、int TEIemType;typedef struct BiTNode TElemType data;struct BiTNode*lchild,*rchild;BiNode,*Bitree;Bitree root;/定义根结点 void in sert_data(i nt x)/*Bitree p,q,s;s=(Bitree)malloc(sizeof(BiNode);/s-data=x;/结点赋值 s-lchild=NULL;s-rchild=NULL;if(!root)root=s;else p=root;while(p)/*q=p;if(p-data=x)II 相同结点不能重复插入

4、prin tf(data already exist!n);return;else if(xdata)p=p-lchild;else p=p-rchild;if(xdata)q-lchild=s;else 生成二叉排序树*/创建结点 如何接入二叉排序树的适当位置*/精品文档 4欢迎下载 q-rchild=s;printf(”请输入数据，-9999 表示输入结束n);do prin tf(please in put data%d:,i);i+;scanf(%d,&x);/*从键盘采集数据，以-9999 表示输入结束*/if(x=-9999)prin tf(nNow output data val

5、ue:n);else in sert_data(x);/*调用插入数据元素的函数*/while(x!=-9999);改写以上程序，实现功能如下(任选三题)：1)编写函数实现前序、中序和后序遍历。请输人数据叨阳表示输入结束 piease ini)ut data 1：5 please inrut 2：丄 please ini)ut data 3-3 please input data 4 piease invut data 5:?please input please input data 7 data already exist!Nou output;dlatA value*DLR=513-17

6、68 LDR：134SC78 1：49168*?5 Press any key 七u cant;lr)uc 2).编写函数实现计算叶节点个数 void main()/*int i=1,x;/i root=NULL;先生成二叉排序树*/记录结点个数，x 存放结点值/*千万别忘了赋初值给 root!*/piease input jpinput:idaA a lread piea?e input data 8:&9 data lC：-9999 精品文档 5欢迎下载 C:Use rssu 20D eskto pl 制雀刘牛夹 晴输入数据 表示输入结束 plfiftSR input data.1；5 p

7、lease injiut data Z；6 pie ast iniiut data 3:2 p le as e in put data 4：8 please inuut data.g please input data.&：7 p 1H dl b ini)ut d.At a 7：?in put data 8：1 please input da.ta.?：5 exist!ir)i)ut dAt a 10:4 p丄 Ease input dAta n：-?y9 Naw output data,value：叶节点个数詁 Press anj/kmy to continue 3).编写函数实现层序遍历

8、4).编写函数实现查询二叉树中的某个结点(分查到和查不到两种情况)5)编写函数实现求二叉树的深度 3 C：U&erss*j 20De&kto p诵雀文件知 青输入数据讣裘示输入结束 output data,vtlue:Press any ke y to can tin Lie input data 1：5 please input data Z：8 please input duta 3：?p lease in pu.t data 4：3 p lease d npu.t data s：2 input data&：&please input 7：4 p ledise mpiut dec 七&!7

9、 卩 lease 1 npu.dlai;st 9-1 please data IS：我 alrcfliy existt Iple-ae inpia dAt li：-9999 精品文档 6欢迎下载 6).编写函数实现中序非递归遍历(利用栈)以下题目为选做题：5.如果通讯字符a,b,c,d出现频度分别为7,5,2,4 某同学设计了如下程序，请根据程序画出对应的二叉树，计算所画出的二叉树 的带权路径长度；精品文档 7欢迎下载 if(input=c)printf(%c,c);else if(input=d)printf(%c,d);else if(input=a)printf(%c,a);else W

10、PL=7*3+5*3+4*2+2*仁46 WPL=2*3+4*3+5*2+7*1=35 根据赫夫曼树，用if-else 语句修改中的程序，写出最佳判定算法 if(input=a)精品文档 8欢迎下载 printf(%c,a);else if(input=b)printf(%c,b);else if(input=c)printf(%c,c);else printf(%c,d);四、实验结果与数据处理 详细记录程序在调试过程中出现的问题及解决方法。记录程序执行的结果(贴图)。五、分析与讨论 对上机实践结果进行分析，上机的心得体会。六、教师评语 签名：日期：成绩 附源程序清单：1、#inelude#

11、in elude typedef int TEIemType;typedef struct BiTNode TElemType data;struct BiTNode*lchild,*rchild;BiNode,*Bitree;DLR(Bitree root)if(root!=NULL)/printf(%d,root-data);/DLR(root-lchild);/DLR(root-rchild);/return(O);非空二叉树 访问 D 递归遍历左子树 递归遍历右子树 精品文档 9欢迎。下载 LDR(Bitree root)if(root!=NULL)LDR(root-lchild);p

12、rintf(%d,root-data);LDR(root-rchild);return(0);LRD(Bitree root)if(root!=NULL)LRD(root-lchild);LRD(root-rchild);printf(%d,root-data);return(0);Bitree root;/定义根结点 void insert_data(int x)/*Bitree p,q,s;s=(Bitree)malloc(sizeof(BiNode);/s-data=x;/结点赋值 s-lchild=NULL;s-rchild=NULL;if(!root)root=s;else p=ro

13、ot;while(p)/*q=p;if(p-data=x)/相同结点不能重复插入 printf(data already exist!n);return;else if(xdata)p=p-lchild;else 生成/树*/创建结点 如何接入二叉排序树的适当位置*/精品文档 10欢迎。下 p=p-rchild;if(xdata)q-lchild=s;else q-rchild=s;int i=1,x;/i 记录结点个数，x 存放结点值 root=NULL;/*千万别忘了赋初值给 root!*/printf(请输入数据,-9999 表示输入结束 n);do printf(please inpu

14、t data%d:,i);i+;scanf(%d,&x);/*从键盘采集数据，以-9999 表示输入结束*/if(x=-9999)printf(nNow output data value:n);else insert_data(x);/*调用插入数据元素的函数*/while(x!=-9999);printf(nDLR:);DLR(root);printf(nLDR:);LDR(root);printf(nLRD:);LRD(root);printf(n);2、#include#include typedef int TElemType;typedef struct BiTNode TElem

15、Type data;struct BiTNode*lchild,*rchild;BiNode,*Bitree;void main()/*先生成二叉排序树*/精品文档 11欢。迎下载 Bitree root;/定义根结点 int CountLeaf(Bitree root)/返回指针 T 所指二叉树中所有叶子结点个数 int m,n;if(!root)return 0;if(!root-lchild&!root-rchild)return 1;else m=CountLeaf(root-lchild);n=CountLeaf(root-rchild);return(m+n);/else /Cou

16、ntLeaf void insert_data(int x)/*Bitree p,q,s;s=(Bitree)malloc(sizeof(BiNode);/s-data=x;/结点赋值 s-lchild=NULL;s-rchild=NULL;if(!root)root=s;else p=root;while(p)/*q=p;if(p-data=x)/printf(data already exist!n);return;else if(xdata)p=p-lchild;else p=p-rchild;if(xdata)q-lchild=s;else q-rchild=s;void main()

17、/*先生成二叉排序树*/int i=1,x;/i 记录结点个数，x 存放结点值 int sum;root=NULL;/*千万别忘了赋初值给 root!*/printf(请输入数据,-9999 表示输入结束 n);do 生成/树*/创建结点 如何接入二叉排序树的适当位置*/相同结点不能重复插入 精品文档 12欢。迎下载 printf(please input data%d:,i);i+;scanf(%d,&x);/*从键盘采集数据，以-9999 表示输入结束*/if(x=-9999)printf(nNow output data value:n);else insert_data(x);/*调用

18、插入数据元素的函数*/while(x!=-9999);printf(n 叶节点个数=);sum=CountLeaf(root);printf(%dn,sum);3、#include#include typedef int TElemType;typedef struct BiTNode TElemType data;struct BiTNode*lchild,*rchild;BiNode,*Bitree;Bitree root;/定义根结点 int Depth(Bitree root)/返回二叉树的深度 int depthval,depthLeft,depthRight;if(root=NUL

19、L)depthval=0;else depthLeft=Depth(root-lchild);精品文档 13欢。迎下载 int i=1,x;/i 记录结点个数，x 存放结点值depthRight=Depth(root-rchild);depthval=1+(depthLeftdepthRight?depthLeft:depthRight);return depthval;void insert_data(int x)/*生成/树*/Bitree p,q,s;s=(Bitree)malloc(sizeof(BiNode);/s-data=x;/s-lchild=NULL;s-rchild=NUL

20、L;if(!root)结点赋值 root=s;创建结点 else p=root;while(p)q=p;if(p-data=x)/*如何接入二叉排序树的适当位置*/相同结点不能重复插入 printf(data already exist!n);return;else if(xdata)p=p-lchild;else p=p-rchild;if(xdata)q-lchild=s;else q-rchild=s;void main()/*先生成二叉排序树*/精品文档 14欢。迎下载 int d;root=NULL;/*千万别忘了赋初值给 root!*/printf(请输入数据,-9999 表示输入结束 n);do printf(please input data%d:,i);i+;scanf(%d,&x);/*从键盘采集数据，以-9999 表示输入结束*/if(x=-9999)printf(nNow output data value:n);else insert_data(x);/*调用插入数据元素的函数*/while(x!=-9999);printf(n 树的深度为=);d=Depth(root);printf(%dn,d);