天大数据结构_实验作业五_查找与排序

《天大数据结构_实验作业五_查找与排序》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实验作业五：查找与排序1.写出在二叉排序树中删除一个结点的算法，使删除后仍为二叉排序树。设删除结点由指针P所指，其双亲结点由指针f所指，并假设被删除结点是其双亲结点的右孩子。2.试修改起泡排序算法，在正反两个方向交替进行扫描，即第一•趟把排序码最大的对象放到序列的最后，第二趟把排序码最小的对象放到序列的最前面。如此反复进行。3.奇偶交换排序是另一种交换排序。它的第一趟对序列中的所有奇数项i扫描,第二趟对序列屮的所有偶数项i扫描。若A[i]>A[i+l],则交换它们。第三趟有对所有的奇数项，第艸趟对所有的偶数项，…，如此反复，•育到整个序列全部排好序为止。编写实习报告要求：一、需

2、求分析二、概要设计1•抽象数据类型2.算法三、详细设计程序代码(注释)四、调试分析调试过程小所做的工作，时间复杂度等五、测试结果输入数据和输出数据示例六、说明(如果有)编程语言：C语言或C++语言实习报告提交方式：下次上机前，将实习报告(.doc)和源程序(.cpp)压缩成一•个rar文件，文件名称为学号_班级—姓名—第几次作业。例如：3010216155_六班_张三—第五次作业实习报告作为本课程的平时成绩。抄袭、雷同，双方均为0分。第一题:需求分析题目需要建立一个二叉排序树，之后输入节点数据，根据内容查找得到节点，然后对此节点进行删除操作。二、概要设计1.抽象数据类型typc

3、defstructNode{intdata;structNode*lcft;structNode*right;Node(intval){left=right=NULL,data=val;}}Node;2.算法(1).创建一个二叉排序树。voidlnsertTree(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->d

4、atadata){p=p->left;}elseif(e~>data>p->data){p=p->right;}else{deletee;return;}if(e->datadata)pre->left=e;}}}(1).删除某个右节点。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«H未找到该节点！”vvendl;retur

5、n;}elseif(pf->right!=p){cout«H该节点不是双亲的右节点，无法删除！”vvendl;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;delete

6、s;}}(1)冲序遍历。voidMidOrder(Node*root){if(root!=NULL){MidOrder(root->left);cout<data<right);)}三、详细设计intmain(){Node*root=NULL;intxlf1000],nl,al,n;cout«H请输入数组的长度(最大长度限制1000)：”；cin»nl;cout«"请输入数组的数据：”；for(al=0;al

7、al

8、;}〃建立一个数组，保存需要建立成二叉排序树的数据for(inti=0;i

9、l;i++){InsertTree(&root,xl[i]);〃调用创建二叉排序树的函数}coutvv”中序遍历:MidOrder(root);〃中序遍历创建的二叉树cout«"根节点为："«root->data«endl;cout«H请输入需要删除的节点数据，以结束符结束：n«endl;while(cin»n){〃删除右节点的操作if(root->data==n){coutvv”需要删除的为根节点,不合规范!"«endl;else{Delete_right(n,root);coutvv”中