软件工程 程序课程设计.doc

程序设计课程设计报告学 院：软件学院专 业：软件工程班 级： 学 号：姓 名： 指导教师： 时 间：2013年6月目录1.文本文件单词的检索与计数21.1【问题描述】21.2【设计需求及分析】21.2.1 串模式匹配算法的设计要求21.2.2 文本文件单词的检索与计数的设计要求21.3【设计功能的实现】31.3.1 朴素模式匹配算法31.3.2 给定位置的串匹配算法31.3.3 建立文本文件41.3.4 给定单词的计数51.3.5 检索单词出现在文本文件中的行号、次数及其位置61.3.6 运行主控程序81.3.7 详细设计（源代码）81.4【实例测试及运行结果】111.4.1 运行实例一111.4.2 运行实例二121.5【实现提示】132停车场管理132.1【问题描述】132.2【设计需求及分析】132.2.1所涉及的类132.2.2 一级菜单系统142.2.3车辆停车函数及流程图152.2.4车辆离开函数及流程图152.2.5列表显示车场信息函数及流程图172.2.6列表显示便道信息172.3【设计功能的实现】182.4【实例测试及运行结果】252.5【实现提示】261.文本文件单词的检索与计数专业：软件工程 班级： 姓名: 学号： 完成日期：6月21日1.1【问题描述】串是非数值处理中的主要对象，如在信息检索、文本编辑、符号处理等许多领域，得到越来越广泛的应用。在高级语言中也引入了串数据类型概念，并且串变量与其他变量（如整型、实型等）一样，可以进行各种运算。然而，在各种不同类型的应用中，所处理的串有不同的特点，要想有效地实现串的处理，就必须熟悉串的存储结构及其基本运算。本课程设计的目的就是熟悉串类型的实现方法和文本模式匹配方法，熟悉如何利用模式匹配算法实现一般的文本处理技术。本课程设计分两步：首先，设计出串定位算法（即模式匹配算法）及其实现；然后，再利用串定位算法设计文本文件的检索及单词的计数等操作。1.2【设计需求及分析】1.2.1 串模式匹配算法的设计要求在串的基本操作中，在主串中查找模式串的模式匹配算法即求子串位置的函数Index(S,T)，是文本处理中最常用、最重要的操作之一。所谓子串的定位就是求子串在主串中首次出现的位置，又称为模式匹配或串匹配。模式匹配的算法很多，在这里只要求用最简单的朴素模式匹配算法。该算法的基本思路是将给定子串与主串从第一个字符开始比较，找到首次与子串完全匹配的子串为止，并记住该位置。但为了实现统计子串出现的个数，不仅需要从主串的第一个字符位置开始比较，而且需要从主串的任一给定位置检索匹配字符串，所以，首先要给出两个算法：1标准的朴素模式匹配算法2给定位置的匹配算法1.2.2 文本文件单词的检索与计数的设计要求要求编程建立一个文本文件，每个单词不包含空格且不跨行，单词由字符序列构成且区分大小写；统计给定单词在文本文件中出现的总次数；检索输出某个单词出现在文本中的行号、在该行中出现的次数以及位置。该设计要求可分为三个部分实现：其一，建立文本文件，文件名由用户用键盘输入；其二，给定单词的计数，输入一个不含空格的单词，统计输出该单词在文本中的出现次数；其三，检索给定单词，输入一个单词，检索并输出该单词所在的行号、该行中出现的次数以及在该行中的相应位置。1建立文本文件2给定单词的计数3检索单词出现在文本文件中的行号、次数及其位置4主控菜单程序的结构1.3【设计功能的实现】1.3.1 朴素模式匹配算法该算法的基本思想是：设有三个指针i,j,k，用i指示主串S每次开始比较的位置；指针j,k分别指示主串S和模式串T中当前正在等待比较的字符位置；一开始从主串S的第一个字符（i=0;j=1）和模式T的第一个字符（k=0）比较，若相等，则继续逐个比较后续字符（j+,k+）。否则从主串的下一个字符（i+）起再重新和模式串（j=0）的字符开始比较。依此类推，直到模式T中的所有字符都比较完，而且一直相等，则称匹配成功，并返回位置i；否则返回-1，表示匹配失败。顺序串的模式匹配算法如下：int index(SString S, SString T) /求子串T在主串S中首次出现的位置int i,j,k,m,n;m=T.length; /模式串长度赋mn=S.length; /目标串长度赋nfor (i=0; i=n-m; i+) j=0; k=i; / 目标串起始位置i送入k while (j=m & s.chk=t.chj) k+; j+; /继续下一个字符的比较 if (j=m) /若相等，则说明找到匹配的子串，返回匹配位置i，/否则从下一个位置重新开始比较 return i; /endforreturn -1; /endIndex1.3.2 给定位置的串匹配算法该算法要求从串S1（为顺序存储结构）中第k个字符起，求出首次与字符串S2相同的子串的起始位置。该算法与上面介绍的模式匹配算法类似，只不过上述算法的要求是从主串的第一个字符开始，该算法是上述算法的另一种思路：从第k个元素开始扫描S1，当其元素值与S2的第一个元素的值相同时，判定它们之后的元素值是否依次相同，直到S2结束为止。若都相同，则返回当前位置值；否则继续上述过程，直至S1扫描完为止，其实现算法如下：Int PartPosition(SString S1, SString S2, int k)int i, j;i=k-1; /扫描s1的下标，因为c中数组下标是从0开始，串中序号相差1j=0; /扫描s2的开始下标while (is1.length & j=s2.length) return i- s2.length; /表示s1中存在s2，返回其起始位置else return -1; /表示s1中不存在s2， 返回-1 /函数结束说明：以上两个算法可统一为一个算法，即在子串定位算法Index(S,T)的参数中增加一个起始位置参数即可。1.3.3 建立文本文件建立文件的实现思路是：（1）定义一个串变量；（2）定义文本文件；（3）输入文件名，打开该文件；（4）循环读入文本行，写入文本文件，其过程如下： While (不是文件输入结束) 读入一文本行至串变量；串变量写入文件；输入是否结束输入标志；（5）关闭文件。定义一个串变量定义文本文件输入文件名，打开该文件循环读入文本行，写入文本文件While文本文件 N Y读入一文本行至串变量串变量写入文件文件输入结束关闭文件1.3.4 给定单词的计数该功能需要用到前一节中设计的模式匹配算法，逐行扫描文本文件。匹配一个，计数器加1，直到整个文件扫描结束；然后输出单词出现的次数。其实现过程如下：（1）输入要检索的文本文件名，打开相应的文件；（2）输入要检索统计的单词；（3）循环读文本文件，读入一行，将其送入定义好的串中，并求该串的实际长度，调用串匹配函数进行计数。具体描述如下：While (不是文件结束) 读入一行并到串中； 求出串长度； 模式匹配函数计数；（4）关闭文件，输出统计结果。给定一个单词，定义N=1，S=0，共M个单词扫描第N个单词If 第N个单词与所给单词相同 NN=N+1 YS=S+1If N=M Y N输出S，即为单词的计数结束1.3.5 检索单词出现在文本文件中的行号、次数及其位置这个设计要求与上一个类似，但要相对复杂一些。其实现过程描述如下：（1）输入要检索的文本文件名，打开相应的文件；（2）输入要检索统计的单词；（3）行计数器置初值0；（4）while (不是文件结束) 读入一行到指定串中； 求出串长度； 行单词计数器置0； 调用模式匹配函数匹配单词定位、该行匹配单词计数； 行号计数器加1； If (行单词计数器!=0) 输出行号、该行有匹配单词的个数以及相应的位置；输入文本文件名假设共X行，每行Y个单词L为行数，I为次数，N为第几个单词输入要检索的单词，定义L=1，I=0，N=1扫描第L行，第N个单词If 第N个单词与所给单词相同输出N，I=I+1 NN=N+1If N=X Y N输出L，IN=1，I=0，L=L+1IfL=Y Y结束 N1.3.6 运行主控程序主控菜单程序的结构要求内容如下：（1）头文件包含；（2）菜单选项包括： 1建立文件 2单词计数 3单词定位 4退出程序（3）选择14执行相应的操作，其他字符为非法。1.3.7 详细设计（源代码）#include#include#include#define MaxStrSize 500 /根据用户需要自己定义大小typedef struct char chMaxStrSize; /ch是一个可容纳个字符的字符数组 int length; SString;/定义顺序串类型int PartPosition (SString s1,SString s2,int k) int i,j; i=k-1; /扫描s1的下标，因为c中数组下标是从开始，串中序号相差 j=0;/扫描s2的开始下标 while(is1.length & j=s2.length) return i-s2.length; else return -1;/表示s1中不存在s2，返回-1 /表示s1中存在s2，返回其起始位置 /函数结束 void CreatTextFile() SString S; char fname10,yn; FILE *fp; printf(输入要建立的文件名：); scanf(%s,fname); fp=fopen(fname,w); yn=n;/输入结束标志初值 while(yn=n|yn=N) printf(请输入一行文本：);gets(S.ch);gets(S.ch); S.length=strlen(S.ch); fwrite(&S,S.length,1,fp); fprintf(fp,%c,10);/是输入换行 printf(结束输入吗？y or n ：);yn=getchar(); fclose(fp);/关闭文件 printf(建立文件结束!); void SubStrCount() FILE *fp; SString S,T;/定义两个串变量 char fname10; int i=0,j,k; printf(输入文本文件名：); scanf(%s,fname); fp=fopen(fname,r); printf(输入要统计计数的单词：); scanf(%s,T.ch); T.length=strlen(T.ch); while(!feof(fp) /扫描整个文本文件 / fread(&S.ch,1,sizeof(S),fp);/读入一行文本 memset(S.ch,0,256); fgets(S.ch,100,fp); S.length=strlen(S.ch); k=0; /初始化开始检索位置 while(kS.length-1) /检索整个主串S j=PartPosition(S,T,k);/调用串匹配函数 if(j0 ) break; else i+;/单词计数器加 k=j+T.length;/继续下一字串的检索 printf(n单词%s在文本文件%s中共出现%d次n,T.ch,fname,i); /统计单词出现的个数void SubStrInd() FILE *fp; SString S,T; /定义两个串变量 char fname10; int i,j,k,l,m; int wz20; /存放一行中字串匹配的多个位置 printf(输入文本文件名：); scanf(%s,fname); fp=fopen(fname,r); printf(输入要检索的单词：); scanf(%s,T.ch); T.length=strlen(T.ch); l=0; /行计数器置 while(!feof(fp) /扫描整个文本文件 /fread(&S,sizeof(S),1,fp); /读入一行文本 memset(S.ch,0,256); fgets(S.ch,256,fp); S.length=strlen(S.ch); l+; /行计数器自增 k=0;/初始化开始检索位置 i=0; /初始化单词计数器 while(kS.length-1) /检索整个主串S j=PartPosition(S,T,k); /调用串匹配函数 if(j0) printf(行号：%d,次数：%d,位置分别为：,l,i); for(m=1;m=i;m+) printf(%4d,wzm+1); printf(n); /检索单词出现在文本文件中的行号、次数及其位置 int main() void CreatTextFile(),SubStrCount(),SubStrInd(); int xz; do printf(* * * * * * * * * * * * * * * * * * * * * * * * *n); printf(*文本文件的检索、字串的统计及定位 *n); printf(* * * * * * * * * * * * * * * * * * * * * * * * *n); printf(* 1. 建立文本文件 *n); printf(* 2. 单词字串的计数 *n); printf(* 3. 单词字串的定位 *n); printf(* 4. 退出整个程序 *n); printf(* * * * * * * * * * * * * * * * * * * * * * * * n); printf( 请选择(1-4) ); scanf(%d,&xz); switch(xz) case 1 : CreatTextFile();break; case 2 : SubStrCount();break; case 3 : SubStrInd();break; case 4 : return 0; default:printf(选择错误，重新选n); while(1);1.4【实例测试及运行结果】1.4.1 运行实例一 Steve Jobs is the CEO of Applewhich he co-founded in 1976. Apple is leading the consumer technology world with its revolutionary iPhone and App Storeits family of iPod media players and iTunes media storeand its Mac computers and iLife and iWork application suites. Apple recently introduced the iPada breakthrough Internet and digital media deviceplus the iBookstorealongside iTunes and the App Store. 图4-1 图4-2 图4-31.4.2 运行实例二苹果电脑创始人斯蒂夫。他是一个美国式的英雄，几经起伏，但依然屹立不倒，就像海明威在老人与海中说到的，一个人可以被毁灭，但不能被打倒。他创造了“苹果”，掀起了个人电脑的风潮，改变了一个时代，但却在最顶峰的时候被封杀，从高楼落到谷底，但是12年后，他又卷土重来，重新开始第二个时代。 图4-4图4-5图4-61.5【实现提示】1.根据所给提示进行，在选择时只能在1-4之间进行选择。2.在输入文本时，要注意规范性。3.在选择文本进行统计时，文本名不能错误，否则一切都重新开始。4.在进行检索时，必须为文中有的字符，否则会出现中断点。2.停车场管理专业：软件工程 班级： 姓名： 学号： 完成日期：6月27日2.1【问题描述】设停车场是一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在停车场的最北端）,若停车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。2.2【设计需求及分析】以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码以及到达或离去的时刻。对每一组输入数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表结构实现。2.2.1所涉及的类class Che /车车compare离开时间进入时间费用车牌 图2-12.2.2 一级菜单系统实现对一级菜单：模拟停车场，便道，实现车辆停车、离开、列表显示停车场信息、退出系统功能的控制，调用各个子函数。开始读取头函数判断输入的数字是否为1执行第一种情况执行其他情况输入是否为4跳出头函数是否空 结束NYNYYN 图2-22.2.3车辆停车函数及流程图车辆停车函数实现：记录停车信息包括车辆车牌号、停车时刻、停车车位等。开始车辆停车，进入函数输入车牌号N停车场车库不满车进便道 Y输出车辆停车位置输入车辆车牌号 结束 图2-3 2.2.4车辆离开函数及流程图车辆离开函数主要实现：记录车辆离开的信息，以及便道上的车是否进入车库中。如图所示。开始N停车场车有车1YN停车场没有车Y输入离开车的车位 车辆离开 输出该车信息便道上有车NY便道上车进停车库显示便道上没有车输入便道上的车进车库时间结束 图2-4 2.2.5列表显示车场信息函数及流程图开始该函数主要判断停车场是否有车，如果有车就显示停车场车辆的信息，没车显示无车。N停车场是否有车Y显示停车场没有车输出停车场中车辆的信息结束 图2-52.2.6列表显示便道信息 判断便道上是否有车，如果有车，输出车辆的车牌号，如果没有车，显示无车. 开始便道是否有车NY输出便道车辆的信息显示便道上没有车结束 图2-62.3【设计功能的实现】#includestdafx.h#include#include#include#include#includeusing namespace stdtemplateclass Chepublic:Che();void ShuRuChePai(string);/输入车牌void JinRu(string);/输入车进入停车场的时间void LiKai(string);/输入车离开停车场的时间bool Compare(string);void ShuChuM(double);private:string s;/车牌号记录double st;/车到停车场的时间double et;/车离开停车场的时间;/车的类template Che:Che()st=0;et=0;templatevoid Che:ShuRuChePai(string a)s=a;templatevoid Che:JinRu(string y)int aa,bb,cc=1;int xx=0;int i;double d;for(i=0;i8;i+) if(yi!=:)xx=yi-0+10*xx; else if(cc=1) aa=xx;if(cc=2)bb=xx; cc+;xx=0; d=60.0*(60*aa+bb)+xx;st=d;templatevoid Che:LiKai(string y)int aa,bb,cc=1;int xx=0;int i;double d;for(i=0;i8;i+) if(yi!=:)xx=yi-0+10*xx; else if(cc=1)aa=xx; if(cc=2)bb=xx; cc+;xx=0; d=60.0*(60*aa+bb)+xx;et=d;templatebool Che:Compare(string a)if(pare(a)=0)return true;else return false;templatevoid Che:ShuChuM(double m)cout.precision(2);cout停车应支付的费用为：fixed(et-st)*m元endl;int main()int c,i,j,m,n101,w101,k,bb;/n101为当前车数,w101记录停车场当前的车数,m为停车场的个数,bb记录车子在哪个停车场,k记录后备队列里的车数;double money;/money为每秒钟的钱string x;/x为车牌号string str;string y;/输入的时间bool abc,xyz;stack Che TCC100;/停车场stack Che TCC2;/临时停车场queue Che BianDao;/便道队列cout*endl;couttttt停车场管理系统endl;Che car;Che lscar;memset(n,0,sizeof(n);k=0;m=-1;while(1)c=0;bb=0;abc=false;xyz=false;docout* ;cout 1:停车场初始化ttendl;cout 2:进入停车场ttendl;cout 3:离开停车场endl;cout 4:查看当前停车场及便道队列的状态ttendl;cout 0:退出endl;cout* ;cout 输入数字(没有前导,例如为非法输入;除上面数字的其他数字都为非法输入)str; if(str.size()1|!(str0=1|str0=2|str0=3|str0=4|str0=0)cout输入数字错误，请重新输入endl;continue; c=str0-0; if(c=1) cout输入拥有的停车场个数m; cout输入每秒的停车费用money; for(i=1;i=m;i+) cout输入第i个停车场拥有的车位数wi; continue; if(c=4)goto C; if(c=0)exit(0); while(!(c=2|c=3);if(m=-1)goto C; cout输入车牌号endl;getline(cin,x);getline(cin,x); car.ShuRuChePai(x);if(c=2)for(i=1;i=m;i+) if(niwi)cout进入第i个停车场endl; cout输入进入的时间(以XX:XX:XX形式输入)y;for(j=0;jy.size();j+)if(isalpha(yj)cout输入错误endl;goto C;car.JinRu(y);TCCi.push(car);ni+;break;else if(i!=m)cout第i个停车场已满endl;else cout第i个停车场已满endl;cout所有停车场已满,进入便道.endl;BianDao.push(car);k+; if(c=3)bool aa=false;for(i=1;i0)aa=true;break;if(aa)i=1;doif(TCCi.empty() while(!TCC2.empty()TCCi.push(TCC2.top();TCC2.pop();i+;if(i=m)break; else continue;lscar=TCCi.top(); TCC2.push(lscar); TCCi.pop();abc=lscar.Compare(x);if(abc=true)bb=i;while(!abc);if(lscar.Compare(x)=false)doif(TCCi.empty() cout停车场没有该车endl; while(!TCC2.