软件综合设计_第1页
软件综合设计_第2页
软件综合设计_第3页
软件综合设计_第4页
软件综合设计_第5页
已阅读5页,还剩40页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、AB初态初态AB出栈出栈ACCC进栈进栈下一页说明:对于指针,当插入元素时,插入后说明:对于指针,当插入元素时,插入后top加加1;删除元素后,;删除元素后,top减减1.basetop空栈空栈base = top 是栈空标志是栈空标志stacksize = 4 topAbasebasetopABABCtopbasetopbaseABCD注意:注意:因为因为 base = top 是栈空标志,所以是栈空标志,所以 top 指针只能指示真正的栈顶元素之上的数组指针只能指示真正的栈顶元素之上的数组元素的下标地址。否则造成矛盾。元素的下标地址。否则造成矛盾。栈满时的处理方法:栈满时的处理方法: 1、

2、报错。返回操作系统。、报错。返回操作系统。 2、分配更大的空间,作为栈的存储空间。将、分配更大的空间,作为栈的存储空间。将 原栈的内容移入新栈。原栈的内容移入新栈。3120# define STACK_INIT_SIZE 100;# define STACK_INCREMENT 10;IniStack(sqstack &s) s.base = ( SElemType * ) malloc(STACK_INIT_SIZE) * sizeof(SElemType); if ( !s.base) exit ( OVERFLOW ) ; s.top = s.base ; / null stac

3、k flag s.stacksize = STACK_INIT_SIZE; return OK; / initstack;012 STACK_INIT_SIZE-1s.base数组数组 s.base0, s.base1, s.baseSTACK_INIT_SIZE-1 Status push (sqstack &s,SElemType e) If (s.top - s.base = s.stacksize) s.base = ( SElem Type * ) realloc(s.base, ( s.stacksize + STACKINCREMENT) * sizeof(SElemTy

4、pe); if ( !s.base) exit ( OVERFLOW ) ; s.top = s.base + s.stacksize ; / s.stacksize += STACKINCREMENT; * s.top + = e; return OK; / push;/ 相当于:相当于: * s.top = e; s.top + 两条指令两条指令;realloc(ptr, size): 将将 ptr 指向的存区长度改变为指向的存区长度改变为 size, size 比原先大,必须进行移动,比原先大,必须进行移动,且返回指向新存区的指针。且返回指向新存区的指针。 0 1 2 97 98 99p

5、tr0 1 2 98 99 107108 109 ptr进制转换进制转换符号配对符号配对函数调用函数调用JIHGFEACXBA的第1棵子树A的第3棵子树A的第2棵子树树(逻辑上)的特点1. 有且仅有一个结点没有前驱结点,该结点为树的根结点。2. 除了根结点外,每个结点有且仅有一个直接前驱结点。3. 包括根结点在内,每个结点可以有多个后继结点。一、树的定义12345678910二、二叉树两种特殊形态的二叉树 若一棵二叉树中的结点,或者为叶结点, 或者具有两棵非空子树,并且叶结点都集中在二叉树的最下面一层.这样的二叉树为满二叉树.1. 满二叉树 若一棵二叉树中只有最下面两层的结点的度可以小于2,并

6、且最下面一层的结点(叶结点)都依次排列在该层从左至右的位置上。这样的二叉树为完全二叉树.2.完全二叉树三、二叉树的遍历操作 二叉树的遍历是指从根结点出发,按照某种次序(原则)访问二叉树中的所有结点,使得每个结点被访问一次且仅被访问一次(得到一个由该二叉树的所有结点组成的序列)二叉树遍历操作的结果?非线性结构线性化抽象操作,可以是对结点进行的各种处理,这里简化为输出结点的数据。在线性结构中,数据元素之间仅具有线性关系;在树结构中,结点之间具有层次关系;FECBAD线性结构ABCDEF树结构不同结构中逻辑关系的对比二叉树的遍历方式:DLR、LDR、LRD、DRL、RDL、RLD 如果限定先左后右,

7、则二叉树遍历方式有:前序:DLR中序:LDR后序:LRD层序遍历:按二叉树的层序编号的次序访问各结点。 考虑二叉树的组成:根结点D左子树L右子树R二叉树二叉树的几种遍历操作 1.前序遍历ABCDEFGIJ前序序列:A B D E J C F I原则: 若被遍历的二叉树非空, 则 1. 访问根结点; 2. 以前序遍历原则遍历根结点的左子树; 3. 以前序遍历原则遍历根结点的右子树.G2.中序遍历中序序列:D B J E A F I C原则: 若被遍历的二叉树非空, 则 1. 以中序遍历原则遍历根结点的左子树; 2. 访问根结点; 3. 以中序遍历原则遍历根结点的右子树.GABCDEFGIJ3.后

8、序遍历后序序列:D J E B I F G C原则: 若被遍历的二叉树非空, 则 1. 以后序遍历原则遍历根结点的左子树; 2. 以后序遍历原则遍历根结点的右子树. 3. 访问根结点;AABCDEFGIJ4.按层次遍历按层次遍历序列: A, B, C, D, E, F, G, J, IABCDEFGIJ前序遍历结果:- + a * b - c d / e f中序遍历结果:a + b * c - d - e / f后序遍历结果:a b c d - * + e f / -二叉树遍历操作练习leftdataright独立结点struct BTreeNodeElemType data;struct BTreeNode *left; struct BTreeNode *right;AGBCDFE前序遍历算法的执行轨迹2)中序遍历void Inorder(struct BTreeNode* BT)if(BT!=NULL)Inorder(BT-left); printf(%c ,BT-data);Inorder(BT-right);3)后序遍历void Postorder(struct BTreeNode* BT)if(BT!=NULL)Postorder(BT-left);Postorder(BT-right);printf(%c ,BT-data);ABCDEFG遍历序列:A

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论