冒泡排序网络可嵌入性质模拟系统.docx

《冒泡排序网络可嵌入性质模拟系统.docx》由会员分享，可在线阅读，更多相关《冒泡排序网络可嵌入性质模拟系统.docx（43页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、苏州大学本科生毕业设计（论文）目 录前 言1第一章系统概述21.1背景21.2意义21.3主要工作及目标31.3.1主要工作31.3.2开发目标31.4组织结构4第二章预备知识和技术介绍52.1冒泡排序图52.2系统相关技术简介62.2.1HTML62.2.2CSS72.2.3JavaScript72.2.4HTML5特性72.2.5HTML5优势7第三章需求分析83.1业务需求分析83.2用户需求分析83.2.1用例图模型83.2.2冒泡排序网络103.2.3路由103.2.4多播/广播构造113.2.5完全二叉树123.2.6圈的嵌入133.3功能需求分析143.4非功能需求分析16第四章

2、总体设计174.1系统功能模块设计174.1.1冒泡排序网络模块184.1.2路由模块184.1.3多播/广播构造模块184.1.4完全二叉树模块184.1.5圈的嵌入模块194.1.6帮助模块19第五章详细设计与实现205.1主界面设计205.2冒泡排序网络模块详细设计225.3路由模块详细设计235.4多播/广播构造模块详细设计285.5完全二叉树模块详细设计325.6圈的嵌入模块详细设计34参考文献36致 谢38摘 要随着多核技术的发展，计算机多核处理器的片内互连问题被视为系统设计的关键。这个问题吸引了越来越多的工作人员来研究互连网络的拓扑结构。人们希望通过比较这些互连网络拓扑图的相关参

3、数如直径，连通度等，找到一种更好的互连方法，以便设计出更好的计算机系统。n维冒泡排序图Bn是一种由凯莱图模型设计出来的新的网络拓扑结构。与经典的n维超立方体结构Qn相比，Bn在图的连通度和容错性等方面都有更好的表现。因为这个网络具有点对称性、可缩结构和结构简单1等特点，所以相关领域内的研究者都很重视有关冒泡排序图的各种性质的研究。本课题的主要内容是设计实现一个冒泡排序网络可嵌入性质模拟系统。本文对冒泡排序网络可嵌入性质模拟系统进行了详细的说明，首先介绍了冒泡排序网络的研究背景和意义，然后对冒泡排序网络可嵌入性质模拟系统进行总体概述，说明了该系统的主要工作以及开发目标。接下来，从功能需求分析方面

4、出发，对系统开发的相关技术如HTML、CSS以及JavaScript等进行简单的介绍，然后对该模拟系统进行总体的分析，接着进行界面设计，再进行该模拟系统的详细设计。关键词：冒泡排序网络；不交路；最短路径；HTML5AbstractWith the development of multi-core technology, the issue of on-chip interconnection of computer multi-core processors is regarded as the key to system design. This problem has attracted

5、 more and more researchers to study the topology of the interconnection network. People hope to find a better interconnection method by comparing the relevant parameters (such as diameter, connectivity, etc.) of these interconnection network topology diagrams in order to design a better computer sys

6、tem.nth bubble-sort graph Bn is a new network topology designed by the Cayley graph. Compared with classical nth hypercube Qn, Bn has better performance in graph connectivity and fault tolerance. Because this network has characteristics such as point symmetry, shrinkable structure and simple structu

7、re, researchers in related fields have paid great attention to the research on various properties of bubble-sort graphs. The main content of this task is to design and implement a simulation system about embedding characteristics of bubble-sort network.This article gives a detailed description of th

8、e simulation system about embeddable characteristics of bubble-sort network. First, the research background and significance of the bubble-sort network are introduced. Then a general overview of the simulation system about embeddable characteristics of bubble-sort network is given. The main work and

9、 development goal of the system are described. Next, from the aspect of functional requirement analysis, the relevant technology such as HTML, CSS and JavaScript are briefly introduced. Then the overall analysis of the simulation system is carried out, followed by the interface design, and then the

