太原理工大學(xué)軟件工程課程設(shè)計(jì)實(shí)驗(yàn)

1、文本文件單詞的檢索與計(jì)數(shù)專(zhuān)業(yè)：軟件工程 班級(jí)： 1227班 姓名： 王曉春 學(xué)號(hào)： 2012005774 同組人：王曉春 閆瑞娟 張澤磊 組長(zhǎng)：王曉春 完成日期： 2014.6.25 一【問(wèn)題描述】串是非數(shù)值處理中的主要對(duì)象，如在信息檢索、文本編輯、符號(hào)處理等許多領(lǐng)域，得到越來(lái)越廣泛的應(yīng)用。在高級(jí)語(yǔ)言中也引入了串?dāng)?shù)據(jù)類(lèi)型概念，并且串變量與其他變量（如整型、實(shí)型等）一樣，可以進(jìn)行各種運(yùn)算。然而，在各種不同類(lèi)型的應(yīng)用中，所處理的串有不同的特點(diǎn)，要想有效地實(shí)現(xiàn)串的處理，就必須熟悉串的存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算。本課程設(shè)計(jì)的目的就是熟悉串類(lèi)型的實(shí)現(xiàn)方法和文本模式匹配方法，熟悉如何利用模式匹配算法實(shí)現(xiàn)一般的文

2、本處理技術(shù)。本課程設(shè)計(jì)分兩步：首先，設(shè)計(jì)出串定位算法（即模式匹配算法）及其實(shí)現(xiàn)；然后，再利用串定位算法設(shè)計(jì)文本文件的檢索及單詞的計(jì)數(shù)等操作。二【設(shè)計(jì)需求及分析】1.設(shè)計(jì)要求 1.1串模式匹配算法的設(shè)計(jì)要求在串的基本操作中，在主串中查找模式串的模式匹配算法即求子串位置的函數(shù)Index(S,T)，是文本處理中最常用、最重要的操作之一。所謂子串的定位就是求子串在主串中首次出現(xiàn)的位置，又稱(chēng)為模式匹配或串匹配。模式匹配的算法很多，在這里只要求用最簡(jiǎn)單的樸素模式匹配算法。該算法的基本思路是將給定子串與主串從第一個(gè)字符開(kāi)始比較，找到首次與子串完全匹配的子串為止，并記住該位置。但為了實(shí)現(xiàn)統(tǒng)計(jì)子串出現(xiàn)的個(gè)數(shù)，不

3、僅需要從主串的第一個(gè)字符位置開(kāi)始比較，而且需要從主串的任一給定位置檢索匹配字符串，所以，首先要給出兩個(gè)算法：1標(biāo)準(zhǔn)的樸素模式匹配算法2給定位置的匹配算法1.2文本文件單詞的檢索與計(jì)數(shù)的設(shè)計(jì)要求要求編程建立一個(gè)文本文件，每個(gè)單詞不包含空格且不跨行，單詞由字符序列構(gòu)成且區(qū)分大小寫(xiě)；統(tǒng)計(jì)給定單詞在文本文件中出現(xiàn)的總次數(shù)；檢索輸出某個(gè)單詞出現(xiàn)在文本中的行號(hào)、在該行中出現(xiàn)的次數(shù)以及位置。該設(shè)計(jì)要求可分為三個(gè)部分實(shí)現(xiàn)：其一，建立文本文件，文件名由用戶(hù)用鍵盤(pán)輸入；其二，給定單詞的計(jì)數(shù)，輸入一個(gè)不含空格的單詞，統(tǒng)計(jì)輸出該單詞在文本中的出現(xiàn)次數(shù)；其三，檢索給定單詞，輸入一個(gè)單詞，檢索并輸出該單詞所在的行號(hào)、該行

