数据结构课程设计报告-毕业论文题目查重系统.doc

计算机科学学院数据结构课程设计题 目：毕业论文题目查重学生姓名：黄肆良学 号：12435012021专 业：计算机科学与技术班 级：12级（2）班 指导教师姓名及职称：方明 讲师 起止时间： 2014 年 2 月 2014年 4 月1 需求分析1.1 课题背景及意义大学生在做毕业论文的时候，有时选题很容易重复，或存在抄袭现象，因此，为了便于对大学生毕业论文设计的管理，很有必要设计这样一个毕业论文题目查重系统。数据结构课程设计是一门实践性的计算机课程，为了学好这门课程，必须在掌握理论知识的同时，加强上机实践。通过这次课程设计，要求掌握较大程序的设计方法，相应数据结构的选择应用、算法的设计及其实现和性能分析等方面中加深对课程基本内容的理解。同时，在设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。1.2 课题要求 A. 可以对一个excel文件的毕业设计选题列进行查重查似计算。B. 使用编辑距离算法进行查重查似计算C. 并把相似度超过50%的题目合并输出到excel文件。D. 选做内容：查重过程中预计剩余计算时间，支持多种其他相似度计算算法，根据常用需求对编辑距离算法进行优化，图形化操作界面。E.附加内容：对毕业论文进行查重1.3 软件格式规定A导入文件格式：用Excel存储学生论文题目信息，工作表中共三列，包含学生学号，学生姓名，学生论文题目。 用word的文档存储学生论文内容。我惹的文档题目为学生信息，包含学生学号，姓名，论文题目，用下划线分开。B. 程序所能达到的功能 :课题中所要求的所有功能C.导出的文件格式： Excel（包含学生学号，姓名，论文题目，相似度）D.测试的数据：1)、以下是7个论文题目：学号姓名题目10000张三学生成绩管理统10001李四学生信息管理统10002王五简易计算器10003赵一压缩软件10004小华公交换乘系统10005小牛城市交通换乘统10006李明城市公交换乘统用编辑距离查重结果：学号姓名 论文 题目相似度10000张三学生成绩管理系统10001李四学生信息管理系统75%10004小华公交换乘系统10005小牛城市交通换乘系统62.5%10004小华公交换乘系统10006李明城市公交换乘系统75%10005小牛城市交通换乘系统10006李明城市公交换乘系统75%1.4 设计目标A. 软件名称：毕业论文题目查重系统B. 软件组成：java版桌面应用程序 C. 制作平台及相关调试工具：EclipseD. 运行环境:winxp/win7/win8E. 性能特点：（1）软件运行界面友好，操作简便（2）运行时间较短，精确到毫秒级。（3）个别其他功能可进行再扩展。2 概要设计2.1问题解决的思路概述首先是确定结构化程序设计的流程图，首先需要操作Excel，导入java的扩展类库jxl.jar来操作Excel，读入学生信息，包含学生学号，姓名，论文题目，用AyyayList集合保存起来。接着调用编辑距离函数或余弦定理或是模糊匹配算法进行论文题目查重，将题目相似的学生信息用另一个动态数组保存起来。最后保存到新建的Excel文件中。总而言之，就是先用自顶向下、逐步细化的设计方法来分析并画出程序设计流程图；然后用自下而上、逐步积累的设计方法来写出程序。2.2 相关函数介绍说明 Java 版的相关函数及功能：public static Object ReadXLS(String path) 读入Excel文档的学生信息public Object CalculateSimilarity(Object objects) throws IOException,RowsExceededException, WriteException 编辑距离算法计算相似度public Object CalculateSimilarityJianDanMoHu(Object objects) throws IOException,RowsExceededException, WriteException 简单模糊算法计算相似度public Object CalculateSimilarityAlgrithm(Object objects) throws IOException,RowsExceededException, WriteException 余弦定理算法计算相似度public void Save(Object objects,String path) throws IOException, WriteException 保存查重结果2.3 主程序的流程基函数调用说明（1）主程序的简要流程图选择功能（题目查重或论文查重）导入Excel或world文档结束保存查重结果选择查重算法Main（）图1 主程序流程图（2）各程序模块之间的层次（调用）关系 调用ReadXLS()函数读入Excel学生成绩信息通过上步调用的学生信息，再调用Edit（）函数进行查重运算，将上步运算结果保存起来，用save（）保存到新建Excel文档中3 详细设计3.1 核心算法 编辑距离：编辑距离，又称Levenshtein距离，是指两个字串之间，由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。例如将kitten一字转成sitting：1. sitten （ks）2. sittin （ei）3. sitting （g）俄罗斯科学家Vladimir Levenshtein在1965年提出这个概念。问题：找出字符串的编辑距离，即把一个字符串s1最少经过多少步操作变成编程字符串s2，操作有三种，添加一个字符，删除一个字符，修改一个字符解析：首先定义这样一个函数edit(i, j)，它表示第一个字符串的长度为i的子串到第二个字符串的长度为j的子串的编辑距离。显然可以有如下动态规划公式： if i = 0 且 j = 0，edit(i, j) = 0 if i = 0 且 j 0，edit(i, j) = j if i 0 且j = 0，edit(i, j) = i ifi 1 且j 1 ，edit(i, j) = min edit(i-1, j) + 1, edit(i, j-1) + 1, edit(i-1, j-1) + f(i, j) ，当第一个字符串的第i个字符不等于第二个字符串的第j个字符时，f(i, j) = 1；否则，f(i, j) = 0。 public static int edit(char P, char T, int m, int n) int i, j; int D = new intm + 1n + 1; for (j = 0; j = n; j+) D0j = j; for (i = 1; i = m; i+) Di0 = i; for (j = 1; j = n; j+) for (i = 1; i 0 & doc2 != null& doc2.trim().length() 0) Map AlgorithmMap = new HashMap();/将两个字符串中的中文字符以及出现的总数封装到，AlgorithmMap中for (int i = 0; i doc1.length(); i+) char d1 = doc1.charAt(i);if(isHanZi(d1)int charIndex = getGB2312Id(d1);if(charIndex != -1)int fq = AlgorithmMap.get(charIndex);if(fq != null & fq.length = 2)fq0+;else fq = new int2;fq0 = 1;fq1 = 0;AlgorithmMap.put(charIndex, fq);for (int i = 0; i doc2.length(); i+) char d2 = doc2.charAt(i);if(isHanZi(d2)int charIndex = getGB2312Id(d2);if(charIndex != -1)int fq = AlgorithmMap.get(charIndex);if(fq != null & fq.length = 2)fq1+;else fq = new int2;fq0 = 0;fq1 = 1;AlgorithmMap.put(charIndex, fq);Iterator iterator = AlgorithmMap.keySet().iterator();double sqdoc1 = 0;double sqdoc2 = 0;double denominator = 0;while(iterator.hasNext()int c = AlgorithmMap.get(iterator.next();denominator += c0*c1;sqdoc1 += c0*c0;sqdoc2 += c1*c1;return denominator / Math.sqrt(sqdoc1*sqdoc2); else throw new NullPointerException( the Document is null or have not cahrs!);public static boolean isHanZi(char ch) / 判断是否汉字return (ch = 0x4E00 & ch = 0x9FA5);/* * 根据输入的Unicode字符，获取它的GB2312编码或者ascii编码， * * param ch * 输入的GB2312中文字符或者ASCII字符(128个) * return ch在GB2312中的位置，-1表示该字符不认识 */public static short getGB2312Id(char ch) try byte buffer = Character.toString(ch).getBytes(GB2312);if (buffer.length != 2) / 正常情况下buffer应该是两个字节，否则说明ch不属于GB2312编码，故返回?，此时说明不认识该字符return -1;int b0 = (int) (buffer0 & 0x0FF) - 161; / 编码从A1开始，因此减去0xA1=161int b1 = (int) (buffer1 & 0x0FF) - 161; / 第一个字符和最后一个字符没有汉字，因此每个区只收16*6-2=94个汉字return (short) (b0 * 94 + b1); catch (UnsupportedEncodingException e) e.printStackTrace();return -1;3.2 操作Excel 。3.2.1读取Excel public static Object ReadXLS(String path) InputStream is;try is = new FileInputStream(path);jxl.Workbook wb = Workbook.getWorkbook(is);/ 得到工作簿jxl.Sheet st = wb.getSheet(0);/ 得到工作簿的第一个工作表/ Cell cell=st.getColumn(0);int Columns = st.getColumns();/ 获得工作表的列数int Rows = st.getRows();String Title = new StringRows;/ 论文题目String name = new StringRows; / 学生姓名String num = new StringRows; / 学生学号for (int i = 1; i st.getRows(); i+) Cell titlecell = st.getCell(2, i);/ 得到工作表中的 第3列单元格 即论文题目Cell namecell = st.getCell(1, i);/ 得到工作表中的 第2列单元格 即姓名Cell numcell = st.getCell(0, i);/ 得到工作表中的 第1列单元格 即学号Titlei = (String) titlecell.getContents();namei = (String) namecell.getContents();numi = (String) numcell.getContents();wb.close();is.close();Object O = num, name, Title, Rows ;/ 将学生信息存入Oject对象中return O; catch (FileNotFoundException e) / TODO 自动生成的 catch 块e.printStackTrace();/ 读到inputstreamcatch (BiffException e) / TODO 自动生成的 catch 块e.printStackTrace(); catch (IOException e) / TODO 自动生成的 catch 块e.printStackTrace();return null;3.2.2保存文件到Excel文件public void Save(Object objects,String path) throws IOException, WriteException / 定义集合的二维数组储存动态生成的学生论文相似的学生信息/ 从object中取出集合信息，object为从 CalculateSimilarity（Object objects）中获得的论文题目相似的学生信息ArrayList TotalNumList = (ArrayList) objects0;ArrayList TotalNameList = (ArrayList) objects1;ArrayList TotalTitleList = (ArrayList) objects2;ArrayList TotalSimilaity = (ArrayList) objects3; OutputStream os = new FileOutputStream(path);WritableWorkbook wwb = Workbook.createWorkbook(os);/ 创建可写工作簿WritableSheet ws = wwb.createSheet(sheet1, 0);Label numlabel = new Label(0, 0, 学号); /输出Excel的首行Label namelabel = new Label(1, 0, 姓名);Label Titlelabel = new Label(2, 0, 论文 题目);Label Similarity = new Label(5, 0, 相似度);ws.addCell(numlabel);ws.addCell(namelabel);ws.addCell(Titlelabel);ws.addCell(Similarity);int k = 1; / k作为输出相似论文行位置for (int i = 0; i TotalNumList.size(); i+) Label namelabel2 = new Label(0, k, (String) TotalNumList.get(i);/ 创建写入位置和内容Label numlabel2 = new Label(1, k, (String) TotalNameList.get(i);Label Titlelabel2 = new Label(2, k, (String) TotalTitleList.get(i);/ k=k+2;ws.addCell(numlabel2);/ 将Label写入sheet中ws.addCell(namelabel2);ws.addCell(Titlelabel2);k+;int n=2;for(int j=0;jTotalSimilaity.size();j+)Label persimilarity=new Label(5,n,(String)TotalSimilaity.get(j); ws.addCell(persimilarity);n=n+2;/ 现在可