10、detailed design of the simulation system. Finally, test and analyze the simulation system.Keywords: Bubble-sort network; Disjoint path; Shortest path; HTML5.39前 言由开关元件按一定拓扑结构和控制方式构成的网络以实现计算机系统内部多个处理机或多个功能部件间的相互连接。在并行处理计算机系统、分布计算机系统和计算机网等由多个处理机或多个功能部件组成的各种系统中，都会遇到机间互连问题。互连必须遵循一定的拓扑结构，通过开关元件来完成，以一定的控制

11、方式实现机间通信。因此，互连网络是这些系统的重要组成部分，它对系统的性能指标有决定性的影响。互连网络具有三大要素，即结点间互连拓扑(包含连接通路)、开关元件和控制方式。在不同的系统中，开关元件所处的物理位置可能是不同的。在采用集中式结构的系统中，互连网络可以是一个独立的部件，由一组开关元件构成，位于被连接的处理机或功能部件结点之间，在一定的控制方式作用下，按照互连拓扑的要求建立结点间的各条连接通路，以实现各个结点对的相互通信。但是，在许多采用分布式结构的系统(特别是计算机网)中，开关元件可能分散地隐含在各个结点内部，从外面只能看到由结点间连接通路所代表的互连拓扑，因而互连网络并不是以一个独立部

12、件的形式出现的，这是一种对互连网络的广义理解，是随着分布式系统结构的日益流行而确立起来的。冒泡排序网络是由Cayley图所设计出来的一种重要的互连网络，这个网络由于它的点对称性、可缩结构以及结构简单而受到了许多研究者的极大关注。本课题的主要内容便是设计并且实现一个冒泡排序网络可嵌入性质模拟系统。本文主要内容及结构如下：第一章主要介绍了课题背景、课题意义、冒泡排序网络可嵌入性质模拟系统的主要工作以及目标。第二章主要介绍了课题相关的一些基本知识以及用于开发系统的技术。第三章主要进行了系统的需求分析，包括业务需求分析、用户需求分析、功能需求分析以及非功能需求分析。第四章主要介绍了系统的总体设计，有哪

13、些功能模块。第五章主要介绍了系统的详细设计，主页面设计，各个功能页面的详细设计，包括功能介绍和功能的实现。第一章系统概述本章节首先介绍了冒泡排序网络可嵌入性质模拟系统的课题背景和意义，然后介绍了本系统的主要功能以及目标，在本章节的最后介绍了本文的结构。1.1背景目前，随着如航天设备开发这些行业的高速发展，人们越来越渴望实现计算机更高的计算性能。虽然计算机处理器的性能越来越高，但是仍然无法满足现实中许许多多的实际问题的需求2。因为这些问题都非常具有挑战性，它们对计算机的运算能力要求达到了每秒百万亿次，有些甚至需要更高级别的运算能力3。多计算机系统和并行计算机是用来满足人们对运算能力日渐增长的需求

14、的一种解决方案4。互连网络可以说是并行计算机的一块重要组成部分，在人们研发高性能的的并行计算机过程中，设计出高性能的互连网络结构能够起到十分重要的作用5。一个网络的拓扑结构便是该网络中的组件之间连接的方式，设计计算机互连网络的第一个步骤便是网络的拓扑结构。人们在研究网络的拓扑结构时，往往把网络中的组件用一个个点来表示，把信道用两个点之间的线来表示，从而该网络的拓扑结构也就可以用一张图来表示，所以研究图的结构问题就相当于研究网络的拓扑结构问题。换而言之，图是网络拓扑结构的一种数学模型6。互连网络对并行计算机的性能高低影响很大。设计出性能优秀的互连网络是提高并行计算机性能的一个关键的问题。选择互连

