串的操作實驗報告

1、數(shù)據(jù)結構實驗報告報告名稱 串的操作 專 業(yè) 網(wǎng)絡工程 班 級 1001 學 號 201003120129 姓 名 張劍 指導教師 陳淑紅 李珍輝 黃哲 2012年 5月8日 一、實驗目的：熟悉串類型的實現(xiàn)方法，了解簡單文字處理的設計方法。二、實驗內容與基本要求：1. 設計可以在主串s中第i個位置之前插入一個子串t的程序。2. 設計可以在主串s中從第i個位置開始共取m個字符，求子串的程序。3. 設計一個程序求子串t在主串s中的起始位置 三、概要設計：1.數(shù)據(jù)結構：#include <stdio.h>#define MaxSize 100 /*最多的字符個數(shù)*/typedef stru

2、ct char dataMaxSize; /*定義可容納MaxSize個字符的空間*/ int len; /*標記當前實際串長*/ SqString;2.抽象數(shù)據(jù)類型：ADT String 數(shù)據(jù)對象：D ai |aiCharacterSet, i=1,2,.,n, n0 數(shù)據(jù)關系：R1 < ai-1, ai > | ai-1, ai D, i=2,.,n StrAssign (&T, chars) 初始條件：chars 是字符串常量。 操作結果：把 chars 賦為 T 的值。 StrCopy (&T, S) 初始條件：串 S 存在。 操作結果：由串 S 復制得串

3、T。DestroyString (&S) 初始條件：串 S 存在。 操作結果：串 S 被銷毀。StrEmpty(S)初始條件：串S存在。 操作結果：若 S 為空串，則返回 TRUE， 否則返回 FALSE。StrCompare (S, T)初始條件：串 S 和 T 存在。操作結果：若S > T，則返回值 > 0； 若S = T，則返回值 = 0； 若S < T，則返回值 < 0。 StrLength (S) 初始條件：串 S 存在。 操作結果：返回 S 的元素個數(shù)， 稱為串的長度。Concat (&T, S1, S2) 初始條件：串 S1 和 S2 存在

4、。 操作結果：用 T 返回由 S1 和 S2聯(lián)接而成的新串SubString (&Sub, S, pos, len)初始條件：串 S 存在，1posStrLength(S) 且0lenStrLength(S)-pos+1。操作結果：用 Sub 返回串 S 的第 pos 個字符起 長度為 len 的子串。Index (S, T, pos)初始條件：串S和T存在，T是非空串，1posStrLength(S)。操作結果： 若主串 S 中存在和串 T 值相同 的子串, 則返回它在主串 S 中第pos個 字符之后第一次出現(xiàn)的位置； 否則函數(shù)值為0。 Replace (&S, T, V)

5、初始條件：串S, T和 V 均已存在且 T 是非空串。 操作結果：用V替換主串S中出現(xiàn)的所有與（模式串）T 相等的不重疊的子串。StrInsert (&S, pos, T)初始條件：串S和T存在， 1posStrLength(S)1。操作結果：在串S的第pos個字符之前 插入串T。StrDelete (&S, pos, len)初始條件：串S存在 1posStrLength(S)-len+1。操作結果：從串S中刪除第pos個字符 起長度為len的子串。 ClearString (&S) 初始條件：串S存在。 操作結果：將S清為空串四、詳細設計：#include <

6、stdio.h>#define MaxSize 100 /*最多的字符個數(shù)*/typedef struct char dataMaxSize; /*定義可容納MaxSize個字符的空間*/ int len; /*標記當前實際串長*/ SqString;void StrAssign(SqString &str,char cstr)/*str為引用型參數(shù)*/ int i;char aMaxSize;gets(a);cstr=a; for (i=0;cstri!='0'i+) str.datai=cstri; str.len=i;SqString InsStr(SqSt

