太原理工大學軟件工程課程設計實驗

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

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

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

4、輸入一個單詞，檢索并輸出該單詞所 在的行號、該行中出現(xiàn)的次數(shù)以及在該行中的相應位置。1 .建立文本文件2 .給定單詞的計數(shù)3 .檢索單詞出現(xiàn)在文本文件中的行號、次數(shù)及其位置4 .主控菜單程序的結(jié)構(gòu)2 .概要設計示例如下:2.6算法設計樸素模式匹配算法該算法的基本思想是：設有三個指針一一i,j,k ,用i指示主用S每次開始 比較的位置；指針j,k分別指示主用S和模式用T中當前正在等待比較的字符位 置；一開始從主用S的第一個字符(i=0;j=1 )和模式T的第一個字符(k=0)比 較,若相等，則繼續(xù)逐個比較后續(xù)字符(j+,k+ )。否則從主審的下一個字符(i+) 起再重新和模式用(j=0)的字符開

5、始比較。依此類推，直到模式T中的所有字符都比較完，而且一直相等，則稱匹配成功，并返回位置 i ;否則返回-1 ,表示 匹配失敗。順序用的模式匹配算法如下：int index(SString S, SString T) / 求子用T在主用S中首次出現(xiàn)的位置int i,j,k,m,n;m=T.length; 模式用長度賦mn=S.length; / 目標用長度賦nfor (i=0; i<=n-m; i+)j=0; k=i; /目標用起始位置i送入kwhile (j<=m && s.chk=t.chj)k+; j+; /繼續(xù)下一個字符的比較if (j=m) /若相等，則說

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

7、sition(SString S1, SString S2, int k) int i, j;i=k-1; / 掃描s1的下標，因為c中數(shù)組下標是從0開始，用中序號相差1j=0; / 掃描s2的開始下標while (i<s1.length && j<s2.length)if (s1.chi=s2.chj) i+; j+; /繼續(xù)使下標移向下一個字符位置else i=i-j+1; j=0;/使i下標回溯到原位置的下一個位置，使j指向s2的第一個字 符，再重新比較if (j>=s2.length)return i- s2.length; /表示si中存在s2,返回

8、其起始位置elsereturn -1;/表示si中不存在s2, 返回-1 函數(shù)結(jié)束說明：以上兩個算法可統(tǒng)一為一個算法,即在子用定位算法Index(S,T)的參 數(shù)中增加一個起始位置參數(shù)即可。2.7各模塊及其偽碼：1 .建立文本文件建立文件的實現(xiàn)思路是：(1)定義一個用變量；(2)定義文本文件；(3)輸入文件名，打開該文件；(4)循環(huán)讀入文本行，寫入文本文件，其過程如下：While (不是文件輸入結(jié)束)讀入一文本行至用變量；用變量寫入文件；輸入是否結(jié)束輸入標志；(5)關(guān)閉文件。2 .給定單詞的計數(shù)該功能需要用到前一節(jié)中設計的模式匹配算法，逐行掃描文本文件。匹配一 個，計數(shù)器加1,直到整個文件掃描

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

10、用中；求出用長度；行單詞計數(shù)器置0;調(diào)用模式匹配函數(shù)匹配單詞定位、該行匹配單詞計數(shù)；行號計數(shù)器加1;If (行單詞計數(shù)器！=0)輸出行號、該行有匹配單詞的個數(shù)以及相應的位置;2.8函數(shù)調(diào)用關(guān)系主程序CreatTextFile()SubStrCount() SubStrInd()PartPosition()三.【設計功能的實現(xiàn)】#include "stdafx.h"#include<stdio.h>#include<string.h>#define MaxStrSize 256 /根據(jù)用戶需要自己定義大小typedef structchar chMax