15、网络的拓扑结构时，不仅要考虑系统的容错和性能，还要考虑系统制造时的成本。冒泡排序网络的容错和性能都十分不错，因此也被很多人研究过。1.2意义本文设计并且实现了冒泡排序网络可嵌入性质模拟系统，本系统主要是为用户演示冒泡排序网络是如何构造以及它的一些性质，让用户能够对冒泡排序网络有一定的了解与认识。本课题的意义主要有以下三点：（1） 冒泡排序网络可嵌入性质模拟系统的各个页面设计以及各项功能的实现都是全新的设计。（2） 冒泡排序网络可嵌入性质模拟系统用户界面友好。本系统可以让用户一步一步自行构造冒泡排序网络，用户也可以根据系统提示对冒泡排序网络的一些性质进行深入的了解。而且，用户可以很轻松容易地学会

16、并使用本系统，在用户使用本系统时可以充分感受到简单易用的特点。（3） 冒泡排序网络可嵌入性质模拟系统可以很容易地扩充功能。1.3主要工作及目标冒泡排序网络可嵌入性质模拟系统的主要工作内容以及系统开发目标如下：1.3.1主要工作本文主要是对冒泡排序网络可嵌入性质模拟系统的需求以及功能的实现进行详细的介绍，本系统的主要工作内容是向用户展示冒泡排序网络的一些基本性质，与用户交互，让用户能够清楚地认识了解冒泡排序网络。本课题的主要工作内容如下：（1） 首先对冒泡排序网络的定义、性质等进行充分地了解，然后从用户需求、业务需求、非功能性需求以及功能性需求这四个方面对冒泡排序网路可嵌入性质模拟系统进行需求上

17、的分析。（2） 对本系统的各个模块进行功能上的设计，本系统主要分为五个功能模块，对这五个模块进行简单扼要的功能设计。（3） 为系统进行界面设计，包括主界面的设计和各个功能页面的设计等，对划分的五个功能模块进行拓展，最后形成详细的功能模块设计。（4） 最后，测试本系统所有的功能模块，模拟用户使用本系统进行操作。1.3.2开发目标本系统努力做到通过图形化演示让用户能够认识了解并清楚地明白冒泡排序网络是什么以及它的一些基本性质等。用户只需根据系统提示进行一些简单的操作，便可以充分得了解到冒泡排序网络，不需要用户进行十分复杂的操作。此外，本系统界面设计简洁明了，各个功能模块分类清晰明了，各功能也有相应

18、的介绍，用户无需担心不会使用本系统，能够很容易就明白本系统的使用方法，因此本系统具有简单实用高效等特点。1.4组织结构本文总共分为五章，各个章节内容安排如下：第一章：系统概述。本章节主要介绍了开发本系统的背景和意义，冒泡排序网络可嵌入性质模拟系统的主要工作和本系统的开发目标，最后一个小节介绍了本文的总体结构。第二章：预备知识和技术介绍。本章节主要介绍了相关的基础知识和技术，包括冒泡排序网络的一些知识、HTML、CSS以及JavaScript技术。第三章：需求分析。本章节主要介绍了冒泡排序网络可嵌入性质模拟系统的功能需求，包括冒泡排序图模块、路由模块、多播/广播构造模块、完全二叉树模块以及帮助模

19、块等。分别从用户需求、业务需求、非功能性需求以及功能性需求四个方面对冒泡排序网络可嵌入性质模拟系统进行需求上的分析。第四章：总体设计。本章节主要介绍了本系统的功能模块的划分，分别介绍了本系统的各个功能模块的设计。第五章：详细设计与实现。本章节主要介绍了本系统的所有的页面设计，包括主界面设计以及各个功能模块页面的设计。然后介绍了本系统的各个功能以及它们的具体实现。共分为：主页面模块的详细设计、冒泡排序网络模块的详细设计、路由模块的详细设计、多播/广播构造模块的详细设计、完全二叉树模块的详细设计以及圈的嵌入模块的详细设计等系统最主要的功能模块的设计与实现。第二章预备知识和技术介绍本章节首先介绍了冒