4、中出現(xiàn)的次數(shù)以及在該行中的相應(yīng)位置。1建立文本文件2給定單詞的計(jì)數(shù)3檢索單詞出現(xiàn)在文本文件中的行號(hào)、次數(shù)及其位置4主控菜單程序的結(jié)構(gòu)2.概要設(shè)計(jì)示例如下：2.6算法設(shè)計(jì) 樸素模式匹配算法該算法的基本思想是：設(shè)有三個(gè)指針i,j,k，用i指示主串S每次開(kāi)始比較的位置；指針j,k分別指示主串S和模式串T中當(dāng)前正在等待比較的字符位置；一開(kāi)始從主串S的第一個(gè)字符（i=0;j=1）和模式T的第一個(gè)字符（k=0）比較，若相等，則繼續(xù)逐個(gè)比較后續(xù)字符（j+,k+）。否則從主串的下一個(gè)字符（i+）起再重新和模式串（j=0）的字符開(kāi)始比較。依此類(lèi)推，直到模式T中的所有字符都比較完，而且一直相等，則稱(chēng)匹配成功，并返

5、回位置i；否則返回-1，表示匹配失敗。順序串的模式匹配算法如下：int index(SString S, SString T) /求子串T在主串S中首次出現(xiàn)的位置int i,j,k,m,n;m=T.length; /模式串長(zhǎng)度賦mn=S.length; /目標(biāo)串長(zhǎng)度賦nfor (i=0; i<=n-m; i+) j=0; k=i; / 目標(biāo)串起始位置i送入k while (j<=m && s.chk=t.chj) k+; j+; /繼續(xù)下一個(gè)字符的比較 if (j=m) /若相等，則說(shuō)明找到匹配的子串，返回匹配位置i，/否則從下一個(gè)位置重新開(kāi)始比較 return i

6、; /endforreturn -1; /endIndex 給定位置的串匹配算法該算法要求從串S1（為順序存儲(chǔ)結(jié)構(gòu)）中第k個(gè)字符起，求出首次與字符串S2相同的子串的起始位置。該算法與上面介紹的模式匹配算法類(lèi)似，只不過(guò)上述算法的要求是從主串的第一個(gè)字符開(kāi)始，該算法是上述算法的另一種思路：從第k個(gè)元素開(kāi)始掃描S1，當(dāng)其元素值與S2的第一個(gè)元素的值相同時(shí)，判定它們之后的元素值是否依次相同，直到S2結(jié)束為止。若都相同，則返回當(dāng)前位置值；否則繼續(xù)上述過(guò)程，直至S1掃描完為止，其實(shí)現(xiàn)算法如下：Int PartPosition(SString S1, SString S2, int k)int i, j;i

7、=k-1; /掃描s1的下標(biāo)，因?yàn)閏中數(shù)組下標(biāo)是從0開(kāi)始，串中序號(hào)相差1j=0; /掃描s2的開(kāi)始下標(biāo)while (i<s1.length && j<s2.length)if (s1.chi=s2.chj) i+; j+; /繼續(xù)使下標(biāo)移向下一個(gè)字符位置else i=i-j+1; j=0; /使i下標(biāo)回溯到原位置的下一個(gè)位置，使j指向s2的第一個(gè)字符，再重新比較if (j>=s2.length) return i- s2.length; /表示s1中存在s2，返回其起始位置else return -1; /表示s1中不存在s2， 返回-1 /函數(shù)結(jié)束說(shuō)明：以上

8、兩個(gè)算法可統(tǒng)一為一個(gè)算法，即在子串定位算法Index(S,T)的參數(shù)中增加一個(gè)起始位置參數(shù)即可。2.7各模塊及其偽碼：1.建立文本文件建立文件的實(shí)現(xiàn)思路是：（1）定義一個(gè)串變量；（2）定義文本文件；（3）輸入文件名，打開(kāi)該文件；（4）循環(huán)讀入文本行，寫(xiě)入文本文件，其過(guò)程如下： While ( 不是文件輸入結(jié)束) 讀入一文本行至串變量；串變量寫(xiě)入文件；輸入是否結(jié)束輸入標(biāo)志；（5）關(guān)閉文件。2給定單詞的計(jì)數(shù)該功能需要用到前一節(jié)中設(shè)計(jì)的模式匹配算法，逐行掃描文本文件。匹配一個(gè)，計(jì)數(shù)器加1，直到整個(gè)文件掃描結(jié)束；然后輸出單詞出現(xiàn)的次數(shù)。其實(shí)現(xiàn)過(guò)程如下：（1）輸入要檢索的文本文件名，打開(kāi)相應(yīng)的

