分类

课内:
不限
类型:
不限 毕业设计 课程设计 小学期 大作业
汇编语言 C语言 C++ JAVA C# JSP PYTHON PHP
数据结构与算法 操作系统 编译原理 数据库 计算机网络 软件工程 VC++程序设计
游戏 PC程序 APP 网站 其他
评分:
不限 10 9 8 7 6 5 4 3 2 1
年份:
不限 2018 2019

资源列表

  • 基于Java语言的C/S模式通讯录备份和查询软件

    一 需求分析本设计要求完成一个基于C/S模式的通讯录备份软件,采用C/S架构,具有易用、美观的图形界面。
    1.1 服务器端功能要求
    能够验证客户身份,接收客户端的备份通讯录的请求,能够实时备份和更新客户的通讯录
    加密存储每个用户的通讯录

    1.2 客户端功能要求
    能登陆连接到服务器,回应:连接成功/失败
    能备份本机通讯录
    能实时更新本机通讯录
    能查询本机通讯录

    1.3 本程序可实现功能
    客户端

    能登陆连接到服务器,回应:连接成功/失败
    能将本机通讯录备份到数据库
    能实时从数据库获取最新内容更新本机通讯录
    能查询本机通讯录
    能增加、删除并且修改本机通讯录

    服务端

    能够验证客户身份,接收客户端的备份通讯录的请求,能够实时备份和更新客户的通讯录
    加、解密用户存储的通讯录


    二 程序实现2.1 总体结构客户端首先建立一个本地文件来存储本地的通讯录数据,通过本地文件对通讯录内容进行查询操作,在数据库中进行通讯录的增添、删除以及修改操作。同时备份功能可将本地文件中的通讯录内容上传至数据库中,更新功能则是将经过增添、删除或修改后的数据库中通讯录内容更新到本地文件中。
    服务器负责验证客户端的登录账号和密码,若一致则与MySQL进行连接并回应客户端登陆成功,否则回应登陆失败。若登录成功,则服务端可响应客户端的备份请求,将本地文件中的通讯录内容经过DES加密后备份至数据库;还可响应客户端的更新要求,将数据库中通讯录的内容经过DES解密后更新至本地文件中。
    2.2 模块关系
    2.3 系统总体流程
    三 程序实现3.1 类的描述
    Client包中包含三个类:Login类,LoginListener类以及Operation类
    Server包中包含三个类:ServerFrame类,Sever类以及DESPlus类

    3.1.1 Login类实现登录界面并实例化LoginListener 类给登录按钮添加ActionListner 监听方法。
    3.1.2 LoginListener类实现LoginListener类,继承ActionListener接口并重写抽象函数ActionPerformed。客户首先输入用户名和密码,然后单击登录按钮通过Java Socket连接到服务器,并且将账号和密码传给服务器,等待服务器响应后的验证结果。若验证通过则弹出通讯录系统主界面,否则弹出窗口显示用户名或密码错误、登陆失败。
    3.1.3 Operation类实现操作主界面,继承ActionListener接口并重写抽象函数ActionPerfomed。在构造方法中实现对各操作按钮的监听,用户点击相应界面上的按钮,通过传socket给服务器端并接收响应结果即可进行相应操作。
    3.1.4 SeverFrame类实现服务端界面,实时显示客户端进行的相应操作。
    3.1.5 Server类主要实现服务端的功能,包括验证用户名以及密码,连接MySQL,响应更新以及备份操作等等。
    3.1.6 DES类实现对通讯录内容的加密和解密。进行备份操作时加密通讯录内容后备份至数据库,进行更新操作时解密数据库内容更新至本地文件。
    3.2 关键类代码实现3.2.1 LoginListener类public class LoginListener implements ActionListener{ public LoginListener(JFrame frame,JTextField text,JPasswordField pw){ this.frame = frame; this.text = text; this.pw = pw; } @SuppressWarnings("deprecation") public void actionPerformed(ActionEvent e){ try{ //发送密码和用户名到客户端 String user = text.getText(); String pass = pw.getText(); Socket s = new Socket("127.0.0.1",8800); OutputStream os = s.getOutputStream(); OutputStreamWriter osw = new OutputStreamWriter(os); PrintWriter pw = new PrintWriter(osw ,true); pw.println(user+"%"+pass); //接收服务器发回来的确认信息 InputStream is = s.getInputStream(); InputStreamReader isr = new InputStreamReader(is); BufferedReader br = new BufferedReader(isr); String answer = br.readLine(); //显示登录成功界面或密码错误界面 if(answer.equals("ok")){ Operation o = new Operation(); o.SetSocket(s); frame.dispose();//关闭登录界面 } else{ JTextField text = new JTextField("用户名或密码错误"); JFrame frame = new JFrame(); frame.setTitle("错误"); frame.setLocation(550,300); frame.setSize(200,100); frame.setDefaultCloseOperation(2); frame.add(text); frame.setVisible(true); } }catch(Exception e1){} }}
    3.2.2 Operation类public class Operation { // 获取已经连接好的Socket值 public Socket s; public void SetSocket(Socket s) { this.s = s; } // 客户端程序入口 public static void main(String args[]) { Login login = new Login(); } public Operation() throws Exception { // 实例化窗口 javax.swing.JFrame frame = new javax.swing.JFrame(); // 实例化欢迎面板 JPanel Welcome = new JPanel(); // 实例化查询显示面板 JPanel CXPanel = new JPanel(); // 实例化添加显示面板 JPanel TJPanel = new JPanel(); // 实例化删除显示面板 JPanel SCPanel = new JPanel(); // 实例化修改显示面板 JPanel XGPanel = new JPanel(); // 实例化备份面板 JPanel BFPanel = new JPanel(); // 实例化更新面板 JPanel GXPanel = new JPanel(); // 实例化帮助面板 JPanel BZPanel = new JPanel(); // 实例化查询界面组件并添加 // 实例化添加面板组件并添加 // 实例化删除面板组件并添加 // 实例化修改面板组件并添加 // 实例化备份面板组件备份文本框并添加 // 实例化更新面板组件更新文本框并添加 // 实例化帮助面板组件更新文本框并添加 // 设置查询按钮的监听 itemcxdh.addActionListener(new ActionListener() { QR1.addActionListener(new ActionListener() { public void actionPerformed(ActionEvent e) { try { // 在本地文件中查询通讯录信息 File f = new File("D:\\通讯录.txt"); FileReader fr = new FileReader(f); BufferedReader br = new BufferedReader(fr); FileReader fr2 = new FileReader(f); BufferedReader br2 = new BufferedReader(fr2); String str = InputText1.getText(); if (str.equals("")) { CXText.append("\n" + "全部的联系人信息是:" + "\n"); while (br2.ready()) { String string = br.readLine(); String str1 = string.split(" ")[0]; String str2 = string.split(" ")[1]; String str3 = string.split(" ")[2]; String str4 = string.split(" ")[3]; CXText.append("姓名: " + str1 + "\n" + "电话: " + str2 + "\n" + "地址: " + str3 + "\n" + "QQ: " + str4 + "\n\n"); } br2.close(); } else { while (br.ready()) { String string = br.readLine(); String str1 = string.split(" ")[0]; String str2 = string.split(" ")[1]; String str3 = string.split(" ")[2]; String str4 = string.split(" ")[3]; if (InputText1.getText().equals(str1) || InputText1.getText().equals(str2)) { CXText.append("\n" + "查询到的联系人信息是:" + "\n"); CXText.append("姓名: " + str1 + "\n" + "电话: " + str2 + "\n" + "地址: " + str3 + "\n" + "QQ: " + str4 + "\n\n"); break; } if (!br.ready()) CXText.append("\n" + "没有所查的联系人信息,请确认信息是否输入正确" + "\n"); } br.close(); } // 向服务器端传送查询的消息 OutputStream os = s.getOutputStream(); OutputStreamWriter osw = new OutputStreamWriter(os); PrintWriter pw = new PrintWriter(osw, true); pw.println("查询" + " " + InputText1.getText() + "的联系方式"); } catch (Exception e1) { } } }); // 设置增添按钮的监听 QR2.addActionListener(new ActionListener() { public void actionPerformed(ActionEvent e) { TJText.setText("\n" + "请在下方的文本框输入想要添加的联系人信息" + "\n" + "然后单击添加按钮" + "\n"); try { // 在数据库中添加新的联系人 Class.forName("com.mysql.jdbc.Driver"); Connection cn = DriverManager.getConnection( "jdbc:mysql://127.0.0.1:3306/addressbook?characterEncoding=utf8&useSSL=true", "root", "twy97620"); System.out.println("Connecting to database..."); System.out.println("Creating statement..."); PreparedStatement ps = cn.prepareStatement("insert into people values(?,?,?,?)"); // 将文本信息加密 ps.setString(1, des.encrypt(nametext.getText().toString())); System.out.println(des.encrypt(nametext.getText().toString())); ps.setString(2, des.encrypt(teltext.getText().toString())); ps.setString(3, des.encrypt(addtext.getText().toString())); ps.setString(4, des.encrypt(qqtext.getText().toString())); int rows = ps.executeUpdate(); System.out.println("Rows impacted : " + rows); ps.close(); cn.close(); nullarea.setText("已完成添加!" + "\n"); // 向服务器端传送添加的指令 OutputStream os = s.getOutputStream(); OutputStreamWriter osw = new OutputStreamWriter(os); PrintWriter pw = new PrintWriter(osw, true); pw.println("添加" + " " + nametext.getText()); } catch (SQLException se) { // Handle errors for JDBC se.printStackTrace(); } catch (Exception e1) { // Handle errors for Class.forName e1.printStackTrace(); InputText3.setText(""); } } }); // 实例化删除按钮的监听 QR3.addActionListener(new ActionListener() { public void actionPerformed(ActionEvent e) { SCText.setText("请在下方文本框中输入想要删除的联系人姓名" + "\n"); try { // 在数据库中按照姓名删除联系人 Class.forName("com.mysql.jdbc.Driver"); Connection cn = DriverManager.getConnection( "jdbc:mysql://127.0.0.1:3306/addressbook?characterEncoding=utf8&useSSL=true", "root", "twy97620"); System.out.println("Connecting to database..."); System.out.println("Creating statement..."); PreparedStatement ps = cn.prepareStatement("delete from people where pname=?"); ps.setString(1, des.encrypt(InputText3.getText().toString())); int rows = ps.executeUpdate(); System.out.println("Rows impacted : " + rows); ps.close(); cn.close(); if (rows == 0) { SCWCText.setText("没有该联系人" + "\n" + "请确认联系人姓名是否正确!" + "\n"); } else { SCWCText.setText("删除成功!" + "\n"); OutputStream os = s.getOutputStream(); OutputStreamWriter osw = new OutputStreamWriter(os); PrintWriter pw = new PrintWriter(osw, true); pw.println("删除" + " " + InputText3.getText() + "的信息"); } } catch (SQLException se) { // Handle errors for JDBC se.printStackTrace(); } catch (Exception e2) { // Handle errors for Class.forName e2.printStackTrace(); } } }); // 实例化修改按钮的监听 QRxg.addActionListener(new ActionListener() { public void actionPerformed(ActionEvent e) { try { // 在数据库中修改联系人 Class.forName("com.mysql.jdbc.Driver"); Connection cn = DriverManager.getConnection( "jdbc:mysql://127.0.0.1:3306/addressbook?characterEncoding=utf8&useSSL=true", "root", "twy97620"); System.out.println("Connecting to database..."); System.out.println("Creating statement..."); PreparedStatement ps = cn.prepareStatement("delete from people where pname=?"); ps.setString(1, des.encrypt(Inputxgname.getText().toString())); int rows = ps.executeUpdate(); System.out.println("Rows impacted : " + rows); if (rows != 0) { PreparedStatement ps1 = cn.prepareStatement("insert into people values(?,?,?,?)"); ps1.setString(1, des.encrypt(Inputxgname.getText().toString())); ps1.setString(2, des.encrypt(xgteltext.getText().toString())); ps1.setString(3, des.encrypt(xgaddtext.getText().toString())); ps1.setString(4, des.encrypt(xgqqtext.getText().toString())); int rows1 = ps1.executeUpdate(); System.out.println("Rows1 impacted : " + rows1); if (rows1 != 0) { System.out.println("成功!"); xgwc.setText("修改成功!" + "\n"); } else { xgwc.setText("修改失败!" + "\n"); } ps1.close(); } else { xgwc.setText("该联系人不存在,修改失败!" + "\n"); } ps.close(); cn.close(); // 向服务器端传送添加的指令 OutputStream os = s.getOutputStream(); OutputStreamWriter osw = new OutputStreamWriter(os); PrintWriter pw = new PrintWriter(osw, true); pw.println("添加" + " " + nametext.getText()); } catch (SQLException se) { // Handle errors for JDBC se.printStackTrace(); } catch (Exception e1) { // Handle errors for Class.forName e1.printStackTrace(); InputText3.setText(""); } } }); // 设置备份按钮的监听 itembf.addActionListener(new ActionListener() { public void actionPerformed(ActionEvent e) { frame.remove(Welcome); frame.remove(CXPanel); frame.remove(XGPanel); frame.remove(TJPanel); frame.remove(SCPanel); frame.remove(GXPanel); frame.remove(BZPanel); frame.add(BFPanel); frame.revalidate(); frame.repaint(); BFText.setText("请稍等,正在备份!" + "\n"); try { // 向服务器发起备份的请求 OutputStream os = s.getOutputStream(); OutputStreamWriter osw = new OutputStreamWriter(os); PrintWriter pw = new PrintWriter(osw, true);//true表示自动刷新缓冲区 pw.println("备份"); File f = new File("D:\\通讯录.txt"); FileReader fr = new FileReader(f); BufferedReader br1 = new BufferedReader(fr); while (br1.ready()) { String string = br1.readLine(); pw.println(string); } br1.close(); pw.println("end"); // 接收服务器端传来备份的结果 InputStream is = s.getInputStream(); InputStreamReader isr = new InputStreamReader(is); BufferedReader br = new BufferedReader(isr); BFText.append(br.readLine() + "\n"); } catch (Exception e1) { } } }); // 设置更新按钮的监听 itemgx.addActionListener(new ActionListener() { public void actionPerformed(ActionEvent e) { try { // 向服务器发起更新的请求 OutputStream os = s.getOutputStream(); OutputStreamWriter osw = new OutputStreamWriter(os); PrintWriter pw = new PrintWriter(osw, true); pw.println("更新"); // 接收服务器传来更新的结果 InputStream is = s.getInputStream(); InputStreamReader isr = new InputStreamReader(is); BufferedReader br = new BufferedReader(isr); File f = new File("D:\\通讯录.txt"); FileWriter fw = new FileWriter(f); PrintWriter pw1 = new PrintWriter(fw); String string = br.readLine(); while (!string.equals("更新成功!")) { pw1.append(string + "\r\n"); string = br.readLine(); } pw1.close(); GXText.append("更新成功!" + "\n"); } catch (Exception e1) { } } }); }// Operation()结束}
    3.2.3 Server类public class Server { public static void main(String[] args) { ServerFrame sf = new ServerFrame(); // 服务器在8800端口监听 @SuppressWarnings("resource") ServerSocket ss = new ServerSocket(8800); System.out.println("服务器正在8800端口监听……"); Socket s = ss.accept(); // 接收用户名和密码 InputStream is = s.getInputStream(); InputStreamReader isr = new InputStreamReader(is); BufferedReader br = new BufferedReader(isr); String uandp = br.readLine(); String u = uandp.split("%")[0]; String p = uandp.split("%")[1]; // 将用户名密码的验证信息传送到客户端 OutputStream os = s.getOutputStream(); OutputStreamWriter osw = new OutputStreamWriter(os); PrintWriter pw = new PrintWriter(osw, true); if (u.equals("twycwt") && p.equals("twy97620")) { pw.println("ok"); sf.text.append("客户登录成功" + "\n"); while (true) { String message = br.readLine(); DES des = new DES(); // 响应客户端备份命令 if (message.equals("备份")) { sf.text.append("备份联系人信息" + "\n"); try { Class.forName("com.mysql.jdbc.Driver"); Connection cn = DriverManager.getConnection( "jdbc:mysql://127.0.0.1:3306/addressbook?characterEncoding=utf8&useSSL=true", "root", "twy97620"); System.out.println("Connecting to database..."); System.out.println("Creating statement..."); Statement st = cn.createStatement(); int rows = st.executeUpdate("delete from people where pname is not null"); System.out.println("Rows impacted : " + rows); String string = br.readLine(); int count = 0; while (!string.equals("end")) { String pname = string.split(" ")[0]; String telephone = string.split(" ")[1]; String address = string.split(" ")[2]; String qq = string.split(" ")[3]; PreparedStatement ps = cn.prepareStatement( "insert into people(pname,telephone,address,qq) values(?,?,?,?)"); //将本地记录加密后备份至数据库 ps.setString(1, des.encrypt(pname)); ps.setString(2, des.encrypt(telephone)); ps.setString(3, des.encrypt(address)); ps.setString(4, des.encrypt(qq)); ps.executeUpdate(); count++; System.out.println("正在备份..." + count); string = br.readLine(); } st.close(); cn.close(); pw.println("备份成功!"); } catch (SQLException se) { // Handle errors for JDBC se.printStackTrace(); pw.println("数据库操作失败!"); } catch (Exception e) { // Handle errors for Class.forName e.printStackTrace(); pw.println("备份失败!"); } } // 相应客户端更新的命令 if (message.equals("更新")) { sf.text.append("更新联系人信息" + "\n"); try { Class.forName("com.mysql.jdbc.Driver"); Connection cn = DriverManager.getConnection( "jdbc:mysql://127.0.0.1:3306/addressbook?characterEncoding=utf8&useSSL=true", "root", "twy97620"); Statement st = cn.createStatement(); System.out.println("Connecting to database..."); System.out.println("Creating statement..."); ResultSet rs = st.executeQuery("select pname,telephone,address,qq from people"); rs.last(); int rows = rs.getRow(); System.out.println("Rows : " + rows); rs.beforeFirst(); int count = 0; while (rs.next()) { String string = new String(); System.out.println(string); //将数据库中的记录解密后更新至本地文件 string = des.decrypt(rs.getString(1)) + " " + des.decrypt(rs.getString(2)) + " " + des.decrypt(rs.getString(3)) + " " + des.decrypt(rs.getString(4)); pw.println(string); count++; System.out.println("正在更新..." + count); } rs.close(); st.close(); cn.close(); pw.println("更新成功!"); } catch (SQLException se) { // Handle errors for JDBC se.printStackTrace(); pw.println("数据库操作失败!"); } catch (Exception e) { // Handle errors for Class.forName e.printStackTrace(); pw.println("更新失败!"); } } if (message.split(" ")[0].equals("查询")) { sf.text.append(message + "\n"); } if (message.split(" ")[0].equals("添加")) { sf.text.append(message + "\n"); } if (message.split(" ")[0].equals("删除")) { sf.text.append(message + "\n"); } } } else { // 发送错误信号到客户端 pw.println("error"); } } catch (Exception e) { } }}
    3.2.4 DES类public class DES { private static String strDefaultKey = "national"; private Cipher encryptCipher = null; private Cipher decryptCipher = null; public static String byteArr2HexStr(byte[] arrB) throws Exception { int iLen = arrB.length; // 每个byte用两个字符才能表示,所以字符串的长度是数组长度的两倍 StringBuffer sb = new StringBuffer(iLen * 2); for (int i = 0; i < iLen; i++) { int intTmp = arrB[i]; // 把负数转换为正数 while (intTmp < 0) { intTmp = intTmp + 256; } // 小于0F的数需要在前面补0 if (intTmp < 16) { sb.append("0"); } sb.append(Integer.toString(intTmp, 16)); } return sb.toString(); } public static byte[] hexStr2ByteArr(String strIn) throws Exception { byte[] arrB = strIn.getBytes(); int iLen = arrB.length; // 两个字符表示一个字节,所以字节数组长度是字符串长度除以2 byte[] arrOut = new byte[iLen / 2]; for (int i = 0; i < iLen; i = i + 2) { String strTmp = new String(arrB, i, 2); arrOut[i / 2] = (byte) Integer.parseInt(strTmp, 16); } return arrOut; } public DES() throws Exception { this(strDefaultKey); } public DES(String strKey) throws Exception { Security.addProvider(new com.sun.crypto.provider.SunJCE()); Key key = getKey(strKey.getBytes()); encryptCipher = Cipher.getInstance("DES"); encryptCipher.init(Cipher.ENCRYPT_MODE, key); decryptCipher = Cipher.getInstance("DES"); decryptCipher.init(Cipher.DECRYPT_MODE, key); } public byte[] encrypt(byte[] arrB) throws Exception { return encryptCipher.doFinal(arrB); } public String encrypt(String strIn) throws Exception { return byteArr2HexStr(encrypt(strIn.getBytes())); } public byte[] decrypt(byte[] arrB) throws Exception { return decryptCipher.doFinal(arrB); } public String decrypt(String strIn) throws Exception { return new String(decrypt(hexStr2ByteArr(strIn))); } private Key getKey(byte[] arrBTmp) throws Exception { // 创建一个空的8位字节数组(默认值为0) byte[] arrB = new byte[8]; // 将原始字节数组转换为8位 for (int i = 0; i < arrBTmp.length && i < arrB.length; i++) { arrB[i] = arrBTmp[i]; } // 生成密钥 Key key = new javax.crypto.spec.SecretKeySpec(arrB, "DES"); return key; } }
    3.4 类间调用关系客户端与服务端的类间调用关系分别如下图所示:

    四 运行测试4.1 用户登录运行operation类,显示登录界面,如图所示:

    若用户名和密码错误,则弹出窗口提示登录失败,如图所示:

    若用户名和密码正确,则登录成功,出现操作主界面,如图所示:

    4.2 查询功能查询功能包括按名称查询和按电话查询,同时既可以查询所有联系人的信息,也可以查询某个联系人的信息。
    点击查看菜单栏会出现按名称查看和按电话查看两个选项,点击一个进入查看界面,直接点击查询按钮即可查看所有联系人的信息,若输入相应联系人名称或电话即可查看该指定联系人的信息,如图所示:


    如果通讯录中不存在要查看的联系人,则显示相应提示,如图所示:

    4.3 备份功能用户点击备份按钮后,客户端发送备份请求到服务端,服务端连接数据库后将本地文件中的通讯录内容经过DES算法加密后存储到数据库中,如图所示:

    备份之前的数据库,如图所示:

    备份之后的数据库,如图所示:

    4.4 更新功能经过增添、删除或修改操作后数据库中通讯录内容已经发生了改变,点击更新菜单栏即可将本地文件中的内容更新至最新的数据,如图所示:

    更新之前的本地文件,如图所示:

    更新之后的本地文件,如图所示:

    4.5 帮助功能点击帮助菜单栏,即可显示该通讯录系统的使用方法,方便用户操作,如图所示:

    4.6 增加功能点击编辑菜单栏,选择增添选项,输入联系人的姓名,电话,qq和地址,点击添加按钮,完成添加,如图所示:

    4.7 删除功能点击编辑菜单栏,选择删除选项,输入要删除联系人的姓名,点击删除按钮即可删除该联系人,如图所示:

    4.8 修改功能点击编辑菜单栏,选择修改选项,输入要修改的联系人名称,再输入修改后的电话、地址和qq,点击修改按钮即可,如图所示:
    修改前:

    修改成功:
    1 评论 30 下载 2018-11-04 20:55:39 下载需要5点积分
  • 基于UDP Socket的DNS中继器设计与实现

    一 需求分析对程序的要求如下:

    读入“IP地址-域名”对照表,当客户端查询域名对应的IP地址时,用域名检索该对照表,有三种可能检索结果:

    ip地址0.0.0.0,则向客户端返回“域名不存在”的报错消息(不良网站拦截功能)普通IP地址,则向客户端返回该地址(服务器功能)表中未检到该域名,则向因特网DNS服务器发出查询,并将结果返给客户端(中继功能)
    需要进行消息ID的转换,以满足多个计算机上的客户端会同时查询

    二 程序设计2.1 主线程流程
    2.2 服务线程流程
    三 程序实现3.1 开发环境
    操作系统:Windows 7 x64
    编译环境:Visual Studio 2012

    3.2 存储模块host_item *hosts_list[MAX_HOST_ITEM]
    存储E:\dnsrelay.txt中导入的所有地址,包括屏蔽地址和已知的缓存地址。
    std::vector<DNSRequest*>request_pool;
    当客户端通过53端口发来数据后,处理函数将请求以DNSRequest类型的格式加入到request_pool这个队列中。所有DNS处理线程从该队列中获取请求,并处理。
    3.3 函数模块主体部分,用于处理DNS请求,处理流程如下所示:

    处理DNS Packet,将二进制流变为程序可处理的部分,流程如下所示:

    获取当前地址的类型,包括缓存地址、屏蔽地址以及未知地址,流程如下所示:

    缓存管理流程如下所示:

    ID管理,在处理过程中,由于各个客户端的发来的DNS请求中ID并不唯一,可能出现重复ID导致错误,因此,添加ID管理以重新分配DNSQuery的请求号,防止重复ID导致的错误。

    四 运行测试4.1 基本功能测试DNS屏蔽功能
    选取DNS屏蔽地址列表中的地址之一:0.0.0.0008.cn
    通过nslookup查找该主机地址,结果如下图所示:

    结果表明,DNS屏蔽功能有效。
    DNS服务器功能
    选择一个在DNS中存在的地址,如:11.111.11.111test1。
    结果如下图所示:

    DNS中继功能
    选一个在DNS中不存在的地址,如:baidu.com,
    在cmd中输入:nslookup baidu.com
    结果如下:

    可以正确解析服务器地址。
    2 评论 70 下载 2018-11-04 19:55:10 下载需要2点积分
  • 基于汇编语言的学生成绩管理系统

    一 需求分析用汇编语言编写一个学生成绩管理系统,实现基本的学生成绩管理,功能包括成绩的录入,总分和平均分的计算,数据存档,从文件中读入数据等。要求程序界面友好,有输入界输出提示,有菜单等。
    二 程序设计2.1 程序总流程设计
    2.2 添加记录流程设计
    2.3 打印记录流程设计
    三 程序实现3.1 开发工具该程序使用基于DOS操作系统的16位实模式汇编语言编写,使用的编译器为微软的MASM 5.0,调试工具为DOS下的debug.exe程序。
    3.2 基本原理本程序使用了DOS系统功能调用(INT 21H),程序中用到的系统功能调用如下:



    AH
    功能
    调用参数
    返回参数




    02
    显示输出
    DL=输出字符



    09
    显示字符串
    DS:DX=串地址 字符串以‘$’符结束



    3C
    建立文件
    DS:DX=ASCIZ串地址 CX=文件属性
    成功:AX=文件代号 失败:AX=错误代码


    3D
    打开文件
    DS:DX=ASCIZ串地址 AL=访问文件和共享方式 0=读,1=写,2=读/写
    成功:AX=文件代号 失败:AX=错误代码


    3E
    关闭文件
    BX=文件代号
    失败:AX=错误代码


    3F
    读文件或设备
    DS:DX=缓冲区首地址 BX=文件代号 CX=读取的字节数
    成功:AX=实际读取的字节数 AX=0已到文件尾 失败:AX=错误代码


    40
    写文件或设备
    DS:DX=缓冲区首地址 BX=文件代号 CX=写入的字节数
    成功:AX=实际写入的字节数 失败:AX=错误代码



    3.3 数据结构程序采用静态链表的方式来存储学生成绩信息,链表结点描述如下:
    struct Node{ byte name[20]; // 学生姓名 word maths; // 数学成绩 word english; // 英语成绩 word computer; // 计算机成绩 word total; // 总成绩 word avg; // 平均成绩 word next; // 指向下一个结点的指针}
    说明:结点大小为32字节,其中name占20字节,剩下的六个字段,每一个都是一个字,占两个字节。
    3.4 模块说明该程序一共分为三大模块:分别完成数据的录入,存档以及从文件读取数据。各模块分别介绍如下:
    3.4.1 数据录入数据的录入项目包括学生的姓名,各科成绩。数据录入后,程序自动计算出每位学生的平均成绩和总成绩。
    姓名的输入方式
    首先利用09号系统调用,将字符串输入到内存缓冲区,然后用字符串传送指令将缓冲区中的字符串传送到记录结点。程序自动在输入的字符串后加上美元符号“$”,目的是方便使用系统调用将其输出。
    成绩的输入方式
    为了方便输入,首先利用09号系统调用,让用户以10进制的形式输入成绩到内存缓冲区,然后调用子程序将字符串转换成二进制数值,并保存到记录中相应的字段里。
    3.4.2 数据存档文件格式采用二进制格式,即直接将内存中的数据复制到文件中而不经过任何转换。文件开头的两个字节表示文件中记录的总数,之后的每32个字节存储一条记录。文件的结构如下表所示:



    记录总数:2个字节




    记录1:20个字节


    记录2:20个字节


    ……


    记录n:20个字节



    3.4.3 从文件中读取数据由于该程序生成的文件为二进制格式,因此读取过程十分简单,是写入过程的逆过程:首先读取文件开头的两个字节,便知道了文件中记录的总数,然后循环读取之后的每一条记录。
    四 运行测试程序共一个可执行文件,可以在DOS系统或者直接在Windows下运行,程序运行后在屏幕上显示主菜单,如下图所示:

    选择相应的菜单项可使用对应的功能,以下为各个功能模块的详细说明。
    4.1 数据的录入在主菜单下选择“1”,进入记录输入模块,按照提示输入各字段的值,如下图所示:

    4.2 数据和显示在主菜单下选择“2”,进入记录输出模块。下图为添加了5条记录后打印的效果:

    4.3 数据存档在主菜单下选择“3”,将当前在内中的全部记录保存到文件中(c:\student.txt),如下图所示:

    4.4 从文件中读取在主菜单下选择“4”,将当前在内中的全部记录保存到文件中(c:\student.txt),如下图所示:
    1 评论 22 下载 2018-11-04 19:18:48 下载需要3点积分
  • 基于C++的9种排序算法的实现与比较

    一、使用说明1.1 项目简介随机函数产生10000个随机数,用快速排序,直接插入排序,冒泡排序,直接选择排序的排序方法排序,并统计每种排序所花费的排序时间和交换次数。其中,随机数的个数由用户定义,系统产生随机数,并且显示他们的比较次数,排序算法包括冒泡排序,直接选择排序,直接插入排序,希尔排序,快速排序,堆排序,归并排序,基数排序,折半插入排序。
    1.2 操作手册运行程序后,首先要输入随机数的个数。

    第一步,选择操作1冒泡排序,之后会出现排序所用时间和交换次数。

    第二步,选择操作2选择排序,之后会出现排序所用时间和交换次数。

    第三步,选择操作3直接插入排序,之后会出现排序所用时间和交换次数。

    第四步,选择操作4希尔排序,之后会出现排序所用时间和交换次数。

    第五步,选择操作5快速排序,之后会出现排序所用时间和交换次数。

    第六步,选择操作6堆排序,之后会出现排序所用时间和交换次数。

    第七步,选择操作7归并排序,之后会出现排序所用时间和交换次数。

    第八步,选择操作8基数排序,之后会出现排序所用时间和交换次数。

    第九步,选择操作9折半插入排序,之后会出现排序所用时间和交换次数。

    1.3 注意事项
    输入的随机数个数必须大于1
    在进行操作时只能输入已有数字操作,不得输入其他数字或字母或符号

    二、概述2.1 基本思路通过main函数里的switch分别判断不同操作对应的排序方法。
    2.2 文件目录
    test.cpp (主文件)
    test.exe (程序可执行文件)
    设计报告.doc (项目文档)
    Sort.h(头文件)

    三、具体实现3.1 冒泡排序(函数Bubble_sort)对数组内的每两个数据分别进行比较,判断二者大小是否需要互换,比较是相邻的两个元素比较,交换也发生在这两个元素之间。冒泡排序最好的时间复杂度为O(n),冒泡排序的最坏时间复杂度为O(n²),平均时间复杂度为O(n²)。是一种稳定排序算法。

    3.2 选择排序(函数Selection_sort)选择排序是每次选择出最小的元素放到序列的起始位置,并分为有序区和无序区,每次都从无序区中取出最小的放到有序区内,直到所有元素遍历完。选择排序的交换操作介于 0 和 (n - 1)次之间,交换次数比冒泡排序少,所以运行速度比冒泡排序快,但是一个不稳定的操作算法。

    3.3 直接插入排序(函数Insert_sort)直接插入排序先从无序区中取出一个元素,将其安排合适的位置后,其后面的数据位置依次加一,再取出其他元素进行插入,直到所有元素都被插入到合适的位置。

    3.4 希尔排序(函数Shell_sort)希尔排序也是插入排序的一种,希尔排序是按数组下标的一定增量进行分组,再对每组进行排序,增量再变为原来的一半,重复分组排序的操作,直到增量为1,则排序完成。是一种不稳定的算法。

    3.5 快速排序(函数Qsort函数Quick_sort)快速排序首先将第一个数据作为枢轴,第一次遍历,将比枢轴小的放到右边,大的放到左边,再将枢轴的数据记录到位,之后不断递归,对枢轴左边和右边的数据重复以上操作,不断分解数组直到不能再分解,每个数组只有一个数据,则排序完成。

    3.6 堆排序(函数Heap_sort MinHeapify)堆排序利用了大根堆或小根堆堆顶记录最大值或最小值这一特征,建好堆之后,第0个数据是堆中最小值,第一次将A[0]与A[n-1]交换,再对A[0…n-2]重新恢复堆。第二次将A[0]与A[n–2]交换,再对A[0…n-3]重新恢复堆,重复这样的操作直到A[0]与A[1]交换。

    3.7 归并排序(函数 mergesort Merge_sort Merge)归并排序是比较a[i]和a[j]的大小,若a[i]≤a[j],则将第一个有序表中的元素a[i]复制到r[k]中,并令i和k分别加上1;否则将第二个有序表中的元素a[j]复制到r[k]中,并令j和k分别加上1,如此循环下去,直到其中一个有序表取完,然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元。归并排序的算法我们通常用递归实现,先把待排序区间[s,t]以中点二分,接着把左边子区间排序,再把右边子区间排序,最后把左区间和右区间用一次归并操作合并成有序的区间[s,t]。

    3.8 基数排序(函数Radix_sort)基数排序适用于位数小的序列,首先根据个位数值分别分配到编号0至9号的桶子里,再根据十位数字进行分配,再分别前先确定好位数的个数,最后将桶子中的数据重新串起来成为排序好的数值。

    3.9 折半插入排序(函数Binary_sort())折半插入排序是对插入排序算法的一种改进,由于排序算法过程中,就是不断的依次将元素插入前面已排好序的序列中。由于前半部分为已排好序的数列,这样我们不用按顺序依次寻找插入点,可以采用折半查找的方法来加快寻找插入点的速度。
    折半插入排序首先利用折半搜索插入位置,取此列数据的中点,如果插入值小于中点值,向左缩小区间,否则向右缩小区间。之后将其他数据成块移动,空出插入位置后,将temp的数据插入排列中。
    1 评论 11 下载 2018-11-04 18:26:30 下载需要7点积分
  • 基于C++实现的二叉排序树

    一、使用说明1.1 项目简介依次输入关键字并建立二叉排序树,实现二叉排序树的插入和查找功能。
    1.2 项目功能要求二叉排序树就是指将原来已有的数据根据大小构成一棵二叉树,二叉树中的所有结点数据满足一定的大小关系,所有的左子树中的结点均比根结点小,所有的右子树的结点均比根结点大。二叉排序树查找是指按照二叉排序树中结点的关系进行查找,查找关键字首先同根结点进行比较,如果相等则查找成功;如果比根节点小,则在左子树中查找;如果比根结点大,则在右子树中进行查找。这种查找方法可以快速缩小查找范围,大大减少查找关键的比较次数,从而提高查找的效率。
    1.3 操作手册运行程序后,进入欢迎界面,首先要输入表达式。
    第一步,选择操作:

    选择操作1后,输入二叉树的所有数据,当输入完所有数据后,输入0即可。系统会自动显示重复的数据,并且从小到大展示二叉树的数据。

    选择操作2后,首先输入要插入的数据。之后会自动显示数据插入后的二叉树。

    如果数据已存在在二叉树中也会有提示,同时会展示二叉树。

    选择操作3后,首先输入要查询的数据,之后会显示是否查询成功。

    1.4 注意事项
    用户需先建立二叉树,才可以进行操作2和3,否则系统会报错
    用户进行操作1输入数据建立二叉树时,数据元素不得为0,0是作为输入数据的结束标志,且必须输入数字,不能输入其他字符
    同样,在进行操作2和操作3时,输入的必须是数字,不得是其他字符

    二、概述2.1 基本思路二叉排序树节点的插入只需要从根节点开始,不断地判定插入值和节点值的大小,小则进入左子树,大则进入右子树,在这过程中,如果不存在子树了,就插入在该处即可。查找的算法也是一样的。
    2.2 文件目录
    test.cpp (主文件)
    tree.h (定义Node结构体和Tree类)
    tree.cpp (Tree类相关函数的具体实现方法)
    test.exe (程序可执行文件)
    设计报告.doc (项目文档)

    三、具体实现3.1 结构体Nodeint data; // 存储数据Node *left; // 二叉树节点左指针Node *right; // 二叉树节点右指针
    3.2 方法实现具体说明
    生成二叉排序树首先利用一个vector来存储用户输入的数据,将数据存入到vector中后,建立一个根节点,为每个节点分配内存并存入vector中对应的数据。其中在建立每个节点时用了递归函数,如果将要存入的数据比节点数据大,则节点作为右子树节点,如果数据比节点数据小,则节点作为左子树节点。存完数据后打印二叉树的数据,按从小到大的顺序,先遍历左子树再遍历右子树。
    插入元素首先获得用户要插入的数据,之后为该数据建立新节点,与生成二叉排序树时为每个数据建立节点的方法相同。
    查询元素同样利用递归的方式寻找数据,如果寻找的数据小于节点数据,从左子树开始遍历,遍历完左子树后对右子树遍历,直到找到该数据。
    1 评论 5 下载 2018-11-04 18:20:26 下载需要2点积分
  • 基于C++的电网建设造价模拟系统

    一、使用说明1.1 项目简介假设一个城市有n个小区,要实现n个小区之间的电网都能够相互接通,构造这个城市n个小区之间的电网,使总工程造价最低。请设计一个能够满足要求的造价方案。
    1.2 项目功能要求在每个小区之间都可以设置一条电网线路,都要付出相应的经济代价。n个小区之间最多可以有n(n-1)/2条线路,选择其中的n-1条使总的耗费最少。
    1.3 操作手册运行程序后,首先要选择操作。
    第一步,选择操作A创建电网顶点,并且输入顶点个数及顶点的名称。

    第二步,选择操作B添加电网的边,输入对应的两个顶点及其边的权。

    第三步,选择操作C构造最小生成树,并且输入起始顶点。

    第四步,选择操作D显示最小生成树。

    1.4 注意事项
    对电网模拟造价系统操作时按照A、B、C、D的操作顺序进行,不可跨步骤进行操作
    在进行操作A创建电网顶点时输入的顶点名称个数不得超过顶点个数
    只有在输入大写的A、B、C、D、E时电网模拟系统才会进行操作
    在进行操作B时输入顶点名称一定是已有的顶点名称,且先输入顶点名称在输入权。且必须按照A操作的名称顺序输入。如在A操作中输入的顺序为a b c d,则对应B操作中需要按照顺序输入a b, b c, c d等,不得出现b a,d b,c a等反顺序
    在进行操作C时输入的起始点必须是已有点

    二、概述2.1 基本思路采用Prim算法,构造MST类,本题中心思想是逐个将顶点连通来构造最小生成树,从连通网络中的某一顶点出发,将起点加入生成树的集合中,选择与它关联的权最小的边,将其终点加入到生成树的集合中,之后每一步从一个顶点在生成树的集合中,和另一个不在生成树的集合中的点集中找到权值最小的边加入生成树的边集中,直到所有顶点加入生成树集合中。
    2.2 文件目录
    test.cpp (主文件)
    test.exe (程序可执行文件)
    设计报告.doc (项目文档)
    MST.h(头文件)
    MSTfunction.cpp(MST相关方法)

    三、具体实现3.1 MST类


    名称
    数据类型
    用途




    pNumber
    int
    电网节点的个数


    pName
    Vector<string>
    存储所有节点的名称


    iCount
    int
    电网节点个数计数器


    iStart
    int
    起始点位置对应pName中的位置


    iWeight
    int
    存在比temp数值更小的边的权


    map
    Int **
    用于存储各边之间的权


    start
    string
    起始点位置的名称


    store
    Vector<pair<int,int>>
    store中的起点存储的每条边的终点和对应的权值




    3.2 创建电网顶点该操作涉及到函数createPoint(),获得顶点个数以及将各顶点的名称存储到pName中,同时各个顶点有相应的顺序序号。
    3.3 添加电网的边该操作涉及到的函数为addEdge(),首先为map开辟相应的顶点数大小。然后搜索输入两个顶点对应的位置,并将权赋值到对应的map中。
    3.4 构造最小生成树首先计数器每次操作前置0,对store进行清空,以方便重新进行操作C。函数先定义的三个int值分别为iPos对应每次搜索的起点,temp对应起点对应的边的权,iName对应搜索后的终点。开始搜索后,首先找到起始点对应pName中的位置,分别讨论iPos为0时可能出现的不同状况,对权赋不同值之后与起点周围的边进行比较,寻找权最小的边,找到后进行判断,store内是否存在顶点对应比temp更小的边,反复重复操作直至所有顶点个数都在store内。其中利用judgePoint和judgeEdge两个方法进行判断是否有重复顶点在store内和是否有权比temp更小的边。
    3.5 显示最小生成树从store内不断取值,首先从store内取出起点和其终点和对应的权,之后进入for循环开始不断判断最小生成树是否有分支,如果有分支,则依据store内的终点和对应的边寻找其起点,首先在map中找到对应的边,依据该边在map中的位置能够推测出起点和终点,之后进行判断哪个为起点,便可输出。
    1 评论 27 下载 2018-11-04 18:16:46 下载需要7点积分
  • 基于C++的表达式计算求值

    一、使用说明1.1 项目简介表达式求值是程序设计语言编译中的一个最基本的问题,就是将一个表达式转化为逆波兰表达式并求值。具体要求是以字符序列的形式从终端输入语法正确的、不含变量的整数表达式,并利用给定的优先关系实现对算术四则混合表达式的求值,并演示在求值过程中运算符栈,操作数栈,输入字符和主要操作变化过程。
    要把一个表达式翻译成正确求值的一个机器指令序列,或者直接对表达式求值,首先要能正确解释表达式。任何一个表达式都是由操作符,运算符和界限符组成,我们称它们为单词。一般来说,操作数既可以是常数,又可以是被说明为变量或常量的标识符;运算符可以分成算术运算符,关系运算符和逻辑运算符3类;基本界限符有左右括号和表达式结束符等。为了叙述的简洁,我们仅仅讨论简单算术表达式的求值问题,这种表达式只包括加,减,乘,除4种运算符。
    人们在书写表达式时通常采用的是“中缀”表达形式,也就是将运算符放在两个操作数中间,用这种“中缀”形式表示的表达式称为中缀表达式。但是,这种表达式表示形式对计算机处理来说是不大合适的。对于表达式的表示还有另一种形式,称之为“后缀表达式”,也就是将运算符紧跟在两个操作数的后面。这种表达式比较合适计算机的处理方式,因此要用计算机来处理,计算表达式的问题,首先要将中缀表达式转化成后缀表达式,又称为逆波兰表达式。
    1.2 项目功能要求为了实现表达式求值,本项目要求首先读入表达式(包括括号)并创建对应二叉树,其次对二叉树进行前序遍历,中序遍历,后序遍历,输出对应的波兰表达式,中缀表达式和逆波兰表达式。
    1.3 操作手册运行程序后,进入欢迎界面,首先要输入表达式。
    第一步,输入中缀表达式:

    在输入相应表达式后,会自动显示中缀、前缀、后缀表达式。



    1.4 注意事项
    进行操作时,只能输入1或0进行操作
    操作的表达式形式为中缀表达式,可以进行括号、加减乘除转化
    不能进行表达式的计算,不能输入等号或其他字符。只能输入数字和运算符

    二、概述2.1 基本思路在得到用户输入的中缀表达式后,先利用栈将其转换为后缀表达式,同样再利用栈将其转化为二叉树,之后对二叉树进行中序遍历得到中缀表达式,前序遍历得到前缀表达式,后序遍历得到后缀表达式。
    2.2 文件目录
    Test.cpp (主文件)
    Expression.h (定义TreeNode结构体)
    Expression.cpp (Brother_list类相关函数的具体实现方法)
    test.exe (程序可执行文件)
    设计报告.doc (项目文档)

    三、具体实现3.1 结构体TreeNodeChar data; // 存储数据BinaryNode *left; // 二叉树节点左指针BinaryNode *right; // 二叉树节点右指针
    3.2 方法实现具体说明
    中缀表达式转后缀表达式在得到用户输入的中缀表达式后,首先要将中缀表达式转换为后缀表达式。这里利用了两个栈,operate为运算符栈,number为数字栈,之后对中缀表达式进行遍历,遇到数字则直接输出 ,遇到’(‘压栈 ,遇到’)’持续出栈,如果出栈的符号不是’(‘则输出,否则终止出栈。 遇到符号则判断该符号与栈顶符号的运算优先级,如果栈顶符号的运算优先级高,则出栈并输出,直到优先级相等或栈为空;如果栈顶符号的运算优先级低于或等于当前符号的运算优先级,则将当前符号压栈。 处理完字符串后将栈中剩余的符号全部输出,最后得到后缀表达式suffix_exp。关于判断运算符的优先级,利用了二维数组判断优先级更加方便。
    后缀表达式转换为二叉树遍历后缀表达式每个字符,数字直接入栈,运算符创建二叉树节点,创建二叉树节点后,为其创建左右子节点,将栈顶的两个数据弹出作为左右子节点,再将运算符入栈。
    前序、中序、后序遍历三种遍历方式分别得到前缀、中缀、后缀表达式,此三种遍历方式的方法大致相同,都是使用递归遍历节点,只是顺序不同。前序遍历,前序遍历先将根节点找出,再不断搜寻左子树的节点,最后将右子树的节点找出可得到前缀表达式。中序遍历,中序遍历是先找出左子树的节点,再找出根节点,最后找出右子树的所有节点从而转为中缀表达式。后序遍历,后序遍历是先找到所有左子树节点,再将右子树节点找出,最后找出根节点。
    1 评论 17 下载 2018-11-04 18:13:03 下载需要2点积分
  • 基于C++的关键字检索系统

    一、使用说明1.1 项目简介建立一个文本文件,文件名由用户用键盘输入,输入一个不含空格的关键字,统计输出关键字在文本中的出现次数。
    1.2 项目功能要求本项目的设计要求可以分成两个部分实现:首先建立一个文本文件,文件名由用户用键盘输入;然后输入一个不含空格的关键字,统计输出该单词在文本中的出现次数。
    1.3 操作手册运行程序后,首先要输入文件名。
    第一步,输入文件名。

    之后输入一段文章:

    文章的结尾通过输入”^”进行判断

    接下来要输入检索的关键字,会先显示源文件内容,之后再显示关键词出现的次数:

    1.4 注意事项
    文章输入完毕后需要输入“^”符号表示文章结束。但该符号并不有影响关键字统计
    按数字0结束系统工作

    二、概述2.1 基本思路利用Vector数组来存储文章内容,article用来存储文章内容。在屏幕输入文章后保存到文本文件,同时存入article容器中。在文章的结尾用”^”来标记,为了防止该标记对关键字统计造成影响便将该标记去除。
    2.2 文件目录
    test.cpp (主文件)
    Keyword.cpp(相关函数具体实现)
    Keyword_search.h(头文件)
    test.exe (程序可执行文件)
    设计报告.doc (项目文档)

    三、具体实现3.1 朴素的模式匹配(Find(string main_string, string keyword))朴素的模式匹配,即B-F算法,方法是让模式串与目标串进行逐个字符的比较,若目标串中存在与模式串相同的部分,则函数返回true,否则返回false或从下一个位置开始继续进行逐个字符比较。
    具体的函数操作为,先进行逐趟比较,模式串与目标串从0的位置开始进行比较,如果相同则证明iJ与模式串长度相同直接返回true,如果不同,iX+1,从下一个位置开始继续进行逐趟比较,直到比较完所有字符仍不相同则返回False。
    3.2 KMP算法本题可以用KMP算法去实现,但是过程比较复杂。因为B-F算法速度慢,因为存在回溯的问题,而KMP算法则避免了多余的回溯。KMP算法的核心思想是利用上一次的比较结果,KMP算法首先需要确定子串key中的每一个字符的前缀和后缀的共有元素的最长长度,得到next数组。比如key[6]的共有元素有A和ABCA两个,最长长度为4。假设key[0]~key[5]都与主串相等,但是key[6]不相等,我们不再直接从key[0]开始比较,而是根据其前一位的next值决定。由于key[6]的前一位key[5]的前缀和后缀共有元素为ABC,那么根据(需要向前移动位数=已匹配位数-共有元素最长长度),需要移动6-3=3位,也就是从直接从key[3]开始比较。从上可知,共有元素最长长度是多少,key就跳到以长度为下标处。若是仍不相等的话,就看key[3]的前一位key[2]的前后缀共有元素为0,长度为0,则跳到key[0]来比对,依此类推。
    3.3 其他函数(display_article(vector<string>article),Search(string fileName, vector<string>article))Display_article函数直接展示文章内容,Search函数用来进行关键字检索并给关键字计数。
    四、体会通过这道题,我对朴素模式的匹配方法已经完全掌握,KMP算法的核心思想也已经掌握,但是由于时间问题暂时未能写出KMP算法的具体函数,对于该文字检索系统可以做进一步的改进,可以考虑通过对每个单词判断,将标点符号去除缩短运行的时间。而去除标点符号的方式则只需判断单词的最后一个字符是否为标点,是的话去除即可。
    1 评论 11 下载 2018-11-04 18:04:15 下载需要3点积分
  • 基于C++的勇闯迷宫游戏

    一、使用说明1.1 项目简介迷宫只有两个门,一个门叫入口,另一个门叫出口。一个骑士骑马从入口进入迷宫,迷宫设置很多障碍,骑士需要在迷宫中寻找通路以到达出口。
    1.2 项目功能要求提示:

    可以采用二维数组,回溯和递归或非递归加栈实现
    也可以用BFS算法(即图的广度优先搜索算法,又叫宽度优先搜索算法)
    如果用数组的方法,则如果有多条出路,只需要显示一条出路即可,且不一定需要选出最短出路
    如果用BFS的方法,则需要显示所有的出路

    迷宫问题的求解过程可以采用回溯法,即在一定的约束条件下试探地搜索前进,若前进中受阻,则及时回头纠正错误另择通路继续搜索的方法。从入口出发,按某一方向向前探索,若能走通,即某处可达,则到达新点,否则探索下一个方向;若所有的方向均没有通路,则沿原路返回前一点,换下一个方向再继续试探,直到所有可能的道路都探索到,或找到一条通路,或无路可走又返回入口点。在求解过程中,为了保证在达到某一个点后不能向前继续行走时,能正确返回前一个以便从下一个方向向前试探,则需要在试探过程中保存所能够达到的每个点的下标以及该点前进的方向,当找到出口时试探过程就结束了。
    1.3 项目要求
    迷宫的行数,列数和起点坐标由用户输入(行数和列数可以不相等),不能由程序定死
    迷宫地图需由用户输入,可以用1代表障碍,0代表通路
    规定第一行,最后一行,第一列,最后一列是墙壁。如果迷宫有出路,则必须从墙壁进,最后从墙壁出,但起点和终点不能是同一个点

    1.4 操作手册运行程序后,首先选择要进行的操作。

    第一步,选择操作1自定义地图模式后,输入迷宫的行数和列数以及起始点所在行和所在列。

    第二步,依次输入每个坐标,0表示通路,1表示墙。

    第三步,系统自动显示迷宫地图和路径图以及迷宫路径的坐标。

    第四步,如果迷宫无解则系统显示迷宫无解。

    之后课继续选择操作1重复迷宫游戏,选择操作0退出游戏。
    1.5 注意事项
    输入的迷宫地图必须用1代表墙,0代表通路,不可输入其他数字
    输入迷宫地图时需要每输入一个坐标的值后便回车,利用二维数组存储需要逐个输入,不可整行输入
    输入的迷宫地图和定义的行列数必须保持一致

    二、概述2.1 基本思路基本思想为利用二维数组,通过回溯和递归实现,由上、下、左、右的顺序进行搜索,对任一可行节点进行递归搜索,每一步保存路径。在递归失败之后层层退栈,继续尝试下一可行节点,直到找到出口。然后将迷宫栈逐步出栈即可找到可行路径。在对迷宫栈进行操作的同时保存通路栈。
    2.2 文件目录
    test.cpp (主文件)
    test.exe (程序可执行文件)
    设计报告.doc (项目文档)
    maze.h(头文件)
    maze.cpp(迷宫相关函数实现)

    三、具体实现3.1 几个全局变量
    int row:迷宫行数
    int colum:迷宫列数
    int start_row:起始点坐标所在行
    int start_col:起始点坐标所在列
    int **map:迷宫地图
    Stack *Maze:迷宫栈
    path *Path:通径栈

    3.2 迷宫栈(struck stack)迷宫栈中的x和y表示坐标点(x,y)所在行和所在列,迷宫栈存放着勇闯迷宫游戏中每步前进所在的坐标。
    3.3 通径栈(struck path)通径栈中的x和y表示坐标点(x,y)所在行和所在列,inPath表示该点是否在通径中,因为迷宫栈中存在不在路径中的坐标点,这种点的inPath为false,通径栈主要是为了方便展示迷宫地图和迷宫路径。
    3.4 检测数字是否合法(函数int legal_number(int num))用来检测用户输入的行数、列数、起始点所在行、起始点所在列是否合法,如果小于0则需重新输入直至无误。
    3.5 检测坐标是否已在迷宫栈内(函数bool search(int x, int y))search函数用于检测(x,y)坐标是否已存在于迷宫栈内,即该位置是否走过。通过对迷宫栈内的每个(x,y)坐标与被检测的坐标进行比较,如果存在相同的数据则返回false,否则返回true。
    3.6 判断下一个坐标点是否可走(函数bool escape_maze(int x, int y))该函数为递归函数,在函数开始阶段,先将坐标点(x,y)加入路径栈和迷宫栈,因为该点一定为游戏中走过的坐标点。在加入迷宫栈之前,先判断其是否为终点,如果为终点则直接返回true,游戏结束。判断是否为终点的方法是利用函数search并判断其是否处在边界。
    在完成以上操作后,开始向四个方向探索,分别先是上、下、左、右,如果被探索的点不在迷宫栈内,且该点为通路,并且没有超出迷宫范围,则以该点为x,y进入下一次递归,再次调用escape_maze函数,直到所有方向都不行,迷宫栈元素出栈,并且该点的inPath标志为false,否则为true。
    3.7 开始进行递归的函数(函数void maze())该函数与excape_maze函数相似,只是进行迷宫游戏的第一步。
    3.8 判断坐标是否在通径栈内(函数bool inPath(int i, int j))该行数用于判断坐标是否在通径栈内,实现方法类似于search函数。
    3.9 展示迷宫(函数void display_maze())该函数用于展示迷宫地图和迷宫路径。
    3.10 迷宫游戏主程序(void maze_game())该函数用于建立迷宫,展示迷宫,展示路径等操作。
    1 评论 18 下载 2018-11-04 18:00:17 下载需要4点积分
  • 基于C++实现的考试报名系统

    一、使用说明1.1 项目简介考试报名工作给各高校报名工作带来了新的挑战,给教务管理部门增加了很大的工作量。本项目是对考试报名管理的简单模拟,用控制台选项的选择方式完成下列功能:输入考生信息;输出考生信息;查询考生信息;添加考生信息;修改考生信息;删除考生信息。
    1.2 项目功能要求本项目的实质是完成对考生信息的建立,查找,插入,修改,删除等功能。其中考生信息包括准考证号,姓名,性别,年龄和报考类别等信息。项目在设计时应首先确定系统的数据结构,定义类的成员变量和成员函数;然后实现各成员函数以完成对数据操作的相应功能;最后完成主函数以验证各个成员函数的功能并得到运行结果。
    1.3 操作手册运行程序后,进入欢迎界面,首先要输入考生的数据。
    第一步,输入所有考生的信息。

    之后会显示所有考生的信息。

    在指定位置插入一个考生信息,例如:

    在位置5插入stu5的信息。
    成功后,系统会显示插入完成后的所有信息。

    删除指定考号的考生信息,例如:

    删除考号为2的学生。删除后系统会显示删除的考生信息和删除操作后的所有信息。

    查找指定考号的考生信息,例如:

    查找考号为3的考试信息。查找完成后系统会显示查找到的考生信息。

    修改指定考号的考生信息,例如:

    修改考号为3的考生的信息。修改完成后系统会显示所有考生信息。

    既统计考生人数又可以统计报考某一类别的考生数量,系统会显示报考该类别的人数。

    1.4 注意事项
    本系统的考号请勿超过9位(16位操作系统请勿超过5位)
    本系统不自动储存考生信息,请自行复制系统打印的信息另行保存
    本系统没有设计排序功能,所以所有查找都采用顺序查找,大数据量可能较慢,请耐心等待

    二、概述2.1 基本思路使用双向链表来存储考生的基本信息,对考生报名系统的所有操作都是通过对双向链表来进行,用链表存储数据更加灵活方便,对双向链表进行插入、删除、查找等操作比较方便。链表是用linkedList类来实现,考生的信息是存储在结构体STU中。链表的头指针和尾指针作为全局变量使用。
    2.2 文件目录
    test.cpp (主文件)
    1.h (定义linkedlist类和STU结构体)
    2.h (linkedlist类相关函数的具体实现方法)
    test.exe (程序可执行文件)
    设计报告.doc (项目文档)

    2.3 具体实现linkedlist接口



    成员函数名
    功能
    参数




    linkedlist ()
    默认构造函数,设定链表长度为0。



    ~linkedlist ()
    析构函数,清空全表



    insertStu()
    插入函数,在输入pos位置后插入*insertStu



    copyStu(STU *student1,STU &student2)
    将student2的信息复制给student1
    被拷贝的信息student2 拷贝的信息student1


    addStu(STU &item)
    添加考生信息
    添加的信息item


    editStu()
    按考号编辑考生信息



    findStu ()
    查找考生信息



    findStu(int item)
    按考号查找考生信息
    item为考号


    showStu()
    展示所有考生信息



    StaStu()
    按报考类别统计考生信息



    2.2 结构体STU
    考生姓名 stuName(string)
    考号 stuTestNum(int)
    年龄 stuAge(int)
    性别 stuSex(string)
    报考类别 stuCategory(string)
    前指针 pre (STU*)
    后指针 next (STU*)

    2.3 方法实现具体说明
    构造函数:将链表长度设置为 0
    析构函数:释放结构体
    插入函数:用户输入插入位置,插入方式为调用类方法findStu(int pos)找到该位置,判断该位置是第一个、最后一个还是中间的位置。然后操作前后指针进行插入,同时动态生成需要插入的数据,最后链表长度加一
    查找函数:根据用户插入的位置,建立一个头指针,依次从头寻找到该位置,将该位置考生的信息输出
    删除函数:根据输入的考生的考号,先判断其位置,找到需要删除的结构体之后,对其前后指针进行操作,将其从链表中脱离出来,然后将其内存释放
    编辑函数:根据输入的考生的考号,找到考生的位置,重新输入考生的信息
    统计函数:先是统计出所有考生人数,然后根据输入的考生的报考类别,对当前链表进行一次遍历,遍历过程中,通过字符串比较,得出报考人数
    1 评论 27 下载 2018-11-04 17:57:05 下载需要2点积分
  • 基于C++的约瑟夫生者死者游戏

    一、使用说明1.1 项目简介约瑟夫生者死者游戏的大意是:30个旅客同乘一条船,因为严重超载,加上风高浪大危险万分;因此船长告诉乘客,只有将全船一半的旅客投入海中,其余人才能幸免于难。无奈,大家只得同意这种方法,并议定30个人围成一圈,由第一个人开始,依次报数,数到第9人,便将他投入大海中,然后从他的下一个人数起,数到第9人,再将他投入大海,如此循环,直到剩下15个乘客为止。问哪些位置是将被扔下大海的位置。
    1.2 项目功能要求本游戏的数学建模如下:假如N个旅客排成一个环形,依次顺序编号1, 2, …, N。从某个指定的第S号开始。沿环计数,每数到第M个人就让其出列,且从下一个人开始重新计数,继续进行下去。这个过程一直进行到剩下K个旅客为止。
    本游戏要求用户输入的内容包括:

    旅客的个数,也就是N的值
    离开旅客的间隔数,也就是M的值
    所有旅客的序号作为一组数据要求存放在某种数据结构中

    本游戏要求输出的内容包括:

    离开旅客的序号
    剩余旅客的序号

    1.3 操作手册运行程序后,进入欢迎界面,首先要输入数据。
    第一步,输入生死游戏的总人数N、游戏开始的位置S、死亡数字M、剩余的生者人数K。

    之后会显示离开旅客的序号和剩余旅客的序号。

    1.4 注意事项
    所有数据必须大于等于0
    生者人数要小于等于总人数
    死亡数字要小于总人数

    二、概述2.1 基本思路使用单循环链表来存储旅客的位置信息,然后在for循环内找到死亡旅客的位置,找到该位置后将前一个位置的next指针连接到下一个位置上,相当于删除了该死亡旅客的位置,并将其信息打印出来,之后总人数减一。逐步寻找并删除,直至总人数等于幸存者人数,然后按位置的大小顺序排序后打印出幸存者位置。
    2.2 文件目录:
    test.cpp (主文件)
    Struct.h (结构体Struct和核心函数)
    test.exe (程序可执行文件)
    设计报告.doc (项目文档)

    三、具体实现3.1 结构体travellerpos 位置 (int)、*next 链接用指针(traveller)
    3.2 方法实现具体说明创建一个单循环链表temp用来存储所有旅客的位置信息,然后处理一下位置为1时的特殊情况,之后用for循环开始寻找死亡旅客的位置,找到后将其前一个数据的指针链接到下一个数据,相当于删除了该数据,并将其位置信息打印出来,总人数减一,之后不断寻找直至总人数和幸存人数相同,然后按位置大小顺序将幸存者位置打印出来。
    1 评论 7 下载 2018-11-04 17:53:15 下载需要2点积分
  • 基于QT实现的可视化链表(单链表、循环链表、双向链表)

    1.1 题目题号1:分别以单链表、循环链表、双向链表为例,实现线性表的建立、插入、删除、查找等基本操作。
    要求:能够把建立、插入、删除等基本操作的过程随时显示输出来。
    1.2 软件功能功能分为三个板块,分别是单链表、循环链表、双向链表的建立、插入、删除等基本操作的过程。
    单链表

    查看单链表定义,相应算法代码
    建立一个带头结点的空单链表
    指定插入位置及元素值到单链表中
    随机插入5个元素到单链表的尾部
    指定删除元素位置(从1开始),从单链表中删除
    输入查找值,得到元素在单链表中位置
    清空销毁单链表
    能够调整演示的速度快慢

    循环链表

    查看循环链表定义,相应算法代码
    建立一个带头结点的空循环链表
    指定插入位置及元素值到循环链表中
    随机插入5个元素到循环链表的尾部
    指定删除元素位置(从1开始),从循环链表中删除
    输入查找值,得到元素在循环链表中位置
    清空销毁循环链表
    能够调整演示的速度快慢

    双向链表

    查看双向链表定义,相应算法代码
    建立一个带头结点的空双向链表
    指定插入位置及元素值到双向链表中
    随机插入5个元素到双向链表的尾部
    指定删除元素位置(从1开始),从双向链表中删除
    输入查找值,得到元素在双向链表中位置
    清空销毁双向链表
    能够调整演示的速度快慢

    上述所有功能采用面向对象的方法通过C++语言程序结合QT框架实现,后面会详细介绍。
    1.3 设计思想
    学习相应知识,做好必要的准备工作由于以前都是采用控制台进行编程,即便涉及一些简单的图像界面,但是比较粗制简陋,无法入眼,并不是标准规范、人性化的用户交互界面,所以要完成本次的数据结构课程设计必须从零起步,学习可视化编程开发。在C++的一系列可视化开发框架下,我选择用Qt来实现程序的功能,因为Qt相对较为简单,容易上手入门,同时Qt是较为新兴的技术框架,并且跨平台开发,很有前景和实用性。通过几天的学习,理解掌握的Qt的必要知识,包括最为核心的信号和槽函数机制、UI控件的使用、Scene-View视图框架等核心技术。
    自顶向下设计有了必要的准备知识,就可以进行程序的总体规划设计了。自顶向下分析是常用的分析方法,本次题目其实较为简单,常用的链表结构我们在学习数据结构课程时已经非常熟练,此次实现图形化界面的演示需要结合原有结构,融入图形化元素和用户界面接口,对程序的功能分析,显然程序的功能分为三个子功能模块,分别对每个模块进行设计即可完成整个任务。
    分模块实现虽然程序有三个部分组成,但是每个部分的功能需要完全一样,用户界面完全一样,划分为三个模块,只要实现一个模块,其余两个模块只要非常短的时间就可完成。实际开发时,先实现单链表模块,完成以后,循环链表和双向链表只需要在前面基础上稍作修改即可。
    自底向上实现具体实现时,先定义每个类的属性和相应函数,然后根据定义,设计相应算法自底向上进行实现,逐个击破,最终完成所有程序的设计。

    1.4 逻辑结构与物理结构1.4.1 单链表节点定义

    单链表

    1.4.2 循环链表节点定义

    循环链表

    1.4.3 双向(循环)链表节点定义

    双向循环链表

    1.5 开发平台1.5.1 开发平台
    计算机型号:惠普Pavilion M4
    计算机内存:4.00GB
    CPU:Intel Core i5 2.6GHz
    操作系统:Windows 10 家庭版
    开发语言:C++(C++11标准以上)
    开发框架:QT
    集成开发环境:Qt Version 5.9.1
    编译器:MinGW 32bit

    1.5.2 运行环境
    可在上述集成环境下运行
    通过windeployqt.exe及Enigma Virtual Box进行整合压缩为发布为了一个 LinkListVisualizer.exe 文件,可在普通 Windows 机型下运行

    1.6 系统的运行结果分析说明1.6.1 调试及开发过程1.6.1.1 调试本次开发采用的是新技术框架Qt,同时也是跨平台的,在Qt Creator中开发调试,Qt中包含了大量的库类,类似于java开发简便,Qt有较好的调试器,但是在本次开发中没有用到,偶尔遇到一些小麻烦或者小bug,我们只需在控制台中输出一些数据便可分析定位错误原因。
    例如:

    输出:

    1.6.1.2 开发本题目虽然有三个小题,但是三个子题目大同小异,架构类似,所以采用分模块逐步开发方式。先确定主窗口,控制好整体界面和架构,然后完成最简单的单链表设计和开发,单链表完成以后整个题目大部分工作已经完成,剩下循环链表和双向链表只需要简单修改就可完成。
    1.6.2 成果分析1.6.2.1 正确性经过多次不同角度的验证,程序表现的十分优秀,与预期没有任何差错。
    单链表运行样例图



    循环链表运行样例图




    双向(循环)链表运行样例图



    1.6.2.2 稳定性图形的大小均采用了宏定义,可根据需要随时调整。

    可通过下拉框和左右拉框看到调整大小和未显示的区域。

    在不同速度调节下,不同速度均表现的十分稳定。

    三个小部件均能同时稳定正确运行。

    1.6.2.3 容错能力本程序有非常好的容错能力,如下:
    按钮只有在能够进行操作的情况下,才会处于有效状态,例如,初始时,只能“创建”,不能“插入”、“删除”等操作;

    在没有节点时,不能“删除”;

    输入利用控件保证输入的正确性;插入删除位置通过选择保证正确;

    输入的合理性通过输入控件保证,当要求输入数字时,输入其它非法字符将不会处理,输入范围在[-999999999, 999999999],其它范围是无法输入的。
    1.7 操作说明本题目分为了三个部分,分别是单链表、循环链表、双向链表的基本操作演示。通过前面介绍的运行环境下进行程序的运行。
    1.7.1 主界面操作1.7.1.1 主界面按下相应按钮进入相应功能。

    将鼠标悬停在相应按钮上可得到相应提示。



    1.7.2 单链表1.7.2.1 进入功能区点击主菜单的“单链表”进入,可以看到初始界面:
    按钮或输入控件较亮表示可以点击或输入,否则处于不可编辑状态。

    1.7.2.2 调节演示速度右下角有操作后的状态提示及过程显示的速度快慢调节器,状态提示不可编辑,速度调节器可以通过鼠标直接“点击”或者点击后按“左右方向键”进行速度调节,最右段为最快速度。

    1.7.2.3 创建单链表点击创建按钮可以创建一个单链表,或者在已经创建一个单链表后销毁并重新创建新的单链表。

    1.7.2.4 插入节点插入节点有两种方式,可以手动插入,也可自动插入。
    手动插入节点方式:

    点击插入位置下拉框,选择插入位置(从1开始)在插入文本框中输入插入值点击插入

    点击“尾端随机5个”按钮,即可自动插入五个随机值到链表尾部去。

    1.7.2.5 删除节点点击删除位置下拉框,可选择相应的删除节点位置,然后点击删除按钮。

    删除后

    1.7.2.5 查找节点在查找值中输入要查找的值,点击“查找”按钮。

    查找结果:

    1.7.2.6 销毁链表点击清空按钮,清空单链表,释放资源。

    1.7.3 循环链表循环链表的操作与单链表完全一样,不再赘述。
    1.7.4 双向(循环)链表双向循环链表的操作与单链表完全一样,不再赘述。
    1 评论 23 下载 2018-11-04 17:36:08 下载需要3点积分
  • 基于栈和队列的停车场管理系统

    1 问题描述设停车场内只有一个可停放n辆汽车的狭长通道,且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序,依次由北向南排列(大门在最南端,最先到达的第一辆车停放在车场的最北端),若车场内已停满n辆汽车,则后来的汽车只能在门外的便道上等候,一旦有车开走,则排在便道上的第一辆车即可开入。
    当停车场内某辆车要离开时,在它之后开入的车辆必须先退出车场为它让路,待该辆车开出大门外,其它车辆再按原次序进入车场,每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。
    试为停车场编制按上述要求进行管理的模拟程序。
    2 基本要求综合利用栈和队列模拟停车场管理,学习利用栈和队列解决实际问题。
    以栈模拟停车场,以队列模拟车场外的便道,按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项:汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻,对每一组输入数据进行操作后的输出数据为:若是车辆到达,则输出汽车在停车场内或便道上的停车位置;若是车离去;则输出汽车在停车场内停留的时间和应交纳的费用(在便道上停留的时间不收费)。栈以顺序结构实现,队列以链表实现。
    需另设一个栈,临时停放为给要离去的汽车让路而从停车场退出来的汽车,也用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车,包含两个数据项:汽车的牌照号码和进入停车场的时刻。
    3 算法思想停车场运用栈的算法思想管理车辆信息;便道运用队列的算法思想管理等待进入停车场的车辆信息;临时停放让路的车辆信息也用队列算法思想管理。
    4 模块划分// 其功能为打印出场车的信息void PRINT(CarNode *p,int room);// 其功能为记录进场车和等待进场车信息void Arrive(SeqStackCar *Enter,LinkQueueCar *W);// 其功能为记录出场车信息void Leave(SeqStackCar *Enter,SeqStackCar *Temp,LinkQueueCar *W);// 其功能为显示存车信息void List1(SeqStackCar *S);
    5 数据结构数据类型Time定义如下:
    typedef struct time{ int hour; int min;}Time;
    数据类型CarNode定义如下:
    typedef struct node{ char num[10]; Time reach; Time leave;}CarNode;
    数据类型SeqStackCar定义如下:
    typedef struct NODE{ CarNode *stack[MAX+1]; int top;}SeqStackCar;
    数据类型QueueNode定义如下:
    typedef struct car{ CarNode *data; struct car *next;}QueueNode;
    数据类型LinkQueueCar定义如下:
    typedef struct Node{ QueueNode *head; QueueNode *rear;}LinkQueueCar;
    6 测试


    1 评论 14 下载 2018-11-04 17:13:54 下载需要3点积分
  • 基于C++实现的N皇后问题

    一、使用说明1.1 项目简介八皇后问题是一个古老而著名的问题,是回溯算法的经典问题。该问题是十九世纪著名的数学家高斯在1850年提出的:在8*8的国际象棋棋盘上,安放8个皇后,要求没有一个皇后能够“吃掉”任何其它一个皇后,即任意两个皇后不能处于同一行,同一列或者同一条对角线上,求解有多少种摆法。
    高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解,后来有人用图论的方法得到结论,有92种摆法。
    本实验拓展了N皇后问题,即皇后个数由用户输入。
    1.2 项目要求八皇后在棋盘上分布的各种可能的格局数目非常大,约等于2的32次方种,但是,可以将一些明显不满足问题要求的格局排除掉。由于任意两个皇后不能同行,即每行只能放置一个皇后,因此将第i个皇后放在第i行上,这样在放置第i个皇后时,只要考虑它与前i-1个皇后处于不同列和不同对角线位置上即可。
    解决这个问题采用回溯法,首先将第一个皇后放置在第一行第一列,然后,依次在下一行上放置一个皇后,直到八个皇后全部放置安全。在放置每个皇后时,都依次对每一列进行检测,首先检测放在第一列是否与已放置的皇后冲突,如不冲突,则将皇后放置在该列,否则,选择该行的下一列进行检测。如整行的八列都冲突,则回到上一行,重新选择位置,依此类推。
    1.3 操作手册运行程序后,首先要输入皇后的个数N:

    这里输入4为皇后个数后出现该问题的2种解法:

    同样输入6时,会出现4种解法:

    每次完成一次解法后可以考虑是否重新输入皇后个数:

    1.4 注意事项
    每次输入的皇后的个数不要太大,且不能小于等于0
    再判断是否重新输入皇后个数时只能输入“Y”或“N”

    二、概述2.1 基本思路基本思想是采用了提示中的回溯和递归,但并未采用二维数组而是用了一维数组。回溯算法的基本思想是:从一条路往前走,能进则进,不能进则退回来,换一条路再试。而用一维数组的原因是,这样做不仅压缩了空间规模,判断冲突也十分简单。首先每行只有一个皇后,且在数组中只占据一个元素的位置,行冲突就不存在了,其次是列冲突,判断一下是否有a[i]与当前要放置皇后的列j相等即可。至于斜线冲突,通过观察可以发现所有在斜线上冲突的皇后的位置都有规律即它们所在的行列互减的绝对值相等,即| row – i | = | col – a[i] | 。这样某个位置是否可以放置皇后的问题已经解决。
    2.2 文件目录test.cpp (主文件)test.exe (程序可执行文件)设计报告.doc (项目文档)NQueen.h(头文件)NQueen.cpp(迷宫相关函数实现)
    三、具体实现3.1 几个全局变量int sum; // 解法种类数 int Queen[20]; // 各皇后所在行号
    3.2 N皇后问题主函数(void NQueen(int iQueen))将sum置0,并且开始搜寻问题的解决方案。
    3.3 放置皇后到棋盘上(void place(int row, int iQueen))首先进行判断,如果此时的行数row已经大于iQueen皇后个数,则已经找到一种解法,直接展示该解法。否则开始试探row行的每一列,完成该列之后开始进行下一次递归。
    3.4 检验第i行的k列上是否可以摆放皇后 (int find(int i, int k))j=1~i-1是已经放置了皇后的行,当j<i时,判断第j行的皇后是否在k列或(j,Queen[j])与(i,k)是否在斜线上,如果不在,继续检测下一行,如果存在,返回0。
    3.5 展示每种解法(void print(int n))先打印出每种解法中皇后所在位置,从iX=1开始,对应Queen[iX]所存列数,之后通过“X”表示皇后的位置,其余位置用“0”表示,展示棋盘。
    1 评论 4 下载 2018-11-04 17:09:36 下载需要4点积分
  • Linux环境下的针对PL0语言的语法词法语义分析

    摘 要此次编译原理课程设计,我利用flex工具进行PL/0语言的词法分析、自己用C++语言实现了LR语法分析、语义分析以及中间代码生成,我选择的是布尔表达式文法,对符合文法的布尔表达式能够产生相应四元式,处理了控制结构的真链与假链,对错误的表达式能够给出错误提示。
    鉴于flex工具原本来自Unix以及个人日常习惯,本实验开发环境选用Linux,代码在Ubuntu16.10中测试通过。
    关键字:flex;词法分析;Linux;语法分析;中间代码生成;真假链
    引 言编译原理是一门实践性比较强的学科,学习了课本上理论知识,阅读了书后示例PL/0编译程序,此次课程设计针对PL/0语言进行了词法分析、语法分析及布尔表达式的中间代码(四元式)生成。其中PL/0的词法分析程序的功能是为语法语义分析提供单词,把输入的字符串形式的源程序分割成一个个单词符号传递给语法语义分析;而语法分析的任务是识别单词符号序列是否符合给定的语法规则。实验中在语法分析过程中需要用到flex工具,这个工具源于Unix和Linux,很多同学使用Windows还需要配置相关环境,我日常使用Linux,因此选用它作为编程环境,免去了不必要的麻烦,配置较为方便。
    一、实验目的实现对布尔表达式的词法分析、语法分析、语义分析并产生四元式中间代码,完成真假链的回填及合并。
    1.1 词法分析部分利用C++和flex工具设计编写一个词法分析程序,实现对标志符、数字、保留字和算符等一系列符号的识别,用于后面做语法分析和语义分析;
    1.2 语法分析部分采用LR(0)语法分析方法,设计、开发如下文法描述语言的语法分析程序,实现对词法分析程序所提供的单词序列进行语法检查和结构分析,加深课堂相关理论教学内容的理解,提高语法分析方法的实践能力。语法分析完成之后可用于语义分析。
    1.3 语义分析部分基于以上两步词法和语法分析的工作,采用一边归约一边建立语义栈并做语义分析的方法,分析给出的布尔表达式是否符合相应文法,最后产生四元式 ,实现真假链的回填及合并 。
    二、实验内容2.1 词法分析阶段词法分析阶段的任务是从左到右一个字符一个字符地读入源程序,对构成源程序的字符流进行扫描和分解,从而识别出一个个单词。利用词法分析程序实现对某输入串的词法分析,将各个符号识别并送给语法分析程序;
    2.2 语法分析阶段利用上述词法分析的结果,一个一个送进LR语法分析的函数 SLR_parser而判断整个输入串是否满足布尔表达式的文法,具体文法如下:
    布尔表达式文法
    [1]E -> E or E[2]E -> E and E[3]E -> not E[4]E -> ( E )[5]E -> id rop id[6]E -> true[7]E -> false
    其中:E-布尔表达式,rop-关系运算符
    2.3 语义分析阶段语义分析阶段,利用上述两步的结果,在归约和移进的过程做语义分析并产生四元式。语义分析时,我将用于语法分析的函数SLR_parser进行扩充,使之在每步归约的时候做中间代码生成以及回填的工作。
    具体的流程如下:

    词法分析之后的语法和语义分析详细过程如下图所示:

    三、主要实现功能3.1 功能一:词法分析接收字符串形式的源程序,按照源程序输入的次序依次扫描源程序,在扫描的同时根据语言的词法规则识别出具有独立意义的单词,并产生与源程序等价的属性字(Token)流。
    我的词法分析通过从读取源文件,得到输入串,利用flex工具,写正则表达式去匹配单词,识别它们的类型,分析结果存到mytoken数组中,待语法分析和语义分析程序使用。
    3.2 功能二:语法分析语法分析是编译过程的一个逻辑阶段。语法分析的任务是在词法分析的基础上将单词序列组合成各类语法短语,如“程序”,“语句”,“表达式”等等.语法分析程序判断源程序在结构上是否正确.源程序的结构由上下文无关文法描述.语法分析程序可以用YACC等工具自动生成。
    应所给题目要求,这里不借助yacc工具,而是自己手写C++代码,完成相应功能。SLR(1)分析核心是要得到一张SLR(1)分析表,理论上可以通过编程求first集和follow集,进而得到这张表。这里我们采用手写的方式得到这张分析表,然后建立状态栈和符号栈,不断查表判断是应该归约还是移进。
    3.3 功能三:语义分析语义分析是编译过程的一个逻辑阶段, 语义分析的任务是对结构上正确的源程序进行上下文有关性质的审查,进行类型审查。语义分析是审查源程序有无语义错误,为代码生成阶段收集类型信息。
    本次课程设计最终目的是产生布尔表达式对应的四元式。上一步语法分析主要通过一个函数SLR_parser实现,此步的语义分析及目标代码生成及真假链的回填与合并是在归约的时候做的,于是就把函数SLR_parser继续扩充,遇到归约就调用相应的函数来生成四元式,实现书上的布尔表达式翻译方案,完成回填和合并工作。如果输入串符合语法 , 把最终生成的四元式写入pcode.txt;若不合语法,给出错误提示。
    四、主要功能的设计4.1 词法分析词法分析部分借助flex工具,我的C++代码pl0lex.cpp完成这一功能,在%{和%}之间写自己的C++代码,之外写正则表达式去匹配相应的符号,在{和}之间写匹配后应该做的事务。通过man flex命令查看系统中flex的帮助文档,我学会了如何让程序既可以从控制台读入又可以从文本读入,主函数是int main( int argc, char **argv ),通过判断调用时后面是带参数函数还是不带参数,选择用标准输入输出还是从文件读入。在每次匹配成功,用于统计总共符号数的total_token加一,rawstr字符串数组存入已经读入的原字符串,mytoken数组存入识别后的结果。这两者有一种对应关系,比如rawstr字符串数组中有一个是x,则mytoken数组中相应位置就存其类型:标识符;rawstr中是大于小于大于等于这类符号,mytoken就存其类型:关系运算符。这样就达到了词法分析的目的,同时还存好了原来的语义值。
    对照课本P15的PL/0语言文法的EBNF表示,通过阅读EBNF范式,我将其逐步转化为正则表达式代码。
    PL/0语言文法的EBNF表示<程序>::=<分程序>.<分程序> ::=[<常量说明>][<变量说明>][<过程说明>]<语句><常量说明> ::=CONST<常量定义>{,<常量定义>};<常量定义> ::=<标识符>=<无符号整数><无符号整数> ::= <数字>{<数字>}<变量说明> ::=VAR <标识符>{, <标识符>};<标识符> ::=<字母>{<字母>|<数字>}<过程说明> ::=<过程首部><分程序>{; <过程说明> };<过程首部> ::=PROCEDURE <标识符>;<语句> ::=<赋值语句>|<条件语句>|<当循环语句>|<过程调用语句> |<复合语句>|<读语句><写语句>|<空><赋值语句> ::=<标识符>:=<表达式><复合语句> ::=BEGIN <语句> {;<语句> }END<条件语句> ::= <表达式> <关系运算符> <表达式> |ODD<表达式> <表达式> ::= [+|-]<项>{<加法运算符> <项>}<项> ::= <因子>{<乘法运算符> <因子>}<因子> ::= <标识符>|<无符号整数>| ‘(’<表达式>‘)’<加法运算符> ::= +|-<乘法运算符> ::= *|/<关系运算符> ::= =|#|<|<=|>|>=<条件语句> ::= IF <条件> THEN <语句><过程调用语句> ::= CALL 标识符<当循环语句> ::= WHILE <条件> DO <语句><读语句> ::= READ‘(’<标识符>{,<标识符>}‘)’<写语句> ::= WRITE‘(’<表达式>{,<表达式>}‘)’<字母> ::= a|b|…|X|Y|Z<数字> ::= 0|1|…|8|9
    PL/0语言的词汇表


    序号
    类别
    单词
    编码




    1
    基本字
    begin, call, const, do, end if, odd, procedure, read then, var, while, write
    beginsym, callsym, constsym dosym, endsym, ifsym, oddsym proceduresym, readsym, thensym varsym, whilesym, writesym


    2
    标识符

    ident


    3
    常数

    number


    4
    运算符
    +, -, *, /, odd =, <>, <, <=, >, >=, :=
    plus, minus, times, slash, oddsym eql, neq, lss, leq, gtr, geq, becomes


    5
    界符
    ( ) , ;.
    Lparen, rparen, comma, semicolon period



    这里像比较高层的程序分程序这种不在词法分析中识别,词法分析中识别的主要是比较低层的单词。
    正则匹配识别函数的设计:
    %%not {/*SLR*/printf("%s:非\n",yytext);mytoken[total_token]=notsym; rawstr[total_token]=yytext; total_token++;/*notsym*/}and {/*SLR*/printf("%s:与\n",yytext);mytoken[total_token]=andsym; rawstr[total_token]=yytext; total_token++;/*andsym*/}or {/*SLR*/printf("%s:或\n",yytext);mytoken[total_token]=orsym; rawstr[total_token]=yytext; total_token++;/*orsym*/}true {/*SLR*/printf("%s:真\n",yytext);mytoken[total_token]=truesym; rawstr[total_token]=yytext; total_token++;/*truesym*/}false {/*SLR*/printf("%s:假\n",yytext);mytoken[total_token]=falsesym; rawstr[total_token]=yytext; total_token++;/*falsesym*/}
    以下省略了匹配成功后相应的代码,基本只列出正则表达式,其中很多是直接匹配。
    begin { /*beginsym*/}call { /*callsym*/}const { /*constsym*/}do { /*dosym*/}end { /*endsym*/}if { /*ifsym*/}odd { /*oddsym*/}procedure { /*procsym*/}read { /*readsym*/}then { /*thensym*/}var { /*var*/}while { /*whilesym*/}write { /*writesym*/}[+] { /*plus*/}[-] { /*pminus*/}[*] { /*times*/}[/] { /*slash*/}[(] { /*lparen*/}[)] { /*rparen*/}[=] { /*eql*/}[,] { /*comma*/}[.] { /*period*/}[#] { /*neg*/}[;] { /*semicolon*/}[<>]|>=|<=|==|!= { /*relationop*/}[*|/] { /*乘法运算符*/}[0-9]* { /*number*/}:= { /*become*/}[0-9][0-9]* { /*无符号整数*/}^-?\d+$ { /*整数*/}[A-Za-z]|[A-Za-z][A-Za-z0-9]* { /*标识符ident*/}\n { /*printf("%s:换行符\n",yytext);*/ ++num_lines; ++num_chars;}[\t\r] { /*printf("%s:制表符\n",yytext);*//*过滤空白*/}[ ] { /*printf("%s:空白\n",yytext);*/} . { ++num_chars;}%%
    这样把所有合法符号判断其类型,映射到枚举类型Token中,Token中的类型如下:
    typedef enum{ /*Boolean expression SLR实验相关*/ notsym,andsym,orsym,truesym,falsesym, /*VN*/ beginsym,callsym,constsym,dosym,endsym,ifsym, oddsym,procsym,readsym,thensym,varsym,whilesym, writesym,pplus,pminus,times,slash,lparen,rparen, eql,comma,period,neg,semicolon, /*VT*/ ident,/*标识符*/ number,/*数字*/ block ,factor, expression, term,condition, relationop,/*关系运算符号*/ become/*赋值符号 :=*/}Token;
    这里类型的命名尽量和书上保持一直,体现规范,从名称不难得知其含义。
    4.2 语法分析要做语法分析需要先保存词法分析的结果,正如上文所说,rawstr字符串数组保存原始字符串,mytoken字符串数组保存识别后的类型,在做语法分析之前,首先得画文法的项目集,我分析的是布尔表达式文法。
    布尔表达式文法如下:
    [1]E -> E or E[2]E -> E and E[3]E -> not E[4]E -> ( E )[5]E -> id rop id[6]E -> true[7]E -> false
    其中:E-布尔表达式,rop-关系运算符
    这里为书写方便 or简写为| ,and 写为 & ,not写为!,rop简写为p ,true和false分别写为1和0。
    E -> E | EE -> E & EE -> ! EE -> ( E )E -> id p idE -> 1E -> 0
    分析之后,一共有I0到I15这16个项目集,项目集结果如下:
    I0 项目集 E' -> .E E -> .E | E E -> .E & E E -> .! E E -> .( E ) E -> .id p id E -> .1 E -> .0 达到状态I0 以后遇到E,转向状态I1以此类推E,1;!,2;(,3;id,4;1,5;0,6I1 项目集 E' -> E . E -> E .| E E -> E .& E 达到状态I1 以后遇到|,转向状态I7以此类推|,7;&,8I2 项目集 E -> ! .E E -> .E | E E -> .E & E E -> .! E E -> .( E ) E -> .id p id E -> .1 E -> .0 达到状态I2 以后遇到E,转向状态I9以此类推E,9 ;!,2 ;(,3 ;id,4 ;1,5 ; 0,6I3 项目集 E -> ( .E ) E -> .E | E E -> .E & E E -> .! E E -> .( E ) E -> .id p id E -> .1 E -> .0 达到状态I3 以后遇到E,转向状态I9以此类推E,10 ;!,2 ;(,3 ;id,4 ;1,5 ;0,6I4 项目集 E -> id .p id 达到状态I4 以后遇到p,转向状态I11以此类推p,11I5 项目集 E -> 1 . I6 项目集 E -> 0 . I7 项目集 E -> E | .E E -> .E | E E -> .E & E E -> .! E E -> .( E ) E -> .id p id E -> .1 E -> .0 达到状态I7 以后遇到E,转向状态I12以此类推E,12 ;!,2 ;(,3 ;id,4 ;1,5 ;0,6I8 项目集 E -> E & .E E -> .E | E E -> .E & E E -> .! E E -> .( E ) E -> .id p id E -> .1 E -> .0 达到状态I8 以后遇到E,转向状态I13以此类推E,13 ;!,2 ;(,3 ;id,4 ;1,5 ;0,6I9 项目集 E -> ! E . E -> E .| E E -> E .& E 达到状态I9 以后遇到|,转向状态I7以此类推|,7&,8I10 项目集 E -> ( E .) E -> E .| E E -> E .& E 达到状态I10 以后遇到),转向状态I14以此类推),14 ;|,7 ;&,8I11 项目集 E -> id p .id 达到状态I11 以后遇到id,转向状态I15以此类推id,15I12 项目集 E -> E | E . E -> E .| E E -> E .& E 达到状态I12 以后遇到E ,转向状态I7以此类推|,7 ;&,8I13 项目集 E -> E & E . E -> E .| E E -> E .& E 达到状态I13 以后遇到|,转向状态I7以此类推|,7 ;&,8I14 项目集 E -> ( E ) . I15 项目集 E -> id p id .
    在根据以上的项目集设计SLR(1)语法分析表如下:

    在实现的过程中,我发现自己对LR分析的理解还不够深入,通过阅读经典的龙书,学习其上对算法的描述,得到了启示。
    本次用到的布尔表达式文法:
    [1]E->E or E[2]E-> E and E[3]E->not E[4]E->(E)[5]E->id rop id[6]E->true[7]E->false
    龙书《Compiler》P251第四章语法分析对LR文法的算法描述:

    龙书中描述的LR分析的算法:
    let a be the first symbol of w$; while(l) { / * repeat forever * / let s be the state on top of the stack; if ( ACTION[S, a ] = shift t ) { push t onto the stack; let a be the next input symbol; } else if ( ACTION[S, a ] = reduce A -> beta) { pop beta symbols off the stack; let state t now be on top of the stack; push GOTO [t, A] onto the stack; output the production A -> beta; } else if ( ACTION[S, a ] = accept ) break; / * parsing is done * / else call error-recovery routine; }
    读懂了龙书中LR分析的算法描述, 我的SLR(1)分析的总控程序就好写了。
    我的语法分析的核心函数是SLR_parser,这个函数也是围绕一个while(1)的循环展开,在这个循环中,每次读入一个识别好的符号,然后就去查表,这里我把Action表和Goto表都放在同一个二维数组里了,这个Action-Goto表左部是ACTION表,右部是GOTO表。
    int ACTION_GOTO[16][11]={/*左部是ACTION表,右部是GOTO表*/ 2 ,0 ,0 ,3 ,0 ,0 ,5 ,6 ,4 ,0 , 1,//0 0 ,8 ,0 ,0 ,0 ,7 ,0 ,0 ,0 ,888 , 0,//1 888 ACC 2 ,0 ,0 ,3 ,0 ,0 ,5 ,6 ,4 ,0 , 9,//2 2 ,0 ,0 ,3 ,0 ,0 ,5 ,6 ,4 ,0 , 10,//3 0 ,0 ,0 ,0 ,11,0 ,0 ,0 ,0 ,0 , 0,//4 0 ,-6,-6,0 ,0 ,-6,0 ,0 ,0 ,-6, 0,//5 0 ,-7,-7,0 ,0 ,-7,0 ,0 ,0 ,-7, 0,//6 2 ,0 ,0 ,3 ,0 ,0 ,5 ,6 ,4 ,0 , 12,//7 2 ,0 ,0 ,3 ,0 ,0 ,5 ,6 ,4 ,0 , 13,//8 0 ,-3,-3,0 ,0 ,-3,0 ,0 ,0 ,-3, 0,//9 0 ,8 ,14,0 ,0 ,7 ,0 ,0 ,0 ,0 , 0,//10 0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,15,0 , 0,//11 0 ,-1,-1,0 ,0 ,-1,0 ,0 ,0 ,-1, 0,//12 0 ,-2,-2,0 ,0 ,-2,0 ,0 ,0 ,-2, 0,//13 0 ,-4,-4,0 ,0 ,-4,0 ,0 ,0 ,-4, 0,//14 0 ,-5,-5,0 ,0 ,-5,0 ,0 ,0 ,-5, 0 //15 };
    在查表的时候,如果表中的相应值是正数,就移进;若是负数,就归约。接受的情况我设了一个比较特殊的数字888,由于状态有限,所以也不会发生冲突,遇到表中是888就接受该字符串,认为其符合文法,跳出循环,恭喜成功。我将表中其他空白处,也就是不合文法的那些地方都填0,所以若是查表遇到了0那可以认为不合文法,跳出循环,报告失败。

    4.3 语义分析我的语法分析核心由SLR_parser实现,语义分析及中间代码生成在归约的时候进行,因此我在上步的SLR_parser函数的基础上继续扩充,使之在归约的过程中能够分析语义和生成四元式,回填和合并真假链 。我的语义分析就是把上步的SLR_parser函数的归约部分进一步展开。
    我结合龙书和课本,把道理看明白,然后采用的是实现课本上的这7个函数,这7个函数分别对应7个产生式,在用相应产生式归约的时候,调用这些函数,生成相应中间代码,完成回填和合并。

    课本《编译原理 第二版(张素琴 吕映芝)》上P185的翻译模式:

    我设了一个语义栈,里面的元素不是string类型,而是自定义的结构体类型,其中是string类型的是这个结构体其中一项,作为它的语义值,这个结构体里还有codebegin记录中间代码的位置,E_true记录若真将转向何方,E_false记录若假将转向何方。按照以上的翻译模式完成相应的函数,在每次归约的时候看用的哪条产生式就调用相应的函数,在这个过程中也完成了真假链的回填和合并。
    伪代码算法描述:
    rule1: E -> E or E [rule1] backpatch(E1.false,E2.codebegin); E.codebegin := E1.codebegin; E.true := merge(E1.true,E2.true) E.false := E2.false rule2: E -> E and E [rule2] backpatch(E1.true,E2.codebegin); E.codebegin := E1.codebegin; E.true := E2.true; E.false := merge(E1.false,E2.false); rule3: E -> not E [rule3] E.true := E1.false; E.codebegin := E1.codebegin; E.false = E1.true; rule4: E -> ( E ) [rule4] E.true := E1.true; E.codebegin := E1.codebegin; E.false = E1.true; rule5: E -> id rop id [rule5] E.true := nextstat; E.codebegin := nextstat; E.false := nextstat+1; emit('if' id1.place 'rop' id2.place 'goto'-); emit('goto'-) rule6:E -> true [rule6] E.true := nextstat; E.codebegin:=nextstat; emit('goto'-) rule7:E -> false [rule7] E.false := nextstat; E.codebegin:=nextstat; emit('goto'-)
    Emit函数每调用一次,nextstat就加一,因为中间代码又多了一行,为了看起来比较清晰,书上默认设nextstat初值从100开始,我也采用这个初值。

    // 回填void Backpatch(int &p,int &t){//gen_pcode[Eid1.E_true]+=Int_to_String(Eid2.codebegin); gen_pcode[p][3]= Int_to_String(t);/*第四区段*/}// 合并int Merge(int &p1,int &p2){ gen_pcode[p2][3]=Int_to_String(p1);/*第四区段*/ return p1;/*返回链首*/}
    五、主要功能的实现5.1 词法分析部分这部分有很多是直接匹配,剩下的是写正则表达式去匹配,代码比较容易,象征性地列出。



    比如标识符 可以用正则表达式r=letter|(letter|digit)* 来表示,落实到代码可以表示为[A-Za-z]|[A-Za-z][A-Za-z0-9]*,这里要注意的是这里识别的顺序还有讲究,这里有先匹配谁的问题。最好要把直接匹配的代码放在上面,如果把标识符匹配的代码放在上面,可能会把关键字像begin和end之类也给识别为标识符。
    5.2 语法分析部分由第一部分的词法分析rawstr字符串数组保存原始字符串,mytoken字符串数组保存识别后的类型。语法分析部分我的核心函数在SLR_parser, 由于在后来的语义分析中,我对这个函数进行了很大扩充,使之具有生成中间代码和真假链回填合并的功能,这个函数变得比较复杂,为方便读者理解,我给出早期在做语法分析部分的SLR_parser函数, 这里称它为SLR_demo, 代码比较简短,是按照龙书上的算法描述进行相应代码实现的。
    SLR_demo函数如下:
    int SLR_demo(){ /*A complete simple demo for SLR Analysis,This is GOOD CODE.*//*This demo just judge whether a sentence is a boolean expression or not,you can change string str to test *Demo result:( ( id rop id ) or ( true and false ) ) # Success! (is boolean expression) */ /*int GOTO[16] = { 1,0,9,10,0,0,0,12,13,0,0,0,0,0,0,0};*/ string str[14]={"(","(","id","rop","id",")","or","(","true","and","false",")",")","#"}; for(int i=0;i<14;i++) cout<<str[i]<<" "; int ip=0,j=0;/*ip指示指到哪了*/ string sym;/*存符号*/ int state_row;/*状态数*/ int sym_col;/*符号数*/ int top; int Reduce_j;/*这是用来存归约Rj的下标j的*/ int Reduce_j_reducenum;/*由Rj知道用到是第几条产生式,这个产生式右部有几个符号(待归约的总数)*/ string nt[7]={"E","E","E","E","E","E","E"};/*布尔表达式文法7个产生式的左部都是E*/ int ACTION_GOTO[16][11]={/*左部是ACTION表,右部是GOTO表*/ 2 ,0 ,0 ,3 ,0 ,0 ,5 ,6 ,4 ,0 , 1,//0 0 ,8 ,0 ,0 ,0 ,7 ,0 ,0 ,0 ,888 , 0,//1 888 ACC 2 ,0 ,0 ,3 ,0 ,0 ,5 ,6 ,4 ,0 , 9,//2 2 ,0 ,0 ,3 ,0 ,0 ,5 ,6 ,4 ,0 , 10,//3 0 ,0 ,0 ,0 ,11,0 ,0 ,0 ,0 ,0 , 0,//4 0 ,-6,-6,0 ,0 ,-6,0 ,0 ,0 ,-6, 0,//5 0 ,-7,-7,0 ,0 ,-7,0 ,0 ,0 ,-7, 0,//6 2 ,0 ,0 ,3 ,0 ,0 ,5 ,6 ,4 ,0 , 12,//7 2 ,0 ,0 ,3 ,0 ,0 ,5 ,6 ,4 ,0 , 13,//8 0 ,-3,-3,0 ,0 ,-3,0 ,0 ,0 ,-3, 0,//9 0 ,8 ,14,0 ,0 ,7 ,0 ,0 ,0 ,0 , 0,//10 0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,15,0 , 0,//11 0 ,-1,-1,0 ,0 ,-1,0 ,0 ,0 ,-1, 0,//12 0 ,-2,-2,0 ,0 ,-2,0 ,0 ,0 ,-2, 0,//13 0 ,-4,-4,0 ,0 ,-4,0 ,0 ,0 ,-4, 0,//14 0 ,-5,-5,0 ,0 ,-5,0 ,0 ,0 ,-5, 0 //15 }; stack<int> statestack;/*状态栈*/ statestack.push(0);/*开始是0状态*/ ip=0; while(1){ sym=str[ip];/*获得符号*/ sym_col=getsymcol(sym);/*获得符号数*/ state_row=statestack.top();/*得到栈顶当前状态*/ if(ACTION_GOTO[state_row][sym_col]>0){/*Shift 移进*/ if(ACTION_GOTO[state_row][sym_col]!=ACC){/*接受ACC在表中是888*/ statestack.push(ACTION_GOTO[state_row][sym_col]); }else{ cout<<" Success! (is boolean expression) \n"; break; } ip++;/*往下挪*/ }else if(ACTION_GOTO[state_row][sym_col]<0){/*Reduce 归约*/ Reduce_j=-ACTION_GOTO[state_row][sym_col]; Reduce_j_reducenum=reducenum(Reduce_j); for(j=0;j< Reduce_j_reducenum;j++){ statestack.pop(); } statestack.push(ACTION_GOTO[statestack.top()][getsymcol(nt[Reduce_j-1])]); }else{ cout<<" Fail! (not a boolean expression) \n"; break; } } return 0;}
    这个函数完成的功能画成下图:

    5.3 语义分析部分我的语义分析是对SLR_parser函数语法分析归约过程的扩展,语义栈中的元素是自定义结构体E的类型,因为是属性文法,需要这个结构体来存相关属性。
    typedef struct E{ int codebegin; int E_true; int E_false; string x;}E;
    其中codebegin存中间代码在第多少行,E_true表示若真,转向第E_true(其数值)行;E_false表示若假,转向第E_false行。
    扩展之后的SLR_parser函数如下:
    int SLR_parser(){/*这里使用plolex.cpp里定义的全局字符串数组globalstr*/ E tempE; int ip=0,j=0;/*ip指示指到哪了*/ string sym;/*存符号*/ int state_row;/*状态数*/ int sym_col;/*符号数*/ int top; int Reduce_j;/*这是用来存归约Rj的下标j的*/ int Reduce_j_reducenum;/*由Rj知道用到是第几条产生式,这个产生式右部有几个符号(待归约的总数)*/ string nt[7]={"E","E","E","E","E","E","E"};/*布尔表达式文法7个产生式的左部都是E*/ int ACTION_GOTO[16][11]={/*左部是ACTION表,右部是GOTO表*//*此处版面限制,省略ACTION_GOTO表,前面已给出*/ }; stack<int> statestack;/*状态栈*/ stack<string> symbolstack;/*符号栈*/ stack<E> semanticstack;/*语义栈*/ statestack.push(0);/*开始是0状态*/ ip=0; symbolstack.push("#"); E _E;_E.x="-"; semanticstack.push(_E); stack <E> Estack; while(1){ sym=globalstr[ip];/*这里从另一个文件pl0lex.cpp里定义的全局字符串数组获得符号*/ sym_col=getsymcol(sym);/*获得符号数*/ state_row=statestack.top();/*得到栈顶当前状态*/ showstack(statestack); showSTRstack(symbolstack); showSemanticstack(semanticstack); showsym(ip); cout<<endl; if(ACTION_GOTO[state_row][sym_col]>0){/*Shift 移进*/ if(ACTION_GOTO[state_row][sym_col]!=ACC){/*接受ACC在表中是888*/statestack.push(ACTION_GOTO[state_row][sym_col]); //cout<<"sym_col:"<<getstrsymcol(sym_col); symbolstack.push(getstrsymcol(sym_col)); E __temp;__temp.x=rawstr[ip]; semanticstack.push(__temp); }else{ cout<<" \nSuccess! (is boolean expression)该语句符合布尔表达式文法 \n"; break; } ip++;/*往下挪*/ }else if(ACTION_GOTO[state_row][sym_col]<0){/*Reduce 归约*/ Reduce_j=-ACTION_GOTO[state_row][sym_col]; Reduce_j_reducenum=reducenum(Reduce_j); cout<<"\n归约所用产生式:["<<Reduce_j<<"]",showBoolean_expression_rules(Reduce_j); for(j=0;j< Reduce_j_reducenum;j++){ statestack.pop(); symbolstack.pop(); } E newtempE;newtempE.x="x";if(Reduce_j==1||Reduce_j==2||Reduce_j==4||Reduce_j==5){ if(Reduce_j!=4){ E tempE2=semanticstack.top(); semanticstack.pop();//id2 E ropE=semanticstack.top(); semanticstack.pop();//rop E tempE1=semanticstack.top(); semanticstack.pop();//id1 if(Reduce_j==5){ /*rule5: E -> id rop id */ newtempE.E_true=nextstat; newtempE.codebegin=nextstat; newtempE.E_false=nextstat+1; gen_pcode[nextstat][0]=ropE.x; gen_pcode[nextstat][1]=tempE1.x; gen_pcode[nextstat][2]=tempE2.x; gen_pcode[nextstat][3]="true"; nextstat++; gen_pcode[nextstat][0]="j";gen_pcode[nextstat][1]="-";gen_pcode[nextstat][2]="-"; gen_pcode[nextstat][3]="false"; nextstat++; }else if(Reduce_j==2){ /*rule2: E -> E and E*/ Backpatch(tempE1.E_true,tempE2.codebegin); newtempE.codebegin=tempE1.codebegin; newtempE.E_true=tempE2.E_true; newtempE.E_false=Merge(tempE1.E_false,tempE2.E_false); }else if(Reduce_j==1){ /*rule1: E -> E or E*/ Backpatch(tempE1.E_false,tempE2.codebegin); newtempE.codebegin=tempE1.codebegin; newtempE.E_true=Merge(tempE1.E_true,tempE2.E_true); newtempE.E_false=tempE2.E_false; } Estack.push(tempE1); Estack.push(tempE2); }else{ /*rule4: E -> ( E )*/ semanticstack.pop();//括号 E E_1=semanticstack.top(); newtempE.E_true = E_1.E_true; newtempE.codebegin=E_1.codebegin; newtempE.E_false=E_1.E_false; Estack.push(tempE); semanticstack.pop(); semanticstack.pop();//括号 } }else if(Reduce_j==3){ /*rule3: E -> not E*/ E n_E=semanticstack.top(); newtempE.E_true=n_E.E_false; newtempE.codebegin=n_E.codebegin; newtempE.E_false=n_E.E_true; Estack.push(n_E); semanticstack.pop();//E semanticstack.pop();//not }else if(Reduce_j==6||Reduce_j==7){ if(Reduce_j==6){ /*rule6:E -> true*/ E t_E=semanticstack.top(); newtempE.E_true=nextstat; newtempE.codebegin=nextstat; Estack.push(t_E); gen_pcode[nextstat][0]="j";gen_pcode[nextstat][1]="-";gen_pcode[nextstat][2]="-"; gen_pcode[nextstat][3]="true"; nextstat++; }else if(Reduce_j==7){ /*rule7:E -> false*/ E f_E=semanticstack.top(); newtempE.E_false=nextstat; newtempE.codebegin=nextstat; Estack.push(f_E); gen_pcode[nextstat][0]="j";gen_pcode[nextstat][1]="-";gen_pcode[nextstat][2]="-"; gen_pcode[nextstat][3]="false"; nextstat++; } semanticstack.pop(); } semanticstack.push(newtempE); statestack.push(ACTION_GOTO[statestack.top()][getsymcol(nt[Reduce_j-1])]); symbolstack.push(getstrsymcol(getsymcol(nt[Reduce_j-1]))); }else{ cout<<" \nFail! (not a boolean expression) 该语句不符合布尔表达式文法 \n"; break; } } showSTRstack(symbolstack); return 0;}

    六、主要功能的测试6.1 词法分析部分语法测试用例及结果分析
    这里第一次实验时做的是针对整个PL/0语言的语法分析,到课设整合的时候面向的对象是布尔表达式,这里给出当时做完语法分析时的测试用例及结果分析。
    本学期为做此次课程设计一共做了4次实验,其中第二次是递归下降分析,比较独立;本课程设计综合了本学期第一次实验的词法分析,第三次实验的语法分析,第四次的语义分析及四元式生成,本次课程设计最终实现完成的功能是针对布尔表达式产生四元式中间代码。
    PL/0词法分析
    以下为第一次实验语法分析时的测试用例:
    词法分析测试用PL/0源程序hello.pl0:
    VAR x, y;VAR aa,bb;BEGIN x := 1/1; WHILE x <= 100 DO BEGIN CALL fun; ! aa; x := x + 1 ENDENDPROCEDURE fun; VAR a,b,c; BEGIN a:=1; b:=2; c:=3; aa:=a+b; END;BEGINCALL fun;END
    词法分析结果result.txt:
    我的词法分析器正在分析程序hello.pl0…
    VAR:变量x:标识符,:和y:标识符;:。VAR:变量aa:标识符,:和bb:标识符;:。BEGIN:复合语句开始x:标识符:=:赋值1:无符号整数/:乘法运算符1:无符号整数;:。WHILE:当型循环当x:标识符<=:关系运算符100:无符号整数DO:当型循环做BEGIN:复合语句开始CALL:过程调用fun:标识符;:。!aa:标识符;:。x:标识符:=:赋值x:标识符+:加法运算符1:无符号整数END:复合语句结束END:复合语句结束PROCEDURE:过程首部fun:标识符;:。VAR:变量a:标识符,:和b:标识符,:和c:标识符;:。BEGIN:复合语句开始a:标识符:=:赋值1:无符号整数;:。b:标识符:=:赋值2:无符号整数;:。c:标识符:=:赋值3:无符号整数;:。aa:标识符:=:赋值a:标识符+:加法运算符b:标识符;:。END:复合语句结束;:。BEGIN:复合语句开始CALL:过程调用fun:标识符;:。END:复合语句结束.:点!程序结束
    词法分析运行截图:


    6.2 语法分析部分第3次实验完成了语法分析,对于符合布尔表达式文法的列出每次归约所用产生式,篇幅有限,为方便观察,暂不列出每次栈的变化。关于栈的变化在整合后的课程设计里是详细给出的。
    运行截图:


    测试用例里有test1.pl0 test2.pl0 test3.pl0 test4.pl0运行结果分别为result1.txt result2.txt result3.txt result4.txt
    读者可以利用管道重定向得到。
    测试用例1 test1.pl0内容:
    ( ( x > y ) or ( true and false) )#
    测试用例1分析结果result1.txt:
    SLR_boolean_expression_parser 待分析语句如下:
    ( ( x > y ) or ( true and false ) )#
    以上为待分析语句
    flex pl0lex.cppg++ -o mypl0lex lex.yy.c -ll我的词法分析器正在分析程序test.pl0..../mypl0lex < test.pl0准备打开文件打开文件成功!,正在词法分析(:左括号(:左括号x:标识符>:关系运算符y:标识符):右括号or:或(:左括号true:真and:与false:假):右括号):右括号#:井号词法分析完成!共有14个符号( ( id rop id ) or ( true and false ) ) # 归约所用产生式:[5]E -> id rop id归约所用产生式:[4]E -> ( E )归约所用产生式:[6]E -> true归约所用产生式:[7]E -> flase归约所用产生式:[2]E -> E and E归约所用产生式:[4]E -> ( E )归约所用产生式:[1]E -> E or E归约所用产生式:[4]E -> ( E ) Success! (is boolean expression)该语句符合布尔表达式文法
    测试用例2 test2.pl0内容:
    ( ( x > y ) or ( true andfalse #
    测试用例2分析结果result2.txt:
    SLR_boolean_expression_parser 待分析语句如下:
    ( ( x > y ) or ( true and false #
    以上为待分析语句
    flex pl0lex.cppg++ -o mypl0lex lex.yy.c -ll我的词法分析器正在分析程序test.pl0..../mypl0lex < test.pl0准备打开文件打开文件成功!,正在词法分析(:左括号(:左括号x:标识符>:关系运算符y:标识符):右括号or:或(:左括号true:真and:与false:假#:井号词法分析完成!共有12个符号( ( id rop id ) or ( true and false # 归约所用产生式:[5]E -> id rop id归约所用产生式:[4]E -> ( E )归约所用产生式:[6]E -> true归约所用产生式:[7]E -> flase归约所用产生式:[2]E -> E and E Fail! (not a boolean expression) 该语句不符合布尔表达式文法
    测试用例3 test3.pl0内容:
    ( ( ( ( true or false ) and ( m > n) ) or (not true) ) and ( x > y) ) #
    测试用例3分析结果result3.txt:
    SLR_boolean_expression_parser 待分析语句如下:
    ( ( ( ( true or false ) and ( m > n) ) or ( not true) ) and ( x > y) ) #
    以上为待分析语句
    flex pl0lex.cppg++ -o mypl0lex lex.yy.c -ll我的词法分析器正在分析程序test.pl0..../mypl0lex < test.pl0准备打开文件打开文件成功!,正在词法分析(:左括号(:左括号(:左括号(:左括号true:真or:或false:假):右括号and:与(:左括号m:标识符>:关系运算符n:标识符):右括号):右括号or:或(:左括号not:非true:真):右括号):右括号and:与(:左括号x:标识符>:关系运算符y:标识符):右括号):右括号#:井号词法分析完成!共有29个符号( ( ( ( true or false ) and ( id rop id ) ) or ( not true ) ) and ( id rop id ) ) # 归约所用产生式:[6]E -> true归约所用产生式:[7]E -> flase归约所用产生式:[1]E -> E or E归约所用产生式:[4]E -> ( E )归约所用产生式:[5]E -> id rop id归约所用产生式:[4]E -> ( E )归约所用产生式:[2]E -> E and E归约所用产生式:[4]E -> ( E )归约所用产生式:[6]E -> true归约所用产生式:[3]E -> not E归约所用产生式:[4]E -> ( E )归约所用产生式:[1]E -> E or E归约所用产生式:[4]E -> ( E )归约所用产生式:[5]E -> id rop id归约所用产生式:[4]E -> ( E )归约所用产生式:[2]E -> E and E归约所用产生式:[4]E -> ( E ) Success! (is boolean expression)该语句符合布尔表达式文法
    测试用例4 test4.pl0内容:
    ( ( ( ( true or false ) and ( m > n) ) or (not true) and ( x > y) #
    测试用例4分析结果result4.txt:
    SLR_boolean_expression_parser 待分析语句如下:
    ( ( ( ( true or false ) and ( m > n) ) or ( not true) and ( x > y) #
    以上为待分析语句
    flex pl0lex.cppg++ -o mypl0lex lex.yy.c -ll我的词法分析器正在分析程序test.pl0..../mypl0lex < test.pl0准备打开文件打开文件成功!,正在词法分析(:左括号(:左括号(:左括号(:左括号true:真or:或false:假):右括号and:与(:左括号m:标识符>:关系运算符n:标识符):右括号):右括号or:或(:左括号not:非true:真):右括号and:与(:左括号x:标识符>:关系运算符y:标识符):右括号#:井号词法分析完成!共有27个符号( ( ( ( true or false ) and ( id rop id ) ) or ( not true ) and ( id rop id ) # 归约所用产生式:[6]E -> true归约所用产生式:[7]E -> flase归约所用产生式:[1]E -> E or E归约所用产生式:[4]E -> ( E )归约所用产生式:[5]E -> id rop id归约所用产生式:[4]E -> ( E )归约所用产生式:[2]E -> E and E归约所用产生式:[4]E -> ( E )归约所用产生式:[6]E -> true归约所用产生式:[3]E -> not E归约所用产生式:[4]E -> ( E )归约所用产生式:[1]E -> E or E归约所用产生式:[5]E -> id rop id归约所用产生式:[4]E -> ( E )归约所用产生式:[2]E -> E and E Fail! (not a boolean expression) 该语句不符合布尔表达式文法

    6.3 语义分析及中间代码生成部分详细给出状态栈和符号栈的变化过程,归约过程可以看得很清楚。从test.pl0读入布尔表达式(以#结尾),在终端敲make运行时在界面上显示分析和产生四元式的过程,同时把产生的四元式写入文本文件pcode.txt。
    测试用例:
    测试用的布尔表达式源文件(布尔表达式以#结尾):test.pl0
    ((( a > b ) and ( c < d ) )or ( e < f )) #
    我的编译程序通过分析test.pl0产生的四元式中间代码pcode.txt:
    [100] {> ,a ,b ,102 }[101] {j ,- ,- ,104 }[102] {< ,c ,d ,true }[103] {j ,- ,- ,101 }[104] {< ,e ,f ,102 }[105] {j ,- ,- ,false }







    这是一个不断移进和归约的过程,状态栈、符号栈和语义栈的变化过程都已详细给出,在控制台也输出了最后真假链接回填和合并后的四元式,同时程序还把生成的四元式写入文本pcode.txt,如下图:

    七、问题讨论以及感想本学期分了几次做实验,最后实验整合成课程设计。开始先是词法分析,然后语法分析,最后语义分析。做语法分析时我按照龙书的算法描述,写出相应实现代码,正确地完成了当时要求的语法分析功能,然而语法分析时我没有考虑语义值,只是对识别结果进行分析,比如原来输入的是x, 我词法分析已经识别其为标识符,那语法分析时我并不需要x这个原来的值,只要知道其类型是标识符即可。这对于光完成语法分析是没毛病的,但做后来的语义分析的时候就造成了麻烦,只知道其为标识符,却得不到它原来是x 。我知道问题在哪,就在它基础上改, 不过还是挺麻烦的,刚开始我的语义栈的类型不是一个结构体,而是字符串类型,那么对于属性文法,像E.codebegin 和E.false这种就没地方存。开始耽搁了很长时间,最后把语义栈改成结构体类型,string只作为这个结构体类型的其中一项,很快就解决了。这样我终于理解属性文法中“属性”二字的含义。
    理解算法是很重要的。理解了的时候,实现只是时间问题,胸有成竹;不理解时代码就无从下手,或是胡乱写了一通代码越写越乱,找不出bug。好好研读书上的算法,能够把思路捋清,节省时间。龙书和课本上的算法给我很大帮助,精炼的算法描述在没有细细研究和动手写代码之前很难一下读懂,等弄懂了,代码写好之后再去看就发现它思路无比清晰,结合代码看算法,对问题的理解也就更深入了。
    本次课程设计锻炼了我的动手能力,“纸上得来终觉浅,绝知此事要躬行”,通过编写代码,我更加深刻地理解了编译原理课本上的知识。
    1 评论 5 下载 2018-11-04 16:47:10 下载需要4点积分
显示 720 到 735 ,共 15 条
eject