20、泡排序图的一些基本知识，其次介绍了冒泡排序网络可嵌入性质模拟系统开发的相关技术。2.1冒泡排序图在这一个部分中，主要介绍了n维冒泡排序图的定义。首先，我们介绍一下用于定义冒泡排序图的置换运算。定义 1 （置换运算）设序列 a = (a1, a2, , an )，1, 2, , n, 用以下式子定义置换运算7Xi(a) = (a1, a2, , ai1, ai+1, ai , ai+2, , an )(1 i n 1).然后，冒泡排序图就可以如下定义。定义 2 (n维冒泡排序图Bn ) Bn 是一个有n!个结点的无向图。每个结点都有一个由序列(a1, a2, , an ) ，1, 2, , n所

21、组成的唯一的标签。两个结点a和b是相邻的当且仅当存在Xi使得Xi (a) = b8。(c)(b)(a)图1. 冒泡排序图(a)B2, (b)B3和(c)B4.图1中展示了二维、三维以及四维冒泡排序图，分别是(a),(b),(c)。n维气泡排序图的结点数、度数和直径分别为n！、n-1和n(n-1)/29。表 2.1. 冒泡排序图和其他图的比较10图度数节点数直径无向对称递归Bnn - 1n!是是是Tn,k4kn是是否CCCn3n2n是是否Qnn2nn是是是Pnn - 1n!是是是Snn - 1n!是是是Rnn - 1n! n - 1否是是dBn,knnkk是否否Kn,knnk+nk-1k是否否表

22、1展示了Bn和其它图的比较。在表中，Tn,k , CCCn , Qn , Pn , Sn , Rn , dBn,k 和Kn,k分别代表了k维n维环面，一个n维立方体连接的循环图，一个n维超立方体图、一个n维饼图、一个n维星图、一个n维旋转图、(n，k)-德布鲁因图和(n，k)-考茨图11。在这些图中，只有冒泡排序图，超立方体，饼图和星图满足无向、对称和递归属性，而其他图，也就是圆环面，立方体连接的循环图，旋转图，德布鲁因图和考茨图不满足其中的一些属性。这些属性有些时候对于实现算法很重要。2.2系统相关技术简介本系统主要采用HTML5技术进行开发，HTML5主要由HTML、CSS和JavaScr

23、ipt三个部分组成12。2.2.1HTMLHTML的中文名称为超文本标记语言。“超文本”的意思就是在页面内可以有非文字元素，例如音乐以及图片等。HTML主要由Head以及 Body组成，Head部分主要是页面的一些信息，Body部分则主要是页面里面的内容13。2.2.2CSSCSS的中文名称为层叠样式表。它主要用来控制HTML页面内容格式。CSS除了可以定义静态的网页格式之外，还可以与其他脚本语言一起定义动态的网页格式14。CSS 能够精确地控制整个页面内所有元素的排版以及格式，也能够显示目前几乎所有的字体。2.2.3JavaScript JavaScript的中文名称为爪哇脚本，其设计者是B

24、rendan Eich。JavaScript一开始用于HTML，主要目的是让HTML页面从静态变为动态15。2.2.4HTML5特性HTML5有许多特点。使用HTML5技术开发的网页应用程序软件的启动时间将会更短，联网的速度也将加快，这是因为HTML5 具有本地存储功能16；使用HTML5技术可以让网页内部的数据与外部设备相连17；HTML5中具有3D功能，所以网页中所能呈现出的视觉效果会令人感到惊讶18；HTML5是开源的，简单易学19。2.2.5HTML5优势使用HTML5技术开发的网页应用程序软件可以让用户的体验更加友好，有着较高的可用性20。HTML5的网页视觉效果十分出色，完全能够代

25、替FLASH21。许多游戏以及应用程序软件都使用HTML5作为开发技术22。第三章需求分析本章节详细介绍了冒泡排序网络可嵌入模拟系统的功能需求，依次介绍了业务需求分析、用户需求分析、功能性需求分析以及非功能性需求分析。 3.1业务需求分析业务需求分析主要是指开发系统的原因。通过对冒泡排序网络的分析，可以归纳出冒泡排序网络可嵌入性质模拟系统的业务需求如下：（1） 用户可以观看冒泡排序网络低维到高维的构造过程；（2） 用户可以通过输入起始节点和目的节点得到两个节点之间的最短路径以及不相交路径；（3） 用户可以通过输入根节点然后广度优先遍历整个冒泡排序图；（4） 用户可以看到完全二叉树的展示，并在冒

