C++数据结构算法演示系统设计(4)
出队 队列 入队
front rear
图6队列示意图
队列（Queue）也是有序列表（Order List），队列具有先进先出的特性（First In First Out），输入与输出在不同端。队列的流程图如图7所示。
图7 队列操作流程图
3.4 树的模块的设计
二叉树是树的一种，应用最多也最广，它的子接最多两个，故称为二叉树，与一般的树比较，二叉树可为空，与子树有顺序关系且结点度数最大为2。
在数组二叉树的实现中，树是由根茎和叶构成，顾名思义树状结构也具有这样的组成特点的结构形态；然而必须注意在数据结构中，树的生长方向是向下的，而且决定延伸的环节是由结点和线段所组成的。
电脑数据并不是真的有结构，而是我们经过程序设计来实现这一程序或步骤，使原来单纯而庞杂的数据能方便地存取及应用。数组二叉树流程图如图8所示。
图 8二叉树流程图 图9 i和i+1在同一层
按照顺序存储结构的定义，在此约定，用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素，即将完全二叉树上编号为i的结点元素存储在定义好的一文数组中下标为i-1的分量中。对于一般二叉树，则应将其每个结点与完全二叉树上的结点相对照，存储在一文数组的相应分量中，如上图9所示。二叉树的顺序存储结构如图10所示。
图10 结点i和i+1不在同一层
4.系统的实现及算法
4.1 算法描述
4.1.1线性表算法描述
（1）在顺序表中插入操作，结点的物理顺序必须和结点的逻辑顺序保持一致，因此必须将表中位置为n ，n-1，…，i上的结点，依次后移到位置n+1，n，…，i+1上，空出第i个位置，然后在该位置上插入新结点x。仅当插入位置i=n+1时，才无须移动结点，直接将X插入表的末尾，判断插入位置的正确性if(i<0|| i>length)否则移动插入元else{for(j=length;j>1;j--)elem[j]=elem[j-1];elem[i]=e;length++;}
（2）算法分析
① 问题的规模：表的长度L-＞length（设值为n）是问题的规模。
② 移动结点的次数由表长n和插入位置i决定，算法的时间主要花费在for循环中的结点后移语句上。该语句的执行次数是n-i+1。
4.1.2堆栈算法描述
（1）算法思想：只能在一端进行插入和删除。
（2）插入和删除操作算法。为能判断栈是空的还是满的，用“FULL”和“EMPTY”来显示此时栈的情况，若做插入操作需先存元素后改指针（p->data=e; p->next=top; top=p;*(p++)=e）；若做“取出”操作需先改指针后存元素（if(S.top==S.base) return ERROR;e=(--Top);e=top->data;p=top;top=top->next; free(p); return(e);），元素的个数Length=Top-Base，每点击一次，指针先减1，然后取出栈内元素。