11、StrSize; /ch 是一個可容納256個字符的字符數(shù)組 int length;SString; / 定義順序用類型int PartPosition(SString s1, SString s2, int k)/檢索單詞出現(xiàn)在文本文件中的位置int i, j;i=k-1; / 掃描s1的下標，因為c中數(shù)組下標是從0開始，用中序號相差1j=0; / 掃描s2的開始下標while (i<s1.length&&j<s2.length) if(s1.chi=s2.chj)i+;j+; /繼續(xù)使下標移向下一個字符位置 else i=i-j+1;j=0;if(j>=s

12、2.length)return i-s2.length;elsereturn -1; / 表示si中不存在s2,返回-1 /表示si中不存在s2,返回其起始位置 /函數(shù)結(jié)束void CreatTextFile()SString S;char fname10, yn;FILE *fp;printf("輸入要建立的文件名：");scanf("%s", fname);fp=fopen(fname,"w");yn='n' /輸入結(jié)束標志初值while(yn='n'|yn='N')printf(&

13、quot;請輸入一行文本：")；gets(S.ch);gets(S.ch);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; /定義兩個用變量char fname10;int i=1,j,k

14、;printf("輸入文本文件名：");scanf("%s", fname);fp=fopen(fname ,"r");printf("輸入要計數(shù)的單詞或字符串：");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.lengt

15、h=strlen(S.ch);k=0; /初始化開始檢索位置while(k<S.length-1) /檢索整個主用 Sj=PartPosition(S,T,k);if(j<0) break; else i+; /單詞計數(shù)器加1k=j+T.length; /繼續(xù)下一字用的檢索printf("n單詞s在文本文件s中共出現(xiàn)次肝，T.ch, fname,i); /統(tǒng)計單詞出現(xiàn)個數(shù)void SubStrInd()/單詞或字符串的檢索與計數(shù)FILE *fp;SString S,T; / 定義兩個用變量char fname10;int i,j,k,l,m;/int wz20;/?pri

16、ntf("輸入文本文件名：");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=

17、0;從用T的掃描初始位置默認為數(shù)組第一位，可根據(jù)用戶要求 改變k值，成為給定位置的用匹配算法i=0;while(k<S.length-1)j=PartPosition(S,T,k);if(j<0)break; elsei+;/i記錄被檢測單詞的出現(xiàn)次數(shù)wzi=j;/ 用數(shù)組wz口記錄被檢測單詞在所在行的位置k=j+T.length;/k 為檢測目標單詞的下一個起始位置 if(i>0) printf(" 行號：%d ,次數(shù)：d,位置分別為：",l, i); for(m=1;m<=i;m+)printf("%4d", wzm+1);p

18、rintf("n");int main() void CreatTextFlie(), SubStrInd();int xz;/ 操作號 doprintf("*n");printf("*n");乂本乂件的描索、子付用的統(tǒng)計及止位printf("*n");*n");printf("*1.建乂乂不乂件printf("*2.單詞字符串的計數(shù)*n");printf("*3.單詞字符串的定位*n");printf("*4.退出程序*n");pri

19、ntf("*n");printf("請選擇(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("選擇錯誤，重新選 n");while(1);四.【實例測試及運行結(jié)果】運行實例一：未輸入文件前的頁面輸入文本文件，計數(shù)單詞出現(xiàn)的次數(shù)乂霓乂冥國展區(qū)MM 乂題異具黑

20、具區(qū)黑異泉MM戰(zhàn)國M展盛晨其黑具娓舞具挺片蔓異黑具M：*3f提興興MM用*WMX*能拉我美景蜒衽：KM*圣*M*鷲蒲獷城劉甘昔肯*菁罟*，菁菁,修片甘董徜新茂善城*選普N音謂選擇11-7)耳區(qū)其黑募裊異泉皆舞吳某區(qū)反圣提共異黑吳裊共X，：反搔黑M裊找娓黑黑黑抬工娓:K畀聶KHK號而皆箝=葡=，芳善褥=謫聲胃說莉蕭*%*，芾蒼/海量褥看券= *神畤菊*請選擇門一。單詞心在交本文件叫xt中共出現(xiàn)2次*文本文葉的檢索、字符出的統(tǒng)計及定位民女江MWMW寫"圣本圣世皿 2,量于手舞半曲計數(shù) 九單詞字符串的定位 也退出程片輸入里建立的文件名：嗎Xt量輸入一行文本：1213141S1G61S141

21、3121結(jié)電糊入后？ y or n： y建立上'2三束! MHKXXhKXXXHKXXMMKKXMKXKXXHKXMMMKKXMMKKXX* £ *之4的檢索、字花出的績斗及定位X洋量不1建立文衣文件2,單詞字符串的十數(shù) 3.單H于符串的定位 匕退出程序輸入文本文件名：my.txt 輸入要統(tǒng)i-段末的單場 1 ?運行實例二:檢索某單詞的行號，出現(xiàn)次數(shù)，以及位置未輸入文件前的頁面年:開發(fā)軟件Wkrcsoft Visual Studio'MyPpjuS、課設- 3!|LJ 1小率*算饕誓左家旅翼XXMK*贊器X旅率 注文本文件的檢索.字符串的統(tǒng)計及定位*解*附X1.建立文

22、本文件«-九單詞字符串的計數(shù)策卜3.單閭字符串的定位*卜4.退出程及請選擇Cl-1t）輸入文本文件，計數(shù)單詞出現(xiàn)的次數(shù)"F:開發(fā)軟件MicgsoftZkual §tudioMyProjects'課設X文本文件的檢索、字符串的統(tǒng)計及定位X1.建立文本文件美舞2 .單詞字符串的計數(shù)M決3.單詞字符串的定位公舞4 .退出程序M其乂拭*MX拭父乂我拭MX我父乂乂興興興興興興餐*興興其興興餐我其X餐式X蕤其X請選擇（1-T）1輸入要建立的文件名：my.txt請輸入一行文本：文本文件結(jié)事輸入嗎？ y or n： y建立文彳牛結(jié)束 *X文本文律的檢索、字符串的統(tǒng)計及定位

23、"*今殺L建立文本文件美興2 .單詞字符串的計數(shù)款共3 ,單詞字符串的定位美圣匕退出程序x請選擇（1-T）2輸入文本文件名：my.txt1輸入要計數(shù)的單詞或字符串：文單詞文在文本文件my_txt中共出現(xiàn)2次半;檢索某單詞的行號，出現(xiàn)次數(shù)，以及位置'"F:Jf發(fā)軟件、Micro5。ft Visual,1囿門升嚴何改依課設.=:尸|款文本文件的檢索、字符串的統(tǒng)計及定位獷業(yè)我舞L建立文本文件具- 2.單詞字符串的計數(shù)我3 .單詞字符串的定位訴某4.退出程序具請選擇（1一4）3輸入文本文件名；my_txt輸入要檢索的單詞：文行號：1 ,次數(shù)：2,位置分別為:15XXMMXK

24、MMKXHMXMMXMXX»fXKKXMKMMKXXMXXMMXKXM棄文本文件的檢索、字符串的統(tǒng)計及定位於L建立文本文件決蕤2.單詞字符串的計數(shù)x- 3,單詞字符串的定位«球丸退出程序*,請選擇（LT）半;5.課程總結(jié)在此次的實驗過程中，我對結(jié)構(gòu)化的編程思想有了更深刻的理解。在實驗中，遇 到過很多問題，比如對抽象數(shù)據(jù)結(jié)構(gòu)線性表的實現(xiàn)方法不熟悉，對數(shù)組定義模糊 等，后來經(jīng)過思考并查閱資料解決了問題， 使自己養(yǎng)成了獨立思考、獨立解決問 題的能力。通過這次設計，我學會了和別人配合工作，因為一個人所學的知識不 可能面面俱到的，只有通過合作，發(fā)揮自己的優(yōu)點，體現(xiàn)團隊精神，才能使工作

25、 做得更為出色。通過這次設計，我學到了許多書本上學不到的知識，增強了自己的動手能 力。計算機技術(shù)的高速發(fā)展，使我深深地認識到只有不斷的加強學習， 才能在計 算機技術(shù)方面不至于被淘汰，今后，我還要加強學習，努力使自己成為一位專業(yè) 的計算機人員，為我自己所從事的工作服務。二.交通咨詢系統(tǒng)設計專業(yè)：軟件工程班級：1227班 姓名： 閆瑞娟 學號：2012005779同組人：張澤磊王曉春 閆瑞娟 組長：張澤磊 完成日期：2014.6.25一、問題描述在交通網(wǎng)絡非常發(fā)達，交通工具和交通方式不斷更新的今天，人們在出差、旅游或做其他出行時，不僅關(guān)心節(jié)省交通費用，而且對里程和所需要的時間等問題也感興趣。對于這

26、樣一個人們關(guān)心的問題，可用一個圖結(jié)構(gòu)來表示交通網(wǎng)絡系統(tǒng)，利用計算機建立一個交通咨詢系統(tǒng)。圖中的頂點表示城市， 邊表示城市之間的交通關(guān)系。這個交通系統(tǒng)可以回答出行旅客提出的各種路徑選擇問題。例如，問題之一： 位旅客要從 A城到B城，他希望選擇一條途 中中轉(zhuǎn)次數(shù)最少的路線?！奔僭O圖中每一站都需要換車，那么這個問題反映到圖上就是要找 一條從頂點A到頂點B的所含邊數(shù)目最少的路徑。我們只需要從頂點A出發(fā)對圖作廣度優(yōu)先搜索，一旦遇到頂點 B就終止。由此所得廣度優(yōu)先生成樹上，從根頂點A到頂點B的路徑就是中轉(zhuǎn)次數(shù)最少的路徑。路徑上 A與B之間的頂點就是路徑的中轉(zhuǎn)站，但這只是一類 最簡單的圖的最短路徑問題。系統(tǒng)

27、還可以回答諸如此類的等等的路徑選擇問題。設計一個交通咨詢系統(tǒng)，為出差、旅游或做其他出行的客人提供各種路徑選擇信息查詢 服務。二、設計需求及分析設計一個交通咨詢系統(tǒng)，能讓旅客咨詢從任一個城市頂點到另一城市頂點之間的最短路 徑(里程)或最低花費或最少時間等問題。對于不同的咨詢要求，可輸入城市間的路程或所需時間或所需費用。本設計共分三部分， 一是建立交通網(wǎng)絡圖的存儲結(jié)構(gòu)；二是解決單源最短路徑問題；三是實現(xiàn)任兩個城市頂點之間的最短路徑問題。3.2.1建立圖的存儲結(jié)構(gòu)n階方陣：設6= (V, E)是一個圖，結(jié)點集為G的鄰接矩陣A (aj)nn, ajV Vl,V2, ,Vno（Wi j）n n, 當（V

28、i,Vj）或Vi ,VjE0或,當（Vi ,Vj）或 Vi ,VjE鄰接矩陣是表示圖形中頂點之間相鄰關(guān)系的矩陣。圖的鄰接矩陣是定義如下的當鄰接矩陣的行表頭、列表頭順序一定時，一個圖的鄰接矩陣表示是唯一的。圖的鄰接矩陣表示，除了需用一個二維數(shù)組存儲頂點之間的相鄰關(guān)系的鄰接矩陣外，通常還需要使用一個具有 n個元素的一維數(shù)組來存儲頂點信息，其中下標為i的元素存儲頂點i的信息。因此，圖的鄰接矩陣的存儲結(jié)構(gòu)定義如下：#definf MVNum 50最大頂點數(shù)typedef structVertexType vexsMVNum;頂點數(shù)組，類型假定為char型Adjmatrix arcsMVNumMVNum

29、;鄰接矩陣，隹i定為 int 型MGraph;三、設計功能的實現(xiàn)(本次課設使用C語言描述)3.3.1建立有向圖的存儲結(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;for (i=1;i<=n;i+)for (j=1;j<=n;j+)G->arcsij=Maxint;printf("輸入 池邊的 i,j 及w:n" ,e);for (k=1;k<=e;k+)

30、scanf( "%d,%d,%d",&i,&j,&w);G->arcsij=w;printf("有向圖建立完畢n");三,停車場管理專業(yè)：軟件工程 班級：1227班 姓名： 張澤磊 學號：2012005779 同組人：張澤磊王曉春 閆瑞娟 組長：張澤磊 完成日期：2014.6.251 .【問題描述】設停車場是一個可停放 n輛汽車的狹長通道，且只有一個大門可供汽車進出。汽車在停 車場內(nèi)按車輛到達時間的先后順序，依次由北向南排列（大門在最南端，最先到達的第一輛車停放在停車場的最北端），若停車場內(nèi)已停滿 n輛汽車，則后來的汽車只能在門外的便道 上等候，一旦有車開走，則排在便道上的第一輛車即可開入；當停車場內(nèi)某輛車要離開時， 在它之后進入的車輛必須先退出車場為它讓路，待該輛車開出大門外