xiaoya的资源

  • 基于guns开源框架的小区管理信息系统

    1 需求分析1.1 需求分析本系统的最终用户为系统管理员和小区住户。该系统的成功开发,将可以巨大便利系统管理员对住户信息的统计与管理。根据查询资料及对相关人员的咨询,我们讨论分析,得出小区管理员和小区住户对本系统的实际要求:
    1.1.1 小区资源的基本信息小区管理员应对小区可用资源得信息进行及时地完善和更新,对小区内所有住房的居住情况和车位的租借情况统计整理,并向有需求的住户提供有效信息和便利服务。
    住房居住的基本信息
    小区管理员应对小区内所有住房被使用情况进行实时地完善与更新,以方便有需求的住户使用。这些住房信息应该包括住房号码,住房状态(使用状态和空闲状态),住房地址,住房所属区域。
    车位租借的基本信息
    小区管理员应对小区内的所有车位租借情况进行实时地完善与更新,以方便有需求的住户租借。车位租借的情况应包括车位号码,车位地址,租借状态(使用状态和空闲状态)
    1.1.2 小区住户的基本信息当住户入住该小区后,通过手机端APP,登记住户个人信息,以方便小区管理员对住户进行管理,与住户进行必要的业务交流。住户需要登记以下信息。
    住户登录的基本信息
    登录手机APP时,每位住户通过注册自己的手机号码和登录密码来获得小区 服务的权限,而系统会为每位住户指定一个唯一的用户ID,用于后台信息的 统计和管理。
    小区住户的基本信息
    每位小区住户都具有必要注册的个人信息,以保证小区内住户个人信息的完 整性,确保小区住户们的安全,其中包括系统为每位住户指定的唯一ID,身 份证号码,姓名,性别,手机号码,年龄,民族,职业,住房号码,登录APP 密码。
    1.1.3 用户对系统的要求1.1.3.1 小区住户
    信息要求

    小区住户需要及时得到小区空闲住房的信息,可租借车位的信息,租借车位需要租借时间,租借时长,支付费用等信息,需要得到小区官方的公告通知,需要对自己提交的投诉,报修或建议等事务查询官方回复
    处理要求

    注册和维护自己的登录信息和个人的基本信息。并要求因注册手机号的不同,系统为其再指定一个用于后台数据库操作的唯一ID注册个人信息时,通过获得小区管理员提供的未被注册的空闲住房,选定其中一个注册。小区管理员也可以根据这一操作,既是录入信息并更新住房信息住户可以随时更新公告信息,得到小区管理员的通知住户可以提出投诉,报修和建议等事务请求。提交事务后,便可以随时查看提交事务的实时信息及官方回复情况住户可以根据小区管理员提供的剩余车位信息,并租借一个想要的车位。系统将会提供该车位的信息,住户也可以停止租借该车位,同时支付必要的租用车位的费用
    安全性与完整性要求

    安全性要求
    系统应设计根据手机端APP提交的手机号和对应的密码鉴别是否是合法的用户,若不是,应拒接登陆请求。在住户注册个人的同时,应提醒注册登录密码信息每当手机端APP向服务器API发出数据库操作请求时,都需要提前申请token秘钥,以保证每次操作都是合理的
    完整性要求
    根据实体完整性的要求,各种主要信息记录要保持完整性,即内容不能为空各种数据间相互的联系要保持正确性相同的数据在不同记录中要保持一致性。


    1.1.3.2 小区管理员
    信息要求

    小区管理员应需要录入小区可用资源的所有必要信息,例如空闲住房和空闲车位等,可以查看小区所有住户的个人信息和登录APP信息,还需要根据小区的实际情况,具有可公告的信息,需要可以接收小区住户的投诉,报修建议等事务信息,并具有及时回复的信息
    处理要求

    创建和维护小区管理员的登录信息根据小区住户提交的注册请求,创建和维护住户们的登录信息和个人信息发布公告信息,根据小区的实时情况,通知小区住户们必要的生活信息提供住房被使用的信息。在小区住户们注册个人信息时,需根据小区管理员提供的住房信息,注册未被正在使用的住房进行注册操作,小区管理员可根据住户操作及时更新小区住房的情况提供车位租借情况的信息。小区应向住户们提供车位正被使用的情况信息,以方便住户们租借空闲车位。小区管理员在接收到住户们的租借车位请求时,需要及时更新小区车位信息,以方便他人租借。住户可以随时停止租借车位,同时需要支付租借车位所需要的费用,系统也会提供给住户本次租借车位操作的信息
    安全性要求

    系统应要求小区管理员登录时,需要验证登录账号和登录密码正确且对应,以确保整个系统的安全性住户每次通过手机APP先服务器API发出操作请求时,所需要的token秘钥,需要小区管理员授权与分配,并实时更新授权秘钥

    1.2 系统功能的设计和划分根据如上得到的用户需求,我们将本系统按照所完成的功能分成以下两部分:
    1.2.1 用户部分
    注册个人信息
    根据手机号与登录密码登录
    发起投诉或报修
    查看发起的投诉或报修
    查看剩余车位的数量
    租用车位
    结束租用车位
    获得最新的一条公告

    1.2.2 管理员部分
    注册新的管理员
    根据账号密码登录管理平台,登记查看修改删除小区人员信息
    登记查看修改删除小区租房信息
    登记查看修改删除车位信息
    解决报修或投诉
    查看租借信息
    发布查看修改删除通知信息
    查看统计信息

    1.3 数据流图1.3.1 总数据流图总数据流图如图所示:

    1.3.2 各子系统的分数据流图房间信息分数据流图如图所示:

    用户信息分数据流图如图所示:

    通知信息分数据流图如图所示:

    车位信息分数据流图如图所示:

    租借信息分数据流图如图所示:

    报修投诉信息分数据流图如图所示:

    管理员信息分数据流图如图所示:

    2 系统的设计与实现2.1 系统框架简介本系统基于guns开源框架。框架基于SpringBoot 2,整合springmvc + mybatis-plus + echarts。Spring Boot是一种JAVA框架,旨在尽可能快地启动和运行,只需最少的Spring前端配置。Spring MVC属于SpringFrameWork的后续产品,已经融合在Spring Web Flow里面。Spring 框架提供了构建 Web 应用程序的全功能 MVC 模块。MyBatis是一个支持普通SQL查询,存储过程和高级映射的优秀持久层框架。MyBatis消除了几乎所有的JDBC代码和参数的手工设置以及对结果集的检索封装。MyBatis可以使用简单的XML或注解用于配置和原始映射,将接口和Java的POJO(Plain Old Java Objects,普通的Java对象)映射成数据库中的记录。Echarts缩写来自Enterprise Charts,商业级数据图表,它最初是为了满足公司商业体系里各种业务系统的报表需求。
    关于系统架构采用的是MVC架构 ,它全名是Model View Controller,是模型(model)-视图(view)-控制器(controller)的缩写,一种软件设计典范,用一种业务逻辑、数据、界面显示分离的方法组织代码,将业务逻辑聚集到一个部件里面,在改进和个性化定制界面及用户交互的同时,不需要重新编写业务逻辑。其逻辑图如下图所示:


    视图:将视图层存放在PeopleManage\src\main\webapp中,其子文件夹static\modular存放各个业务功能的JavaScript代码,另一个子文件夹WEB-INF\view 存放各个业务功能的HTML代码
    控制器:将控制器存放在PeopleManage\src\main\java\cn\stylefeng\guns\modular的各个业务功能的controler文件夹中
    模型:将模型存放在PeopleManage\src\main\java\cn\stylefeng\guns\modular\system\model中,各个模型通过其对应的Mapper.xml进行需要的sql查询,通过Mapper接口类来调取Mapper.xml,sql查询的结果。若模型的业务逻辑复杂,将多增加对应的Service类来组合形成更复杂的业务逻辑,使业务逻辑更清晰有条理

    2.2 业务的实现本系统的增删查改模式基本都类似,只是有些具体的业务有不同的需求,系统会有相应的处理,总体框架是没有变的。现在以住房管理为例,详细说明本系统增删查改的逻辑。
    2.2.1 信息列表的显示首先用户看到的应该是住房管理的主页面,如图所示:

    本界面存储在 PeopleManage\src\main\webapp\WEBINF\view\room_info\info\info.html
    其HTML代码如下:
    <div class="ibox float-e-margins"> <div class="ibox-title"> <h5>住房管理</h5> </div> <div class="ibox-content"> <div class="row row-lg"> <div class="col-sm-12"> <div class="row"> <div class="col-sm-3"> <#NameCon id="condition" name="名称" /> </div> <div class="col-sm-3"> <#button name="搜索" icon="fa-search" clickFun="Info.search()"/> </div> </div> <div class="hidden-xs" id="InfoTableToolbar" role="group"> @if(shiro.hasPermission("/info/add")){ <#button name="添加" icon="fa-plus" clickFun="Info.openAddInfo()"/> @} @if(shiro.hasPermission("/info/update")){ <#button name="修改" icon="fa-edit" clickFun="Info.openInfoDetail()" space="true"/> @} @if(shiro.hasPermission("/info/delete")){ <#button name="删除" icon="fa-remove" clickFun="Info.delete()" space="true"/> @} </div> <#table id="InfoTable"/> </div> </div> </div>
    表格显示的位置在<#tableid=”InfoTable”/>,表格由其对应的JavaScript向Controller发出请求获得数据。控制住房管理的JavaScript存放在 PeopleManage\src\main\webapp\static\modular\room_info\info\info.js 中。
    其代码如下:
    /** * 住房管理初始化 */ var Info = { id: "InfoTable", //表格id seItem: null, //选中的条目 table: null, layerIndex: -1 }; /** * 初始化表格的列 */ Info.initColumn = function () { return [ {field: 'selectItem', radio: true}, {title: '区域标识号', field: 'room_id', visible: true, align: 'center', valign: 'middle',width:"100px"}, {title: '名称', field: 'name', visible: true, align: 'center', valign: 'middle'}, {title: '地址', field: 'address', visible: true, align: 'center', valign: 'middle'}, {title: '类型', field: 'type', visible: true, align: 'center', valign: 'middle', formatter: function(value,row,index){ if(row.type==true) { value='<div style="text-align: center;" ><i class="fa fa-bed"></i> 房间</div>'; } else value='<div style="text-align: center;" >区域</div>'; return value ; }}, {title: '父节点', field: 'parent_id', visible: false, align: 'center', valign: 'middle'} ]; }; $(function () { var defaultColunms = Info.initColumn(); var table = new BSTreeTable(Info.id, "/info/list", defaultColunms); table.setExpandColumn(2); table.setIdField("room_id"); table.setCodeField("room_id"); table.setParentCodeField("parent_id"); table.setExpandAll(true); table.init(); Info.table = table; });
    JavaScript页面中的表格控制工具BSTreeTable向Controler发出请求,请求地址为info/list,Controler接收到请求后返回所需的信息,BSTreeTable根据后端返回的信息对后端返回的信息进行处理,table.init初始化函数对返回的数据进行处理,formatter函数对房间类型进行处理,当房间类型为1时显示为房间,当房间类型为0时显示为区域。
    房间管理的控制器位置在 PeopleManage\src\main\java\cn\stylefeng\guns\modular\room_info\controller\InfoController.java,控制器收到/info/list请求地址后执行list函数,list函数调用infoService.list方法后返回房间管理的列表,再使用RoomWarpper处理数据,最后返回给BSTreeTable显示到前端页面中。控制器代码如下:
    /** * 住房管理控制器 */ @Controller @RequestMapping("/info") public class InfoController extends BaseController { private String PREFIX = "/room_info/info/"; /** * 获取住房管理列表 */ @RequestMapping(value = "/list") @ResponseBody public Object list(String condition) { List<Map<String, Object>> list = this.infoService.list(condition); return super.warpObject(new RoomWarpper(list)); } } infoService中的list方法,在InfoMapper.xml中实现,其代码如下所示: <select id="list" resultType="map"> select * from info_room <if test="condition != null and condition != ''"> where address like CONCAT('%',#{condition},'%') </if> </select>
    经过上述各个步骤,数据才能从数据库中取出来,放到前端界面进行展示。
    2.2.2 新增信息在info.html页面点击添加按钮,info.javascrpit会向控制器发送一个添加请求,请求地址为/info/info_add,其代码如下所示:
    Info.openAddInfo = function () { var index = layer.open({ type: 2, title: '添加住房', area: ['800px', '420px'], //宽高 fix: false, //不固定 maxmin: true, content: Feng.ctxPath + '/info/info_add' }); this.layerIndex = index; };
    当InfoController接收到/info/info_add请求后会返会info_add.html页面,其代码如下所示:
    @RequestMapping("/info_add") public String infoAdd() { return PREFIX + "info_add.html"; }
    info_add.html页面如图所示:

    控制此页面的JavaScript是info_info.javascript,其主要代码如下所示:
    /** * 初始化住房管理详情对话框 */ var InfoInfoDlg = { infoInfoData : {} }; /** * 收集数据 */ InfoInfoDlg.collectData = function() { this .set('roomId') .set('type') .set('name') .set('parentId') .set('address') } /** * 提交添加 */ InfoInfoDlg.addSubmit = function() { this.clearData(); this.collectData(); //提交信息 var ajax = new $ax(Feng.ctxPath + "/info/add", function(data){ Feng.success("添加成功!"); window.parent.Info.table.refresh(); InfoInfoDlg.close(); },function(data){ Feng.error("添加失败!" + data.responseJSON.message + "!"); }); ajax.set(this.infoInfoData); ajax.start(); }
    当用户填完所有信息,点击提交按钮时,会向后端送请求,请求地址为info/add,参数为填写的信息。
    当InfoControler接收到此信息时会调用add函数,add函数会判断其是不是顶层区域,如果是顶层区域,此房间的地址就是房间名,如果不是顶层区域,此房间的地址就是上一层房间的地址再加上此房间名。然后使用mybatis简化的插入方法,infoService.insert(info)函数将信息插入到数据库中。其实现代码如下所示:
    @RequestMapping(value = "/add") @ResponseBody public Object add(Info info) { if(info.getParentId()!=0) info.setAddress(infoService.selectById(info.getParentId()).getAddress()+info.getName()); else info.setAddress(info.getName()); infoService.insert(info); return SUCCESS_TIP; }
    2.2.3 修改信息在info.html选中一条记录,再在页面点击修改按钮,info.javascrpit会找到选择记录的id,然后向Controller发送修改请求,请求地址info/info_update,当请求完成后打开新的子页面,如图其代码如下所示:
    Info.openInfoDetail = function () { if (this.check()) { var index = layer.open({ type: 2, title: '住房详情', area: ['800px', '420px'], //宽高 fix: false, //不固定 maxmin: true, content: Feng.ctxPath + '/info/info_update/' + Info.seItem.id }); this.layerIndex = index; } };
    当控制器接收到修改请求后,先根据选中条目id获得完整的房间信息,然后将信息注入到info_edit.html页面中,然后再返回info_edit.html页面。其代码实现如下所示:
    @RequestMapping("/info_update/{infoId}") public String infoUpdate(@PathVariable Integer infoId, Model model) { Info info = infoService.selectById(infoId); model.addAttribute("item",info); if(info.getParentId()!=0) model.addAttribute("pName", infoService.selectById(info.getParentId()).getName()); else model.addAttribute("pName","顶级"); LogObjectHolder.me().set(info); return PREFIX + "info_edit.html"; }
    info_edit.html界面如下图所示:

    当修改成功后,info_info.html会收集用户更改的信息,然后向控制器发送更改请求,请求地址为/info/update其代码如下:
    InfoInfoDlg.editSubmit = function() { this.clearData(); this.collectData(); //提交信息 var ajax = new $ax(Feng.ctxPath + "/info/update", function(data){ Feng.success("修改成功!"); window.parent.Info.table.refresh(); InfoInfoDlg.close(); },function(data){ Feng.error("修改失败!" + data.responseJSON.message + "!"); }); ajax.set(this.infoInfoData); ajax.start(); }
    当控制器接收到修改请求后先找出原来的房间信息,然后查看房间名有没有被修改过,如果房间名被修改了,那此房间所有的子节点的地址都要修改,这样才能保持地址的正确性,然后使用mybatis提供的更新方法,将新数据更新到数据库中。
    @RequestMapping(value = "/update") @ResponseBody public Object update(Info info) { Info oldinfo=infoService.selectById(info.getRoomId()); String name=info.getName(); String oldaddress=oldinfo.getAddress(); String newaddress; if(info.getParentId()==0)newaddress=name; else newaddress=oldaddress.substring(0,oldaddress.length()-oldinfo.getName().length())+name; info.setAddress(newaddress); infoService.updateById(info); ChangeChildAddress(newaddress,oldaddress,info.getRoomId()); return SUCCESS_TIP; }
    2.2.4 删除信息用户选择某一条记录,然后点击删除按钮,前端会发送一个删除请求到控制器,请求地址为/info/delete其实现代码如下所示:
    Info.delete = function () { if (this.check()) { var ajax = new $ax(Feng.ctxPath + "/info/delete", function (data) { Feng.success("删除成功!"); Info.table.refresh(); }, function (data) { Feng.error("删除失败!" + data.responseJSON.message + "!"); }); ajax.set("infoId",this.seItem.id); ajax.start(); } };
    当控制器接收到删除请求时,先通过TreeTool的removeTreeNode方法找出本房间的所有子节点,方法返回所有子节点的id与自己的id,然后通过返回的所有id删除房间信息。
    @RequestMapping(value = "/delete") @ResponseBody public Object delete(@RequestParam Integer infoId) { List<Integer> list= TreeTool.removeTreeNode(infoService.list(null),infoId); for(Integer i :list) infoService.deleteById(i); return SUCCESS_TIP; }
    3 结论和展望在这次的课程设计中,我花费了很多的心思与精力。只要努力就有收获,这个成品我还是比较满意的。在这个过程中,我不但对JAVA Springboot2框架和数据库有了深刻的认识和了解,同时还学会了自学与独立思考的能力。此外,在我所负责的领域中,还有几个地方考虑不足:

    报修与投诉管理员回复一次默认已经解决了问题,但是实际情况可能需要管理员多次与住户进行交流才能够完全解决问题
    租借流程中缺少管理员对租借的确认,如果系统分配的车位因为一些不可预知的原因不能租借,管理员不能及时反馈给用户
    通知信息无法插入图片
    插入信息没有控制其格式,可能会导致插入失败

    我会根据上述说的不足加以改进,使系统更人性化。
    参考文献[1] 王珊,数据库系统概论[M].高等教育出版社, 2014.
    [2] 埃克尔,JAVA编程思想(第4版)[M].机械工业出版社, 2007.
    [3] 杨开振,深入浅出SpringBoot 2.x[M].人民邮电出版社, 2019.
    [4] 朱要光,SpringMVC+MyBatis开发从入门到项目实战[M].电子工业出版社, 2018.
    1  留言 2019-03-26 10:13:53
  • 基于easyx实现的黑白棋游戏

    一 需求分析C语言课程设计,界面结合 秦时明月 中的 墨攻棋阵 ,实现该黑白棋小游戏。
    二 功能说明游戏包含 单人模式、双人模式、联机对战、观战模式 等四种模式,主界面如下图所示。

    游戏对战界面如下图所示:

    三 游戏设计关键思路3.1 局部最优解人机对战中有三种模式:简单、中等、困难,下棋的时候我们总是想着如何才能对自己最有利,当前最优?还是全局最优?
    如果我们往后几步考虑的话,那便是全局最优啦!那当我们只看眼下哪一个位置的落子对自己最有利,这样便是当前最优,也是局部最优。
    在黑白棋中,我们同样可以采用这样的思想。首先来看看简单AI,因为简单呗,所以它返回的仅仅只是当前的最优解,再怎么说也不能让它随机返回坐标对吧!局部最优解我们采用的是能够转换对方棋子最多的位置。
    代码如下所示:
    POINT2 Easy() //人机对战简单AI{ POINT2 MAX; //定义以及初始化最优解 MAX.INIT(0, 0); int maxx = 0; for (int i = 0; i < SIZE; ++i) for (int j = 0; j < SIZE; ++j) { if (expect[i][j] >= maxx) //寻找可以转化棋子最多的点作为最优解 { maxx = expect[i][j]; MAX.INIT(i, j); } } if (ESCEXIT)gameStart(); Sleep(800); //间歇 return MAX; //返回最优解}
    3.2 估值表在黑白棋中,不同位置都有不同位置的估值,虽然这样的估值表的用处并不是很大,但却在某些细节中表现出至关重要的作用。黑白棋的棋盘默认是8*8的,总共64格,从游戏规则我们可以看出来,角上的子很重要,因为这里不会被对方转换,角边上的点很危险,它给了对方直接进角的机会。边上中间的四个点比较重要,只能从一个方向被翻转……等等。
    根据这样的经验,我们大致可以得到以下的估值表:




    A
    B
    C
    D
    E
    F
    G
    H




    1
    90
    -60
    10
    10
    10
    10
    -60
    90


    2
    -60
    -80
    5
    5
    5
    5
    -80
    -60


    3
    10
    5
    1
    1
    1
    1
    5
    10


    4
    10
    5
    1
    1
    1
    1
    5
    10


    5
    10
    5
    1
    1
    1
    1
    5
    10


    6
    10
    5
    1
    1
    1
    1
    5
    10


    7
    -60
    -80
    5
    5
    5
    5
    -80
    -60


    8
    90
    -60
    10
    10
    10
    10
    -60
    90



    有了这张表,AI 进行估值的时候就很简单了。
    3.3 稳定子稳定子,即不能被转换的棋子,稳定子的数量在游戏中是变化的,比如,一方占据整整一条边,那么这一条边上的所有棋子都是稳定子。
    3.4 行动力行动力,某方当前可走位置的个数,因为在黑白棋的游戏规则中,每一步的走棋都要形成转换,否则不能走棋,既然这样的话,我们在AI中便要尽可能让自己的行动力最大,而对方行动力最小,也就是尽可能让双方行动力差最大,这样的话,很容易AI便可以把玩家逼上绝路,玩笑而已……
    3.5 极大极小博弈树搜索这里假设AI的对手都是最聪明的,会选择最优解,即会选择对AI最不利的选择。搜出来的结果集是AI方的结果,那么要选择最终得分最高的那个位置。搜出来的结果集是玩家方的结果,那么要选择最终得分最低的那个位置。
    如下图所示:

    假设圆形代表的是AI节点,方形代表玩家节点。对于A2和A3这两种选择,AI显然是选择A2得10分。对于A4和A4这两种选择,AI显然是选择A4得20分。但是对于B1,B2来说,玩家如果下B2,使得AI可以得20分,下B1,使得AI只能得10分,那么玩家显然是下B1。所以最终A1这一步,AI只能得10分。这就是极大极小算法。
    3.6 α-β剪枝如下图所示:

    现在A2,A3已经选出最大值10,B1的得分是10分。而对于B1,B2来说是要选最小值,既然B1的得分是10分,则B1,B2之间的最终结果是<=10的。而A4的得分是20分,对于A4,A5来说是选择最大值得,即A4,A5之间的最终结果是>=20的,说明B2的最终结果是>=20的。那么这种情况下肯定是选B1了,对于还没有搜索的A5节点来说,已经影响不到最终的选择结果了,所以就可以不用考虑了。
    3.7 本游戏的AI算法int difai(int x,int y,int mapnow[SIZE][SIZE],int expectnow[SIZE][SIZE],int depin,int depinmax) //极大极小搜索{ if (depin >= depinmax)return 0; //递归出口 int maxx = -10005; //最大权值 POINT2 NOW; int expectnow2[SIZE][SIZE] , mapnow2[SIZE][SIZE],mapnext[SIZE][SIZE],expectlast[SIZE][SIZE]; //定义临时数组 copymap(mapnow2, mapnow); //复制当前棋盘 mapnow2[x][y] = NOWCOLOR ? 1 : -1; //模拟在当前棋盘上下棋 int ME = MAPPOINTCOUNT[x][y] + expectnow[x][y]; //当前棋子权 NOW.INIT(x,y); Change(NOW, mapnow2, false); //改变棋盘AI结束 int MAXEXPECT = 0, LINEEXPECT = 0, COUNT = 0; for (int i = 0; i < SIZE; ++i) for (int j = 0; j < SIZE; ++j) { expectnow2[i][j] = Judge(i, j, !NOWCOLOR, mapnow2);//预判对方是否可以走棋 if (expectnow2[i][j]) { ++MAXEXPECT; if ((i == 0 && j == 0) || (i == 0 && j == SIZE - 1) || (i == SIZE - 1 && j == SIZE - 1) || (i == SIZE - 1 && j == 0))return -1800; //如果对方有占角的可能 if ((i < 2 && j < 2) || (i < 2 && SIZE - j - 1 < 2) || (SIZE - 1 - i < 2 && j < 2) || (SIZE - 1 - i < 2 && SIZE - 1 - j < 2))++LINEEXPECT; } } if (LINEEXPECT * 10 > MAXEXPECT * 7)return 1400;//如果对方走到坏点状态较多 剪枝 for (int i = 0; i < SIZE; i++) for (int j = 0; j < SIZE; j++) if (expectnow2[i][j]) //如果对方可以走棋 { int YOU = MAPPOINTCOUNT[i][j] + expectnow2[i][j];//当前权值 copymap(mapnext, mapnow2); //拷贝地图 mapnext[i][j] = (!NOWCOLOR) ? 1 : -1; //模拟对方走棋 NOW.INIT(i, j); Change(NOW, mapnext, false); //改变棋盘 for (int k = 0; k < SIZE; k++) for (int l = 0; l < SIZE; l++) expectlast[k][l] = Judge(k, l, NOWCOLOR, mapnext); //寻找AI可行点 for (int k = 0; k < SIZE; k++) for (int l = 0; l < SIZE;l++) if (expectlast[k][l]) { int nowm = ME - YOU + difai(k, l, mapnext, expectlast, depin + 1, depinmax); maxx = maxx < nowm ? nowm : maxx; } } return maxx;}
    1  留言 2018-11-13 12:16:17
  • 基于Android开发的聊天机器人新闻天气社交APP

    摘要5G网络就快到来了,4G网络已经基本上覆盖了,便捷的网络环境为安卓手机添加更多的精彩丰富的内容提供了良好的平台和基础。目前安卓开发正对我们的生活造成巨大的影响,我们的生活已经离不开如微信、QQ、微博等应用。 这些应用极大的便利了我们的生活,为我们的工作生活带来了很多的乐趣,丰富和充实了我们的生活。该系统是正是利用Android开源平台开发的一款娱乐APP,叫做知心App,利用当今主流的编程语言Java进行代码的编写,利用Google最新开发的Android Studio为开发工具,通过了解安卓平台的系统架构和应用程序开发流程,最终成功开发出了该款应用。该款应用主要包括了人脸识别登录、网易新闻、欧酷天气、图灵机器人、作者个人信息、应用更新等模块。此款应用采用了ButterKnife依赖注入技术、Gson数据解析框架、OkHttp网络处理框架、科大讯飞语音识别技术、图灵机器人技术、一登刷脸登录技术、Bmob登录注册技术、蒲公英应用发布以及自动更新等技术。此款应用严格按照软件开发标准流程进行设计与开发,代码结构清晰,用户体验较好。
    关键词:Android;Android Studio;人脸识别;语音识别;图灵机器人
    Abstract5G network is coming soon, 4G network has basicallycovered, convenient network environment for Android phones to add morewonderful rich content provides a good platform and foundation. At present,Android development is having a huge impact on our lives, our lives have beeninseparable from applications such as wechat, QQ, microblogging. Theseapplications greatly facilitate our lives, bring a lot of fun to our work life,enrich and enrich our lives. This system is just an entertainment app developedby using Android open source platform, called bosom app. it is successfullydeveloped by using Java, the mainstream programming language, and Androidstudio, which is newly developed by Google, as a development tool, throughunderstanding the system architecture and application development process ofAndroid platform. This application mainly includes face recognition login,Netease news, cool weather, turing robot, author’s personal information,application updates and other modules. This application uses button knifedependency injection technology, gson data analysis framework, ok http networkprocessing framework, hkust xunfei speech recognition technology, turing robottechnology, a brush face registration technology, bmob registration technology,dandelion application release and automatic update technology. This applicationis designed and developed in strict accordance with the standard process ofsoftware development, with clear code structure and good user experience.
    Key Words: Android; Android Studio;Face Recognition; Speech Recognition; Turing Robot;
    第1章 绪论1.1 课题背景目前市场上主流的手机操作系统有两种,那就是Android和IOS。Android系统是谷歌开发的并且最重要的是开放源代码,而IOS则是苹果公司研发的,不开放源代码。就当今用户使用手机情况来看,安卓手机占据大约60%的手机市场,而苹果手机大约占30%的市场。全世界的企业大部分还是中小企业,经济能力有限,因此大部分厂商还是喜欢用开源免费的。因此,我的这个应用就是基于Android平台开发的。想必大家都用过智能手机,也用过普通的手机软件,早在五年之前安卓市场非常火爆,但是当时的软件还是非常的普通,完全不具备现在的人工智能与大数据技术。现在的应用都在慢慢的被大数据与人工智能技术所熏陶,比如说微博、微信等应用,各种个性化推荐信息、智能提示非常方便用户使用。
    目前处于人工智能和大数据飞速发展的时代,为了让用户体会到大数据与人工智能的魅力,感受新时代的气息,我在应用中添加了人脸识别和图灵机器人以及语音识别等功能模块。目前提供人脸识别服务的平台比较多,想百度AI平台,阿里云平台,腾讯云平台,Face++,一登等。但是从个人选择上来讲,一登接入比其他的平台简单,并且是免费的。智能聊天机器人采用图灵公司开发的新一代的机器人。语音识别功能采用的是科大讯飞的语音识别技术,相对来说科大讯飞的语音技术在国内应该是顶尖的。这些是具有人工智能功能的应用是传统的应用所无法替代的,因此为了适应时代发展的潮流,我在普通应用的基础之上有了自己的创新。利用最新的Android开发技术结合人工智能技术开发具有良好用户体验以及更加智能的安卓应用。
    1.1.1 人工智能人工智能技术简称AI,它的研究主要是便于机器模拟人的思维,能够像人一样思考,最终利用机器人更好地为人类服务。
    1.1.2 大数据大数据技术,它的研究主要是为了处理当今社会生活中产生的大批量的数据。目前主流的大数据平台有Hadoop和Spark。Hadoop平台主要是支持大批量数据的离线处理,而Spark平台主要是基于内存的高速实时数据流处理。两者在性能上有较大的差距,Spark的处理速度大约是Hadoop的10倍。当然两者分别具有各自的特色,适用于不同的应用场景。
    1.2 目的意义目前正处在人工智能和大数据的时代,为了让用户感受到人工智能的存在,我在应用中添加了人脸识别和图灵机器人以及语音识别等功能模块。这些是传统的应用所不具备的功能,因此我在其基础之上有了自己的创新,让应用更加智能话。具有良好的用户体验是衡量一个安卓应用品质的很重要的标准。只有拥有良好的用户体验的应用才能长期生存下去。新的时代需要不断创新,要把最新的技术运用到Android应用之上,让App具有新意,更加符合人们的使用需求。因此,我设计了这款App帮助用户更好的体验智能化的生活。
    1.3 论文主要工作目前正是人工智能和大数据技术火热的时候,为了在让传统的安卓应用具有新时代的特点,我在本次开发中加入了一些人工智能的元素,希望能给用户带来全新的用户体验。
    本课题的主要开发流程包括需求分析、概念设计、详细设计、编码测试、应用上线。需求分析阶段主要采用市场调研和问卷调查两种方式。概念设计阶段主要是总体结构设计,采用MVP三层架构技术。其中详细设计阶段主要设计应用的各个功能模块,如引导页模块、登录注册模块、网易新闻模块、图灵机器人模块、开发者个人信息模块、应用更新等模块。编码实现阶段采用Java语言开发,运用AndroidStudio开发工具进行开发。后期的编码测试采用真机测试,记录日志信息,修复Bug。应用开发完成后,进行应用打包,最后发布到蒲公英应用发布平台。
    第2章 相关技术和理论基础2.1 技术与理论基础在此应用中主要用到了ButterKnife依赖注入框架、Gson数据解析框架、OkHttp网络处理框架。
    2.1.1 ButterKnife依赖注入框架1.ButterKnife概念
    Annotate fields with @BindView and a view ID for ButterKnife to find and automatically cast the corresponding view in your layout.
    2.项目配置
    在AndroidStudio Module中的build.gradle中添加以下依赖:

    compile’com.jakewharton:butterknife:8.8.1’
    annotationProcessor’com.jakewharton:butterknife-compiler:8.8.1’

    3.示例代码

    2.1.2 Gson框架1.Gson概念
    Gson(又称Google Gson)是Google公司发布的一个开放源代码的Java库,主要用途为序列化Java对象为JSON字符串,或反序列化JSON字符串成Java对象。
    2.项目配置
    在AndroidStudioModule中的build.gradle中添加以下依赖:

    compile’com.google.code.gson:gson:2.8.2’
    2.1.3 OkHttp网络框架1.OkHttp概念
    AnHTTP & HTTP/2 client for Android and Java applications.
    2.项目配置
    在AndroidStudio Module中的build.gradle中添加以下依赖:

    compile ‘com.squareup.okhttp3:okhttp:3.10.0’
    3.示例代码

    2.2 技术与理论基础在此应用中主要用科大讯飞语音识别技术、图灵机器人技术、一登刷脸登录技术、Bmob登录注册技术、蒲公英应用发布以及更新、GitHub项目管理等技术。
    2.2.1 科大讯飞语音识别与图灵机器人
    语音识别的概念
    语音识别包括听写、语法识别功能。语音识别技术就是把人说的话转换成相应的文本数据。语法识别是基于语法规则,将与语法一致的自然语言音频转换为文本输出的技术。
    科大讯飞开发者文档:http://doc.xfyun.cn/msc_android/index.html
    图灵机器人的概念
    图灵机器人是图灵公司开发一款机器人,具备与人交流的能力,可以和人进行简单的对话。主要应用领域是聊天机器人、客服机器人和服务机器人。
    图灵机器人开发者文档:https://www.kancloud.cn/turing/web_api/522992

    2.2.2 Bmob后端服务平台以及蒲公英应用平台
    Bmob后端服务平台Android开发者文档:http://doc.bmob.cn/data/android
    蒲公英开发者文档:http://www.pgyer.com/doc/view/sdk_android_guide

    2.2.3 GitHub项目管理工具
    GitHub网址:https://github.com
    Git 常用命令

    git init //初始化项目git status //查看项目状态git add //添加文件到 git 追踪列表里git commit //提交到本地仓库git log //提交记录git clone //复制项目到本地git branch //查看或者创建分支
    git branch net //创建net分支git branch -d net //删除分支
    git checkout //签出一个分支或者一个路径,在开发中常用于分支切换和恢复文件
    git checkout net //切换net分支:git checkout — SayHello.java //恢复文件
    git merge //合并分支
    git merge net //合并net分支
    git tag //列出项目的标签和创建项目的标签
    git tag -a v1.0 -m “这里写相关信息” //为版本打一个标签git show 标签名 //来查看该分支的具体信息
    git help //帮助git push //推送
    git push 仓库名 分支名git push origin master:master 或git push origin master //本地master分支提交到origin的master分支,分支相同的可简写
    git push origin :net //删除origin仓库的net分支git pull //更新最新的代码git ignore //忽略文件fork //远程复制别人的仓库到自己的仓库

    示例代码

    第3章 系统分析(需求分析)3.1 功能需求分析随着大数据、人工智能的迅速发展,我们的生活变得越来越便利。传统的应用只能通过账号密码来登录,用户体验不是太好。而如今的App变得越来越智能化了,比如支付宝、淘宝、微信等。支付宝现在正运用最先进的大数据与人工智能技术开启了刷脸登录与刷脸支付的时代。为了让App具有新时代的特点,不得不运用大数据与人工智能的技术,这也是未来发展的趋势。经过市场的调查,发现当前大部分的应用还是不具备新时代的特点,因此我觉得我这个项目是符合市场需求的。
    3.1.1 用户需求分析此软件要求能够运行在Android 5.0以上的系统终端上,相对来说使用群体还是占据很大一部分,但是用户对软件也有一定的要求:

    简单易学
    运行稳定
    操作简单

    3.1.2 功能需求分析本项目应当具有以下功能:

    应用引导页、欢迎页
    账号密码登录、注册
    刷脸登录
    网易新闻
    图灵机器人
    欧酷天气
    开发者个人信息
    应用更新
    应用打包发布

    3.2 非功能需求分析
    开发环境为Android Studio
    要求系统响应不超过3秒
    要求应用兼容Android 5.0以上的主流手机平台
    多渠道打包

    3.3 可行性分析3.3.1 经济可行性本软件基于开源的Android系统开发,采用Android Studio免费软件进行开发,运用第三方平台提供的免费服务实现特定功能,开发成本相对较低。
    3.3.2 技术可行性


    Windows版本
    Windows 10 家庭版64位




    Android Studio版本
    3.1.1


    Android编译SDK版本
    26


    Android测试版本
    华为荣耀青春版(Android7.0)


    Gradle版本
    4.4


    Maven版本
    3.5.3


    Git版本
    2.16.2



    本软件基于开源的Android系统开发,使用主流的编程语言Java进行编码,因此该软件在技术上可行。
    3.3.3 操作可行性该软件采用主流的Android软件应用开发风格,并使用Google 全新的设计语言Material Design,界面友好,简单易懂,为用户带来全新的视觉体验。
    第4章 系统设计4.1 总体设计系统结构图

    MVP架构图

    4.1.1 功能模块图该软件的功能模块图如下:

    4.1.2 用例图
    4.1.3 数据流图
    4.2 详细设计
    对于引导页模块,采用图片滑动形式,引导用户了解如何使用该软件以及相关的功能
    对于登录模块,采用两种登录方式:账号密码登录和刷脸登录。账号密码登录的话采用Bmob后端云数据库实现,刷脸登录采用的是一登刷脸服务
    对于注册模块,同样采用的是Bomb后端云数据库
    对于网易新闻模块,采用的是网易新闻的接口
    对于欧酷天气模块,采用的是天气预报的接口
    对于图灵机器人模块,采用的图灵智能机器人的接口
    对于开发者个人信息模块,采用列表显示出来
    对于应用更新模块,采用蒲公英应用发布平台的App更新技术

    4.2.1 登录注册模块登录模块处理逻辑如下:

    用户输入账号密码进行登录
    通过回调函数获取登录返回结果
    根据返回结果判断登陆是否成功,若登录成功则显示用户信息,否则提示登录失败
    登陆成功将用户的姓名和电话显示出来

    注册模块处理逻辑如下:

    用户输入账号密码进行注册
    通过回调函数获取注册返回结果
    根据注册返回结果判断是否注册成功,若注册成功则返回登录页面,否则提示注册失败

    4.2.2 网易新闻模块网易新闻模块处理逻辑如下:

    通过天气接口的URL获取返回的JSON数据
    将JSON数据转换为News对象
    将数据显示在页面上

    4.2.3 图灵机器人模块图灵机器人模块的处理逻辑如下:

    将语音数据转换为文本数据
    通过图灵接口的URL获取返回的JSON数据
    将JSON数据转换为TalkBean对象
    获取对象中的内容,再将其转换为语音输出

    4.2.4 欧酷天气模块欧酷天气模块处理逻辑如下:

    通过城市URL获取城市JSON数据
    将JSON数据转换为城市对象
    通过天气URL获取天气JSON数据
    将天气JSON数据转换为天气对象
    在页面显示天气信息

    4.2.5 引导页、欢迎页模块引导页、欢迎页模块处理逻辑如下:

    判断应用是不是第一次打开
    判断本地数据库是否有记录,若是第一次打开的话则显示引导页,并将记录写到本地数据库
    否则直接进入欢迎页

    4.2.6 开发者详情模块开发者详情模块处理逻辑如下:

    直接加载布局文件的内容显示出来
    4.2.7 应用更新模块应用更新模块的处理逻辑如下:

    点击检测更新按钮
    系统比较本地版本和服务器上的版本
    若本地版本等于服务器版本,则提示用户“您的应用已是最新版本!”
    若本地版本低于服务器版本,则提示用户“检测到新版本,是否更新?”
    若用户点击“取消”,则退出更新
    若用户点击“确定”,则后台服务自动下载应用更新包
    下载完成后,系统提示用户是否立即安装
    若用户点击“取消”,则退出安装程序
    若用户点击“确定”,则等待安装完成

    第5章 系统实现与测试5.1 系统实现该项目主要包含引导页模块、登录注册模块、网易新闻模块、图灵机器人模块、开发者个人信息模块、应用更新等模块。各个模块的设计与实现如下:
    5.1.1 登录、注册模块实现登录模块流程图如下:

    登录模块主要代码如下:


    注册模块流程图如下:

    注册模块代码如下:

    5.1.2 图灵机器人模块实现图灵机器人流程图如下:

    图灵机器人实现代码如下:
    语音识别函数

    语音合成函数

    语音处理适配器类

    语音处理适配器类(续)

    5.1.3 网易新闻模块实现网易新闻模块流程图如下:

    网易新闻模块主要代码实现:

    5.2 系统测试该系统为安卓项目,测试采用华为荣耀8真机,安卓系统版本为7.0。主要包括账号登录、刷脸登录、注册、语音对话、获取新闻信息、获取城市信息、获取天气详细信息、开发者个人信息展示、应用更新等功能的测试。
    5.2.1 登录注册功能测试账号登录测试

    测试账号:187xxxx9552
    测试密码:1234
    测试截图如下:


    刷脸登录测试

    5.2.2 图灵机器人、网易新闻模块测试图灵机器人对话测试

    网易新闻测试效果图

    5.2.3 欧酷天气模块测试欧酷天气城市列表测试效果图


    第6章 总结和展望6.1 本文总结这个项目大概花了一个多月的时间才弄完的,查阅各种资料,虽然中途出现了各种问题,但是最终收获还是很多的。刚开始做这个项目的时候,搭建各种环境花费了一番功夫,好在之前自学了一段时间的安卓,最后顺利把环境搭建好了。这个项目主要包含了账号密码登录、刷脸登录、账号密码注册、网易新闻、图灵机器人、欧酷天气、开发者详情、应用更新等模块。其中涉及到的技术主要有ButterKnife注解、Gson数据解析、OkHttp网络处理、Bmob后端云数据库、一登人脸识别、图灵机器人、科大讯飞语音识别、蒲公英应用发布与自动更新。在上学期学的安卓知识终于派上用场了,这次的项目总体来说还是不错的,加入了新时代的元素,比如说人工智能和大数据。人工智能和大数据是目前最火的技术,代表了未来发展的趋势,因此我在项目里加入了这些元素。项目开发一个很重要的问题就是规范,开发必须要按照标准的流程来,制定相应的代码规范,这样才能有效地减少开发人员的代码修改。在这次开发中,我引进了项目源代码管理仓库GitHub,将开发过程记录到其中了。GitHub是一个团队开发利器,可以方便的进行代码管理和并行开发,有效减少了代码之间的复制。在开发这个项目的时候遇到了一些比较莫名其妙的问题,有一些是依赖包的版本问题,还有一些是android系统版本的问题。我到现在也还没有把安卓手机兼容性问题解决掉,这个问题有点棘手,市场上的手机种类太多了。在刚开发安卓项目的时候,只知道去百度找资料,那时候还不会翻墙,不知道去谷歌搜索。后来学会了翻墙技术,就可以去谷歌查找更加专业的资料了,身为一个程序员只会百度的话那也太低级了。在遇到问题的时候,先去查看运行输出的错误日志,然后根据错误信息分析错误原因在哪里,最后才百度或者谷歌看看别人如何解决的。在这次项目开发中,发现自己还有许多不足之处,希望在日后不断学习,能够有所改善。本次项目依然存在许多不足之处,比如说程序安全性和健壮性不够,操作界面不够美观,功能不够完善,代码结构不够清晰。希望在以后的工作中能够做得更好。
    6.1.1 项目管理总结项目管理工具目前主流的是SVN和GitHub,个人推荐还是GitHub比较好用。
    6.1.2 项目中遇到问题如何解决遇到问题,首先分析错误日志,然后分析错误的可能原因,最后看书或者去网上搜索找到解决方案。
    6.1.3 如何获取开发方面的优质资源推荐几个学习网站:StackOverFlow,掘金,简书,慕课,网易云课堂。
    6.2 未来展望希望在以后的学习中能够学会更多的技术,比如目前流行的大数据与人工智能技术。利用大数据技术与人工智能技术让移动应用更加智能化,更加便利我们的生活。本系统还存在许多不足之处,比如说功能方面还可以更加完善,性能上还有待提高,由于时间关系,来不及全部完成。
    6.2.1 可添加的功能
    根据定位自动获取并显示天气信息
    利用QQ、微信或者其他第三方平台登录
    添加好友聊天功能
    语音唤醒机器人
    百度地图定位当前位置
    二维码识别、生成
    文本、图片识别

    6.2.2 解决兼容性问题由于Android系统版本较多,不同的手机获取资源对应的包不同,以及不同手机尺寸的不同,所以会出现部分手机闪退现象。希望在以后学习更多的知识后能够解决这个问题。
    参考文献[1]李刚. 疯狂 Android 讲义[M]. 北京:电子工业出版社,2013:25-42.
    [2]杨丰盛. Android 技术内幕[M]. 北京: 机械工业出版社,2011:77-89.
    [3]杨云君. Android 的设计与实现[M]. 北京:机械工业出版社,2013:45-49.
    [4]柯元旦. Android 内核剖析[M]. 北京:电子工业出版社,2011:59-70.
    [5]丰生强. Android 软件安全与逆向分析[M]. 北京:人民邮电出版社,2013:78-90.
    [6]余成锋,李代平,毛永华. Android3.0 内存管理机制分析[M]. 计算机应用与软件,2013:55-80.
    [7]佐冰冰. Android 平台下 Launcher 启动器的设计与实现[D]. 哈尔滨工业大学,2012:108-150.
    [8]杜吉志,徐明昆. Android 系统内存管理研究及优化[J]. 软件,2012,24(5):69-80.
    [9]马越. Android 的架构与应用[D]. 北京:中国地质大学,2008:330-357.
    [10]姚昱旻,刘卫国. Android 的架构与应用开发研究[J]. 计算机系统应用,2008,77(11):99-111.
    [11]高巍. Android 操作系统软件自动化测试方案的设计与实施[D]. 北京:北京邮电大学,2012:440-479.
    [12]孙剑. Android 系统上应用程序按需加载机制的设计与实现[M]. 北京大学,2011:99-110.
    [13]卢娜. 基于 Android 平台的手机桌面资讯系统的设计与实现[M]. 西安电子科技大学,2011:290-300.
    [14]高焕堂. Google Android 应用框架原理与程序设计 36 计[M].Misoo,2010:8-13.
    [15]钟茂生,王明文. 软件设计模式及其使用[J].计算机应用,2002,22(8):32-33.
    [16] Gartner November Report[EB/OL].http://www.gartner.com/newsroom/id/2482816, 2013
    [17] B. John. A binary analysis ofresultatives[C]. In Proceedings of Texas Linguistics Society Conference (TLSC),Stanford, California, USA, 1997, 43-58
    5  留言 2018-11-13 12:14:09
  • 二叉树应用

    1 项目要求
    建立一棵二叉树前序、中序、层次非递归遍历该二叉树判断该二叉树是否为二叉排序树如果是二叉排序树,进行结点的插入或删除输出结果
    2 解题思路首先设计一个结构体,确定需要输入的数据类型,再设计一个结构体,用来存放左右孩子的指针。输入数据建立一个二叉树,首先输入左子树的数据,以‘0’以表示最后的数据作为叶子结点,再输入右子树,并以同样的方式结尾,构成二叉树。接下来进行二叉树的非递归的先序、中序、层次遍历。然后判断该树是否为二叉排序树,则先判断是否是空树,是则不是二叉排序树,不是则递归调用并且遍历左子树,检查左子树是否符合二叉排序树,一旦发现有数据大于根节点,则不是二叉排序树;若没有,则遍历右子树,检查右子树是否符合二叉排序树特征,有发现数据小于根节点,则不是二叉排序树,如果两者都不是,此二叉树就是二叉排序树。在判断为二叉排序树后,调用查找函数,插入数据,以及删除数据。
    3 函数调用图
    4 数据介绍4.1 各函数功能// 创建二叉树int createTree(BitTree *T);// 非递归先序遍历int preOrder(BitTree T);// 非递归先序遍历int preOrder(BitTree T);// 非递归层次遍历int levelPrint(BitTree T);// 判断是否为二叉树int judge(BitTree T);// 查找节点int searchBst(BitTree T, BitTree G, Elemtype key, BitTree *p);// 二叉排序树插入int insertBst(BitTree T, Elemtype key);// 删除二叉排序树int deleteBst(BitTree *T, int key);// 删除节点int Delete(BitTree *p);// 主函数,流程控制int main();
    5 测试









    6 源代码#include<stdio.h>#include<stdlib.h>#include<malloc.h>#include<stdbool.h>typedef int Elemtype;typedef struct { Elemtype e;}Elem;typedef struct BitTree { Elem data; /*定义数据*/ struct BitTree *lChild, *rChild; /*定义左右孩子指针*/}BitNode, *BitTree;BitNode *T = NULL;int createTree(BitTree *T) { /*创建二叉树*/ Elemtype ch; scanf("%d", &ch); if(ch == 0) { /*0表示空树*/ *T = NULL; } else { *T = (BitTree)malloc(sizeof(BitNode)); if (!T) { exit(1); } (*T) -> data.e = ch; /*生成根节点*/ createTree(&(*T) -> lChild); /*构造左子树*/ createTree(&(*T) -> rChild); /*构造右子树*/ } return 1;}int preOrder(BitTree T) { /*非递归先序遍历*/ BitTree stack[100]; /*基于栈进行遍历*/ int front = 0, rear = 0; BitNode *p; if(T != NULL) { stack[rear] = T; /*将根节点入栈*/ rear = (rear + 1) % 100; } while (front != rear) { p = stack[front]; front = (front + 1) % 100; printf("%5d", p -> data); /*输出节点*/ if(p -> lChild != NULL) { /*左子树不为空就输出左子树*/ stack[rear] = p -> lChild; /*左子树入栈*/ rear = (rear + 1) % 100; } if(p -> rChild != NULL) { /*最后是右子树*/ stack[rear] = p -> rChild; /*右子树入栈*/ rear = (rear + 1) % 100; } } return;}int inOrder(BitTree T) { /*非递归中序遍历*/ BitNode *stack[100]; int top; BitNode *p; top = 0; p = T; while(p != NULL || top > 0) { while(p != NULL) { /*遍历到最左端的节点*/ stack[top++] = p; p = p -> lChild; } if(top > 0) { /*出栈,选择当前节点的右子树*/ p = stack[--top]; printf("%5d", p -> data); p = p -> rChild; } }}int levelPrint(BitTree T) { /*非递归层次遍历*/ BitTree queue[100]; BitNode *p; int front = -1, rear = -1; rear++; queue[rear] = T; while(front != rear) { front = (front + 1) % 100; p = queue[front]; printf("%5d", p -> data); if(p -> lChild != NULL) { rear = (rear + 1) % 100; queue[rear] = p -> lChild; } if(p -> rChild != NULL) { rear = (rear + 1) % 100; queue[rear] = p -> rChild; } }}int judge(BitTree T) { /*判断是否为二叉树*/ if(!T) { /*返回1代表是二叉排序树*/ return 1; } else if(!(T -> lChild)&&!(T -> rChild)) { /*左右子树都没有*/ return 1; } else if((T -> lChild)&&!(T -> rChild)) { /*只有左子树*/ if((T->lChild->data.e)>(T->data.e)) { return 0; /*返回0代表无二叉树*/ } else { return(judge(T -> lChild)); /*继续寻找子节点*/ } } else if(!(T -> lChild)&&(T -> rChild)) { /*只有右子树*/ if((T->rChild -> data.e) < (T -> data.e)) { return 0; } else { return(judge(T -> rChild)); } } else { /*如果左右子树都存在*/ if((T -> lChild -> data.e) > (T -> data.e)||(T -> rChild -> data.e) < (T -> data.e)) { return 0; } else { return (judge(T -> lChild) && judge(T -> rChild)); } }}int searchBst(BitTree T, BitTree G, Elemtype key, BitTree *p) { /*查找节点*/ if(!T) { /*判断原树是否存在*/ *p = G; return 0; } else if(key == T -> data.e) { *p = T; return 1; } else if(key < T -> data.e) { return searchBst(T -> lChild, T, key, p); } else { return searchBst(T -> rChild, T, key, p); } return 1;}int insertBst(BitTree T, Elemtype key) { /*二叉排序树插入*/ BitTree p, N; if(searchBst(T, NULL, key, &p)) { return 0; } else { N = (BitTree)malloc(sizeof(BitNode)); N -> data.e = key; N -> lChild = NULL; N -> rChild = NULL; if(!p) { T = N; } else if(key < p -> data.e) { p -> lChild = N; } else { p -> rChild = N; } } return 1;}int deleteBst(BitTree *T, int key) { /*删除二叉排序树*/ if(!(*T)) { return 0; } else { if(key == (*T) -> data.e) { Delete(T); /*找到指定节点,删除*/ } else if(key < (*T) -> data.e) { return deleteBst(&(*T)->lChild, key); } else { return deleteBst(&(*T)->rChild, key); } }}int Delete(BitTree *p) { /*删除节点*/ BitTree q, N; if(!(*p) -> lChild && !(*p) -> rChild) { *p = NULL; } else if(!(*p) -> lChild) { q = *p; free(q); } else if(!(*p) -> rChild) { q = *p; free(q); } else { q = *p; N = (*p) -> lChild; while(N -> rChild) { q = N; N = N -> rChild; } (*p) -> data.e = N -> data.e; if(q!=*p) { q -> rChild = N -> lChild; } else { q -> lChild = N -> lChild; } free(N); } return 1;}int main() { int ch = 0, flag = 0, key, m; flag = judge(T); while(1) { printf("1.创建二叉树\n"); printf("2.先序非递归遍历\n"); printf("3.中序非递归遍历\n"); printf("4.层次非递归遍历\n"); printf("5.判断二叉树是否为二叉排序树\n"); printf("6.二叉排序树插入数据\n"); printf("7.二叉排序树删除数据\n"); printf("0.退出\n"); printf("请输入你的选择:"); scanf("%d", &ch); switch(ch) { case 1:printf("请输入数据,0为空节点:\n"); createTree(&T);printf("\n");break; case 2:printf("非递归先序遍历为:\n"); preOrder(T);printf("\n");break; case 3:printf("非递归中序遍历为:\n"); inOrder(T);printf("\n");break; case 4:printf("非递归层次遍历为:\n"); levelPrint(T);printf("\n");break; case 5:flag = judge(T); if(flag) printf("该树是二叉排序树\n"); else printf("该树不是二叉排序树\n"); printf("\n");break; case 6:printf("请输入数据:"); scanf("%d",&key); insertBst(T, key);break; case 7:printf("请输入数据:"); scanf("%d",&m); deleteBst(&T, m);break; case 0:exit(0); } printf("\n"); } return 1;}
    0  留言 2018-11-12 09:26:41
eject