天大数据结构实验作业五查找与排序.docx
- 文档编号:16960010
- 上传时间:2023-07-20
- 格式:DOCX
- 页数:14
- 大小:77.26KB
天大数据结构实验作业五查找与排序.docx
《天大数据结构实验作业五查找与排序.docx》由会员分享,可在线阅读,更多相关《天大数据结构实验作业五查找与排序.docx(14页珍藏版)》请在冰点文库上搜索。
天大数据结构实验作业五查找与排序
实验作业五:
查找与排序
1.写出在二叉排序树中删除一个结点的算法,使删除后仍为二叉排序树。
设删除结点由指针p所指,其双亲结点由指针f所指,并假设被删除结点是其双亲结点的右孩子。
2.试修改起泡排序算法,在正反两个方向交替进行扫描,即第一趟把排序码最大的对象放到序列的最后,第二趟把排序码最小的对象放到序列的最前面。
如此反复进行。
3.奇偶交换排序是另一种交换排序。
它的第一趟对序列中的所有奇数项i扫描,第二趟对序列中的所有偶数项i扫描。
若A[i]>A[i+1],则交换它们。
第三趟有对所有的奇数项,第四趟对所有的偶数项,…,如此反复,直到整个序列全部排好序为止。
编写实习报告要求:
一、需求分析
二、概要设计
1.抽象数据类型
2.算法
三、详细设计
程序代码(注释)
四、调试分析
调试过程中所做的工作,时间复杂度等
五、测试结果
输入数据和输出数据示例
六、说明(如果有)
编程语言:
C语言或C++语言
实习报告提交方式:
下次上机前,将实习报告(.doc)和源程序(.cpp)压缩成一个rar文件,文件名称为学号_班级_姓名_第几次作业。
例如:
_六班_张三_第五次作业.rar。
实习报告作为本课程的平时成绩。
抄袭、雷同,双方均为0分。
第一题:
需求分析
题目需要建立一个二叉排序树,之后输入节点数据,根据内容查找得到节点,然后对此节点进行删除操作。
二、概要设计
1.抽象数据类型
typedefstructNode{
intdata;
structNode*left;
structNode*right;
Node(intval){left=right=NULL,data=val;}
}Node;
2.算法
(1).创建一个二叉排序树。
voidInsertTree(Node**root,intval)
{
if(root==NULL)return;
Node*e=newNode(val);
if(e==NULL)return;
if(*root==NULL){
*root=e;
}
else{
Node*p=*root,*pre=NULL;
while(p!
=NULL){
pre=p;
if(e->data
p=p->left;
}
elseif(e->data>p->data){
p=p->right;
}
else{
deletee;
return;
}
}
if(e->data
pre->left=e;
else{
pre->right=e;
}
}
}
(2).删除某个右节点。
voidDelete_right(intm,Node*root)
{
Node*p=root,*pf,*q,*s;
while(p!
=NULL&&p->data!
=m){
pf=p;
if(p->data>m)p=p->left;
elsep=p->right;
}
if(p==NULL){
cout<<"未找到该节点!
"< return; } elseif(pf->right! =p){ cout<<"该节点不是双亲的右节点,无法删除! "< return; } else{ if(p->left==NULL){ pf->right=p->right; return; } elseif(p->right==NULL){ pf->right=p->left; return; } else{ q=p; s=q->left; while(s->right! =NULL){ q=s; s=s->right; } p->data=s->data; if(p->left! =s)q->right=s->left; elseq->left=s->left; deletes; } } }} (3).中序遍历。 voidMidOrder(Node*root) { if(root! =NULL){ MidOrder(root->left); cout< MidOrder(root->right); } } 三、详细设计 intmain() { Node*root=NULL; intx1[1000],n1,a1,n; cout<<"请输入数组的长度(最大长度限制1000): "; cin>>n1; cout<<"请输入数组的数据: "; for(a1=0;a1 cin>>x1[a1]; }//建立一个数组,保存需要建立成二叉排序树的数据 for(inti=0;i { InsertTree(&root,x1[i]);//调用创建二叉排序树的函数 } cout<<"中序遍历: "; MidOrder(root);//中序遍历创建的二叉树 cout<<"根节点为: "< cout<<"请输入需要删除的节点数据,以结束符结束: "< while(cin>>n){//删除右节点的操作 if(root->data==n){ cout<<"需要删除的为根节点,不合规范! "< } else{ Delete_right(n,root); cout<<"中序遍历: "; MidOrder(root); cout<<"根节点为: "< } cout<<"请输入需要删除的节点数据,以结束符结束: "< } system("pause"); return0; }四、调试分析 对程序加入中序遍历、判断节点是否为根节点或者左子女,然后再进行删除。 根据visualStudio2010编译器的提醒,修正代码错误,然后输入数据进行调试。 输入数据,进行校验。 五、测试结果 示例1: 示例2: 六、说明(如果有) 第二题: 一、需求分析 程序要求改写起泡排序,需要先建立数组,保存数据内容,然后按照新的起泡排序进行编排。 二、概要设计 1.抽象数据类型 无 2.算法 (1).修改后的起泡排序。 voidBubbleSort(intv[],intn1,intn2){ inta,b; for(a=n2-1;a>=n1;a--){ if(v[n2] { b=v[n2]; v[n2]=v[a]; v[a]=b; } } n2--; for(a=n1+1;a<=n2;a++){ if(v[n1]>v[a]) { b=v[n1]; v[n1]=v[a]; v[a]=b; } } n1++; if(n1! =n2)BubbleSort(v,n1,n2); } 三、详细设计 #include usingnamespacestd; voidBubbleSort(intv[],intn1,intn2){ //修改后的起泡排序 inta,b; for(a=n2-1;a>=n1;a--){ if(v[n2] { b=v[n2]; v[n2]=v[a]; v[a]=b; } } n2--; for(a=n1+1;a<=n2;a++){ if(v[n1]>v[a]) { b=v[n1]; v[n1]=v[a]; v[a]=b; } } n1++; if(n1! =n2)BubbleSort(v,n1,n2); } intmain(){ intv[1000],n,a; cout<<"请输入数组位数(0—1000): "; cin>>n; cout<<"请依次输入数组数据: "< for(a=0;a { cin>>v[a];//用数组保存数据 } cout<<"未排序前数组数据为: "< for(a=0;a { cout< }//查看未排序的数组内容 cout< BubbleSort(v,0,n-1); cout<<"排序后数组数据为: "< for(a=0;a { cout< ////查看排序后的数组内容 } cout< system("pause"); return0; } 四、调试分析 根据visualC++6.0编译器的提醒,修正代码错误,然后输入数据进行调试。 最终校验输出结果,检查正误。 五、测试结果 第三题: 需求分析 题目需要建立建立一种新的排序方式,奇数趟对数组中的所有奇数项扫描,偶数趟对序列中的所有偶数项扫描。 若A[i]>A[i+1],则交换它们。 如此反复,最后得出排好的序列为止,最后的终止条件是进行一趟排序对比时,不在出现A[i]>A[i+1]的情况。 二、概要设计 1.抽象数据类型 无 2.算法 (1).奇偶交换排序。 intoesort(intv[],intn){ boolpr=true;//定义布尔类型的变量,判断是否终止排序。 intx,num=0; while(pr){ pr=false; for(x=1;x if(v[x]>v[x+1]) { swap(v[x],v[x+1]); pr=true; } } if(pr){ num++; pr=false; } for(x=0;x if(v[x]>v[x+1]) { swap(v[x],v[x+1]); pr=true; } } if(pr)num++; } returnnum; } 三、详细设计 intmain(){ int*v,n,sum,a; cout<<"请输入数组位数(0—1000): "; cin>>n; v=newint[n]; cout<<"请依次输入数组数据: "< for(a=0;a { cin>>v[a];//用数组保存数据 } cout<<"未排序前数组数据为: "< for(a=0;a { cout< }//查看未排序的数组内容 cout< sum=oesort(v,n);//进行奇偶交换排序,并返回排序的趟数 cout<<"排序后数组数据为: "< for(a=0;a { cout< //查看排序后的数组内容 } cout< cout<<"总共排序趟数为: "< //输出排序的总趟数 system("pause"); return0; } }四、调试分析 对程序加入查看未排序数组、排序后数组以及数组排序趟数的代码,然后根据结果,进行人工校验。 根据visualStudio2010编译器的提醒,修正代码错误,然后输入数据进行调试,最后输入数据,进行校验。 五、测试结果 示例1: 示例2: 六、说明(如果有)
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 实验 作业 查找 排序