26、泡排序图中展示完全二叉树的嵌入；（5） 用户可以通过输入根节点得到不同长度的圈。（6） 用户可以通过本系统认识到冒泡排序系统并学习到它的一些性质。3.2用户需求分析用户需求是指用户通过本系统所想要完成的任务。本文主要通过用例来介绍本系统的用户需求。用例模型包括用例描述和用例图。下面先对冒泡排序网络可嵌入性质模拟系统建立用例模型，然后通过用例规约来介绍其中的几个关键用例。3.2.1用例图模型针对本系统的用户需求，设计出用例图的模型，如图3.1所示。最后，本系统简要地介绍冒泡排序网络、路由、多播/广播构造、完全二叉树、圈的嵌入等用例。图3.1 系统用例图在冒泡排序网络用例中主要是进行网络结构构造。

27、在路由用例中有最短路由和不交路构造两个用例。多播/广播构造用例包含深度优先多播、广度优先多播以及广度优先广播三个用例。完全二叉树用例包含完全二叉树展示和嵌入展示两个用例。圈的嵌入用例中主要展示每个节点所能构造的路径长度小于等于6的圈。最后，帮助用例中有功能介绍用例。下面对冒泡排序网络、路由、多播/广播构造、完全二叉树、圈的嵌入等用例进行详细的介绍。3.2.2冒泡排序网络冒泡排序网络用例是本系统中的基础部分。通过该用例，用户可以观察冒泡排序网络从低维到高维的逐步构造过程。冒泡排序网络用例的用例规约如表3.1所示。表3.1 冒泡排序网络用例规约用例名称冒泡排序网络用例描述冒泡排序网络从一维到四维的

28、逐步构造过程参与者用户前置条件（1） 进入冒泡排序网络可嵌入性质模拟系统（2） 点击按钮进入冒泡排序网络页面（3） 点击下一步按钮后置条件（1） 一维演变到四维冒泡排序图基本操作流程（1） 用户进入本系统（2） 用户选择冒泡排序网络功能（3） 用户逐次点击“下一步”按钮补充说明无用户进入冒泡排序网络可嵌入性质模拟系统，点击冒泡排序网络按钮进入功能页面，然后按照系统提示逐次点击“下一步”按钮进行冒泡排序网络一维到四维的构造过程。3.2.3路由路由用例是本系统中的重要部分。通过该用例，用户可以了解到冒泡排序网络中任意两个节点之间的最短路径以及不相交路径。路由用例的用例规约如表3.2所示。用户进入冒

29、泡排序网络可嵌入性质模拟系统，选择路由功能，其分为两个子功能，分别为最短路由和不交路构造。选择最短路由，进入功能页面，输入起始节点和目的节点，点击构造按钮，则冒泡排序网络中会以不同颜色显示最短路由，如最短路由数量超过四条，则为了显示清楚，会以文字形式显示在图下方。选择不交路构造，进入功能页面，输入起始节点和目的节点，逐次点击构造按钮，则冒泡排序网络中会以不同颜色显示不相交路径，由于本系统中的冒泡排序网络为四维，所以任意两个节点间有三条不相交路径，用户每点击一次构造按钮，图中就会显示出一条不相交路径，当用户第四次点击构造按钮时，清空图中所有不相交路径。表3.2 路由用例规约用例名称路由用例描述构

