3.4.3数制转换问题.doc

井冈山大学电子与信息工程学院数据结构课程设计报告 ( 20142015年度第一学期)课程名称： 数据结构课程设计 题 目 一： 文学研究助手系统 P73 题 目 二： 运动会分数统计系统 P33 题 目 三： 文学研究助手系统 P73 院 系： 计算机科学系 班 级： 12软件本（2）班 姓 名： 谢伟 学 号： 120913001 指导教师： 孙凌宇老师 成 绩： 2014 年 月 日成 绩 评 定一、 指导教师评语二、 成绩成绩备注 指导教师： 日 期： 年 月 日 设计题目<一>：4.3 文学研究助手系统 p73一、设计要求1问题描述文学研究人员需要统计某篇英文小说中某些特定单词的出现次数和位置（行号和列号）。试写出一个实现这一目标的文字统计系统，称为“文学研究助手系统”。2需求分析要求建立一个文本文件，每个单词不包含空格和不跨行，单词由字符序列构成且区分大小写；检索输出给定单词出现在文本中行号，以及在该行中出现的位置（列号）；统计给定单词在文本文件出现的总次数。二、概要设计 该设计可分为三个部分实现；第一，建立文本文件，文件名由用户通过键盘输入；第二，检索给定单词：输入一个单词，检索并输出该单词所在的行号和列号；第三，给定单词的计数：输入一个单词，统计输出该单词在文本中的出现次数。可从3个方面着手设计。 1. 建立和读入文本文件 建立和读入文件的实现步骤如下： （1）定义一个串变量； （2）定义文本文件； （3）输入文件名，打开该文件； （4）循环读入文本行，写入文本文件，其过程如下： While(不是文件输入结束符) 读入一文本行至串变量； 串变量写入文件； 输入是否结束输入标志； 2 存储结构设计主串和模式串都采用定长顺序存储表示，其0号单元存放串长度： #define MAXSTRLEN 255 Typedef char SStringMAXSTRLEN+1;2.3字符串的模式匹配问题 本系统使用改进的KMP匹配算法实现字符串的模式匹配问题。匹配可如下进行：假设以指针i和j分别指示主串和模式中的比较字符，令i的初值为pos,j的初值为1.若在匹配过程中si=sj,则i和j分别增1，若sisj匹配失败后，则i不变，j退到nextj位置再比较，若相等，则指针各自增1 ，否则j再退到下一个next值的位置，依次类推。直至下列两种情况：一种是j退到某个next值时字符比较相等，则i和j分别增1继续进行匹配；另一种是j退到值为零（即模式的第一个字符失败），则此时i和j也要分别增1，表明从主串的下一个字符起和模式重新开始匹配。三、模块设计1模块设计本程序包含3个模块：主程序模块，查找模块，功能模块。其调用关系如图4.1所示。 图 4.1 2 系统子程序及功能设计本系统共设置5个子程序，各子程序的函数名及功能说明如下。 （1） Void get_next(SString T,int next) /求模式串T的next函数值并存入数组next （2） Int Index(SString S,SString T,int pos）/KMP匹配函数 （3） Int lenth(SString str) /取串str的长度 （4） Void find(char name,SString keys) /查找函数，对于输入的每一个要查找的关键字，从文本文件中逐行读取字符串查找。 /调用(1),(2),(3) （5） （5） Void main() /主函数，负责系统的输入和输出。调用(4）3 函数主要调用关系图 本系统5程序之间的主要调用关系如图4.2所示。图中数字是各函数的编号 图 4.2四、详细设计1数据类型定义（1）定长顺序存储串类型的定义 #define MAXSTRLEN 255 /最大串长 typedef char SStringMAXSTRLEN+1;/串的定长顺序存储表示，0号单元存放串的长度 （2）全局变量的定义 int nextMAXSTRLEN /KMP算法中用到的next数组2系统主要子程序详细设计（1）主函数模块设计，负责系统的输入输出工作，调用查找函数。 void main() 输入包含路径的文本文件名； 输入要查找的关键字个数； 一次性输入要查找的关键字；对于每一个关键字，循环调用find函数进行查找统计； （2）查找模块设计 void find(char name,SString keys) /该函数是整个程序的重要部分，对于输入的每一个要查询的关键字，从小说文件中逐行 /杜取字符串查找 SString text; /存放从小说文件中读取的一行字符串 int i=1,j=0,k; /i用于存放行号，j用于存放列号，k用于输出格式的控制 int n=0; /n用于记录出现的次数 FILE *fp; if(!(fp=(fopen(name,"r") /打开小说文件 printf("Open file error!n"); exit(0); keys0=lenth(keys); /调用lenth函数求关键字 get_next(keys,next);调用get_next函数求模式串（关键字）每一个字符对应的next printf("n%s出现于:n",&keys1); /打印关键字while(!feof(fp) /如果还没有找到小说文件末尾 k=0; fgets(&text1,MAXSTRLEN,fp); /从小说文件中读取一行字符串，存入text串中 text0=lenth(text); /求读入的串的长度 k=0; fgets(&text1,MAXSTRLEN,fp); /从小说文件中读取一行字符串，存入text串中 text0=lenth(text); /求读入的串的长度 j=Index(text,keys,j+1); /调用KMP算法，统计关键字在该行出现的位置，若匹配不成功则返回0 if(j!=0) printf("trow=%d,tcol=%d",i,j); k+; n+; while(j!=0) j=Index(text,keys,j+1); if(j!=0) n+; printf(",%d",j); i+; if(k) printf("n"); printf("%s公出现%d次n",keys1,n); （3）其他功能模块设计 1.求next函数值 void get_next(SString T,int next) int j=1,k=0; next1=0; while(j<T0) if(k=0|Tk=Tj) +j; +k; if(Tj!=Tk) nextj=k; else nextj=nextk; 2.KMP匹配函数 int Index(SString S,SString T,int pos) /利用模式串T的next函数球T主串S中第POS个字符之后的位置的KMP算法 int i=pos,j=1; while(i<=S0&&j<=T0) if(j=0|Si=Tj) /继续比较后继字符 +i; +j; else j=nextj; /模式串向右移动 if(j>T0) return (i-T0); /匹配成功 else return 0; /匹配失败 五、 测试分析系统运行后，要求用户输入带路径的小说文件名，如4.3图所示。 图 4.3用户输入D：shiyan4.txt并回车。此文本文件已正确建立，内容为： - Spring is a delightful season.The temperatures are moderate, and the blooming trees and flowers make the city bright with colors. It is the time when we can begin to wear lighter and more brightly colored clothes and go outdoors more often. Smaller children like to bring their kites out to the spacious square.Also I enjor going back to the village on this holiday after bejin in the city for the winter months. -回车后，系统提示用户输入待查找的单词个数，如图4.4所示、 图4.4用户输入3并回车，系统提示用户输入单词内容，如图4.5、4.6所示 图4.5 图4.6 六、用户手册 （1）本程序执行文件为“文学研究助手系统.exe”。（2）进入本系统后，随即显示系统主菜单界面。用户可以在该界面下按提示输入命令并观察结果。 七、调试报告1、由于刚开始程序比较简单，虽能运行，但处理错误的能力很低，后来经过反 复的添加修改，使程序能处理了错误，提高了健壮性。2、算法的时空分析：线性表使用的是顺序结构，各种算法的时间复杂度相对比较合理 3、本程序相对来说比较容易看明白，其中涉及到的一些函数相对来说比较容易。通过调试，运行，基本上达到了要求，但还存在一些缺点。八、 程序清单#include "stdafx.h" #include <stdio.h> #include <stdlib.h> #define MAXSTRLEN 255 /最大串长 typedef char SStringMAXSTRLEN+1; /串的定长顺序存储表示，0号单元存放串的长度 int nextMAXSTRLEN; /KMP算法中用到的next数组/1. 求模式串T的next函数值并存入数组next void get_next(SString T,int next ) / 求模式串T的next函数值，并存入数组next int j=1,k=0; next1=0; while (j<T0) if (k=0 | Tk=Tj) +j; +k; if (Tj!=Tk) nextj=k; else nextj=nextk; else k=nextk; /2. KMP匹配函数 int Index(SString S,SString T,int pos) / 利用模式串T的next函数求T在主串S中第pos个字符之后的位置的KMP算法 / 其中T非空，1 pos StrLength(s) int i=pos,j=1; while (i<=S0&&j<=T0) if (j=0|Si=Tj) +i;+j; / 继续比较后继字符 else j=nextj; / 模式串向右移动 if (j>T0) return (i-T0); / 匹配成功 else return 0; / 匹配失败 /3. 求串长 int lenth(SString str) int i=1; while(stri) i+; return(i-1); /4. 查找函数 void find(char name,SString keys) /该函数是整个程序的重要部分，对于输入的每一个 /要查找的关键字，从小说文件中逐行读取字符串查找 SString text; /存放从小说文件读取的一行字符串 int i=1,j=0,k; /i用于存放行号，j用于存放列号,k用于输出格式的控制 int n=0; /n记录出现次数 FILE *fp; if (!(fp=(fopen(name,"r") /打开小说文件 printf("Open file error!n"); exit(0); keys0=lenth(keys); /调用lenth函数求关键字的长度 get_next(keys,next); /调用get_next函数求模式串（关键字）每一个字符对应的next值 printf("n%s出现于：n",&keys1); /打印关键字 while (!feof(fp) /如果还没到小说文件末尾 k=0; fgets(&text1,MAXSTRLEN,fp); /从小说文件中读取一行字符串，存入text串中 text0=lenth(text); /求读入的串的长度 j=Index(text,keys,j+1); /调用KMP算法，统计关键字在该行出现的位置，若匹配不成功则返回0 if (j!=0) printf("trow=%d,tcol=%d",i,j); k+; n+; /若匹配成功则打印行号和列号 while(j!=0) /若该行找到了关键字，则继续寻找看是否还能匹配成功 j=Index(text,keys,j+1); /调用KMP算法从刚找到的列号后一字符起匹配 if (j!=0) n+; printf(",%d",j); /若匹配成功，则打印列号 i+; /行号加1，在下一行中寻找 if (k) printf("n"); /输出格式控 printf("%s共出现%d次n",&keys1,n); /5. 主函数 void main() char name50; /存储输入的小说路径字符串 SString words10; /定义字符串数组，用于存储输入的关键字 int n,i; printf("请输入已创建的文本文件的路径 (如D:novel.txt):n"); scanf("%s",name); /用户输入包含路径的文本文件名 printf("请输入要查找的单词数n (n<10)：n"); scanf("%d",&n); /用户输入要查找的关键字个数 printf("请输入要查找的单词，词与词之间用空格隔开 (区分大小写):n"); for (i=0;i<n;i+) scanf("%s",&wordsi1); /用户一次性输入要查找的关键字，wordsi0用于存放字符串的长度 for (i=0;i<n;i+) find(name,wordsi); /对于每一个关键字，调用find函数进行查找统计 设计题目<二>：2.4.1运动会分数统计系统P33一、设计要求1问题描述参加运动会有n个学校，学校编号为1n。比赛分成m个男子项目，和w个女子项目。项目编号为男子1m，女子m+1m+w。不同的项目取前五名或前三名积分；取前五名的积分分别为：7、5、3、2、1，前三名的积分分别为：5、3、2；哪些项目取前五名或前三名由学生自己设定。（m<=20,n<=20）2需求分析(1)、可以输入各个项目的前三名或前五名的成绩；(2)、能统计各学校总分；(3)、可以按学校编号、学校总分、男女团体总分排序输出；(4)、可以按学校编号查询学校某个项目的情况； (5)、可以按项目编号查询取得前三或前五名的学校。二、概要设计1主界面设计为了实现学生通讯录的管理系统各功能的管理，设计一个含有多个菜单的主控才担子程序以连接系统的各鸽子程序功能，为方便用户使用本系统。本系统主控菜单运行界面如图2.1所示。图2.1、“运动会分数统计系统”主界面2存储结构设计本系统采用结构体来存储“运动会分数统计系统”中的信息。(1) 、运动项目 项目编号 ；名次；(2) 、学校 学校编号；项目；团体总分；男团体总分；女团体总分；3系统功能设计本系统设置了4个子功能菜单，5个子功能的设计描述如下：(1) 、统计各学校总分，可以将之前输入的各个学校的分数统计并输出，该功能由zonfen()函数来实现。(2) 、按要求输出总分，可以分别按学校编号、学校总分、男团体总分、女团体总分等方式输出总分，分别通过调用xuexiaobianhao()、xuexiaozonfen()、boytuanzonfen()、girltuanzonfen()等函数来实现功能。(3) 、按学校编号查询项目情况，可以按学校编号查询项目情况，本功能通过chaxunxuexiaoxiangmu()函数来实现。(4) 、按项目编号查询取得名次的学校，可以按项目编号查询取得名次的学校，本功能通过chaxunxiangmuxuexiao()函数来实现。三、模块设计1模块设计 程序模块之间的关系如图2.2所示。图2.2、程序模块之间的关系图2系统子程序及功能设计本系统共有1个子程序，各程序的函数名及功能说明如下：(1) 、mulu()/调用函数目录(2) 、input()/调用运动会分数输入菜单(3) 、zonfen()/统计各学校总分(4) 、xuexiaobianhao() /按学校编号排序 (5) 、xuexiaozonfen()/按学校总分排序 (6) 、boytuanzonfen()/按男团体总分排序(7) 、girltuanzonfen()/按女团体总分排序(8) 、chaxunxuexiaoxiangmu() /按学校编号查询学校某个项目情况(9) 、chaxunxiangmuxuexiao() /按项目编号查询取得名次的学校(10) 、totaljisuan()/计算总数(11) 、tuichu()/退出系统 3 函数主要调用关系图本系统11个子程序之间的主要调用关系如图2.3所示图2.3系统函数调用关系四、详细设计1数据类型(1)、运动项目的定义： struct match int matchnum; int rank3; matbm+gm; (2) 、学校的定义： struct school int schoolnum; struct match matbm+gm; int total; int boytotal; int girltotal; schN;2 系统主要子程序详细设计 (1)、本函数主要是使用顺序表来实现输入成绩的操作：void input() /输入成绩 int i,j,k;for(i=0;i<N;i+) /初始化分数schi.total=0;schi.boytotal=0;schi.girltotal=0;for(k=0;k<bm+gm;k+) schi.matk.rank0=0;schi.matk.rank1=0;schi.matk.rank2=0;schi.matk.matchnum=k+1; printf("*输入成绩*n"); printf("输入说明：n");printf(" 1.学校编号为1-%d; 项目编号为1-%d (1-%d为男子项目,%d-%d为女子项目).n",N,bm+gm,bm,bm+1,bm+gm);printf(" 2. 成绩只能是0或1:n(0表示没获得该项目的该名次，1表示获得了该项目的该名次.)n",N);for(i=0;i<N;i+) printf("*请输入学校编号: ");loop3:scanf("%d",&schi.schoolnum); if(schi.schoolnum<=0|schi.schoolnum>N) printf("输入错误（只能是1-%d）请重新输入：",N); goto loop3; printf("项目编号: "); for(k=0;k<bm+gm;k+)printf("%d",schi.matk.matchnum);printf("n");for(j=0;j<3;j+) loop: printf(" 第(%d)名:",j+1);for(k=0;k<bm+gm;k+)scanf(" %d",&schi.matk.rankj);for(k=0;k<bm+gm;k+)if(schi.matk.rankj!=0&&schi.matk.rankj!=1) printf("输入错误，请重新输入，成绩只能是0或1n");goto loop; （2）、计算总数，主要用于统计各个学校的分数总和：void totaljisuan() int i,k,b;for(i=0;i<N;i+)for(k=0,b=0;k<bm+gm;k+) b=schi.matk.rank0*5+schi.matk.rank1*3+schi.matk.rank2*2; schi.total=schi.total+b; if(k<bm)schi.boytotal=schi.boytotal+b;if(k>=bm)schi.girltotal=schi.girltotal+b; 五、 测试分析1、 输入成绩当用户一运行该程序，就需要按照输入说明来输入运动会成绩，运行结果如图2.4所示。图2.4、输入成绩2、 统计各学校总分在主菜单下，用户输入1并回车，就可以统计出各个学校的总分。运行结果如图2.5所示。图2.5、统计各学校总分3、 按要求输出总分在主菜单下，用户输入2并回车，就可以看到系统提示，用户可以选择所需的方式来输出总分。运行结果如图2.6所示。图2.6、按要求输出总分4、 按学校编号查询项目情况在主菜单下，用户输入3并回车，就可以看到系统提示，用户输入学校编号及项目编号，就可以查询该学校的该项目情况。运行结果如图2.6所示。图2.6、某个学校的项目情况5、 按项目编号查询取得名次的学校在主菜单下，用户输入4并回车，就可以看到系统提示，用户输入项目编号，就可以查询该项目取得名次的学校。运行结果如图2.7所示。图2.7、某个项目的名次情况六、 用户手册 （1) 本程序执行文件为“gamesScorsSystem.exe”。（2) 进入本系统后，随即显示系统主菜单界面。用户可以在该界面输入各子菜单前对应的数字并按回车键，执行相应的子菜单命令。 七、调试报告1、由于刚开始程序比较简单，虽能运行，但处理错误的能力很低，后来经过反 复的添加修改，使程序能处理了错误，提高了健壮性。 2、算法的时空分析：线性表使用的是顺序结构，各种算法的时间复杂度相对比较合理 3、本程序相对来说比较容易看明白，其中涉及到的一些函数相对来说比较容易。通过调试，运行，基本上达到了要求，但还存在一些缺点。八、程序清单#include<stdio.h>#include<stdlib.h>#include<process.h>#define N 4 /学校个数 #define bm 3 /男团体个数 #define gm 2 /女团体个数 void xunhuan(); struct match /项目 int matchnum;int rank3; matbm+gm;struct school /学校 int schoolnum;struct match matbm+gm;int total;int boytotal;int girltotal;schN;/3.输入分数void input() /输入成绩 int i,j,k;for(i=0;i<N;i+) /初始化分数schi.total=0;schi.boytotal=0;schi.girltotal=0;for(k=0;k<bm+gm;k+) schi.matk.rank0=0;schi.matk.rank1=0;schi.matk.rank2=0;schi.matk.matchnum=k+1; printf("*输入成绩*n"); printf("输入说明：n");printf(" 1.学校编号为1-%d; 项目编号为1-%d (1-%d为男子项目,%d-%d为女子项目).n",N,bm+gm,bm,bm+1,bm+gm);printf(" 2. 成绩只能是0或1:n(0表示没获得该项目的该名次，1表示获得了该项目的该名次.)n",N);for(i=0;i<N;i+) printf("*请输入学校编号: ");loop3:scanf("%d",&schi.schoolnum); if(schi.schoolnum<=0|schi.schoolnum>N) printf("输入错误（只能是1-%d）请重新输入：",N); goto loop3; printf("项目编号: "); for(k=0;k<bm+gm;k+)printf("%d",schi.matk.matchnum);printf("n");for(j=0;j<3;j+) loop: printf(" 第(%d)名:",j+1);for(k=0;k<bm+gm;k+)scanf(" %d",&schi.matk.rankj);for(k=0;k<bm+gm;k+)if(schi.matk.rankj!=0&&schi.matk.rankj!=1) printf("输入错误，请重新输入，成绩只能是0或1n");goto loop; /4.计算总数void totaljisuan() int i,k,b;for(i=0;i<N;i+)for(k=0,b=0;k<bm+gm;k+) b=schi.matk.rank0*5+schi.matk.rank1*3+schi.matk.rank2*2; schi.total=schi.total+b; if(k<bm)schi.boytotal=schi.boytotal+b;if(k>=bm)schi.girltotal=schi.girltotal+b; /2.目录void mulu()printf("n*欢迎使用运动会分数统计系统*n");/目录printf(" * 1 统计各学校总分 *n");printf(" * 2 按要求输出总分 *n");printf(" * 3 按学校编号查询项目情况 *n");printf(" * 4 按项目编号查询取得名次的学校 *n");