2013年广东省理论数据大纲

发布时间:2021-08-04 19:32:19

1、有一个带头结点的单链表,每个结点包括两个域,一个是整型域 info,另一个是指向下 一个结点的指针域 next。假设单链表已建立,设计算法删除单链表中所有重复出现的结点, 使得 info 域相等的结点只保留一个。 #include <stdio.h> typedef char datatype; typedef struct node{ datatype data; struct node * next; } listnode; typedef listnode* linklist; /*--------------------------------------------*/ /* 删除单链表中重复的结点 */ /*--------------------------------------------*/ linklist deletelist(linklist head) { listnode *p,*s,*q; p=head->next; while(p) {s=p; q=p->next; while(q) if(q->data==p->data) {s->next=q->next;free(q); q=s->next;} else { s=q; /*找与 P 结点值相同的结点 */ q=q->next; } p=p->next; } return head; } 2、 二叉树的层次遍历序列的第一个结点是二叉树的根。实际上,层次遍历序列中的每个结 点都是 “局部根” 。 确定根后, 到二叉树的中序序列中, 查到该结点, 该结点将二叉树分为 “左 根右”三部分。若左、右子树均有,则层次序列根结点的后面应是左右子树的根;若中序序 列中只有左子树或只有右子树,则在层次序列的根结点后也只有左子树的根或右子树的根。 这样,定义一个全局变量指针 R,指向层次序列待处理元素。算法中先处理根结点,将根结 点和左右子女的信息入队列。然后,在队列不空的条件下,循环处理二叉树的结点。队列中 元素的数据结构定义如下: typedef struct { int lvl; int l,h; int f; int lr; //层次序列指针,总是指向当前“根结点”在层次序列中的位置 // 中序序列的下上界 // 层次序列中当前“根结点”的双亲结点的指针 // 1—双亲的左子树 2—双亲的右子树

}qnode; BiTree Creat(datatype in[],level[],int n) //由二叉树的层次序列 level[n]和中序序列 in[n]生成二叉树。 n 是二叉树的结点数 {if (n<1) {printf( “参数错误\n”); exit(0);} qnode s,Q[]; //Q 是元素为 qnode 类型的队列,容量足够大 init(Q); int R=0; //R 是层次序列指针,指向当前待处理的结点 BiTree p=(BiTree)malloc(sizeof(BiNode)); //生成根结点 p->data=level[0]; p->lchild=null; p->rchild=null; //填写该结点数据 for (i=0; i<n; i++) // 在中序序列中查找根结点,然后,左右子女信息入队列 if (in[i]==level[0]) break; if (i==0) //根结点无左子树,遍历序列的 1—n-1 是右子树 {p->lchild=null; s.lvl=++R; s.l=i+1; s.h=n-1; s.f=p; s.lr=2; } enqueue(Q,s);

else if (i==n-1) // 根结点无右子树,遍历序列的 1 —n-1 是左子树 {p->rchild=null; s.lvl=++R; s.l=1; s.h=i-1; s.f=p; s.lr=1; enqueue(Q,s); } else //根结点有左子树和右子树 {s.lvl=++R; s.l=0; s.h=i-1; s.f=p; s.lr=1;enqueue(Q,s);//左子树有关信息入队列 s.lvl=++R; s.l=i+1;s.h=n-1;s.f=p; s.lr=2;enqueue(Q,s);//右子树有关信息入队列 } while (!empty(Q)) //当队列不空,进行循环,构造二叉树的左右子树 { s=delqueue(Q); father=s.f; for (i=s.l; i<=s.h; i++) if (in[i]==level[s.lvl]) break; p=(bitreptr)malloc(sizeof(binode));

//申请结点空间 //填写该结点数据

p->data=level[s.lvl]; p->lchild=null; p->rchild=null; if (s.lr==1) father->lchild=p; else father->rchild=p; // 让双亲的子女指针指向该结点 if (i==s.l) {p->lchild=null; // 处理无左子女 s.lvl=++R; s.l=i+1; s.f=p; s.lr=2; enqueue(Q,s); }

else if (i==s.h) {p->rchild=null; //处理无右子女 s.lvl=++R; s.h=i-1; s.f=p; s.lr=1; enqueue(Q,s); } else{s.lvl=++R; s.h=i-1; s.f=p; s.lr=1; enqueue(Q,s);//左子树有关信息入队 列 s.lvl=++R; s.l=i+1; s.f=p; s.lr=2; enqueue(Q,s); // 右子树有关信息入队列 } }//结束 while (!empty(Q)) return(p);

}//算法结束 3、设有一组初始记录关键字为(45,80,48 ,40,22 ,78) ,要求构造一棵二叉排序树并给出 构造过程。


相关文档

  • 2013年广东省数据理论纲要
  • 2013年广东省数据基础理论大纲
  • 2013年广东省数据大纲
  • 2013年广东省基础数据大纲
  • 2013年广东省数据理论基础
  • 2013年广东省分析数据大纲
  • 2013年广东省数据整理大纲
  • 2013年广东省数据分析纲要
  • 2013年广东省数据理论深入
  • 猜你喜欢

  • 儿童启蒙故事
  • 谈心沟通师生感情的桥梁.
  • 云莫滓┛毓赏蹲视邢薰?鲸企业信用报告)- 天眼查
  • 基于总体*均经验模态分解与改进Elman神经网络的风功率组合预测
  • 公共教育收费制度改革在*代中国
  • 云南达闻商贸有限公司企业信用报告-天眼查
  • 胸外科围术期护理安全管理
  • 略论生态建筑设计及建筑设计生态化趋势
  • 2019年春一年级数学下册第2单元20以内的退位减法第12课时整理和复习(2)课堂作业(无答案)新人教版
  • 南京怡美医疗器械有限公司(企业信用报告)- 天眼查
  • 2020年浙江鸭高考历史总复*专题5古代希腊罗马的政治文明考点13罗马人的法律课件
  • 陶渊明诗歌中的人道主义精神
  • The Magic Barrel 续写
  • 冬至红领巾广播稿
  • 弥漫性肺疾病的病理诊断PPT学*课件
  • 【推荐】经济困难补助申请报告范文-word范文 (3页)
  • 越字取名男孩子的名字有哪些
  • 一件让我后悔的事_小学五六年级记事_1
  • 大二班第三周家园小报
  • 最新中考初中文言文答题技巧(精)+文言文练*题
  • 猪年生日祝福短信|学生猪年祝福短信
  • 2020年期末大学生个人总结
  • 修改作文的基本步骤(精)
  • 生 产 岗 位 职 责
  • 2007年监理工程师考试三控真题及答案
  • 黄冈市人民政府办公室关于做好2014年市直部门预算编制工作的通知
  • 小学语文教学中如何适时使用电教媒体
  • 我国房地产金融风险成因及防范
  • 我的高效编程秘诀
  • opencv3.1.0 + opencv_contrib用CMake编译及遇到的问题
  • 小学教室及功能室窗帘采购项目招投标书范本
  • 本科财务管理专业论文
  • 粤教高中必修3《书愤》张爱斌教案PPT课件 一等奖新名师优质课教学设计
  • 是什么让胎记长在你脸上
  • 江宁县宁菸商店丹阳镇分店企业信息报告-天眼查
  • 图形创意第一节
  • 冬天的雪小学作文500字
  • 中国邮政储蓄银行股份有限公司喀什市团结路支行企业信用报告-天眼查
  • 群升太阳能热水器怎么设置
  • only引导状语从句详细用法精品讲解.ppt
  • 童年,那段美好的记忆_初中作文
  • vivos7与vivos7e的区别
  • 电脑版