30、造任意两个节点之间的最短路由以及不相交路径参与者用户前置条件（1） 进入冒泡排序网络可嵌入性质模拟系统（2） 点击按钮进入最短路由和不交路构造页面（3） 输入起始节点和目的节点（4） 点击构造按钮后置条件（1） 在冒泡排序图中以不同颜色显示最短路由（2） 最短路由数超过四条时，以文字形式显示在图下方（3） 在冒泡排序图中以不同颜色显示不相交路径基本操作流程（1） 用户进入本系统（2） 用户选择路由功能（3） 用户选择最短路由功能（4） 用户选择不交路构造功能（5） 用户输入起始节点和目的节点（6） 用户点击构造按钮补充说明无3.2.4多播/广播构造多播/广播构造用例是本系统中的第三部分。通过该

31、用例，用户可以看到冒泡排序网络中以任意一个节点为根节点进行广度优先遍历。多播/广播构造用例的用例规约如表3.3所示。用户进入系统后选择多播/广播构造功能，选择深度优先多播功能，系统会跳到深度优先多播功能页面，然后逐次点击下一步按钮，进行完全二叉树的深度优先遍历；用户选择广度优先多播功能，进入广度优先多播页面，然后逐次点击下一步按钮，进行完全二叉树的广度优先遍历；用户还可以选择广度优先广播功能，进入广度优先广播页面，页面中有一个四维冒泡排序图，用户输入任意一个根节点，然后逐次点击构造按钮，进行以该节点为根节点的广度优先遍历。表3.3 多播/广播构造用例规约用例名称多播/广播构造用例描述以图中任意

32、一节点为根节点进行遍历参与者用户前置条件进入冒泡排序网络可嵌入性质模拟系统点击按钮进入相应功能页面输入根节点逐次点击构造按钮后置条件以不同颜色逐层显示路径基本操作流程（1） 用户进入系统（2） 用户选择多播/广播构造功能（3） 用户选择深度优先多播功能（4） 用户选择广度优先多播功能（5） 用户选择广度优先广播功能（6） 用户输入根节点（7） 用户逐次点击构造按钮补充说明无3.2.5完全二叉树完全二叉树用例是本系统中的第四部分。通过该用例，用户可以了解到如何在冒泡排序网络中嵌入完全二叉树。完全二叉树的用例规约如表3.4所示。用户进入系统选择完全二叉树功能，然后选择完全二叉树展示功能，系统会进入

33、完全二叉树展示页面，用户逐次点击下一步，系统会逐条路径显示出完全二叉树。用户还可以选择嵌入展示功能，系统会进入嵌入展示页面，用户点击嵌入按钮，系统会在冒泡排序网络中以不同颜色显示出完全二叉树。表3.4 完全二叉树用例规约用例名称完全二叉树用例描述展示完全二叉树，在冒泡排序网络中显示完全二叉树参与者用户前置条件进入冒泡排序网络可嵌入性质模拟系统点击按钮进入相应功能界面点击下一步按钮点击嵌入按钮后置条件逐条路径显示完全二叉树以不同颜色在冒泡排序图中显示完全二叉树基本操作流程（1） 用户进入系统（2） 用户选择完全二叉树功能（3） 用户选择完全二叉树展示功能（4） 用户逐次点击下一步按钮（5） 用户

34、选择嵌入展示功能（6） 用户点击嵌入按钮补充说明无3.2.6圈的嵌入圈的嵌入用例是本系统中的第五部分。通过该用例，用户可以查看以冒泡排序网络中任意一个节点为起始节点和目的节点所能构造的路径长度小于等于6的圈。补考成绩录入用例的用例规约如表3.5所示。表3.5 圈的嵌入用例规约用例名称圈的嵌入用例描述展示以冒泡排序网络中任意一个节点为起始节点和目的节点所能构造的路径长度小于等于6的圈参与者用户前置条件（1） 进入冒泡排序网络可嵌入性质模拟系统（2） 点击按钮进入圈的嵌入功能页面（3） 输入根节点（4） 逐次点击构造按钮后置条件以不同颜色逐次显示路径数从小到大的圈基本操作流程（1） 用户进入系统（