9、文件；（2）輸入要檢索統(tǒng)計(jì)的單詞；（3）循環(huán)讀文本文件，讀入一行，將其送入定義好的串中，并求該串的實(shí)際長(zhǎng)度，調(diào)用串匹配函數(shù)進(jìn)行計(jì)數(shù)。具體描述如下：While (不是文件結(jié)束) 讀入一行并到串中； 求出串長(zhǎng)度； 模式匹配函數(shù)計(jì)數(shù)；（4）關(guān)閉文件，輸出統(tǒng)計(jì)結(jié)果。3.檢索單詞出現(xiàn)在文本文件中的行號(hào)、次數(shù)及其位置這個(gè)設(shè)計(jì)要求與上一個(gè)類(lèi)似，但要相對(duì)復(fù)雜一些。其實(shí)現(xiàn)過(guò)程描述如下：（1）輸入要檢索的文本文件名，打開(kāi)相應(yīng)的文件；（2）輸入要檢索統(tǒng)計(jì)的單詞；（3）行計(jì)數(shù)器置初值0；（4）while (不是文件結(jié)束) 讀入一行到指定串中； 求出串長(zhǎng)度； 行單詞計(jì)數(shù)器置0； 調(diào)用模式匹配函數(shù)匹配單詞定位、該行匹配單

10、詞計(jì)數(shù)； 行號(hào)計(jì)數(shù)器加1； If (行單詞計(jì)數(shù)器!=0) 輸出行號(hào)、該行有匹配單詞的個(gè)數(shù)以及相應(yīng)的位置；2.8函數(shù)調(diào)用關(guān)系主程序CreatTextFile()SubStrCount() SubStrInd()PartPosition()三【設(shè)計(jì)功能的實(shí)現(xiàn)】#include "stdafx.h"#include<stdio.h>#include<string.h>#define MaxStrSize 256 /根據(jù)用戶(hù)需要自己定義大小typedef structchar chMaxStrSize; /ch是一個(gè)可容納256個(gè)字符的字符數(shù)組int len

11、gth;SString; /定義順序串類(lèi)型int PartPosition(SString s1, SString s2, int k)/檢索單詞出現(xiàn)在文本文件中的位置int i, j;i=k-1; /掃描s1的下標(biāo)，因?yàn)閏中數(shù)組下標(biāo)是從0開(kāi)始，串中序號(hào)相差1j=0; /掃描s2的開(kāi)始下標(biāo)while (i<s1.length&&j<s2.length)if(s1.chi=s2.chj)i+;j+; /繼續(xù)使下標(biāo)移向下一個(gè)字符位置elsei=i-j+1;j=0;if(j>=s2.length)return i-s2.length;else return -1;

12、/表示s1中不存在s2，返回-1 /表示s1中不存在s2，返回其起始位置 /函數(shù)結(jié)束void CreatTextFile()SString S;char fname10, yn;FILE *fp;printf("輸入要建立的文件名： ");scanf("%s", fname);fp=fopen(fname,"w");yn='n' /輸入結(jié)束標(biāo)志初值while(yn='n'|yn='N')printf("請(qǐng)輸入一行文本：");gets(S.ch);gets(S.ch);

