Pubertyly的资源

  • 基于JAVA实现的支持多线程访问的WEB服务器

    1.系统概述1.1 业务背景web服务提供了可供浏览的网页,对浏览web服务的需求是本程序的背景,当然现在已经有很多web服务器的很好的实现,本程序也不可能说做得比知名的那些要好,在这里程序的目的是为了锻炼网络程序设计与实践和软件系统设计与开发实践能力。
    1.2 总体目标实现一个web服务器,能够提供让标准浏览器用HTTP协议来进行访问的网页,并且能够支持多线程非阻塞的服务,最后会提供一个web服务器程序。
    2.系统分析和设计2.1 系统概述2.1.1 业务需求描述
    为标准浏览器提供web服务
    能够接受http请求并返回html网页
    能够支持多线程非阻塞的访问

    2.1.2 外部接口需求
    硬件接口:无直接硬件接口,只通过OS等软件接口与硬件间接交互
    软件接口:相应的JDK、JVM环境,以及标准的浏览器软件
    通讯接口: HTTP协议

    2.1.3 非功能性需求
    Web服务器要求响应时间要短
    安全可靠

    2.1.4 约束条件开发环境

    Eclipse-Java IDE,windows7系统
    整个项目由Java开发,所以要求系统装有相应的JDK、JVM环境,另外,web服务器要求系统有http协议的接口,web客户端即为标准的浏览器软件

    开发规范

    文件命能清楚的描述其功能
    代码中的空格与空行上下保持一致
    有适量且清楚的注释
    界面整洁,方便使用
    所有函数及变量有能描述其功能的名字
    应注意代码的简洁和优化

    2.2 用例模型2.2.1 用例图
    2.2.2 详细描述


    用例名称
    Web浏览器查看网页




    描述
    用户用Web浏览器访问Web服务器的一个网页:http://localhost:6789/13S103066.html


    参与者与关注点
    Web浏览器(用户):希望得到快速的响应,能够看到正确的网页。Web服务器:希望能够快速正确地完成浏览器请求,并且能够处理多用户同时访问的场景。


    事件流
    主成功场景(或基本流程): 用户在浏览器中输入要访问的网址:http://localhost:6789/13S103066.html; web服务器解析HTTP协议请求; web服务器处理该请求并通过TCP连接向浏览器返回目标网页html文件;浏览器解析并显示该html文件;用户看到该网页;完成。 扩展(或替代流程): 传递网页的TCP连接建立失败:web服务器报错给服务器管理员,管理员检查服务器状态是否异常;Web服务器没有响应(浏览器无法连接到服务器):检查web服务器是否已经运行、网址是否输入正确。


    前置条件
    Web浏览器已运行



    2.3 领域类图2.3.1 Web(TCP)类图
    2.3.2 Web(TCP)核心顺序图
    2.4 体系结构设计
    2.5 程序流程图
    2.6 测试截图
    3.总结综上所述,程序实现了一个支持多线程访问的Web服务器。在简单规模的测试及使用下,程序运行正确且良好,在较大用户数下表现得一般,响应时间不是很好。作为一个学习网络程序设计的程序已经完成了目标。
    这次作业中,复习了很多计算机网络的相关知识的同时也学到了很多新的实践方面的知识,锻炼了编程能力,感谢老师的辛勤付出。
    1  留言 2019-05-06 11:46:04
  • 基于C++实现的每对结点之间的最短路径(Floyd-Warshall算法)

    1、实验题每对结点之间的最短路径问题(Floyd-Warshall算法):
    G = ( V, E)是一个有n 个结点的有向图。补充ALL-PATHS算法,增加前驱矩阵,使得在求出结点间的最短路径长度矩阵A后,能够推导出每对结点间的最短路径。
    2、设计思路这里要求的是有向图中每一对节点之间的最短路径,用Floyd_WallShall算法解决此问题。
    从节点v到节点u的最短路径有2种可能:直接从v到u,或者从v出发,经过一条包含若干个节点的路径,到达u。
    设D(i,j)是当前已求得的从节点u到节点v的最短路径长度,其中i、j分别为两个节点的序号。现在需要继续计算以更新最短路径。对于图中的每个点w,判断d(i,k)+d(k,j)与d(i,j)的大小关系,若前者小于后者,说明找到了一条新路径,将该值替换原来的最短路径长度。如此往复,遍历所有的节点,最终将得到一条最短的路径。
    3、运行演示运行程序,输出每对节点间的路径和路径长度。
    1  留言 2019-03-13 18:15:38
  • 基于C++实现的最优二分查找树

    1、实验题目设计算法,输入如表3-1,输出是最优二叉搜索树的结构,形如:

    k2为根
    k1为k2的左孩子
    d0为k1的左孩子
    ……

    表3-1 搜索概率表



    i
    0
    1
    2
    3
    4
    5




    pi

    0.15
    0.10
    0.05
    0.10
    0.20


    qi
    0.05
    0.10
    0.05
    0.05
    0.05
    0.10



    2、设计思路用动态规划思想求解最优二分查找树问题。
    2.1 最优子结构如果一棵最优二叉搜索树T有一棵包含关键字ki,…,kj的子树T’,则T’必然是包含关键字ki,…,kj和伪关键字di-1,…,dj的子问题的最优解。
    用剪切-粘贴法证明:
    对关键字ki,…,kj和伪关键字di-1,…,dj,如果存在子树T’’,其期望搜索代价比T’低,那么将T’从T中删除,将T’’粘贴到相应位置,则可以得到一棵比T期望搜索代价更低的二叉搜索树,与T是最优的假设矛盾。
    2.2 递归解利用最优二叉搜索树的最优子结构性来构造最优二叉搜索树。
    对给定的关键字ki,…,kj,若其最优二叉搜索树的根结点是kr(i≤r≤j),则kr的左子树中包含关键字ki,…,kr-1及伪关键字di-1 ,…,dr-1,右子树中将含关键字ki+1,…,kj及伪关键字dr,…,dj。
    检查所有可能的根结点kr(i≤r≤j),如果事先分别求出含关键字ki,…,kr-1和关键字kr+1,…,kj的最优二叉搜索子树,则可保证找到原问题的最优解。
    求解包含关键字ki,…,kj的最优二叉搜索树,其中, i≥1,j≤n 且 j≥i-1。定义e[i,j]:为包含关键字ki,…,kj的最优二叉搜索树的期望搜索代价。
    e[1,n]为问题的最终解。
    当j≥i时,我们需要从ki,…,kj中选择一个根结点kr,其左子树包含关键字ki,…,kr-1且是最优二叉搜索子树,其右子树包含关键字kr+1,…, kj且为最优二叉搜索子树。
    子树的每个结点的深度增加1,根据二叉搜索树的期望搜索代价计算公式,这棵子树对根为kr的树的期望搜索代价的贡献是其期望搜索代价+其所含所有结点的概率之和:

    若kr为包含关键字ki,…,kj的最优二叉搜索树(树根),则其期望搜索代价与左、右子树的期望搜索代价e[i,r-1]和e[r+1,j]有如下递推关系:

    其中,

    故有:

    求kr的递归公式为:

    3、运行演示测试用例已经在代码中写入,运行程序,结果如图3-1和图3-2,先输出最优二叉搜索树的结构,再输出搜索代价、根节点矩阵、e矩阵和w矩阵。
    最优二叉搜索树测试

    最优二叉搜索树测试
    1  留言 2019-03-12 21:13:14
  • 基于C++实现的大整数计算

    1、实验题目大整数(big integer):位数很多的整数,普通的计算机不能直接处理,如:9834975972130802345791023498570345。
    对大整数的算术运算,显然常规程序语言是无法直接表示的。编程实现大整数的加、减、乘运算,需考虑操作数为0、负数、任意位等各种情况。
    要求利用分治法,时间复杂度不高于O(n2)。
    2、设计思路2.1 概要设计设a和b分别为两个大整数,它们的位数过长,以致计算机中没有变量可以一次性存下来,所以要对其进行拆分。使用分治算法的思路是:
    将a表示为a = a1×10^k + a2,b表示为b = b1×10^j + b2;
    其中k是a2的位数,j是b2的位数。也就是把大整数分成了高位和低位,这样,a×b = a1×b1×10^(j+k) + a1×b2×10^k + b1×a2×10^j + a2×b2;
    两个大数相乘变成了四个较小的数相乘,四个较小的数可能仍然过大,可以继续分解,直到分解为每个数都是个位数,再进行算数运算,这个过程使用递归。
    2.2 详细设计具体计算时,需要先实现加法和减法,才能实现乘法,而且在算数运算过程中还要用到一些辅助函数。
    2.2.1 加法用字符串存放大整数,在进行运算前,先要判断两个大数的符号:
    假如都为负数,则去掉最高位的负号,用绝对值进行加法,最后在结果的最高位恢复负号;如果一正一负,则转换为减法,直接调用大数减法函数;如果两者皆为正数,则继续运算。
    加法运算过程不需要递归,将两个字符串从末端开始取字符,转换成数字后进行加法,大于9则进位,最终结果仍以字符串返回。
    2.2.2 减法与加法类似,先判断符号,两个一正一负的两个数相减时,转换成加法,调用加法函数;两个负数相减时,用绝对值相减,最后加上符号。
    2.2.3 移位在前面的分析中,高位的数乘上了一个10的幂次方,在实际运算过程中,通过在字符串末尾增加字符0的方法来实现,所以将这一功能封装为一个移位函数。
    2.2.4 对齐对于计算的两个数的位数不等的情况,在较短的数之前补零使两者等长,这一过程也用函数实现。
    2.2.5 乘法先将两个大数各自拆分成两部分,再递归调用大数乘法函数,将四个小数相乘,相乘的结果再用前面实现的大数加法加起来,得到最后的结果。递归的结束条件是,数字的尾款为0或1。
    3、运行演示在程序中给出了一组测试用例,a = 1234567890,b = 9876543210,运算结果如图2-1,分别输出两数之和、差、积。

    继续输入测试用例,a的值不变,b取原值的相反数,测试一正一负的计算,结果如图2-2,可见乘积的绝对值不变,但是多出了负号。

    再测试两个负数的计算,a = -1111222233334444, b = -5555666677778888,运算结果如图2-3,乘积为正数。

    测试0的运算,a = 0,b任意输入一个值,运算结果如图2-4,两数之和为b,差为-b,乘积为0。
    1  留言 2019-03-12 17:30:29
  • 基于C语言实现的最近点对问题

    1、实验题目最近点对问题:
    已知平面上分布着点集P中的n个点p1,p2,…pn,点i的坐标记为(xi,yi),1≤i≤n。两点之间的距离取其欧式距离,记为:

    问题:找出一对距离最近的点。
    注:允许两个点位于同一个位置,此时两点之间的距离为0。
    2、设计思路2.1 基本思路由于不要求控制算法的时间复杂度,所以采用最简单直观的暴力求解法。
    对于所有的n个点,计算任意两个点之间的距离,一边计算一边比较,遇到距离更近的点对则保存下来,这样可以在所有的距离中,选出最小的值,即为算法需要的结果。
    2.2 数据结构设计需要两个数组分别存放点的横坐标和纵坐标,数组下标代表点的序号,这里假定点的坐标都是整数,所以用int型数组。此外还需要一个浮点型变量用于计算两点间的距离,4个int型变量用于存放当前最近点对的坐标。
    2.3 时间复杂度将所有的点排成一排,从第一个点开始,依次求其后面的点与它的距离,要计算n-1次,第二个点需要计算n-2次……倒数第二个点计算1次,所以一共计算的次数为:
    1 + 2 + 3 + … + n-2 + n-1 = n(n-1)/2因此算法时间复杂度为O(n)。
    3、运行演示测试用例以数组形式存放在代码中已经写好,不用手动输入,共8个点,坐标分别为:(1,9)、(-8,-22)、(-9,16)、(101,68)、(6,13)、(233,100)、(12,-138)、(-35,591),这些点覆盖了各大象限,距离也有近有远,足够验证算法的正确性,运行结果如图1-1和图1-2。

    遍历过程中每对点的距离都进行了输出,通过距离比较可以发现距离最近的两点是(1.9)和(-9,16),距离是约为6.4。
    1  留言 2019-03-12 14:29:14
  • 基于C语言实现的线性表拆分

    介绍设有一个线性单链表,其结点值均为正整数,且按值从大到小链接。试写出一个算法,将该线性单链表分解成两个线性单链表,其中一个链表中的结点值均为奇数,而另一个链表中的结点值均为偶数,且这两个链表均按值从小到大链接。
    1 解题思路先建立一个结构体,结构体中包含数据域以及next的指针域。然后将原链表先通过冒泡排序倒置,再遍历倒置后的链表。如果数据是奇数的放入新的链表L2,如果是偶数放入新的链表L3,直到遍历完成。就成功拆分了原链表。
    2 函数调用图
    3 各函数功能// 建立线性表int createList (LNode *L);// 打印数据int print(LNode *L);// 对链表进行冒泡排序int sortList(LNode *L);// 将原线性表分开成两个线性表int splitList(LNode *L1, LNode *L2, LNode *L3);// 主函数,流程控制int main();
    4 测试




    1  留言 2019-01-19 19:39:34
  • 基于C语言实现的表达式求解

    1 解题思路构造包含顶指针,底指针和增量的结构体。然后分别构造一个只包含运算符的栈(OPTR)和只包含数字的栈(OPND)。之后依次读入所输入的表达式。判断是不是数字,如果是数字就将数字放入数字栈(OPND)。如果不是即运算符,让运算符栈栈顶元素和读入的运算符进行比较。如果优先级小于将读入的运算符入栈,优先级相等的就让栈顶元素出栈,优先级的大于的就让栈顶元素弹栈,并且连续两次让数字栈弹栈,得到一个运算符和两个数字,进行计算,得到的结果放入数字栈。循环以上过程直到读入的表达式字符为#为止。最后将数字栈出栈,即得到结果。
    2 函数调用图
    3 各函数功能// 构造空栈char InitStack (SqStack *S);// 让e入栈char Push(SqStack *S, char e);// 让e出栈char Pop(SqStack *S, char *e);// 返回栈顶第一个元素char getTop(SqStack S);// 比较两个运算符的优先级,a,b中存放待比较的运算符,'>'表示a>b,'0'表示不可能出现的比较,这是通过二维数组建立比较表实现的char Precede(char a, char b);// 判断输入的某个字符是否是运算符int in(char c, char OP[8]);// 四则运算计算char Operate(char a, char n, char b);// 表达式计算,流程控制char evaluateExpression(SqStack OPTR, SqStack OPND);// 主函数,建立OPTR与OPND栈int main();
    4 测试





    5 编译与运行情况编译正常通过。运行时如果计算中出现负数就无法运算,而且输入表达式的时候因为用的是getchar所以无法读出两位数以上的数字进行计算,这是该程序缺陷的地方。
    1  留言 2019-01-19 15:15:54
  • 基于JAVA3D的网络三维技术的设计与实现

    摘 要互联网的出现及飞速发展使IT业的各个领域发生了深刻的变化,它必然引发一些新技术的出现。3D图形技术并不是一个新话题,在图形工作站以至于PC机上早已日臻成熟,并已应用到各个领域。然而互联网的出现,却使3D图形技术发生了和正在发生着微妙而深刻的变化。Web3D协会(前身是VRML协会)最先使用Web3D术语,这一术语的出现反映了这种变化的全貌,没有人能严格定义Web3D,在这里我们把Web3D理解为:互联网上的3D图形技术,互联网代表了未来的新技术,很明显,3D图形和动画将在互联网上占有重要的地位。
    Java3D API是Sun定义的用于实现3D显示的接口。使用Java 的重要理由之一是它的平台无关性。Java3D提供了基于Java的上层接口。Java3D把OpenGL和DirectX这些底层技术包装在Java接口中。这种全新的设计使3D技术变得不再繁琐并且可以加入到J2SE、J2EE的整套架构,这些特性保证了Java3D技术强大的扩展性
    本文以Java3D为开发平台,利用Java语言强大的网络功能,实现了在网页上对3D动画进行显示和操作。
    关键字:Java3D、Web3D、三维
    第1章 系统设计1.1 总体设计设计思想是:以JAVA3D为平台,使用JBuilder编译器,生成一个三维小场景,实现简单实体建模,物体运动,场景移动,各种灯光,雾等场景变换操作以及更换背景图片增加背景音乐等三维体系的基本功能。
    1.2 基本形体的生成和VRML不同,JAVA3D没有基本形体类,因而在程序中无法直接生成大量应用的基本形体,如BOX、CONE、SPHERE等。我们可以通过复杂的编程生成这些基本形体,也可以直接调用JAVA3D为我们提供的geometry classes,利用它生成程序所需要的BOX、COLORCUBE、CONE、SPHERE、CYLINDER。下面是这些基本体的生成方法。
    1.2.1 平板的生成UTILITY里BOX的构造函数有:

    Box():成一个各边尺寸均为2的BOX,要说明的是,BOX、COLORCUBE、SPHERE的坐标原点均在其中心点,CONE、CYLINDER的则在其轴线的中点上
    Box(float xdim, float ydim, Appearance ap) :成一个给定尺寸、给定外观属性的BOX ,例Box(.5f, .6f, .4f, myApp)
    Box(float xdim, float ydim, float zdim, int primflags, Appearance ap):生成一个有特定说明的BOX,例如:Box(.4f,.6f,.3f,Primitive.ENABLE_APPEARANCE_MODIFY, ap)表示程序在运行时可以改变其外观属性

    1.2.2 立方体的生成UTILITY里COLORCUBE的构造函数有:

    ColorCube():生成一个边长均为2的COLORCUBE
    ColorCube(double scale):将边长均为2的COLORCUBE按比例放大缩小

    1.2.3 圆锥的生成UTILITY里CONE的构造函数有:

    public Cone():生成一个底半径为1,高为2的CONE。
    Cone (float radius, float height)
    Cone (float radius, float height, int primflags, Appearance ap)
    Cone(float radius, float height, int primflags, int xdivision, int ydivision, Appearance ap)

    这里,xdivision、ydivision可用来表示圆锥的显示是高精度的显示,或是底精度的显示,缺省时的中等精度时xdivision = 15; ydivision = 1; 我们可利用这两个参数来改变显示的效果,使显示圆锥的三角片更多或更少些。
    1.2.4 球体的生成UTILITY里SPHERE的构造函数有:

    Sphere():生成一个半径为1的SPHERE。
    phere (float radius)
    Sphere (float radius, Appearance ap)
    Sphere(float radius, int primflags, Appearance ap)
    Sphere(float radius, int primflags, int divisions)
    Sphere(float radius, int primflags, int divisions,Appearance ap)

    这里divisions的作用和圆锥的xdivision、ydivision相似。
    1.2.5 圆柱体的生成UTILITY里CYLINDER的构造函数有:

    Cylinder():生成一个底半径为1,高为2的CYLINDER。
    Cylinder (float radius, float height)
    Cylinder (float radius, float height, Appearance ap)
    Cylinder (float radius, float height, int primflags, Appearance ap)
    Cylinder(float radius, float height, int primflags, int xdivision, int ydivision, Appearance ap)

    1.3 点、线、面的生成1.3.1 点的生成编写JAVA3D程序实际上是编写一个特定的场景图,给出了场景图中带有形体及其属性的一个分支(BranchGroup)和表示观察位置等数据的另一个分支(View Platform)。一般来说,表示观测位置的分支可以用JAVA3D的UTILITY来完成,即createSceneGraph方法的定义。
    在这个方法里,程序先定义了一个分支objRoot,然后用数组的形式定义了顶点坐标vert和颜色color,再用PointArray定义了一组点point,并将顶点坐标及颜色赋值给point,由于JAVA3D中的PointArray点是Shape3D的子类,它不能直接放入一个BranchGroup,因而我们还要先定义一个Shape3D对象shape,再将point赋予shape,这样point就可以放入BranchGroup类型的对象objRoot中了。
    JAVA3D提供的API中,可用于生成Point的对象有: PointArray IndexedPointArray
    PointArray
    PointArray的构造函数为:

    PointArray( int vertexCount, int vertexFormat );这里,vertexCount表示应生成的点的数目,vertexFormat表示所需要的顶点的格式
    点、线、面几何体所需要的顶点的格式有:

    COORDINATES 顶点坐标数组
    NORMALS 顶点法向数组
    COLOR_3 不带alpha值的颜色数组
    COLOR_4 带alpha值的颜色数组
    TEXTURE_COORDINATE_2 二维纹理坐标数组
    TEXTURE_COORDINATE_3 三维纹理坐标数组

    IndexedPointArray
    IndexedPointArray的构造函数为:

    IndexedPointArray( int vertexCount, int vertexFormat,int indexCount );
    利用本函数,我们可以从众多的点中,选择特定的点来显示。这里,vertexCount表示顶点坐标数组所提供的点的总个数,indexCount表示最终应生成的点的个数。JAVA3D可以生成任意大小的点,并且可以使点为方点或圆点。
    1.3.2 直线的生成利用JAVA3D的一些对象,生成各种直线。可以生成直线的对象有:

    LineArray
    LineStripArray
    IndexedLineArray
    IndexedLineStripArray

    我们可以根据各种不同的情况,生成不同的直线,如给定宽度的直线、虚线等。相应的的方法有:

    setLineWidth(float lineWidth)
    setLinePattern(int linePattern)
    setLineAntialiasingEnable(boolean state)

    对于线型linePattern有以下数据可选:

    int PATTERN_SOLID,int PATTERN_DASH,int PATTERN_DOT,int PATTERN_DASH_DOT
    这些内容对所有种类的直线都有效。
    1.3.3 面的生成生成平面的对象及其定义
    JAVA3D可通过编程显示出面来,面有两种:三角形和四边形,相应的对象为Triangle和Quad。
    JAVA3D用于生成平面的对象有:

    TriangleArray
    QuadArray
    TriangleStripArray
    TriangleFanArray
    IndexedTriangleArray
    IndexedTriangleStripArray
    IndexedTriangleFanArray

    1.4 外部复杂形体的调用利用前面介绍的方法生成我们所需要的基本形体,生成点、线、平面。但有的时候,我们需要用到其它格式的三维形体,如VRML2.0格式的图形文件,AUTOCAD绘出的DWG格式的三维形体,3DS MAX绘制出的复杂形体。对于这些形体,我们可以非常方便地将其用到JAVA3D程序中去。下面我们介绍一些图形格式在JAVA3D中的应用方法。
    1.4.1 Wavefront的OBJ格式的图形文件的调用JAVA3D编译环境所带的UTILITY有两个LOADER,一个可用来调用Wavefront软件的OBJ格式的三维图形格式文件,一个可用来调用Lightwave软件的LWS及LWO格式的三维图形格式文件。
    为了使JAVA3D能够调用Wavefront的OBJ格式的图形文件,程序的头四行import语句就是用来处理Wavefront的OBJ格式的图形文件,第五行的import语句则是打开外部文件之用。
    import com.sun.j3d.loaders.objectfile.ObjectFile;import com.sun.j3d.loaders.ParsingErrorException; import com.sun.j3d.loaders.IncorrectFormatException; import com.sun.j3d.loaders.Scene; import java.io.*;
    1.4.2 VRML2.0(VRML97)图形文件在JAVA3D中的应用简介利用VRML97的LOADER我们可以在JAVA3D程序中方便地调用VRML图形。调用VRML97程序就象调用Wavefront的OBJ一样简单。
    1.4.3 AUTOCAD R14的DWG图形及3DS MAX图形在JAVA3D中的应用。在三维图形生成过程中,国内目前大量使用AUTOCAD及3DS MAX等软件。对于3DS MAX软件,处理起来非常方便3DS MAX可以将其图形直接输出成VRML97格式。对于AUTOCAD R14来说,目前还不太方便,需借助第三方软件转换成JAVA3D支持格式。
    1.5 背景变换的实现方法1.5.1 灯光光用于照亮场景中的几何对象。有几种不同的光类型,它们都是抽象 Light 类的子类。所有光都有一个颜色值,即开/关位,以及一个描述它照亮的场景区域的绑定对象。在现实世界里,周围的对象被几个不同的光源照亮。从窗户射进的阳光和屋顶的灯光一起照亮了屋内的一切。两种光都会影响屋内对象的颜色和外观。在 Java 3D 中,可以通过使用多个光源来模拟实际的光照效果。
    光的类型

    环境光:在场景中 AmbientLight 无处不在。它不发自某个特定点,也不指向某个特定方向

    方法:AmbientLight ()
    点光:Point Light 从一个指定位置向各个方向辐射,并随着距离的增加而减弱。点光源的一个例子是没有灯罩的台灯

    方法:PointLight(); void setPosition( Point3f pos )
    Spotlight PointLight的继承,是一种将光的范围限制在一个圆锥形内的点光源。聚光源的一个例子是手电筒。
    直射光:DirectionalLight 的光线射向某一个特定方向,却不发自任何特定的位置。这种定向光的所有光线都平行发射。虽然从技术上说,太阳是一个点光源,但使用 DirectionalLight 可以更准确地模拟太阳光


    所有的 Light 节点都是场景图中的叶节点。创建它们时,需要指定 Bounds 对象;我们使用BoundingSphere。光将仅仅影响那些位于光的 BoundingSphere 所定义的空间内的几何对象,因此我们需要确保 BoundingSphere 足够大。在创建完光之后,我们用Scene1.addChild( Node );将其附加到场景图的顶部 BranchGroup。光、行为和材质都在场景图的上面添加。
    1.5.2 纹理贴图装入纹理 同光照一样,纹理贴图影响整个几何对象。再一次使用 Appearance 类来指定纹理贴图效果。
    Java 3D 简化了装入纹理图像的过程。TextureLoader类位于 Java3D 实用类中。为了看起来更真实,请总是将纹理图像的宽度和高度设置成 2 的幂。其它的值会导致 TextureLoader 将纹理压变形。
    Primitive 类将生成纹理坐标――就象它们为计算光照生成法线一样。
    1.5.3 雾雾效果可以增添场景的真实感,也可以使远处的形体变模糊或是屏蔽它们,也可以使场景产生透视效果。
    Java3D中可以用ExponentialFog类添加雾效果。
    它的方法:ExponentialFog ()
    1.6 动画的生成所有的内插器节点在使用时都需要与TimeSensor(时间传感器)配合使用。TimeSensor把给定的时间周期归一化,虽然时间的周期 cycleInterval 有给定的秒数,但计算机内部将其处理成从0.0到 1.0,即起始时间为0.0,终止时间为1.0,假如一个时间周期为20(单位均为秒),则第6秒的归一化结果是0.3,第10秒的归一化结果是0.5,第20秒的归一化结果是1.0。 Alpha可以输出从0到1之间的数值给特定的内插对象,当Alpha输出的数值为0时,对应的特定内插对象的值为最小;当Alpha输出的数值为1时,对应的特定内插对象的值为最大;当Alpha输出的数值为0到1之间的数值时,对应的特定内插对象生成和Alpha成相同比例的数值。假设某一时刻Alpha输出的数值为0.2,则对应的特定内插对象的当前值为最小值加上最大最小值之差乘以0.2。(当前值-最小值)/(最大值-最小值)=0.2
    JAVA3D里的各种Interpolator对象可用来旋转形体、移动形体的坐标、变化形体的颜色等。假设我们要让一个形体在规定的时间内按照指定的方式运动,我们首先要给出时间段的大小,还要指出时间是否要循环。这些内容都是由Alpha类来完成的。基本上我们用它以及一个旋转内插器RotationInterpolator来使形体绕着其所在的局部坐标系不停地旋转。
    第2章 JAVA3D场景的实现2.1 Java3D的实现流程本次毕业设计中实现一个JAVA3D场景,其中包括各类灯光的实现,三维场景的移动,任意物体的运动,场景背景变换,指数雾的实现以及与之配合的背景音乐.
    该3D场景设计中运用到立方体、圆锥及椭圆等基本形体,生成Temple和Tower;各种点、线、面生成地面及背景环境。以下即是其设计流程图:

    2.2 JAVA3D的建模2.2.1 生成场景先生成一个Scene1场景作为父结点,以后在此结点下加入子结点完成各种操作及图形显示。
    public Group buildScene( SimpleUniverse u) // 继承Group类{ Group Scene1= new Group ( ); …… return Scene1;}
    这里的SimpleUniverse是对VirtualUniverse的继承,一个应用程序只有一个SimpleUniverse(VirtualUniverse)。它同时定义了其下的Locale、Node、Group及BranchGroup结点。
    2.2.2 圆柱体的构建在程序中定义了一个函数buildColumns来生成一对圆柱体.
    // 开始构建柱体 Vector3f trans = new Vector3f( ); Transform3D tr = new Transform3D( ); TransformGroup tg; for ( int i = 0; i < NumberOfColumns; i++ ) { // 左边的圆柱 trans.set( x, y, z ); tr.set( trans ); tg = new TransformGroup( tr ); tg.addChild( new Link( column ) ); group.addChild( tg ); z += zSpacing; } // 柱体构建完毕 return group;
    然后创建一个函数ColumnScene设置光线、纹理,并将buildColumns加入.
    public ColumnScene (Component observer){ // 在地面上构建一系列圆柱 SharedGroup column = buildSharedColumn ( ); Group columns = buildColumns (column); addChild (columns);}
    利用addChild方法调用ColumnScene函数,在场景中显示构建好的圆柱体。
    Scene1.addChild (new ColumnScene (this));

    2.2.3 Tower的构建创建函数TowerScene构建Tower场景,并加到Scene1中。
    public TowerScene (Component observer){ …… // 构建粗糙的地面 CraterGrid grid = new CraterGrid ( 50, 50, // 栅格范围 1.0, 1.0, // 位置 4.0, // 高度放大比例 craters, // 栅格仰角 moonApp ); // 显示 addChild (grid); …… // 构建金字塔 Arch towerShape = new Arch ( 0.0, // 起始λ角 1.571, // 结束λ角 2, // nλ 0.0, //起始θ角 Math.PI*2.0, // 结束θ角 5, // nθ 3.0, // 起始半径 8.0, // 结束半径 0.0, // 起始λ层 0.0, // 结束λ层 towerApp); // 显示 tower.addChild (towerShape);}
    插入到Scene1场景中.
    Scene1.addChild(new TowerScene (this));
    在这里面函数CraterGrid是建立粗糙栅格表面,Arch是建立给定参数的一个弧面。这两个函数是Java3D里已经定义好的功能所以这里就直接拿来调用,而不给出具体建模的算法了。

    2.3 动画的实现2.3.1 调用galleon.obj文件将galleon.obj文件调入到场景中要加入五行import .
    import com.sun.j3d.loaders.objectfile.ObjectFile;import com.sun.j3d.loaders.ParsingErrorException;import com.sun.j3d.loaders.IncorrectFormatException;import com.sun.j3d.loaders.Scene;import java.io.*;
    下面这段代码就是用来调用外部OBJ文件的.
    TransformGroup trans = new TransformGroup ();trans.setCapability(trans.ALLOW_TRANSFORM_READ);trans.setCapability(trans.ALLOW_TRANSFORM_WRITE);int flags = ObjectFile.RESIZE;ObjectFile f = new ObjectFile(flags, (float) (49.0 * Math.PI / 180.0));Scene s = null;try { s = f.load("galleon.obj"); // 读出obj文件在工程目录下}
    然后再把它加到场景中去.
    trans.addChild(s.getSceneGroup());Scene1.addChild(trans);
    2.3.2 物体转动要使galleon转动学要用到interpolator behaviors,它继承了Behavior类。转动的类是RotationInterpolato。
    Alpha spinAlpha = new Alpha (-1, 4000);spinAlpha.setCapability (Alpha.DECREASING_ENABLE);spinAlpha.setCapability (Alpha.INCREASING_ENABLE);spinner = new RotationInterpolator(spinAlpha, trans);spinner.setEnable(false);spinner.setSchedulingBounds ( new BoundingSphere (new Point3d(), 1000.0));trans.addChild (spinner);
    这样就使得galleon.obj的帆船在场景中转动了。


    2.3.3 场景的移动鼠标交互移动
    主要实现了“行走模式”和“视检模式”两种模式,具体方式可用Java3D封装的WalkViewerBehavior以及ExamineViewerBehavior两个类来实现,这两个类都是对ViewerBehavior类的继承。
    examineBehavior = new ExamineViewerBehavior( exampleSceneTransform, exampleFrame);examineBehavior.setSchedulingBounds (allBounds);sceneRoot.addChild (examineBehavior);walkBehavior = new WalkViewerBehavior( exampleViewTransform, exampleFrame );walkBehavior.setSchedulingBounds (allBounds);sceneRoot.addChild (walkBehavior);
    场景的自动移动
    在这个小场景中,使用了PositionInterpolator类来实现场景位置的前后来回自动移动.
    TransformGroup vpTrans = universe.getViewingPlatform().getViewPlatformTransform(); //这条语句是让操作对整个场景的,而不是某个物体Transform3D axisOfTranslation = new Transform3D ();Alpha transAlpha = new Alpha (-1,Alpha.INCREASING_ENABLE | Alpha.DECREASING_ENABLE, 0, 0,5000, 0, 0, 5000, 0, 0);axisOfTranslation.rotY(-Math.PI/2.0); // 延X轴平移translator = new PositionInterpolator(transAlpha, vpTrans, axisOfTranslation,-4.0f, 20.5f); // 起始位置,中止位置translator.setSchedulingBounds(bounds);translator.setEnable(false);objScale.addChild(translator);Scene1.addChild (objScale);
    这样场景就可以自动从-4.0到20.5的位置移动了。
    2.4 背景变换2.4.1 创建灯光在这个场景中创建了强弱不同的两组Ambient光,照射方向不同的两组Directional光,分别为红色和黄色,以及一组橙色的Point光。
    2.4.1.1 创建一个环境光**AmbientLight ambient = new AmbientLight( ); // 光的类型为AmbientLight ambient.setEnable (ambientOnOff); // 根据ambientOnOff的值设置为true或false ambient.setColor (new Color3f (0.3f, 0.3f, 0.3f)); // 光的颜色 ambient.setCapability (AmbientLight.ALLOW_STATE_WRITE); ambient.setInfluencingBounds (worldBounds);Scene1.addChild (ambient); // 加到场景中设置包围球:BoundingSphere worldBounds = new BoundingSphere (new Point3d ( ), 1000.0);myLight.setInfluencingBounds (myBounds);
    运行结果如下:
    无灯光效果的场景:

    加入AmbientLight效果的场景

    2.4.1.2 创建PointLightPointLight orangePoint = new PointLight ( ); orangePoint.setEnable (orangePointOnOff); orangePoint.setColor (new Color3f (1.0f, 0.5f, 0.0f)); / / 同样为光的颜色,橙色 orangePoint.setPosition (new Point3f (0.0f, 0.5f, 0.0f)); / / 设置光的位置 orangePoint.setCapability (AmbientLight.ALLOW_STATE_WRITE); orangePoint.setInfluencingBounds (worldBounds);Scene1.addChild (orangePoint);
    运行结果如下:

    2.4.1.3 创建一个DirectionalLight:DirectionalLight redDirectional = new DirectionalLight ( ); redDirectional.setEnable (redDirectionalOnOff); redDirectional.setColor (new Color3f (1.0f, 0.0f, 0.0f)); redDirectional.setDirection (new Vector3f (1.0f, -0.5f, -0.5f)); redDirectional.setCapability (AmbientLight.ALLOW_STATE_WRITE); redDirectional.setInfluencingBounds (worldBounds);Scene1.addChild (redDirectional);
    执行结果如下:

    2.4.2 创建背景图片这里的背景图片实际上就是一张640×480的jpg图片,所以就是么把2D图片读到场景中。为了同时实现交互式更换背景图片,这里也加入了菜单。
    读入2D图片要用到ImageComponent2D和TextureLoader两个类。其中ImageComponent2D用于定义一个二维组件,TextureLoader则是读取ImageComponent2D定义的二维组件。
    // 预载背景图片// 使用TextureLoader读图片// 将要读取的图片装入ImageComponent2D[ ]中 if ( debug ) System.err.println( " background images..." ); TextureLoader texLoader = null; String value = null; imageComponents = new ImageComponent2D[images.length]; for ( int i = 0; i < images.length; i++ ) { value = (String)images[i].value; if ( value == null ) { imageComponents[i] = null; continue; } texLoader = new TextureLoader( value, this ); imageComponents[i] = texLoader.getImage( ); }

    2.4.3 指数雾用ExponentialFog可以产生雾的效果
    雾的密度通过指数控制厚度:
    effect = e(-density * distance) color = effect * shapeColor + (1-effect) * fogColor
    下面是场景中对雾的初始化:
    // 设置雾的颜色、密度和范围fog = new ExponentialFog();fog.setColor(color);fog.setDensity(density);fog.setCapability(Fog.ALLOW_COLOR_WRITE);fog.setCapability(ExponentialFog.ALLOW_DENSITY_WRITE);fog.setInfluencingBounds(worldBounds);Scene1.addChild (fog);

    2.4.4 背景音乐在场景中加入背景音乐可以是气氛更加活跃。
    首先要把音乐加入到背景中
    if ( debug ) System.err.println( " sounds..." );String path = getCurrentDirectory( );MediaContainer backgroundMedia = new MediaContainer( path + "canon.wav" );backgroundMedia.setCacheEnable( true );
    然后对背景音乐初始化
    backgroundSound = new BackgroundSound( );backgroundSound.setEnable( true );backgroundSound.setLoop( Sound.INFINITE_LOOPS ); // 设置音乐循环播放backgroundSound.setSoundData( backgroundMedia );backgroundSound.setInitialGain( 1.0f ); // 设置音量backgroundSound.setSchedulingBounds( worldBounds );backgroundSound.setCapability( Sound.ALLOW_ENABLE_WRITE );backgroundSound.setCapability( Sound.ALLOW_INITIAL_GAIN_WRITE );backgroundSound.setCapability( Sound.ALLOW_PAUSE_WRITE);backgroundSound.setCapability( Sound.ALLOW_PAUSE_READ);Scene1.addChild( backgroundSound );
    4.5 在网页上显示3D图形Java3D一个最大的特性是可以使用Applet作为显示容器.
    <HTML> <BODY> <APPLET code= ExExponentialFog.class width=400 height=400> </APPLET> </BODY> </HTML>
    0  留言 2018-12-29 08:54:16
  • 基于JAVA实现的迷宫鼠迷宫小游戏

    1 功能说明1.1 问题描述用JAVA实现电脑鼠走迷宫的程序,一个假想的小车能在图示的迷宫中穿行输出其可能的组合式。
    1.2 题目要求根据国际比赛规则,电老鼠走迷宫分为三个阶段:

    从起点走到终点从终点
    进一步遍历完整个迷宫,获得整个迷宫的地图(墙和通路)
    从起点选择最短路径冲刺到终点

    因此程序分为三部分:

    从任意一点走到另外给定点
    遍历完整个迷宫的程序
    计算最短路径(计算等高表,按路径行规定走)

    1.3 功能图
    2 算法说明2.1 生成迷宫关键字:递归回溯

    首先将迷宫分成若干个正方形的单元格,并选中左上角(0,0)作为起始点(start)。将正被访问的单元格标记为已访问,得到它所有相邻单元格。在这些相邻的单元格中随机选择一个,如果这个被选中的单元格没有被访问过,那么移掉正被访问单元格和被选中单元格之间的墙体,并将这个被选中单元格作为正被访问单元格。如果正被访问单元格的所有相邻单元格都被访问过,那么在所有被访问过的单元格(这里指迷宫中所有已被访问过的单元格)中选上一个被访问的作为正被访问单元格,如此递归下去,直到迷宫中所有的单元格都被访问过为止(即访问到终点)。这样迷宫就生成了。
    2.2 寻找路径
    先将老鼠置于起始点(start)。将正老鼠所在的单元格标记为已访问,得到它所有相邻的没有被访问过的单元格。从这个(些)单元格中随机选一个,移掉正被访问单元格和被选中单元格之间的墙体,并将老鼠移动到这个被选中单元格。如果老鼠旁边没有未被访问过的单元格,那么在所有被访问过的单元格(这里指迷宫中所有已被老鼠访问过的单元格)中选上一个被访问的作为正被访问单元格,如此递归下去,直到迷宫中的老鼠访问到终点。这样迷宫就走完了。
    2.3 遍历迷宫
    在之前寻找到路径的基础上,探索整个迷宫地图。原理和之前的差不多,只是终止条件变成了栈为空(即老鼠访问了迷宫的所有格子)。
    2.4 最短路径
    由于生成迷宫时使用的算法可以保证生产的随机迷宫有且只有一条通路,所以在寻找最短路径时只需要把寻找路径过程中找到的迷宫通路去除死路即可以得到最短路径。
    事实上,我们的栈已经把最短路径存放好了,我们只需要稍作处理即可。
    3 系统模型
    4 系统测试


    测试环境
    OS X 11.11




    用例名称
    Reigning’S Maze


    前提条件
    Java 1.8+


    测试步骤
    打开程序,测试是否存在未知BUG


    输入数据
    5x5 50


    预期输出
    5x5的迷宫


    实际输出
    5x5的迷宫



    5 课程设计总结本次课程设计时间紧任务重,对于我来说是个不小的挑战。虽然算是完成了,但仍有一些做的不是很好需要优化。
    5.1 程序亮点
    格子的访问状态和墙的面数使用4位二进制数据(由于是JAVA所以使用了整形)储存,使用位运算进行数据运算。众所周知,位运算是基于系统底层级别的运算,在现在的计算机中,位运算比其他运算更为迅速,也更能优化程序性能,大量节省CPU占用时间,避免程序未响应。
    提高空间复杂度以降低时间复杂度。现在的计算机的内存普遍都很大,参考OS X的内存管理制度,我们完全可以提高内存的使用率来换取用户对于程序的一些体验。程序中有一些代码片段会占用一些看起来不必要的内存,但是其对于减少用户等待时间是非常重要的。
    使用了JAVAFX作为了GUI语言并且使用了动画编程SequentialTransition 类作为动画编程的核心。在JAVAFX资料少和课本内容不全面的情况下,我通过阅读JAVA源代码及官方英文文档掌握了SequentialTransition 类的用法并且获得了不错的动画效果。
    尽量避免使用访问器(getter)和修改器(setter)。我之前开发安卓的经验告诉我,getter和setter往往是安卓程序卡顿停滞的重要原因。在本程序中,尽量避免了使用getter和setter,性能有所优化。

    5.2 程序不足
    由于没有使用getter和setter,时间不是很足,直接后果是类的封装太差了,不利于后期维护和调试。
    生成迷宫的算法单一,只能生成有且仅有一条通路的迷宫,最短路径的算法无法得到实现和体现。后期应该添加其它的生成迷宫算法,获得具有多条通路的迷宫,这样就可以很好的体现最短路径的算法。
    占用内存偏高。因为程序是JAVA编写,加上一些占内存的代码及动画效果,不推荐在05年以及之前的电脑上运行。
    0  留言 2018-12-01 12:40:13
  • 基于C++实现的表达式计算

    一、使用说明1.1 操作手册运行程序后,进入欢迎界面,首先要输入中缀表达式。
    第一步,输入中缀表达式。


    第三步,进行具体操作。
    1.1.1 波兰表达式在第一行输出波兰表达式,例如:

    1.1.2 中缀表达式在第二行输出中缀表达式,例如:

    1.1.3 逆波兰表达式在第三行输出逆波兰表达式,例如:

    二、概述2.1 程序设计目的运用树的知识对于表达式生成一个二叉树,通过树的前中后序遍历来输出波兰表达式、中缀表达式和逆波兰表达式。
    2.2 算法思路本题的算法非常简单,针对不同的类型有不同的优先级,通过运算符栈和数字栈两个数据结构将表达式最终表达成一个树。遇到数字直接进入数字栈,遇到运算符则判定运算符栈栈顶运算符和当前运算符的优先级大小,判定是否出栈运算或是入栈。如果运算符出栈就从数字栈取两个数值生成节点,然后再压回数字栈,直到表达式解析完。
    2.3 数据结构每一个树的节点都是一个结构体,整个树是一个类,采用树形的数据结构。
    三、函数接口3.1 node结构体


    成员
    功能




    Char data
    存储节点内容


    Node *leftChild
    指向节点的左子树


    Node *rightChild
    指向节点的右子树



    3.2 Tree接口


    成员函数名
    功能
    参数
    返回值类型




    Tree()
    默认构造函数,使根节点指向NULL。




    Tree(const string s)
    生成表达式树
    一个中缀表达式



    Node * buildTree(const string s)
    生成表达式树的核心函数
    一个中缀表达式
    Node *


    Node * create()
    初始化节点

    一个已经分配了空间的节点


    Node * getRoot()
    获取根节点

    Node *


    void PostOrder(Node * node)
    后序遍历
    开始后序遍历的节点



    void InOrder(Node * node)
    前序遍历
    开始前序遍历的节点



    四、体会这道题让我练习了树这个数据结构,并从这个题目中我明白了二叉树的前中后序遍历是怎么一回事。并明白了计算机是怎么从我们输入的中缀表达式计算出值得。收益颇多。
    1  留言 2018-11-07 15:32:14
  • 基于C语言实现的表达式求解

    1 解题思路构造包含顶指针,底指针和增量的结构体。然后分别构造一个只包含运算符的栈(OPTR)和只包含数字的栈(OPND)。之后依次读入所输入的表达式。判断是不是数字,如果是数字就将数字放入数字栈(OPND)。如果不是即运算符,让运算符栈栈顶元素和读入的运算符进行比较。如果优先级小于将读入的运算符入栈,优先级相等的就让栈顶元素出栈,优先级的大于的就让栈顶元素弹栈,并且连续两次让数字栈弹栈,得到一个运算符和两个数字,进行计算,得到的结果放入数字栈。循环以上过程直到读入的表达式字符为#为止。最后将数字栈出栈,即得到结果。
    2 函数调用图
    3 各函数功能// 构造空栈char InitStack (SqStack *S);// 让e入栈char Push(SqStack *S, char e);// 让e出栈char Pop(SqStack *S, char *e);// 返回栈顶第一个元素char getTop(SqStack S);// 比较两个运算符的优先级,a,b中存放待比较的运算符,'>'表示a>b,'0'表示不可能出现的比较,这是通过二维数组建立比较表实现的char Precede(char a, char b);// 判断输入的某个字符是否是运算符int in(char c, char OP[8]);// 四则运算计算char Operate(char a, char n, char b);// 表达式计算,流程控制char evaluateExpression(SqStack OPTR, SqStack OPND);// 主函数,建立OPTR与OPND栈int main();
    4 测试





    5 编译与运行情况编译正常通过。运行时如果计算中出现负数就无法运算,而且输入表达式的时候因为用的是getchar所以无法读出两位数以上的数字进行计算,这是该程序缺陷的地方。
    1  留言 2018-11-07 15:30:06
  • 基于C语言实现的线性表综合题

    介绍
    按照输入的顺序建立顺序表
    对顺序表进行排序(直接插入、冒泡、选择、快速、合并)
    按照由大到小的顺序建立一个单链表
    链表逆置
    将顺序表和链表合并成一个有序表
    结果输出

    1 解题思路通过建立一个数组和一个结构体,数组用以保存顺序表,而在结构体内建立数据域和指针域用以保存链表。首先设定序表长度并要求输入数据,建立输出顺序表函数,在通过关于顺序表的五种排序的子函数选择其一进行排序,最后通过输出函数输出;再建立链表,使数据输入链表且由大到小输出,并设计链表逆置函数;最后再写出函数将已有的顺序表和链表合并为一张有序表并输出。而在主函数中通过switch函数来选择所需要的步骤。
    2 函数调用图
    3 各函数功能// 建立顺序表int createList (int arr[]); // 建立顺序表int createList (int arr[]); // 排序列表,流程控制,并且建立快速排序和归并排序所需数组int sort(int arr[]); // 直接插入排序int insertSort(int arr[]); // 冒泡排序int bubbleSort(int arr[]); // 直接选择排序int selectionSort(int arr[]); // 快速排序int quickSort(int arr[], int M, int N); // 归并排序递归int merge(int r[], int r2[], int S, int M, int N); // 归并排序int mergeSort(int r[], int r2[], int S, int N); // 建立链表int createNode(Node *L); // 对链表节点进行倒序int sortNode(Node *L); // 结合两张表int combine(int arr[], Node *L2); // 主函数,建立链表节点,流程控制int main();
    4 测试







    5  留言 2018-11-07 15:27:31
  • 基于C语言实现的线性表相加

    介绍将两个有序线性表合并成一个有序线性表,并去掉重复元素。
    1 解题思路先建立一个结构体,结构体中包含数据域以及next的指针域。将每个结构体定义为一个节点,再通过指针域链接来建立链表。选择升序或者降序排序,分别输入节点数据,建立L1,L2的链表。然后根据选择升序或者降序调用不同的合并函数。如果是升序则数据小的先插入链表,大的后插入,如果是降序则大的先插入链表,小的后插入。最后输出新链表L3。
    2 函数调用图
    3 各函数功能// 建立线性表int createList (LNode *L);// 将L1,L2合并成L3,升序并输出int mergeListSL(LNode *L1, LNode *L2, LNode *L3);// 将L1,L2合并成L3,降序并输出int mergeListLS(LNode *L1, LNode *L2, LNode *L3);// 主函数,流程控制int main();
    4 测试



    1  留言 2018-11-07 15:24:12
  • 基于C语言实现的线性表拆分

    介绍设有一个线性单链表,其结点值均为正整数,且按值从大到小链接。试写出一个算法,将该线性单链表分解成两个线性单链表,其中一个链表中的结点值均为奇数,而另一个链表中的结点值均为偶数,且这两个链表均按值从小到大链接。
    1 解题思路先建立一个结构体,结构体中包含数据域以及next的指针域。然后将原链表先通过冒泡排序倒置,再遍历倒置后的链表。如果数据是奇数的放入新的链表L2,如果是偶数放入新的链表L3,直到遍历完成。就成功拆分了原链表。
    2 函数调用图
    3 各函数功能// 建立线性表int createList (LNode *L);// 打印数据int print(LNode *L);// 对链表进行冒泡排序int sortList(LNode *L);// 将原线性表分开成两个线性表int splitList(LNode *L1, LNode *L2, LNode *L3);// 主函数,流程控制int main();
    4 测试




    1  留言 2018-11-07 15:21:56
  • 基于C语言实现的约瑟夫环

    1 解题思路先定义包含一个数字域以及next的指针域的结构体。然后输入节点总数创建链表,最后将链表尾指针指向第一个数据节点使之闭合成为约瑟夫环。接下来输入开始节点和间距。如果间距为1就是依次输出即可。如果间距大于一就相隔间距输出,并且输出后将断环闭合。最后直到约瑟夫环中没有节点即结束。
    2 函数调用图
    3 各函数功能// 创建链表int create(Node *L);// 实现约瑟夫环,先进行闭环操作,然后根据开始节点和间距进行输出节点操作int process(Node *L);// 流程控制,并且建立列表Lint main();
    4 测试



    1  留言 2018-11-07 15:19:19
  • 基于C#和SQL SERVER数据库实现的学生图书管理系统

    1 项目介绍1.1 课程设计的目标通过课程集中实践,要求学生加深对讲授内容的理解,累积经验、学会独立上机调试程序;并且逐步达到综合运用封装、继承和多态等C#难点知识,更深地理解面向对象程序设计的基本概念与方法,从而学会利用C#语言解决一般应用问题,能设利用可视化编程技术开发复杂和综合性的计算机管理信息系统,并为后续专业课程的学习奠定程序设计基础。
    1.2 开发环境搭建
    开发语言:C#
    开发工具:Microsoft Visual Studio 2010
    数据库管理工具:SQL Server 2008

    2 系统的设计与实现2.1 物理数据模型设计




    2.2 主要界面设计界面中用了textbox,label,combobox,textbox用于获取数据输入,combobox用于数据选取,button用于单击事件。在用户类别可以选择用户类型,管理员。

    界面中用了textbox,label,combobox,dataGridView,textbox用于获取数据输入,combobox用于数据选取,button用于单击事件,dataGridView用于数据显示。功能:可以增加,修改,删除图书。

    界面中用了textbox,label,combobox,dataGridView,textbox用于获取数据输入,combobox用于数据选取,button用于单击事件,dataGridView用于数据显示,用户借书,管理员可以查看用户的借书记录。

    密码修改:可以更改当前用户登录的密码,旧密码符合条件,新密码和旧密码不能相同,新密码和确认密码的相同的条件。

    读者记录查询界面中用了textbox,label,combobox,dataGridView,textbox用于获取数据输入,combobox用于数据选取,button用于单击事件,dataGridView用于数据显示,用户借书,管理员可以查看用户的借书记录。模糊查询在下面有具体介绍。

    管理员信息管理:可以对管理员进行增添改查。

    书库管理:对书库进行增删改查。

    书库查询:按地区分类;

    按书库编号分类,第二个combobox会自动加载所有记录的值供你选择。

    书库管理:用来增加书库,删除,修改。

    用户管理:对用户的增删改查。

    用户登录之后的界面。

    管理员登录之后的界面。

    2.3 主要代码分析2.3.1 查询功能
    假如有四条数据:

    福建闽侯
    福建省福州市闽侯
    福建鼓楼
    福州市鼓楼

    我们输入福建闽侯,当我们用like %string%是只会显示第一条数据,所以我写了个小算法,输入查询字符对应的每个单字符都和结果相对比,用foreach获取字符相同时的字符数组下标,可以找到与 %福%州%闽%侯%相同的数据,比如福州市闽侯,更为精准,具体实现如下所示:
    public List<TSGLXT.Model.DZB> DataNew(DataTable dt,string c,int b){ int charA = 0; int Sq = 0; bool mark = false ; int x = 0; int num = 0; List<TSGLXT.Model.DZB> modelList = new List<TSGLXT.Model.DZB>(); int rowsCount = dt.Rows.Count; if (rowsCount > 0) { TSGLXT.Model.DZB model; for (int n = 0; n < rowsCount; n++) { model = new TSGLXT.Model.DZB(); if (dt.Rows[n]["SKID"] != null && dt.Rows[n]["SKID"].ToString() != "") { model.skid = dt.Rows[n]["SKID"].ToString(); } if (dt.Rows[n]["BKISBN"] != null && dt.Rows[n]["BKISBN"].ToString() != "") { model.BKISBN = dt.Rows[n]["BKISBN"].ToString(); } if (dt.Rows[n]["BKNAME"] != null && dt.Rows[n]["BKNAME"].ToString() != "") { model.bkname = dt.Rows[n]["BKNAME"].ToString(); } if (dt.Rows[n]["BKPRICE"] != null && dt.Rows[n]["BKPRICE"].ToString() != "") { model.bkprice = dt.Rows[n]["BKPRICE"].ToString(); } if (dt.Rows[n]["BKAUTHOR"] != null && dt.Rows[n]["BKAUTHOR"].ToString() != "") { nmodel.bkauthor = dt.Rows[n]["BKAUTHOR"].ToString(); } if (dt.Rows[n]["DZID"] != null && dt.Rows[n]["DZID"].ToString() != "") { model.DZID = dt.Rows[n]["DZID"].ToString(); } if (dt.Rows[n]["DZNAME"] != null && dt.Rows[n]["DZNAME"].ToString() != "") { model.DZNAME = dt.Rows[n]["DZNAME"].ToString(); } if (dt.Rows[n]["DZYEAR"] != null && dt.Rows[n]["DZYEAR"].ToString() != "") { model.DZYEAR = (int)dt.Rows[n]["DZYEAR"]; } if (dt.Rows[n]["DZDUTY"] != null && dt.Rows[n]["DZDUTY"].ToString() != "") { model.DZDUTY = dt.Rows[n]["DZDUTY"].ToString(); } if (dt.Rows[n]["DZADDRESS"] != null && dt.Rows[n]["DZADDRESS"].ToString() != "") { model.DZADDRESS = dt.Rows[n]["DZADDRESS"].ToString(); } if (b == 0) { foreach (char a in c) { while (num < model.DZNAME.Length) { mark = false; if (a == model.DZNAME[num]) { Sq++; mark = true; } if (mark) { num++; break; } num++; } charA++; } if (charA == Sq) { modelList.Add(model); } charA = 0; num = 0; Sq = 0; } else if (b == 1) { foreach (char a in c) { while (num < model.bkname.Length) { mark = false; if (a == model.bkname[num]) { Sq++; mark = true; } if (mark) { num++; break; } num++; } charA++; } if (charA == Sq) { modelList.Add(model); } charA = 0; num = 0; Sq = 0; } else if (b == 2) { foreach (char a in c) { while (num < model.DZID.Length) { mark = false; if (a == model.DZID[num]) { Sq++; mark = true; } if (mark) { num++; break; } num++; } charA++; } if (charA == Sq) { modelList.Add(model); } charA = 0; num = 0; Sq = 0; } } } return modelList;}
    2.3.2 借书
    private void BindData(){ dgvData.DataSource = BLLDB.TSB.GetModelList("");}private void BorrowForm_Load(object sender, EventArgs e){ dgvData.AutoGenerateColumns = false; InitCBX(); BindData(); cbxWork.SelectedIndex = 0; }private void dgvData_CellClick(object sender, DataGridViewCellEventArgs e){ if (dgvData.SelectedRows.Count == 1) { TSB model = (TSB)dgvData.SelectedRows[0].DataBoundItem; ISBN = model.BKISBN; }}private bool CheckInput(){ if (string.IsNullOrEmpty(txtName.Text.Trim())) { txtName.Focus(); tip.Show("必须输入", txtName, 1000); return false; } else if (string.IsNullOrEmpty(cbxAddress.Text)) { cbxAddress.DroppedDown = true; tip.Show("必须选择", cbxAddress, 1000); return false; } else if (string.IsNullOrEmpty(cbxWork.Text.Trim())) { cbxWork.DroppedDown = true; tip.Show("必须选择", cbxWork, 1000); return false; } else if (string.IsNullOrEmpty(cbxYear.Text.Trim())) { cbxYear.DroppedDown = true; tip.Show("必须选择", cbxYear, 1000); return false; } else { return true; }}private void borrow_Click(object sender, EventArgs e){ if (CheckInput() && ISBN != null) { string msg = MakeIdentifying(); DZB model = new DZB() { DZID = msg, DZADDRESS = cbxAddress.Text, DZDUTY = cbxWork.Text, DZNAME = txtName.Text, DZYEAR = int.Parse(cbxYear.Text), BKISBN = ISBN }; if (BLLDB.DZB.Add(model) == true) { MessageBox.Show("借书成功"); } else { MessageBox.Show("借书失败"); } } }private string MakeIdentifying(){ int num = 0; char[] str = new char[] { '1', '2', '3', '4', '5', '6', '7', '8', '9', '0', }; Random r = new Random(); string msg = null; while (true) { int rand = r.Next(0, 10); msg += str[rand]; num++; if (num == 5) break; } return msg;}
    2.3.3 书库查询
    private void BindData(string msg){ dgvData.DataSource = BLLDB.SKB.GetViewModelList(msg);}private void SKQuiry_Load(object sender, EventArgs e){ dgvData.AutoGenerateColumns = false; BindData("");}private void cbxType_SelectedIndexChanged_1(object sender, EventArgs e){ if (cbxType.SelectedIndex == 1) { cbxSelect.DataSource = BLLDB.SKB.GetAddressModelList(""); cbxSelect.DisplayMember = "SKADDRESS"; cbxSelect.ValueMember = "SKADDRESS"; } else if (cbxType.SelectedIndex == 0) { cbxSelect.DataSource = BLLDB.SKB.GetModelList(""); cbxSelect.DisplayMember = "SKID"; cbxSelect.ValueMember = "SKID"; }}private void cbxSelect_SelectedIndexChanged_1(object sender, EventArgs e){ string txt = cbxSelect.Text; if (cbxType.SelectedIndex == 0) { StringBuilder str = new StringBuilder(); str.Append(" SKID=" + "'" + txt + "'"); BindData(str.ToString()); } else if (cbxType.SelectedIndex == 1) { StringBuilder str = new StringBuilder(); str.Append(" SKADDRESS=" + "'" + txt + "'"); BindData(str.ToString()); }}
    2.3.4 管理员信息管理和书库信息管理
    private void InitCBX(){ cbxSKID.DataSource = BLLDB.SKB.GetModelList(""); cbxSKID.DisplayMember = "SKID"; cbxSKID.ValueMember = "SKID";}private void BindData(){ dgvData.DataSource = BLLDB.GLB.GetViewModelList("");}private void ClearInput(){ txtName.Clear(); cbxSKID.SelectedIndex = -1; txtUSER.Clear(); cbxSex.SelectedIndex = -1; btnAdd.Enabled = true; btnDelete.Enabled = false; btnDelete.Enabled = false; txtUSER.ReadOnly = false; txtName.Focus();}private bool CheckUserInput(){ if (string.IsNullOrEmpty(txtName.Text.Trim())) { txtName.Focus(); tip.Show("必须输入", txtName, 1000); return false; } else if (string.IsNullOrEmpty(txtUSER.Text.Trim())) { txtUSER.Focus(); tip.Show("必须输入", txtUSER, 1000); return false; } else if (string.IsNullOrEmpty(cbxSex.Text.Trim())) { cbxSex.DroppedDown = true; tip.Show("必须选择", cbxSex, 1000); return false; } else if (string.IsNullOrEmpty(cbxSKID.Text.Trim())) { cbxSKID.DroppedDown = true; tip.Show("必须选择", cbxSKID, 1000); return false; } else { return true; }}private void GLYInformation_Load(object sender, EventArgs e){ dgvData.AutoGenerateColumns = false; BindData(); InitCBX();}private void SelectedSex(string str){ if (str == "男") { cbxSex.SelectedIndex = 0; } else if (str == "女") { cbxSex.SelectedIndex = 1; } else { cbxSex.SelectedIndex = 2; } }private bool CheckModelChanged(){ if (dgvData.SelectedRows.Count == 1) { GLB model = (GLB)dgvData.SelectedRows[0].DataBoundItem; return model.ADYNAME == txtName.Text && model.ADSEX == cbxSex.Text && model.SKID == cbxSKID.Text; } else { return false; }}private void dgvData_CellClick(object sender, DataGridViewCellEventArgs e){ if (dgvData.SelectedRows.Count == 1) { GLB model = (GLB)dgvData.SelectedRows[0].DataBoundItem; txtName.Text = model.ADYNAME; txtUSER.Text = model.ADUSERNAME; SelectedSex(model.ADSEX); cbxSKID.Text = model.SKID; txtUSER.ReadOnly = true; btnDelete.Enabled = true; btnAdd.Enabled = false; }}private void btnAdd_Click(object sender, EventArgs e){ if (CheckUserInput() && !BLLDB.GLB.CheckADNAME(txtUSER.Text)) { string pd = Interaction.InputBox("请输入密码", "输入密码", "", -1, -1); GLB model = new GLB() { SKID = cbxSKID.Text, ADSEX = cbxSex.Text, ADPASSWORD = pd, ADUSERNAME = txtUSER.Text, ADYNAME = txtName.Text }; if (BLLDB.GLB.Add(model) == true) { MessageBox.Show("添加成功"); BindData(); ClearInput(); } else { MessageBox.Show("添加失败"); } }}private void btnClear_Click(object sender, EventArgs e){ ClearInput();}private void btnModify_Click(object sender, EventArgs e){ if (CheckUserInput() && !CheckModelChanged()) { GLB model = new GLB() { SKID = cbxSKID.Text, ADSEX = cbxSex.Text, ADUSERNAME = txtUSER.Text, ADYNAME = txtName.Text, ADPASSWORD = BLLDB.GLB.GetPassword(txtUSER.Text) }; if (BLLDB.GLB.Update(model) == true) { MessageBox.Show("更新成功"); BindData(); ClearInput(); } else { MessageBox.Show("更新失败"); } }}private bool CheckUsed(string msg){ if (msg == LoginForm.username) { return true; } else { return false; }}private void btnDelete_Click(object sender, EventArgs e){ if (MessageBox.Show("确定要删除吗?", "删除提示", MessageBoxButtons.YesNo, MessageBoxIcon.Question) == DialogResult.Yes) { if (CheckUsed(txtUSER.Text)) { MessageBox.Show("当前管理员账户正在使用中,不能删除"); } else { if (BLLDB.GLB.Delete(txtUSER.Text)) { MessageBox.Show("删除成功"); BindData(); ClearInput(); } else { MessageBox.Show("删除失败"); } } }}

    private void BindData(){ dgvData.DataSource = BLLDB.YHB.GetModelList("");}private void ClearInput(){ txtUser.Clear(); btnAdd.Enabled = true; btnCZ.Enabled = false; btnDelete.Enabled = false; txtUser.Focus();}public ManageUser(){ InitializeComponent();}private bool CheckModelExist(){ if (string.IsNullOrEmpty(txtUser.Text.Trim())) { txtUser.Focus(); tip.Show("必须输入", txtUser, 1000); return false; } else { return true; }}private void btnAdd_Click(object sender, EventArgs e){ if (CheckModelExist() && !BLLDB.YHB.CheckYserExist(txtUser.Text)) { string pd = Interaction.InputBox("请输入密码", "输入密码", "", -1, -1); YHB model = new YHB() { username = txtUser.Text, password = pd }; if (BLLDB.YHB.Add(model) == true) { MessageBox.Show("添加成功"); BindData(); ClearInput(); } else { MessageBox.Show("添加失败"); } }}private void btnCZ_Click(object sender, EventArgs e){ if (MessageBox.Show("确定要重置账户密码吗?", "删除提示", MessageBoxButtons.YesNo, MessageBoxIcon.Question) == DialogResult.Yes) { YHB model = new YHB() { username = txtUser.Text, password = "666" }; if (BLLDB.YHB.Update(model) == true) { MessageBox.Show("重置密码成功,密码为666,请重新登录"); Form frm = Program.Context.MainForm; LoginForm log = new LoginForm(); Program.Context.MainForm = log; log.Show(); frm.Close(); } else { MessageBox.Show("重置密码失败"); } }}private void btnDelete_Click(object sender, EventArgs e){ if (MessageBox.Show("确定要删除当前账户吗?", "删除提示", MessageBoxButtons.YesNo, MessageBoxIcon.Question) == DialogResult.Yes) { if (LoginForm.username == txtUser.Text) { MessageBox.Show("不能删除正在登录的账户"); } else { if (BLLDB.YHB.Delete(txtUser.Text) == true) { MessageBox.Show("删除成功"); BindData(); ClearInput(); } else { MessageBox.Show("删除失败"); } } }}private void btnClear_Click(object sender, EventArgs e){ ClearInput();}private void ManageUser_Load(object sender, EventArgs e){ dgvData.AutoGenerateColumns = false; BindData();}private void dgvData_CellClick(object sender, DataGridViewCellEventArgs e){ if (dgvData.SelectedRows.Count == 1) { YHB model = (YHB)dgvData.SelectedRows[0].DataBoundItem; txtUser.Text = model.username; btnDelete.Enabled = true; btnCZ.Enabled = true; btnAdd.Enabled = false; }}
    3 调试过程中出现的问题及解决办法数组索引超出界限
    解决方法:利用断点调试,重新赋值。

    数据列填写错误,是这个类新增字段


    从试图获取数据时,应添加新的字段

    ValueMember是后台取得数据的值,DisplayMember是前台显示的值,所以ValurMember要和数据库的列相对应,而DisplayMember可以看作是标识符。
    cbxSelect.DataSource = BLLDB.DZB.GetAddressModelList("");cbxSelect.DisplayMember = "DZADDRESS";cbxSelect.ValueMember = "DZADDRESS";
    4 总结在这次课设中,基本都是在学习新知识的过程,从powerdesigner到动软生成软件,让我知道了这个工具的强大之处,渐渐开始会用一点,在第一天晚上想重做一遍学生信息管理系统,不料,生成的路径没改,直接给覆盖了,所以只能重头再来,在这时就有想法想做个不一样的系统,上学期用C++做了个图书管理系统,有点印象,就选择做这个,一开始一直模范着你给的day1,day2,day3,看不懂BLL,DAL,MODEL之间的关系,经过思考,理解了他们之间的关系,BLL负责储存方法相当于API,DAL负责储存数据,MODEL负责各个对象的类,后面理解了就开始自己写,用户负责借书,用户的增删改,添加用户,管理员负责查询书库,书库的增删改查,查询图书,图书的增删改查,借书记录的增删改查,在这个过程中不仅了解了动软生成软件的机制,而且可熟练的利用这个工具,在这个工具的基础之上,我写出了更多好用的函数供自己使用。在windows应用开发上了解更多控件和控件属性的使用和结合,可以做出功能和界面相对完整的程序,总之,在这次课设中受益匪浅。
    1  留言 2018-11-06 15:53:05
  • 基于汇编语言实现打字练习软件

    一 需求分析根据以下几部分来实现打字练习:

    随机显示字母,字母出现的位置随机
    字母自动落下
    从键盘输入的字母与落下字母相同则该字母消失,否则字母自动接着落下
    按下“Esc”键则程序返回主菜单
    字母下落过程中按空格键暂停
    在主界面按“E”则程序退出

    打字练习的主要功能由以上六部分组成,每一部分之间的联系都是比较紧密的。对于以上及部分,最主要的部分就是中间的四个部分,这是打字练习的重点,需要详细设计其所需要的功能。
    二 程序设计主模块是打字游戏的核心模块,主要通过各个键盘符来控制各个子模块之间的协调,完成打字游戏的运行。
    子模块主要包括:初始化子模块、速度设定子模块、显示时钟子模块、开始打字子模块,显示打字结果子模块。

    初始化子模块包括显示初始界面菜单,初始化程序参数,判断是否进入游戏
    速度设定子模块包括速度选择子程序和速度设置子程序
    显示时钟子模块包括取系统时钟和显示两个子程序
    开始打字子模块包括显示分数子程序,当敲入字符与下落相符时扬声器发声子程序,字母下落子程序,产生新的字母和新的位置子程序,延时子程序。这些程序有机的组合在一起,完成整个指法练习的程序

    初始化子模块包括初始化程序参数,显示初始界面菜单,判断是否进入游戏。首先初始化字母出现的位置,初始化得分和各种标志的值,然后显示初始界面菜单,通过一个比较指令和堆栈操作来判断是否进入游戏。
    2.1 系统总体框架
    2.2 系统流程图
    三 程序实现3.1 实现环境
    硬件环境:IBM-PC机,硬盘40G以上,内存256M以上,打印机等
    软件环境:Windows 2000 Server或Windows XPServer操作系统,TC,QE等编辑软件,MASM汇编软件

    3.2 关键代码说明Init_game macro op1,op2,op3,op4,op5 local ns mov cx,00h mov dh,op1 mov dl,op2 ns:mov ah,02h;设置光标位置 mov bh,00h;页号为0 int 10h push cx mov ah,0ah;在当前光标位置写字符 mov al,op3;al=字符的ascii码 mov bh,00h;bh=页号bl=字符属性 mov cx,01h;cx=写入字符重复次数 int 10h pop cx;cx=0 inc cx;cx=cx+1 inc op4 cmp cx,op5 jne ns endmclear_screen macro op1,op2,op3,op4 ;清屏宏定义 cx,屏幕的左上角,dx屏幕的右下角 mov ah,06h mov al,00h mov bh,0eh;改变行属性的色彩,字的色彩,bh空白行的属性/07就是正常的黑底白字 mov ch,op1 mov cl,op2 mov dh,op3 mov dl,op4 int 10h mov ah,02h;设置光标的位置从0000开始 mov bh,00h mov dh,00h mov dl,00h int 10hendmmenu macro op1,op2,op3 ;菜单显示宏定义 mov ah,02h mov bh,00h mov dh,op1 mov dl,op2 int 10h mov ah,09h lea dx,op3 int 21hendmdata segment ZK db "WELCOME TO PLAY$" no db "date:2013/12/27$" meg db "press Enter key to continue.......$" meg1 db "when a letter is dropping,please hit it!$" meg2 db "press space key to pause!$" meg3 db "press ESC key to return main interface!$" meg4 db "press letter 'E' to exit!$" speed dw 600d letters_bak db "jwmilzoeucgpravskntxhdyqfb" db "iytpkwnxlsvxrmofzhgaebudjq" db "nwimzoexrphysfqtvdcgljukda" letters db 78d dup(0) letter_counter db 0 life_flag db 78 dup(0) position_flag db 78 dup(0) present_position db 1 data endsstack segment para stack 'stack' db 64 dup(0)stack endscode segment main proc far assume cs:code,ds:data,ss:stack start: mov ax,data mov ds,ax mov letter_counter,00h mov present_position,1 lea si,position_flag; mov ah,00h mov cx,00h lea di,letters;di的偏移地址为letters lea si,letters_bak;si的偏移地址为letter_bak mov cx,00h;cx=0 init_letters: mov ah,[si];ah=j mov [di],ah;ah的值放到letters里面;letters_bak的值放入letters里面 inc si;si+1 inc di;di+1 inc cx;cx+1 cmp cx,78d; jne init_letters;不为0就到init_letters,一直循环到letters里 mov ah,00h lea si,life_flag; mov cx,00h init_life_flag: mov [si],ah inc si inc cx cmp cx,78d jne init_life_flag mov cx,00h ;ch=光标开始行,cl=光标结束行 根据CX给出光标的大小 mov ah,01h or ch,00010000b;ch>20h,光标消失,cl>20h,覆盖字符 int 10h clear_screen 00d,00d,24d,79d ;清屏,0000- 2479 Init_game 00d,00d,0ah,dl,80d ;这个四个是初始化屏幕的上下左右的框框 Init_game 24d,00d,0ah,dl,80d Init_game 00d,00d,0ah,dh,25d Init_game 00d,79d,0ah,dh,25d menu 05d,15d,ZK ;菜单信息的宏调用,这五行是在屏幕上显示提示消息 menu 07h,15d,no menu 09d,15d,meg menu 11d,15d,meg1 menu 13d,15d,meg2 menu 15d,15d,meg3 menu 17d,15d,meg4 put: mov ah,02h ;设置光标位置 mov bh,00h;设置页码 mov dh,22d;dx行列坐标 mov dl,33d int 10h mov ah,01h ;从键盘输入任意字符并回显示,al=输入字符 int 21h cmp al,0dh;是否为换行符 je speed3;如果是换行符则跳转到speed3处 cmp al,45h;比较是否为e je exit;如果为e,转到exit exit: mov ah,4ch int 21h speed3: mov ax,speed+12 mov speed,ax jmp begin begin: clear_screen 01d,01d,23d,78d ;清屏宏调用 ; clear_screen 01d,01d,23d,78d Init_game 23d,01d,03h,dl,78d;23d01d行列坐标,初始化倒数第二行的字符 mov ah,02h mov bh,00h mov dh,01h mov dl,01h int 10h mov cx,00h lea si,letters ;si的偏移地址是letters nextletter: mov ah,02h ;显示字母 mov dl,[si] ;把letters的字符放到dl里 int 21h ;通过dos中断的2号功能项,把字符显示出来 inc si inc cx cmp cx,78d je nextcycle;全部显示完了后,跳到nextcycle jmp nextletter from_front: sub present_position,78d ;当超过78个字时的处理方式 减去78 jmp gobackto_si;跑到gobackto_si这来 find_zero: cmp letter_counter,78d ;letter_counter有78了,初始化 je recycle;如果有跑到recycle cmp present_position,78d;如果present_position等于78d, je from_one mov ah,00h nextsi: add present_position,01h inc si cmp [si],ah je gobackto_di cmp present_position,78d je from_one jmp nextsi from_one:mov present_position,01h ;present_position=01 jmp gobackto_si recycle:mov letter_counter,00h;letter_counter=0 mov present_position,01d;present_position=01 lea si,position_flag;si=position_flag的偏移地址 mov cx,00h mov ah,00h clearsi: mov [si],ah;position_flag地址搞成0 inc cx cmp cx,78d je nextcycle inc si jmp clearsi nextcycle: lea di,letters;di的偏移地址是letters[字母] lea si,position_flag;si的偏移地址是position_flag add present_position,31d;31一跳,这个你可以随便设置 cmp present_position,78d;;超过78个字节 ja from_front gobackto_si: add si,word ptr present_position;si=si+present_position,si向后偏移 dec si; 要不要都无所谓,只不过,因为开始就觉定了是要31一跳,所以这里减一个1位 mov ah,[si];把position_flag放到ah里 cmp ah,01h;看看position_flag里面有没有标志1 je find_zero;如果ah为1转移,否则 gobackto_di: mov ah,01h mov [si],ah add di,word ptr present_position dec di;因为列坐标是从0开始,而字符是从1开始,所以这里是32-1 mov dl,present_position; mov ah,02h mov bh,00h mov dh,01h int 10h mov cx,00h nextrow: push cx mov cx,00h out_cycle: ; 延迟 push cx mov cx,00h in_cycle: add cx,01h cmp cx,1000 ; jne in_cycle ;zf=0转到标号处执行, push dx mov ah,06h ;从键盘输入字符,al等于字符 mov dl,0ffh int 21h pop dx jz pass cmp al,1bh ;如果键入ESC,则返回主菜单 je to_start1 cmp al," " ;如果键入SPACE,则游戏暂停 je pause cmp al,[di] ;输入字母正确!则字母消失 je disappear pass: pop cx inc cx cmp cx,speed je print jmp out_cycle pause: push dx ;暂停处理 第一次知道暂停是这样的,循环空代码 mov ah,06h mov dl,0ffh int 21h pop dx cmp al," " jne pause jmp pass to_start1: ;返回主菜单 jmp start print: mov ah,0ah ;在当前光标位置写空格 mov al," " mov bh,00h mov cx,01h int 10h inc dh mov ah,02h ;改变光标位置 mov bh,00h int 10h mov ah,0ah ;在当前光标位置写字母 mov al,[di] mov bh,00h mov cx,01h int 10h pop cx inc cx cmp cx,21d je print_next_letter jmp nextrow ;下一行 disappear: ;击中字母后输出空格 pop cx pop cx mov ah,0ah;在光标处按原来属性显示字符 mov al," " mov bh,00h mov cx,01h int 10h jmp hit print_next_letter: lea si,life_flag add si,word ptr present_position dec si mov ah,0ah;在当前光标处按原有属性显示字符 mov al," ";最倒数第二排写入字符,意思是当掉下来的字符到倒数第二行的时候,自动变成空格消失 mov bh,00h mov cx,01h int 10h inc dh ;这就是到了最后一行 mov ah,02h;2号中断,设置文本光标位置 mov bh,00h int 10h mov ah,0ah;把最后一行的字符变成空格 mov al," " mov bh,00h mov cx,01h;重复输出,这里的重复输出的意思就是输入一个空格 int 10h mov ah,1;把life_flag变成1,这样下次就可以不在同一个位置掉字符下来 mov [si],ah hit: mov ah,02h;设置光标 mov bh,00h mov dh,01h;第一行 mov dl,present_position;下一个字符的列 int 10h mov al,[di] ; 出现下一个新字母的数法 add al,7;di+7 cmp al,7ah;z的ascii码就是7ah,所以当al大于7ah时转移 ja convey_letter mov ah,0ah;在当前光标按原有属性显示字符,al=字符 mov bh,00h mov cx,01h int 10h mov [di],al add letter_counter,01h;统计次数 jmp nextcycle convey_letter: sub al,7ah add al,61h;al等于要显示的字符,加61表示是小写字母 mov ah,0ah mov bh,00h mov cx,01h int 10h mov [di],al add letter_counter,01h jmp nextcycle clear_screen 01,01,23,78 mov ah,02h mov bh,00h mov dh,11d mov dl,20d int 10h inc dh inc dh mov ah,02h mov bh,00h int 10h notkey: mov ah,07h int 21h cmp al,0dh je to_start cmp al,1bh je over jmp notkey to_start: clear_screen 00,00,24,79 jmp start over: clear_screen 01,01,23,78 mov ah,02h mov bh,00h mov dh,11d mov dl,15h int 10h mov ah,02h mov bh,00h mov dh,13d mov dl,15h int 10h mov ah,07h int 21h mov ah,07h int 21h clear_screen 00,00,24,79 mov ax,4c00h int 21h main endpcode endsend start四 运行测试


    五 参考文献[1] 方立友.微机原理与汇编语言实用教程.北京:清华大学出版社,2007年02月
    [2] 颜志英.微机系统与汇编语言.北京:机械工业出版社,2007年9月
    [3] 王成.计算机组成原理实验指导书与习题集.北京:清华大学出版社,2000年4月
    [4] 张代远.计算机组成原理教程.北京:清华大学出版社,2005年6月
    [5] 朱家铿.计算机组成原理.沈阳:东北大学出版社,2000年3月
    [6] 王爱英.计算机组织与结构.北京:清华大学出版社,1998年7月
    [7] 唐塑飞.计算机组成原理.北京: 高等教育出版社,2000年9月
    [8] 白英中.计算机组成原理.第二版.北京:科学出版社,2001年3月
    1  留言 2018-11-03 10:40:58
  • CG树顶端节点集群的设计与实现

    摘要本文描述了一个CG树顶端节点集群的设计与实现,主要内容有:

    详细阐述了顶端节点集群的设计方案。该方案维持集群节点间的通信,当集群内节点失效时能及时发现;负载均衡器(LB)能够将客户端的请求通过一定的调度策略转发给下面的真实服务器(RS);能够保证所有真实服务器上的数据库的一致性。
    实现了一个顶端节点集群的系统原型,技术分析和实验结果表明,该集群系统具有稳定性和高可用性。


    搭建了一个测试系统,对客户端的请求进行分析处理,返回客户端需要的信息,并测试顶端节点集群的性能。根据测试结果分析顶端节点和顶端节点集群之间的性能差异,证明设计方案的有效性。
    [关键词] 集群 CG树 LVS 顶端节点集群
    AbstractThis paper describes the design and implementation for the top node cluster in CG-Tree. The major contents include:

    A detail design solution for the top node cluster is described. It can maintain the communications among cluster nodes and detect node faults whenever cluster fails. The load balancer (LB) can forward the client’s request to the real server (RS) by selected strategy. The databases on all real servers are kept consistency.A prototype of the top nodecluster is implemented. The technical analysis and experimental result showthat the cluster is with stability and highly availability.A test system is built to analyze and process the request from clients, return the required information to clients, and test the performance of the top node cluster. Accorded to the test results, the difference of the performance between the top node and the top node cluster is analyzed to show the effectiveness of the design solution.
    [Keywords] Cluster, CG-Tree, LVS, Top Node Cluster
    第一章 引言1.1 研究背景1.1.1 集群技术Internet 的飞速发展给网络带宽和服务器带来巨大的挑战。从网络技术的发展来看,网络带宽的增长远高于处理器速度和内存访问速度的增长。热门网站引发前所未有的访问流量,很多网络服务因为访问次数爆炸式地增长而不堪重负。一些新兴的网络技术如视频点播,动态网页,CGI 等带来更大的网络带宽需求。这时单一的计算机系统,如单处理器或者SMP 系统,往往因为巨大的网络负载而不堪重负,其存在着诸多的问题,主要表现在:扩展能力差并且扩展的代价昂贵;升级导致的服务中断会带来巨大的商业损失,并造成原有计算资源的浪费;单点故障发生的概率较高导致无法提供持续的可靠服务。解决网络服务的可伸缩性和可靠性已是非常紧迫的问题。
    通过高性能网络或局域网互联的服务器集群[1]正成为实现高可伸缩的、高可用网络服务的有效结构。这种松耦合结构的服务器集群系统有下列优点:

    提高性能
    一些计算密集型应用,如:天气预报、核试验模拟等,需要计算机有很强的运算处理能力。这时,一般都使用计算机集群技术,集中几十台甚至上百台计算机的运算能力来满足要求。提高处理性能一直是集群技术研究的一个重要目标之一。随着网络的普及和计算机硬件性能的不断提高,集群系统的应用领域越来越广,目前集群系统主要应用于Web服务、Cache服务、媒体服务、科学计算以及数据库应用等领域。
    降低成本
    组成集群系统的 PC 服务器或RISC 服务器和标准网络设备因为大规模生产降低成本,价格低,具有很高的性能价格比。若整体性能随着节点数的增长而接近线性增加,该系统的性能价格比接近于PC 服务器。所以,这种松耦合结构比紧耦合结构的多处理器系统具有更好的性能价格比。
    提高可扩展性
    用户若想扩展系统能力,不得不购买更高性能的服务器,才能获得额外所需的CPU和存储器。如果采用集群技术,则只需要将新的服务器加入集群中即可,对于客户来看,服务无论从连续性还是性能上都几乎没有变化,好像系统在不知不觉中完成了升级。
    增强可靠性
    集群技术使系统在故障发生时仍可以继续工作,将系统停运时间减到最小。集群系统在提高系统的可靠性的同时,也大大减小了故障损失。

    目前集群系统因其诸多的优点,已被广泛应用于 Web 服务,Cache 服务,媒体服务,科学计算及数据库等领域。
    1.1.2 CG树简介对于视频点播这种大流量的服务需求,服务器这一端的带宽将在很大程度上影响媒体服务的质量,如果将服务器节点限制在单个局域网内,媒体集群将受到网关流量的制约而提供很有限的服务。
    CG树[2,3]是适用于分布式集群的一种模型,CG树将集群的节点分级分层,组织成以前端调度节点为根节点,服务器池的所有节点分组管理的树形结构。该模型下前端负载均衡器不必跟服务器池的所有节点通信,有效减少了前端节点的负载。集群节点采用分级分层的结构,能有效减轻集群前端负载均衡器的负担,并能有效地减少跨网络集群节点间的通信开销,具有较高的实用价值,是跨网络集群的一个较好的解决方案。
    如图1-1是一棵CG 树的结构图。

    在以往的CG树的实现中,顶端节点(如图1-2)需要负责处理客户端的请求,数据库的查询,CG森林的维护,资源的调度等任务,导致顶端节点的压力非常大,成为了整个系统的瓶颈。其中,数据库的查询操作占据了节点的绝大多数的资源。对于此,本文对顶端节点的性能做出过测试,在千兆局域网内选择了1台计算机作为顶端节点,其详细配置为:

    操作系统:Ubuntu10.10Linux内核版本:Linux 2.6.35CPU:Intel® Core™ 2 Quad CPU Q8400 2.66GHz(四核)内存:2GB数据库:MySQLServer 5.1
    然后客户端不断地发送请求,由客户端记录发送请求和收到响应的数量。实验结果表明,顶端节点在满负荷的条件下,每秒钟只能执行数据库查询一万次左右,即每秒钟可以处理客户端的一万次左右的资源请求。如果系统面向全世界服务,其性能显然无法满足客户的需求,因此,顶端节点成为了整个系统的瓶颈。

    1.1.3 系统的提出为了解决这一问题,本文提出了一种将顶端节点修改为顶端节点集群(如图1-3)的做法。这种做法的思路是,用分布的做法让多台服务器组成顶端节点集群来分担原来单个顶端节点的工作,从而提高系统的整体性能。顶端节点集群由两层计算机组成,第一层仅仅负责请求的转发,第二层由多台计算机组成,作为真实服务器,负责请求的处理,其数量取决于整个CG树的规模。由于顶端节点仅仅在选择真实服务器的时候需要与客户端通讯,真正提供服务时是由真实服务器与客户端直接进行通讯的,因此,基于CG树结构的服务器在管理规模上几乎没有限制。

    1.2 研究工作本文设计与实现了一种CG树顶端节点集群的设计方案,主要包括以下内容:

    集群整体架构的设计:设计了一种可用的集群方案,引入了心跳机制,通过心跳的传递使负载均衡器了解每个节点的运行状态,同时通过TCP消息的传递,保证了各个节点数据库的一致性。调度策略的设计:实现了轮转调度、源地址哈希调度、加权轮转调度三种种可用的调度策略。集群的实现:使用UNIX/Linux下Socket编程技术以及多线程技术,实现了本文设计的集群系统,包括负载均衡器和真实服务器两大模块的实现以及数据库连接池的实现。性能测试:模拟了一个基于CG树的视频点播系统,在系统正常工作的条件下,测试了网络的丢包率,测试了顶端节点和顶端节点集群的性能,分析并比较了顶端节点集群与以往顶端节点之间的性能差异,并且对数据库的一致性进行了简单的测试。最后,本文对顶端节点集群的设计方案和测试结果给出了结论,提出了系统存在的缺点,对未来的研究方向做出了展望。
    1.3 论文结构本论文共有七章。

    第一章为引言。本章首先分析了以往CG树所存在的问题,从而引出了将CG树的顶端节点改为顶端节点集群的想法。第二章为相关技术介绍。主要介绍了本文中用到的相关技术。第三章为系统设计。本章主要介绍了CG树顶端节点集群的设计方案。第四章为系统实现。本章主要介绍了CG树顶端节点集群的具体实现。第五章为实验部分。在校园网的实验环境下进行了相关测试,并对实验结果进行了分析。第六章为总结与展望。提出了本文研究工作的结论和不足,并对课题给予展望。最后是参考文献与致谢。
    第二章 相关实现技术简介2.1 Socket通信简介所谓socket[4]通常也称作“套接字”,应用程序通常通过“套接字”向网络发出请求或者应答网络请求。有两种常用的Socket类型:流式Socket(SOCK_STREAM)和数据报式Socket(SOCK_DGRAM)。流式Socket是一种面向连接的Socket,针对于面向连接的TCP服务应用;数据报式Socket是一种无连接的Socket,对应于无连接的UDP服务应用。

    用户数据报协议(UDP)
    UDP是一个简单的传输层协议,应用进程往一个UDP套接字写入一个消息,该消息随后被封装到一个UDP数据报,该UDP数据报进而又被封装到一个IP数据报,然后发送到目的地。UDP不能保证UDP数据报会到达其最终目的地,不保证各个数据报的先后顺序跨网络后保持不变,也不保证每个数据报只到达一次。
    传输控制协议(TCP)
    TCP不同于UDP,它提供客户与服务器之间的连接,TCP客户首先与服务器建立一个连接,然后通过该连接与服务器交换数据,然后终止这个连接。TCP提供了可靠的数据传输和流量控制,但是其开销要大于UDP。

    在本文的设计方案中,心跳信息的传递使用UDP协议,数据库更新信息和节点之间的其他信息的传递使用TCP协议。
    2.2 多线程技术简介由于本文涉及的系统涉及到多个功能模块的并发操作,对于并发操作主要有两种方式实现:多进程结构和多线程结构。在多进程结构中,程序通过创建子进程来实现并发操作,如此可以充分发挥多核CPU的性能。然而创建子进程的开销是非常昂贵的,每创建一个子进程,需要把父进程的内存映像复制到子进程,且进程间的通信非常复杂。而线程则可以解决上述问题,线程的创建和切换的开销要比进程小得多。同一进程内的所有线程可以共享相同的全局内存,使得线程之间易于共享信息,随之而来的同步问题则可以通过互斥量来解决。
    为了提高系统运行的效率,本系统将采用多线程技术实现任务的并发操作。本系统使用的是POSIX线程[5],也称为Pthread。
    2.3 MySQL数据库简介MySQL[6]是最流行的开放源码关联数据库管理系统。关联数据库将数据保存在不同的表中,而不是将所有数据放在一个大的仓库内。这样就增加了速度并提高了灵活性。MySQL的SQL指得是“结构化查询语言”。SQL是用于访问数据库的最常用标准化语言,它是由ANSI/ISO SQL标准定义的。MySQL数据库服务器具有快速、可靠和易于使用的特点。
    第三章 系统设计3.1 整体结构3.1.1 整体结构的设计以往的CG树由一个顶端节点负责控制一个CG森林,顶端节点需要负责整个集群系统的维护、客户端请求的处理以及资源的调度等等,这样使得顶端节点的负担很重,成为整个系统的瓶颈,为了解决这一问题,本文提出了将顶端节点改为顶端节点集群的办法,其结构图如图3-1所示。

    顶端节点集群为两层结构,第一层是一台负载均衡器,第二层由若干台真实服务器组成。负载均衡器负责接收第二层节点的心跳信息,保存它们的相关信息。第二层的每台服务器都维持一个同样内容的数据库,保存CG树叶子节点上相关资源的信息。由负载均衡器接受客户端的请求,然后按照一定的转发策略转发给第二层的真实服务器,真实服务器通过数据库查询操作得到保存客户端请求资源的CG树节点,将查询结果发送给客户端。
    3.1.2 与LVS的比较LVS[7]是基于IP层负载均衡技术的典型代表。用户通过虚拟IP地址(Virtual IP Address)访问服务时,访问请求的报文会到达负载均衡器,由它进行负载均衡调度,从一组真实服务器选出一个,将报文的目标地址Virtual IP Address改写成选定服务器的地址,报文的目标端口改写成选定服务器的相应端口,最后将报文发送给选定的服务器。真实服务器的回应报文经过负载均衡器时,将报文的源地址和源端口改为Virtual IP Address和相应的端口,再把报文发给用户;或者真实服务器直接将回应报文的源地址和源端口改为Virtual IP Address和相应的端口,发给用户。
    以LVS为代表的典型集群在结构上一般分为三层:负载调度器(load balancer),它作为整个集群系统对外的前端,负责将客户的请求发送到后台的一组服务器上执行,客户不需要知道真实服务器的IP地址;服务器池(server pool),位于后台的一组真正提供应用程序服务的服务器,他们之间通过传递心跳信息来维持可用的服务器列表;共享存储(shared storage),它为服务器提供一个共享的存储区,这样很容易使得服务器池拥有相同的内容,提供相同的服务。
    图2-1展示了一个LVS系统的基本结构。

    LVS集群由负载调度器、服务器池和共享存储三大部分组成,本文的设计方案借鉴了LVS,同样有一个负载调度器,一组真实服务器。因为CG树顶端节点处理客户请求仅仅需要查询数据库,因此,不需要设置共享存储。
    对于MySQL分布式数据库,LVS的一般做法是使用高冗余的同步集群(MySQL Cluster)或者相对简单的异步集群(MySQL replication)来实现。同步集群的特点是配置和管理方便,不会丢失数据,但是其需要较多的内存且速度一般。异步集群的特点是使用主从(mater/slave)模式,速度较快,但是往往会导致主数据库的压力过大且可能会丢失数据。无论哪种数据库集群,其都会产生较大的数据冗余。
    在本系统的应用中,客户端的请求是查询所需资源的地址,而数据库的更新操作只有在CG树叶子节点上的资源更新时才会发生。因此,本文根据这个特点设计了一种简单的数据库的维护方式,即每台真实服务器保留一个数据库的完整副本,从而提高数据库的查询效率。
    3.2 心跳的设计心跳机制[8]是高可用集群的重要技术之一。心跳周期性的检测集群中节点机器的工作状态,当节点机器的工作状态发生改变时,能够通知集群软件的其他部件。
    本集群将采用心跳机制来维持系统的高可用性,由第二层的真实服务器周期性地向第一级的负载均衡器发送心跳信息,以告知负载均衡器其最新的状态。负载均衡器接收到心跳信息后,更新节点的状态信息,记录节点的心跳时间,同时设置一个心跳超时时间,其一般为心跳周期的2到3倍,若负载均衡器在超时时间内没有接收到真实服务器的心跳信息,则认为该节点发生故障,将节点状态设为故障。在实际应用上,可在心跳信息中捎带其他信息,如节点的工作负载等。
    因为心跳的发送频繁,为了减少网络通信的开销,本文使用UDP协议来进行心跳的传递。
    3.3 数据库一致性的保持因为本文的设计方案中,集群中第二层的所有节点使用内容相同的数据库,因此保持数据库的一致性就是我们要关心的问题之一。
    在本文的设计方案中,负载均衡器和真实服务器都要创建一个用于数据库更新的线程,CG树节点向负载均衡器发出数据库更新消息,当负载均衡器接受到数据库更新消息后,通过TCP将更新消息转发给每一台真实服务器,由真实服务器执行数据库的更新操作,从而保证每台服务器数据库的一致性。
    3.4 调度策略的设计本文为了提供整个集群的可用性,共实现了三种请求的转发调度策略[9],分别是:
    3.4.1 轮转调度轮转调度是最简单的调度策略,当负载均衡器接收到客户端的请求时,将请求轮询式的转发给第二层的节点。使用这种调度策略,负载均衡器的负担最小,同时,当客户端请求资源少而频繁时,此调度策略具有非常高的效率。但是,当请求服务时间变化比较大时,轮转调度算法容易导致服务器间的负载不平衡。
    // 轮转调度算法// 假设有一组服务器S = {S0, S1, …, Sn-1},一个指示变量i表示上一次选择的服务器,W(Si)表示服务器Si的权值,大于0表示服务器可用。变量i被初始化为n-1,其中n > 0j = i;do { j = (j + 1) mod n; if (W(Sj) > 0) { i = j; return Si; }} while (j != i);return NULL;
    3.4.2 源地址哈希调度通过源调度哈希转发即通过哈希函数将客户端的IP映射到唯一的一台服务器上。该调度算法可以使请求得到较均匀的分布。
    // 源地址哈希调度算法// 假设有一组服务器S = {S0, S1, …, Sn-1},W(Si)表示服务器Si的优先级,0表示服务器不可用。ServerNode[]是一个有256个桶(大小可调整)的Hash表,变量i表示上一次选择的服务器,变量ip表示客户端IP,getNext表示使用轮转获取下一个可用节点。算法的初始化是将所有服务器顺序、循环地放置到ServerNode表中j = hash(ip);if (W(Sj) == 0) { j = getNext(i);}Return Sj;hash(unsigned int ip) { return (ip * 2654435761) & HASH_TAB_MASK;}// 其中,2654435761UL是2到2^32 (4294967296)间接近于黄金分割的素数。// 2654435761 / 4294967296 = 0.618033987
    3.4.3 加权轮转调度为了解决集群第二层服务器性能可能存在差异的问题,可以使用加权轮转调度。其具体实现就是根据每台服务器的性能为每个节点设置一个优先级,性能越好,优先级越高。当服务器向负载均衡器注册时,同时告知优先级信息。在客户端发来请求时,负载均衡器根据优先级转发给第二层的真实服务器。
    // 加权轮转调度算法// 假设有一组服务器S = {S0, S1, …, Sn-1},W(Si)表示服务器Si的优先级,变量i表示上一次选择的服务器,变量cw表示当前调度的权值,max(S)表示集合S中所有服务器的最大权值,gcd(S)表示集合S中所有服务器优先级的最大公约数。变量i初始化为-1,cw初始化为零。while (true) { i = (i + 1) mod n; if (i == 0) { cw = cw - gcd(S); if (cw <= 0) { cw = max(S); if (cw == 0) return NULL; } } if (W(Si) >= cw) return Si;}
    例如,有三个服务器A、B和C分别有权值4、3和2,则在一个调度周期内调度序列为AABABCABC。当第二层服务器性能差异较大时,相对于轮询转发,此转发策略可以提高每台服务器的使用效率。
    第四章 系统实现4.1 LB模块的实现LB模块运行于集群第一层的负载均衡器上,负责转发客户端的请求、维持集群的运作、转发数据库更新消息等。
    4.1.1 LB模块的主要数据结构LB模块的主要数据结构为:
    class TopNode{ /**< 存放节点信息的容器 */ vector<Node *> nodeVector; /**< 转发请求时,下一个节点的序号 */ vector<Node *>::size_type m_nextNode; /**< m_nextNode的互斥锁 */ pthread_mutex_t m_nextNodeLock; /**< property的互斥锁 */ pthread_mutex_t m_propertyLock; /**< threadNum的互斥锁 */ pthread_mutex_t m_threadNumLock; /**< 数据库更新的互斥锁 */ pthread_mutex_t m_dbUpdateLock; /**< 接收心跳的端口 */ int m_heartbeatPort; /**< 接收消息的端口 */ int m_messagePort; /**< 接受数据库更新消息的端口 */ int m_dbPort; /**< 对外提供服务的端口 */ int m_servicePort; /**< 客户端请求转发策略 1:轮转调度 2: 源地址哈希转发 3:加权轮转调度 */ int m_policy; /**< 提供服务的套接字 */ int m_sockfd; /**< 接受请求计数 */ int m_count; /**< 二层服务器的数量 */ int m_rsNum; /**< 数据库连接池 */ ConnPool *m_pool; };/** @brief the arg of the function thread_handleRequest */struct requestArgs{ /**< 指向TopNode */ TopNode *topNode; /**< 客户端的地址结构*/ struct sockaddr_in cliaddr; /**< 客户端的socket套接字*/ int connfd; /**< 客户端的请求内容*/ string *request; };class Node{ /**< store node's priority information */ s_propertyMesg m_sProMesg; /**< 数据库更新的套接字 */ int m_sockdbfd; /**< 节点ID */ string ID; /**< 节点状态 */ int status; /**< 节点接收请求的端口 */ int m_servicePort; /**< 节点上次发出心跳的时间 */ time_t heartBeatTime; /**< 节点接收请求的地址结构 */ struct sockaddr_in m_serviceAddr; /**< 节点状态的互斥锁 */ pthread_mutex_t statusLock; /**< 节点心跳时间的互斥锁 */ pthread_mutex_t heatBeatTimeLock; };
    4.1.2 LB模块的接口RS模块提供的接口为:
    class TopNode{ /**< 初始化 */ void init(); /**< 轮询获得下个可用节点 */ Node *getNextNode(); /**< 读取配置文件 */ void readConf(char *); /**< 对外提供服务 */ void *serve(void *arg); /**< 接收心跳 */ void *receiveheartbeat(void *arg); /**< 接收消息 */ void *receiveMessage(void *arg); /**< 检查各字节点状态 */ void *changeStatus(void *arg); /**< 对请求进行处理 */ void *handleRequest(int, const struct sockaddr_in *, string *); /**< 对消息进行处理 */ void *handleMesg(int, const struct sockaddr_in *); /**< 通过IP获得下个可用节点 */ Node *getNextNodeByIP(uint32_t); /**< 通过负载获得下个可用节点*/ Node *getNextNodeByLoad(); /**< 通过优先级获得下个可用节点*/ Node *getNextNodeByProperty(); /**< 处理数据库更新消息*/ void *handledbUpdate(int); /**< 接受数据库更新消息*/ void *dbUpdate(void *arg);};class Node{ /**< 连接服务器,返回套接字 */ int connectServer(); /**< 关闭套接字 */ void closeServer(int); /**< 向服务器发送消息 */ void sendtoServer(int, char *, size_t);};
    4.1.3 LB的启动流程
    读取配置文件。从配置文件中读取服务端口等相关信息,同时读取数据库的相关配置。初始化数据。初始化程序运行所需要的数据,包括网络地址结构、数据库连接池等。创建提供服务的线程。该线程用于处理客户端发过来的请求,并将请求的内容转发给第二层的真实服务器。创建接受数据库更新消息的线程。该线程用于处理CG树发送过来的数据库更新消息,并将消息转发给每一台服务器。创建接受消息的线程。该线程用于接受所有节点发送过来的消息,并对消息进行处理。创建控制线程。该线程用于控制整个程序的运行,包括日志更新,节点状态的检测等功能。创建接受心跳的线程。该线程接受真实服务器发送的心跳信息,并记录真实服务器的状态。
    4.2 RS模块的实现RS模块运行于集群第二层的真实服务器上,负责处理客户端的请求,并把处理结果发送给客户端。
    4.2.1 RS模块的主要数据结构RS模块的数据结构为:
    class RealServer{ /**< 负载均衡服务器的地址 */ char m_lbIP[20]; /**< 负载均衡服务器的接收心跳的端口 */ int m_lbHbPort; /**< 负载均衡服务器的接收消息的端口 */ int m_lbMessagePort; /**< 节点ID */ string m_ID; /**< 提供服务的端口 */ int m_servicePort; /**< 接收数据库更新的端口 */ int m_dbPort; /**< 数据库连接池 */ int m_property; /**< 数据库连接池 */ ConnPool *m_pool; /**< 处理请求数 */ int m_connNum; /**< 处理数据库更新次数 */ int m_dbNum; /**< 提供服务的套接字 */ int m_sockfd; /**< 日志文件 */ FILE *m_log; };/**< 用于创建线程时传递参数 */struct requestArgs{ /**< 指向RealServer */ RealServer *realServer; /**< 客户端的地址结构*/ struct sockaddr_in cliaddr; /**< 客户端的socket套接字*/ int connfd; /**< 客户端的请求内容*/ string *request; };
    4.2.2 RS模块的接口RS模块提供的接口为:
    /**< 发送心跳 */void *heartbeat(void *arg);/**< 向LB注册 */int registerToTopNode();/**< 初始化服务器 */void init(); /**< 对外提供服务 */void *serve();/**< 处理客户端请求 */void *handleRequest(int, const struct sockaddr_in *, string *); /**< 读取配置文件 */void readConf(char *); /**< 数据库更新 */void *dbUpdate(void *);
    4.2.3 RS的启动流程
    读取配置文件。从配置文件中读取负载均衡器的IP和端口的相关信息,同时读取数据库的相关配置。初始化数据。初始化程序运行所需要的数据,包括网络地址结构、数据库连接池等。创建提供服务的线程。该线程用于处理负载均衡器转发过来的客户端请求,并将处理结果发送给客户端。创建接受数据库更新消息的线程。该线程用于处理负载均衡器发送过来的数据库更新消息,对数据库进行更新。向负载均衡器注册。向负载均衡器发送注册消息,告知负载均衡器自己的服务端口、优先级等信息。创建发送心跳信息的线程。该线程按照一定的周期向第一层的负载均衡器发送心跳信息。
    4.3 数据库连接池的实现数据库连接池负责分配、管理和释放数据库连接,它允许应用程序重复使用一个现有的数据库连接,而不是再重新建立一个。在高并发的条件下,数据库连接池可以明显提高数据库操作的效率。因此,为了提高效率,本系统实现了一个简单的数据库连接池。
    4.3.1 数据库连接池的数据结构数据库连接池的数据结构为:
    /** @brief 存放每个连接的地址和状态*/typedef struct _sConStatus{ /**< 数据库连接地址 */ MYSQL *connAddr; /**< 数据库连接状态 0:空闲 1:使用中*/ int status; }sConStatus;class connPool { /**< 数据库地址 */ string m_strHost; /**< 数据库用户名 */ string m_strUser; /**< 密码 */ string m_strPwd; /**< 数据库名 */ string m_strDbName; /**< 数据库服务器端口 */ int m_intMysqlPort; /**< 最大连接数 */ int m_intConnNum; /**< 存放连接的容器 */ vector<sConStatus *> m_vectorConn; /**< 从连接的地址,快速找到索引 */ map<sConStatus *, int> m_mapVI; /**< 从连接快速找到状态 */ map<MYSQL *, sConStatus *> m_mapMysqlScs; /**< 互斥锁 */ pthread_mutex_t m_mutexScs; };
    4.3.2 数据库连接池的接口数据库连接池对外提供的接口为:
    /**< 初始化数据库连接池 */int init(char *strHost, char *strUser, char *strPwd, char *strDbName, int intMysqlPort, int intConnNum);/**< 创建一个数据库连接 */MYSQL *createOneConn();/**< 从连接池取一个连接 */MYSQL *getOneConn();/**< 将连接放回连接池。以便其他人用*/void retOneConn(MYSQL *pMysql);
    第五章 实验及其结果分析5.1 实验环境在千兆局域网内选择了6台计算机,其详细配置为:

    操作系统:Ubuntu10.10Linux内核版本:Linux 2.6.35CPU:Intel® Core™ 2 Quad CPU Q8400 2.66GHz(四核)内存:2GB数据库:MySQLServer 5.1
    5.2 实验测试与分析5.2.1 丢包率测试测试方法:由三台计算机作为客户端,不断的发送UDP请求并记录发出的请求次数,服务器记录收到的请求次数。
    UDP数据报格式:

    测试结果:当发送速率在40万次/秒、50万次/秒、60万次/秒、65万次/秒的条件下,服务器收到包的成功率分别为100%、99.89%、93.19%、84.12%。



    发送速率(万/秒)
    接受成功率




    40
    100%


    50
    99.89%


    60
    93.19%


    65
    84.12%



    结果分析:在丢包率允许的范围内,服务器每秒钟最大可以接受50万次左右的请求,未来整个系统的搭建应该考虑网络的上限。
    5.2.2 顶端节点性能测试测试方法:选择一台计算机作为CG树的顶端节点,同时建立一个数据库,其规模为200万条记录,记录资源的相关信息。客户端不断的发送请求,每次请求1到10个资源,服务器负责查询数据库,将保存资源的CG树节点IP告知客户端。客户端记录收到的响应数,服务器端记录处理的请求数以及数据库查询操作的次数。
    测试结果:在满负荷的条件下,服务器平均每秒钟处理客户端请求1790次,数据库查询操作9836次。
    图5-1记录了顶端节点的CPU、内存以及网络使用等负载情况。

    结果分析:从图5-1中可以看出,CPU的使用率已经达到了90%以上,而每秒钟数据库的查询操作只有不到一万次,整个系统的性能会收到严重的制约。
    5.2.3 顶端节点集群性能测试测试方法:类似于上小节的测试方法,将顶端节点改为顶端节点集群,一台计算机作为负载均衡器,分别选择2、3、4台计算机作为真实服务器,进行同样的测试。
    测试结果:当真实服务器的数量分别为2、3、4台时,整个集群平均每秒钟处理的请求数分别为3746次、5346次、7670次,平均每秒钟数据库查询次数分别为20600次、29405次、42190次。
    满负荷运行时,真实服务器的负载情况如图5-2所示。

    当挂载四台真实服务器时,整个集群最大负荷条件下,负载均衡器的负载情况如图5-3所示。

    结果分析:将顶端节点改为顶端节点集群后,整个系统的处理能力大大加强。表5-1给出了性能测试的统计结果。



    真实服务器数量
    客户端请求数(次/秒)
    数据库查询次数(次/秒)
    性能




    0(即顶端节点)
    1790
    9836
    1


    2
    3746
    20600
    2.09


    3
    5346
    29405
    2.99


    4
    7670
    42190
    4.28



    根据表中数据可以看出,整个系统的性能几乎是和真实服务器的数量成正比的。
    另外,由图5-3所示,因为负载均衡器仅仅负责转发,所以在真实服务器满负荷的条件下,负载均衡器的CPU使用率只有15%左右,在网络条件允许的情况下完全可以挂载更多的服务器,从而继续增强整个系统的处理能力。
    5.2.4 数据库一致性测试测试方法:使用五台计算机组成顶端节点集群,由另外一台计算机向集群发出插入、更新、删除记录的消息,由每台真实服务器统计执行操作的次数,并人工检查几个数据库是否保持了一致性。
    测试结果

    首先测试数据库插入,每次插入一条数据,整个集群的插入效率是每秒钟插入18500条记录。然后测试更新语句的执行,每次更新一条记录,整个集群的更新效率是每秒钟更新16000条记录。
    最后测试删除语句的执行,每次删除一条记录,整个集群的删除效率是每秒钟删除15000条记录。(以上的测试数据会随着数据库的规模改变以及查询条件的改变而有所波动)
    最后检查所有数据库的内容,可以保证所有数据库内容一致。

    结果分析
    由于每台服务器上都有一个数据库,所以数据库更新时,所有的真实服务器都需要进行更新,真实服务器的增加不会使整个集群的效率增加,反而会增加网络的负担。但是由于CG树数据库更新操作较少,大部分的数据库操作都是查询操作,因此数据库一致性保持上所损失的性能是可以接受的。
    5.2.5 数据库更新与查询综合测试
    测试方法:使用五台计算机组成顶端节点集群,由另外的计算机分别发出客户端请求和数据库更新消息,统计满负荷下集群处理客户请求的数量。
    测试结果:当以每秒钟1000次左右的速率发送数据库更新消息时,整个集群每秒钟可以处理客户请求7600次左右,数据库查询42000次左右。
    结果分析:当数据库更新操作数量有限时,对整个集群客户端请求处理能力影响不大。考虑到CG树节点更新频率不高,因此本文的集群方案是可行的。

    第六章 总结与展望本章对本文的工作做了一个全面的总结,并指出了不足之处和下一步的研究内容。
    6.1 工作总结
    本文首先介绍了一种适用于分布式集群的模型——CG树,并且分析了CG树顶端节点存在的问题,然后引出了将顶端节点改为顶端节点集群的想法。
    然后本文介绍了一种顶端节点集群的设计方案,包括心跳设计、数据库一致性的保持以及调度策略等内容。
    随后,本文给出了顶端节点集群的详细设计,并利用socket编程以及多线程技术实现了顶端节点集群。
    最后,本文利用顶端节点集群搭建了一个简单服务器,并对其性能进行了测试,并与以往的顶端节点做出了比较。实验结果表明,顶端节点集群处理客户端请求的能力明显提高,具有一定的可行性。

    6.2 课题展望本文的实现方案中,第二层的所有服务器都使用相同的数据库,有较大的数据冗余,同时增加了数据库同步的开销,如果数据库的规模达到一定的程度,可以考虑将第二层的服务器分组,从而进步一减轻每台服务器的负担。
    另外,本文的系统建立于数据库更新操作不频繁的基础上,如果要应用于数据库更新频繁的平台,数据库的更新策略需要修改。
    本文的实现只针对Linux操作系统,在系统的实现中大量用到了Linux系统相关的API,今后如果有意把系统用在面向跨平台应用上,这些部分都需要进行扩充和修改。
    参考文献[1] William Stallings. 操作系统——精髓与设计原理(第五版)[M],北京:电子工业出版社,2006.
    [2] 刘维峰. 分布式媒体集群的设计与实现[D],厦门:厦门大学,2005.
    [3] 吴国才. 基于CG树的分布式服务器集群的设计与实现[D].,厦门:厦门大学,2008.
    [4] W.Richard Stevens,UNIX网络编程卷一:套接字联网API(第三版)[M],北京:人民邮电出版社,2010.
    [5] W.Richard Stevens,UNIX环境高级编程(第二版)[M],尤晋元等译,北京:人名邮电出版社,2006.
    [6] MySQL官方网站,http://www.mysql.com/.
    [7] 章文嵩. LVS项目介绍[Z],http://www.linuxvirtualserver.org/zh/lvs1.html,2002.
    [8] 李大夜. 基于Linux的集群和心跳设计[D],哈尔滨:哈尔滨工业大学,2006.
    [9] 章文嵩. LVS集群的负载调度[Z],http://www.linuxvirtualserver.org/zh/lvs4.html,2002.
    致谢语大学本科生活即将结束,回首总结这四年的求学生涯,许多老师、同学和朋友给予了我真诚、无私的指导和帮助,在此我要表示我最真挚的感激和谢意。
    首先,我要衷心感谢指导我完成毕业设计的老师。老师对我们认真负责,严格要求,从课题确定到最后论文的定稿,为我们倾注了许多的心血与汗水。在毕业设计期间,老师每周都抽出时间与我们讨论,了解我们毕设的进展,并提出了许多宝贵的建议和意见。正是由于老师的严格要求和悉心指导,本文才得以顺利完成。
    其次,我要感谢在这四年里教导我的所有老师们,是你们的辛苦付出让我在计算机学科道路上不断成长,不断成熟。
    感谢实验室里的几位学长,在毕业设计中给了我很大的支持。
    最后,特别感谢我的父母和家人,一直以来你们给予了我最大的关爱和帮助。在这二十年的学习生活中,正是因为有了你们作为我的坚强后盾,我才能在人生道路上一往无前,也正是有了你们,在我遇到挫折的时候,你们给了我避风的港湾。
    1  留言 2020-09-02 21:51:32

发送私信

走在一起是缘分,一起在走是幸福

18
文章数
20
评论数
eject