35、2） 用户选择圈的嵌入功能（3） 用户输入根节点（4） 用户逐次点击构造按钮补充说明无用户进入系统选择圈的嵌入功能，系统会进入圈的嵌入功能页面，用户输入一个根节点，然后逐次点击构造按钮，系统会在冒泡排序网络中以不同颜色逐次显示以该节点为起始节点和目的节点所能构造的路径数目从小到大且长度小于等于6的圈。3.3功能需求分析功能需求表示本系统中所要实现的功能，本小节主要介绍本系统的功能模块的一些功能，如表3.6所示。表3.6 系统基础功能表 冒泡排序网络可嵌入性质模拟系统功能项功能描述冒泡排序网络用户可以查看一维到四维冒泡排序网络的构造过程。最短路由用户可以输入起始节点和目的节点，点击构造按钮，查看

36、两个节点之间的最短路径，若有多条最短路径，则以不同颜色显示，若最短路径数目大于4，则为了显示清楚，以文字形式显示在图的下方。不交路构造用户可以输入起始节点和目的节点，逐次点击构造按钮，依次查看四维冒泡排序图中两个节点之间的不相交路径，不同的路径以不同的颜色显示。所有不相交路径显示完后，再次点击构造按钮，系统会清空所有的不相交路径。深度优先多播用户可以对完全二叉树进行深度优先遍历。广度优先多播用户可以对完全二叉树进行广度优先遍历。广度优先广播用户可以输入一个根节点，然后逐次点击构造按钮，从而对整个冒泡排序网络进行广度优先遍历，不同层的路径以不同颜色显示。完全二叉树展示用户可以点击下一步按钮，查看

37、整个完全二叉树。嵌入展示用户可以点击嵌入按钮，系统会在冒泡排序网络中显示整个完全二叉树。圈的嵌入用户可以输入一个根节点，然后逐次点击构造按钮，查看以该节点为起始节点和目的节点所能构造的路径数从小到大的长度小于等于6的圈，不同的圈以不同颜色显示在冒泡排序网络中，当所有的圈在图中显示完毕后，再次点击构造按钮，会清空冒泡排序网络中所有的圈。功能介绍用户可以查看相关功能模块的详细介绍。3.4非功能需求分析非功能性需求是指系统除了功能需求以外的特性需求。非功能性需求主要有可靠性需求、性能需求、可复用性需求以及界面友好性需求等方面。下面对本系统的非功能性需求进行简单地介绍。1、可靠性需求可靠性是一个软件系

38、统的最基本的需求。本文设计和实现的本系统运行流畅，不会运行一段时间后就突然停止响应或者出现了什么无法使用的问题，因此，本系统具有可靠性。2、性能需求性能就是指软件系统的响应速度和计算速度。很多方面都会影响到系统的性能，包括使用的编程语言、算法的设计以及业务需求等。所以，在设计和实现本系统的时候，应该尽最大努力解决这些影响系统性能的问题。本系统主要使用的是HTML5技术，因此本系统的响应速度十分迅速。3、可复用性需求因为系统开发结束以后无法保证以后系统是否会进行升级改善，用户是否会提出更多的功能需求，所以为了之后系统的可扩展性，系统设计就显得十分重要。本系统的各个功能模块都分别用单独的页面实现，

39、耦合性低，一些函数也进行了封装，可以让各个功能模块进行调用。因此，本系统具有可复用性。4、界面友好性需求本文设计和实现的系统界面简洁明了，具有用户体验性强、容易操作等特点。第四章总体设计本章节主要介绍了本系统的总体设计，具体内容包括系统的各个功能模块的设计。4.1系统功能模块设计根据本系统的功能需求分析我将本系统分为六大功能模块，分别是冒泡排序网络模块、路由模块、多播/广播构造模块、完全二叉树模块、圈的嵌入模块以及帮助模块。冒泡排序模块中用户可以查看一维到四维冒泡排序网络的构造过程。路由模块中用户可以查看冒泡排序网络中任意两个节点之间的最短路径以及不相交路径。多播/广播构造模块中用户可以看到冒