13、S.length=strlen(S.ch);fwrite(&S, S.length, 1, fp);fprintf(fp,"%c", 10); /是輸入換行printf("結(jié)束輸入嗎？y or n: ");yn=getchar();fclose(fp); /關(guān)閉文件printf("建立文件結(jié)束！");void SubStrCount()FILE *fp;SString S,T; /定義兩個(gè)串變量char fname10;int i=1,j,k;printf("輸入文本文件名： ");scanf("

14、%s", fname);fp=fopen(fname ,"r");printf("輸入要計(jì)數(shù)的單詞或字符串：");scanf("%s", T.ch);T.length=strlen(T.ch);while(!feof(fp)/掃描整個(gè)文件文本/fread(&S.ch,1,sizeof(S),fp); /讀入一行文本memset(S.ch,'0', 256);fgets(S.ch,100,fp);S.length=strlen(S.ch);k=0; /初始化開(kāi)始檢索位置while(k<S.leng

15、th-1) /檢索整個(gè)主串Sj=PartPosition(S,T,k);if(j<0)break;elsei+; /單詞計(jì)數(shù)器加1k=j+T.length; /繼續(xù)下一字串的檢索printf("n單詞%s在文本文件%s中共出現(xiàn)%d次n", T.ch, fname,i); /統(tǒng)計(jì)單詞出現(xiàn)個(gè)數(shù)void SubStrInd()/單詞或字符串的檢索與計(jì)數(shù)FILE *fp;SString S,T; /定義兩個(gè)串變量char fname10;int i,j,k,l,m;/int wz20;/?printf("輸入文本文件名：");scanf("%s&

16、quot;, 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;/從串T的掃描初始位置默認(rèn)為數(shù)組第一位，可根據(jù)用戶(hù)要求改變k值，成為給定位置

17、的串匹配算法i=0;while(k<S.length-1)j=PartPosition(S,T,k);if(j<0)break;elsei+;/i記錄被檢測(cè)單詞的出現(xiàn)次數(shù)wzi=j;/用數(shù)組wz記錄被檢測(cè)單詞在所在行的位置k=j+T.length;/k為檢測(cè)目標(biāo)單詞的下一個(gè)起始位置if(i>0)printf("行號(hào)：%d , 次數(shù)：%d, 位置分別為：",l, i);for(m=1;m<=i;m+) printf("%4d", wzm+1); printf("n");int main()void CreatTe

18、xtFlie(), SubStrInd();int xz;/操作號(hào)doprintf("*n");printf("*文本文件的檢索、字符串的統(tǒng)計(jì)及定位*n");printf("*n");printf("* 1.建立文本文件 *n");printf("* 2.單詞字符串的計(jì)數(shù) *n");printf("* 3.單詞字符串的定位 *n");printf("* 4.退出程序 *n");printf("*n");printf(" 請(qǐng)選擇

19、（1-4） n");scanf("%d", &xz);switch(xz)case 1:CreatTextFile(); break;case 2:SubStrCount(); break;case 3:SubStrInd(); break;case 4:return 0;default: printf("選擇錯(cuò)誤，重新選n");while(1);四【實(shí)例測(cè)試及運(yùn)行結(jié)果】運(yùn)行實(shí)例一：未輸入文件前的頁(yè)面輸入文本文件，計(jì)數(shù)單詞出現(xiàn)的次數(shù) 檢索某單詞的行號(hào)，出現(xiàn)次數(shù)，以及位置運(yùn)行實(shí)例二：未輸入文件前的頁(yè)面輸入文本文件，計(jì)數(shù)單詞出現(xiàn)的次數(shù)檢索某

20、單詞的行號(hào)，出現(xiàn)次數(shù)，以及位置5課程總結(jié)在此次的實(shí)驗(yàn)過(guò)程中，我對(duì)結(jié)構(gòu)化的編程思想有了更深刻的理解。在實(shí)驗(yàn)中，遇到過(guò)很多問(wèn)題，比如對(duì)抽象數(shù)據(jù)結(jié)構(gòu)線(xiàn)性表的實(shí)現(xiàn)方法不熟悉，對(duì)數(shù)組定義模糊等，后來(lái)經(jīng)過(guò)思考并查閱資料解決了問(wèn)題，使自己養(yǎng)成了獨(dú)立思考、獨(dú)立解決問(wèn)題的能力。通過(guò)這次設(shè)計(jì)，我學(xué)會(huì)了和別人配合工作，因?yàn)橐粋€(gè)人所學(xué)的知識(shí)不可能面面俱到的，只有通過(guò)合作，發(fā)揮自己的優(yōu)點(diǎn)，體現(xiàn)團(tuán)隊(duì)精神，才能使工作做得更為出色。通過(guò)這次設(shè)計(jì)，我學(xué)到了許多書(shū)本上學(xué)不到的知識(shí)，增強(qiáng)了自己的動(dòng)手能力。計(jì)算機(jī)技術(shù)的高速發(fā)展，使我深深地認(rèn)識(shí)到只有不斷的加強(qiáng)學(xué)習(xí)，才能在計(jì)算機(jī)技術(shù)方面不至于被淘汰，今后，我還要加強(qiáng)學(xué)習(xí)，努力使自己成為

21、一位專(zhuān)業(yè)的計(jì)算機(jī)人員，為我自己所從事的工作服務(wù)。 二交通咨詢(xún)系統(tǒng)設(shè)計(jì)專(zhuān)業(yè)：軟件工程 班級(jí)： 1227班 姓名： 閆瑞娟 學(xué)號(hào)： 2012005779 同組人：張澤磊 王曉春 閆瑞娟 組長(zhǎng)：張澤磊 完成日期： 2014.6.25 一、問(wèn)題描述在交通網(wǎng)絡(luò)非常發(fā)達(dá),交通工具和交通方式不斷更新的今天,人們?cè)诔霾?、旅游或做其他出行時(shí)，不僅關(guān)心節(jié)省交通費(fèi)用，而且對(duì)里程和所需要的時(shí)間等問(wèn)題也感興趣。對(duì)于這樣一個(gè)人們關(guān)心的問(wèn)題，可用一個(gè)圖結(jié)構(gòu)來(lái)表示交通網(wǎng)絡(luò)系統(tǒng)，利用計(jì)算機(jī)建立一個(gè)交通咨詢(xún)系統(tǒng)。圖中的頂點(diǎn)表示城市，邊表示城市之間的交通關(guān)系。這個(gè)交通系統(tǒng)可以回答出行旅客提出的各種路徑選擇問(wèn)題。例如，問(wèn)題