7、ring s1,int i,SqString s2) int j; SqString str; str.len=0; if (i<=0 | i>s1.len+1) /*參數(shù)不正確時返回空串*/printf("參數(shù)不正確n"); return s1; for (j=0;j<i-1;j+) /*將s1.ch0s1.chi-2復制到str*/ str.dataj=s1.dataj; for (j=0;j<s2.len;j+) /*將s2.ch0s2.chs2.len-1復制到str*/ str.datai+j-1=s2.dataj; for (j=i-1;

8、j<s1.len;j+) /*將s1.chi-1s.chs1.len-1復制到str*/ str.datas2.len+j=s1.dataj; str.len=s1.len+s2.len; return str;SqString SubStr(SqString s,int i,int j) SqString str; int k; str.len=0; if (i<=0 | i>s.len | j<0 | i+j-1>s.len)printf("參數(shù)不正確n"); return str; /*參數(shù)不正確時返回空串*/ for (k=i-1;k&

9、lt;i+j-1;k+) /*將s.chis.chi+j復制到str*/ str.datak-i+1=s.datak; str.len=j; return str; int Index(SqString s,SqString t)int i=0,j=0;while(i<s.len&&j<t.len)if(s.datai=t.dataj)i+;j+;elsei=i-j+1;j=0;if(j>=t.len)return(i-t.len+1);elsereturn(-1);void DispStr(SqString str) int i; if (str.len&g

10、t;0) for (i=0;i<str.len;i+) printf("%c",str.datai);printf("n"); main() SqString s,s0,s1,s2,s3,s4,s5; char *p,*q,*r,*l,*m; int c,x,y,z,w; printf("/*本程序可實現(xiàn)如下功能*/n"); printf("t1.在主串s中第i個位置之前插入一個子串tnt2.在主串s中從第i個位置開始共取m個字符，求子串tnt3.求子串t在主串s中的起始位置tnt4.退出程序n"); whi

11、le(c) printf("請選擇您要進入的功能: ");scanf("%d",&x); switch(x) case 1: getchar(); printf("請輸入主串S："); StrAssign(s1,p); printf("請輸入子串T："); StrAssign(s2,q); printf("請輸入插入位置i："); scanf("%d",&y); InsStr(s1,y,s2); s=InsStr(s1,y,s2); printf("

12、輸出新串為: "); DispStr(s); break; case 2: getchar(); printf("請輸入主串S："); StrAssign(s3,r); printf("從位置 y 開始取長度為 z 的子串：n"); scanf("%d%d",&y,&z); SubStr(s3,y,z); s0=SubStr(s3,y,z); printf("輸出子串為: "); DispStr(s0); break; case 3: getchar(); printf("請輸入

13、主串S："); StrAssign(s4,l); printf("請輸入子串T："); StrAssign(s5,m); Index(s4,s5); w=Index(s4,s5); if(w) printf("主串和子串在第%d個字符處首次匹配n",w); else printf("主串和子串匹配不成功n"); break; case 4: getchar();c=0;break; default:printf("輸入錯誤，請重試！n"); break; 五、調試分析及測試結果：測試數(shù)據(jù)：1. 在主串s(

14、abcdefg)中第3個位置之前插入一個子串t(apple),輸出新串。2. 在主串s(thisisacprogram)中從第5個位置開始共取3個字符，求子串的程序。3. 主串s(thekingisababyandstrong),子串t(isababy),輸出子串t在主串s中的起始位置。 測試結果及分析： 圖一1.程序通過編譯后，運行程序。進入選擇界面，該程序主要實現(xiàn)三個功能，如圖一所示?！?.在主串s中第i個位置之前插入一個子串；2.在主串s中從第i個位置開始共取m個字符，求子串；3.求子串t在主串s中的起始位置?！贝私缑嫱ㄟ^switch分支語句實現(xiàn)。按相應的數(shù)字鍵進入相應的功能。 圖二2.

15、按數(shù)字鍵1鍵實現(xiàn)串的插入功能。輸入主串“abcdefg”，依照提示輸入子串“apple”，選擇插入的位置為i=3；按回車鍵結束，輸入新串為“abapplecdefg”,程序運行正確，輸出結果無誤。在程序運行過程中，調用串的創(chuàng)建StrAssign（）函數(shù)，插入字符InsStr（）函數(shù)，以及字符串的輸出DispStr（）函數(shù)。 圖三 3.輸入數(shù)字2，進入從主串中的第i個位置開始共取m個字符，求子串的操作。該操作主要是SubStr（）函數(shù)的實現(xiàn)。輸入主字符串“thisisacprogram”,從位置5開始取長度為3的字符串，輸出結果為“isa”，程序運行完畢，進入功能選擇。 圖四4. 進入功能4，求子串在主串s中的起始位置t;該過程主要實現(xiàn)Index（）的用法。這里采用的是BrutForce算法