40、泡排序网络中以任意一个节点为根节点进行广度优先遍历的过程。完全二叉树模块中用户可以了解到如何在冒泡排序网络中嵌入完全二叉树。圈的嵌入模块中用户可以查看以冒泡排序网络中任意一个节点为起始节点和目的节点所能构造的圈。最后，帮助模块中用户可以查看本系统所有功能的详细介绍。具体的功能模块的划分如图4.1所示图4.1 系统功能模块划分4.1.1冒泡排序网络模块冒泡排序网络模块中用户可以点击冒泡排序网络按钮进入功能页面，然后按照系统提示逐次点击“下一步”按钮进行冒泡排序网络一维到四维的构造过程。4.1.2路由模块路由模块有最短路由和不交路构造两个功能。点击最短路由按钮进入功能页面，输入起始节点和目的节点，

41、点击构造按钮，则冒泡排序网络中会以不同颜色显示最短路由。如最短路由数量超过四条，则为了显示清楚，会以文字形式显示在图下方。点击不交路构造按钮进入功能页面，输入起始节点和目的节点，逐次点击构造按钮，则冒泡排序网络中会以不同颜色显示不相交路径。由于本系统中的冒泡排序网络为四维，所以任意两个节点间有三条不相交路径，用户每点击一次构造按钮，图中就会显示出一条不相交路径，当用户第四次点击构造按钮时，清空图中所有不相交路径。4.1.3多播/广播构造模块多播/广播构造模块有深度优先多播、广度优先多播以及广度优先广播三个功能。用户进入系统后点击深度优先多播按钮，系统会跳到深度优先多播功能页面，然后逐次点击下一

42、步按钮，进行完全二叉树的深度优先遍历；用户点击广度优先多播按钮，系统会进入广度优先多播页面，然后逐次点击下一步按钮，进行完全二叉树的广度优先遍历；用户还可以点击广度优先广播按钮，系统会进入广度优先广播页面，页面中有一个四维冒泡排序图，用户可以输入任意一个根节点，然后逐次点击构造按钮，进行以该节点为根节点的广度优先遍历。4.1.4完全二叉树模块完全二叉树模块有完全二叉树展示以及嵌入展示两个功能。用户进入系统后点击完全二叉树展示按钮，系统会进入完全二叉树展示页面，用户逐次点击下一步，系统会逐条路径显示出完全二叉树。用户还可以点击嵌入展示按钮，系统会进入嵌入展示页面，用户点击嵌入按钮，系统会在冒泡排

43、序网络中以不同颜色显示出完全二叉树。4.1.5圈的嵌入模块圈的嵌入模块中用户可以输入任意一个节点作为根节点，然后逐次点击构造按钮，系统会在冒泡排序网络中以不同颜色逐次显示以该节点为起始节点和目的节点所能构造的路径数目从小到大的长度小于等于6的圈。4.1.6帮助模块帮助模块中有功能介绍这个功能。功能介绍中有对本系统中所有功能的详细介绍，若用户有什么不明白的地方可以点击功能介绍按钮进行阅读。第五章详细设计与实现一个漂亮美观的系统页面往往要比功能复杂丰富的后台显得更加重要，每个做软件系统的人都应该考虑到用户的体验性。本章节主要介绍了各个功能模块的详细的设计，包括主界面设计以及各个功能模块界面设计。并且详细介绍了各个功能模块的设计过程，包括前台页面和功能上的实现23。5.1主界面设计主界面如图5.1所示。图5.1 主界面本系统的主页面模块主要有一个功能选择菜单，可以让用户选择进入想要了解的功能模块。当用户将鼠标放在相应的功能模块按钮上时，若有子功能，则系统会显示相应的子功能的下拉菜单。功能菜单下方显示的是冒泡排序网络的简单介绍以及定义，还有一维到四维冒泡排序网络的图形。主页面的功能菜单实现代码如下所示：主页冒泡排序网络路由最短路由不交路构造多播/广播构造深度优先多播广度优先多播广度优先广播完全二叉树完全二叉树展示嵌入展示圈的嵌入帮助