22、之一：“一位旅客要從A城到B城，他希望選擇一條途中中轉(zhuǎn)次數(shù)最少的路線(xiàn)。”假設(shè)圖中每一站都需要換車(chē)，那么這個(gè)問(wèn)題反映到圖上就是要找一條從頂點(diǎn)A到頂點(diǎn)B的所含邊數(shù)目最少的路徑。我們只需要從頂點(diǎn)A出發(fā)對(duì)圖作廣度優(yōu)先搜索，一旦遇到頂點(diǎn)B就終止。由此所得廣度優(yōu)先生成樹(shù)上，從根頂點(diǎn)A到頂點(diǎn)B的路徑就是中轉(zhuǎn)次數(shù)最少的路徑。路徑上A與B之間的頂點(diǎn)就是路徑的中轉(zhuǎn)站，但這只是一類(lèi)最簡(jiǎn)單的圖的最短路徑問(wèn)題。系統(tǒng)還可以回答諸如此類(lèi)的等等的路徑選擇問(wèn)題。設(shè)計(jì)一個(gè)交通咨詢(xún)系統(tǒng)，為出差、旅游或做其他出行的客人提供各種路徑選擇信息查詢(xún)服務(wù)。二、設(shè)計(jì)需求及分析設(shè)計(jì)一個(gè)交通咨詢(xún)系統(tǒng)，能讓旅客咨詢(xún)從任一個(gè)城市頂點(diǎn)到另一城市頂點(diǎn)之間

23、的最短路徑（里程）或最低花費(fèi)或最少時(shí)間等問(wèn)題。對(duì)于不同的咨詢(xún)要求，可輸入城市間的路程或所需時(shí)間或所需費(fèi)用。本設(shè)計(jì)共分三部分，一是建立交通網(wǎng)絡(luò)圖的存儲(chǔ)結(jié)構(gòu)；二是解決單源最短路徑問(wèn)題；三是實(shí)現(xiàn)任兩個(gè)城市頂點(diǎn)之間的最短路徑問(wèn)題。3.2.1建立圖的存儲(chǔ)結(jié)構(gòu)鄰接矩陣是表示圖形中頂點(diǎn)之間相鄰關(guān)系的矩陣。圖的鄰接矩陣是定義如下的n階方陣：設(shè)G=（V，E）是一個(gè)圖，結(jié)點(diǎn)集為。G的鄰接矩陣當(dāng)鄰接矩陣的行表頭、列表頭順序一定時(shí)，一個(gè)圖的鄰接矩陣表示是唯一的。圖的鄰接矩陣表示，除了需用一個(gè)二維數(shù)組存儲(chǔ)頂點(diǎn)之間的相鄰關(guān)系的鄰接矩陣外，通常還需要使用一個(gè)具有n個(gè)元素的一維數(shù)組來(lái)存儲(chǔ)頂點(diǎn)信息，其中下標(biāo)為i的元素存儲(chǔ)頂點(diǎn)i

