C++数据结构算法演示系统设计(3)
时间:2016-12-10 11:38 来源:毕业论文 作者:毕业论文 点击:次
3.2 线性表 此模块包括：链表模型、链表操作三个部分，分别对应表的算法演示。 在链表操作的实现中，此程序是用一组地址连续的存储单位依次存储线性表的数据元素，以此实现线性表的顺序存储结构，流程图如图2所示。 图2顺序表流程图 线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的，也可以是不连续的)。因此，为了表示每个数据元素与其直接后继数据元素之间的逻辑关系，对数据元素来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息。根据以上思想，流程图如下页图3所示。 是 否 图3链表流程图 在链表操作的实现中，此程序是链表的基本操作模型，在这种存储结构中，容易实现线性表的某些操作， 在此程序中，重点实现了链表的插入和删除。 假设要在线性表的两个数据元素a和b之间插入一个数据元素x，已知p为其链表存储结构中指向接点a的指针，如图4(a)所示。 P p (a) (b) 图4在单链表中插入结点时指针变化状况 为插入数据元素x，首先要生成一个数据域为x的结点，然后插入在单链表中。根据插入操作的逻辑定义，还需要修改结点a中的指针域，令其指向结点x，而结点x中的指针域应指向结点b，从而实现3个元素a、b和x之间逻辑关系的变化。插入后的单链表如图4(b)所示。 反之，在线性表中删除元素b时，为在单链表中实现元素a、b和c之间的逻辑关系的变化，仅需要修改结点a中的指针域即可。 3.3堆栈及队列模块的设计 此模块包括：基本堆栈、基本队列两个部分，分别对应堆栈和队列的算法演示。 3.3.1栈模块设计 栈是限定仅在表尾进行插入或删除操作的线性表。表尾称为栈顶，表头称为栈底，不含元素的空表称空栈。栈的修改是按后进先出的原则进行的，因此，栈又称为先进后出的线性表（简称FILO结构），它的特点可用图5来形象地表示。 进 出 栈顶 、、、 栈底 图5栈模块 3.3.1队列模块设计 和栈相反，队列是一种先进先出（FIFO）的线性表。它只允许在表的一端进行插入，而在另一端删除元素。在队列中，允许插入的一端本叫做队尾（rear），允许删除的一端则称为队头（front）。假设队列为Q=（a1，a2，…，an），那么，a1就是队头元素，an则是队尾元素。队列中的元素是按照a1，a2，…，an的顺序进入的，退出队列也只能按照这个次序依次退出。下图6是队列的示意图。 (责任编辑：qin) |