软件综合设计

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