24、的信息。因此，圖的鄰接矩陣的存儲(chǔ)結(jié)構(gòu)定義如下：#definf MVNum 50 /最大頂點(diǎn)數(shù)typedef struct VertexType vexsMVNum; /頂點(diǎn)數(shù)組，類(lèi)型假定為char型 Adjmatrix arcsMVNumMVNum; /鄰接矩陣，假定為int型MGraph;三、設(shè)計(jì)功能的實(shí)現(xiàn)（本次課設(shè)使用C語(yǔ)言描述）3.3.1 建立有向圖的存儲(chǔ)結(jié)構(gòu)#include <stdio.h>void CreateMGraph(MGraph *G,int n,int e)int i,j,k,w;for(i=1;i<=n;i+)G->vexsi=(char)i;f

25、or(i=1;i<=n;i+)for(j=1;j<=n;j+)G->arcsij=Maxint;printf("輸入%d條邊的i,j及w:n",e);for(k=1;k<=e;k+)scanf("%d,%d,%d",&i,&j,&w);G->arcsij=w;printf("有向圖建立完畢n");三停車(chē)場(chǎng)管理專(zhuān)業(yè)：軟件工程 班級(jí)： 1227班 姓名： 張澤磊 學(xué)號(hào)： 2012005779 同組人：張澤磊 王曉春 閆瑞娟 組長(zhǎng)：張澤磊 完成日期： 2014.6.25 一【問(wèn)題描述】設(shè)

26、停車(chē)場(chǎng)是一個(gè)可停放n輛汽車(chē)的狹長(zhǎng)通道，且只有一個(gè)大門(mén)可供汽車(chē)進(jìn)出。汽車(chē)在停車(chē)場(chǎng)內(nèi)按車(chē)輛到達(dá)時(shí)間的先后順序，依次由北向南排列（大門(mén)在最南端，最先到達(dá)的第一輛車(chē)停放在停車(chē)場(chǎng)的最北端）,若停車(chē)場(chǎng)內(nèi)已停滿(mǎn)n輛汽車(chē)，則后來(lái)的汽車(chē)只能在門(mén)外的便道上等候，一旦有車(chē)開(kāi)走，則排在便道上的第一輛車(chē)即可開(kāi)入；當(dāng)停車(chē)場(chǎng)內(nèi)某輛車(chē)要離開(kāi)時(shí)，在它之后進(jìn)入的車(chē)輛必須先退出車(chē)場(chǎng)為它讓路，待該輛車(chē)開(kāi)出大門(mén)外，其他車(chē)輛再按原次序進(jìn)入車(chē)場(chǎng)，每輛停放在車(chē)場(chǎng)的車(chē)在它離開(kāi)停車(chē)場(chǎng)時(shí)必須按它停留的時(shí)間長(zhǎng)短交納費(fèi)用。試為停車(chē)場(chǎng)編制按上述要求進(jìn)行管理的模擬程序。二【設(shè)計(jì)需求及分析】以棧模擬停車(chē)場(chǎng)，以隊(duì)列模擬車(chē)場(chǎng)外的便道，按照從終端讀入的輸入數(shù)據(jù)序列進(jìn)行模擬管理。每一組輸入數(shù)據(jù)包括三個(gè)數(shù)據(jù)項(xiàng)：汽車(chē)“到達(dá)”或“離去”信息、汽車(chē)牌照號(hào)碼以