串基本操作的演示

1、信息科學(xué)與技術(shù)學(xué)院數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告題目名稱：串的基本操作演示專業(yè)班級：學(xué)生姓名：學(xué)生學(xué)號：指導(dǎo)教師：完成日期：目錄一、需求分析1二、概要設(shè)計2三、詳細(xì)設(shè)計21、自定義數(shù)據(jù)類型22、基本操作函數(shù)33、主函數(shù)8四、調(diào)試分析10五、用戶手冊10六、測試結(jié)果11七、實驗中出現(xiàn)的問題、解決方法和心得體會11八、附錄11一、需求分析【問題描述】 如果語言沒有把串作為一個預(yù)先定義好的基本類型對待,又需要用該語言寫一個涉及串操作的軟件系統(tǒng)時,用戶必須自己實現(xiàn)串類型。試實現(xiàn)串類型,并寫一個串的基本操作的演示系統(tǒng)。 【基本要求】 在教科書節(jié)用堆分配存儲表示實現(xiàn)HString串類型

2、的最小操作子集的基礎(chǔ)上,實現(xiàn)串抽象數(shù)據(jù)類型的其余基本操作(不使用C語言本身提供的串函數(shù))。參數(shù)合法性檢查必須嚴(yán)格。 利用基本操作函數(shù)構(gòu)造以下系統(tǒng):它是一個命令解釋程序,循環(huán)往復(fù)地處理用戶鍵入的每一條命令,直至終止程序的命令為止。命令定義如下: (1)賦值。  格式: A <串標(biāo)識> <回車> 用<串標(biāo)識>所表示的串的值建立新串,并顯示新串的內(nèi)部名和串值。例:A Hi! (2)判相等。格式: E <串標(biāo)識1> <串

3、標(biāo)識2> <回車> 若兩串相等,則顯示"EQUAL",否則顯示"UNEQUAL"。 (3)聯(lián)接。 格式:C <串標(biāo)識1> <串標(biāo)識2> <回車> 將兩串拼接產(chǎn)生結(jié)果串,它的內(nèi)部名和串值都顯示出來。 (4)求長度。格式:L串標(biāo)識> <回車> 顯示串的長度。 (5)求子串。格式:S <串標(biāo)識> +<數(shù)1>+<數(shù)2>

4、<回車> 如果參數(shù)合法,則顯示子串的內(nèi)部名和串值。<數(shù)>不帶正負(fù)號。 (6)子串定位。格式:I <串標(biāo)識1> <串標(biāo)識2> <回車> 顯示第二個串在第一個串中首次出現(xiàn)時的起始位置。 (7)串替換。格式: R <串標(biāo)識1> <串標(biāo)識2> <串標(biāo)識3> <回車> 將第一個串中所有出現(xiàn)的第二個串用第三個串替換,顯示結(jié)果串的內(nèi)部名和串值,原串不變。 (8)顯

5、示。格式:P <回車>顯示所有在系統(tǒng)中被保持的串的內(nèi)部名和串值的對照表。 (9)刪除。格式:D <內(nèi)部名> <回車> 刪除該內(nèi)部名對應(yīng)的串,即賦值的逆操作。 (10)退出。格式:Q <回車> 結(jié)束程序的運行。 在上述命令中,如果一個自變量是串,則應(yīng)首先建立它。基本操作函數(shù)的結(jié)果(即函數(shù)值)如果是一個串,則應(yīng)在尚未分配的區(qū)域內(nèi)新辟空間存放。 【測試數(shù)據(jù)】 自定。但要包括以下幾組: (1)E   <

6、;回車>,應(yīng)顯示"EQUAL"。 (2)E abc abcd<回車>,應(yīng)顯示"UNEQUAL"。 (3)C      <回車>,應(yīng)顯示"。 (4)I a  <回車>,應(yīng)報告:參數(shù)非法。 (5)R aaa aa b<回車>,應(yīng)顯示'ba (6)R aaabc a aab

7、<回車>,應(yīng)顯示aabaabaabbc。 (7)R Faaaaaaaa aaaa ab,<回車>,應(yīng)顯示Fabab。二、概要設(shè)計 實現(xiàn)串的抽象數(shù)據(jù)類型和實現(xiàn)其基本操作，程序中將涉及下列抽象數(shù)據(jù)類型： 1定義串的基本主結(jié)構(gòu) ADT String 數(shù)據(jù)對象：D=ai| aicharcaterset,i=1,2,n,n>=0 數(shù)據(jù)關(guān)系：R1=<ai-1,ai>|ai-1,aiD, i=1,2,n 基本操作： compare(hstring s,hstring t) 初始條件：S和T是已存在的Hstring類型。 操作結(jié)

8、果：比較其值，顯示結(jié)果“UNEQUAL”或“EQUAL”。 length(hstring s) 初始條件：S是已存在的Hstring類型。 操作結(jié)果：返回該串的長度。 concat(hstring &t,hstring s1,hstring s2) 初始條件：S1和S2是已存在的Hstring類型。 操作結(jié)果：由S1和S2聯(lián)接成新串。 index(hstring s,hstring t,int pos) 初始條件：S和T是已存在的Hstring類型。 操作結(jié)果：顯示第二個串在第一個串中首次出現(xiàn)的起始位置。 replace(hstring &s,hstring t,hstring

9、 v) 初始條件：M、t和v是已存在的Hstring類型。 操作結(jié)果：將第一個串中所有出現(xiàn)的第二個串用第三個串替換，顯示結(jié)果串的內(nèi)部名和串值，原串不變。 sub (hstring &sub,hstring s,int pos,int len) 初始條件：S是已存在的Hstring類型。 操作結(jié)果：如果參數(shù)合法，則顯示子串的內(nèi)部名和串值 。 display(HString S) 初始條件：S是已存在的Hstring類型。 操作結(jié)果：顯示串S的內(nèi)部名和串值 。 copy(hstring &t,hstring s) 初始條件：S是已存在的Hstring類型。 操作結(jié)果：由串s復(fù)制得串

10、tgetin(int n) 初始條件：處理命令串S1, 操作結(jié)果：把串值存入串頭表中 ADT String三、詳細(xì)設(shè)計1、自定義數(shù)據(jù)類型typedef struct hstring char *ch; int length; hstring; hstring headlist100; /串頭數(shù)組2、基本操作函數(shù)1、賦值void strassign() char c; int i; char a20; while(c=getchar()!='n') if(c=''') i=0; while(c=getchar()!=''') ai+

11、=c; headlistcurnum.ch=(char*)malloc(i+1)*sizeof(char); headlistcurnum.length=i; for(i=0;i<headlistcurnum.length;i+) headlistcurnum.chi=ai; curnum+; printf("內(nèi)部名：%d 串值:",curnum-1); for(i=0;i<=headlistcurnum-1.length-1;i+) printf("%c",headlistcurnum-1.chi); printf("n"

12、;); 2比較void compare() char c; int i,m,n,j=0; while(c=getchar()!='n') if(c>=48&&c<=57) i=0; bi+=c; while(c=getchar()>=48&&c<=57)/還是數(shù)字 bi+=c; bi='0' sj=atoi(b); j+; if(c=''') i=0; while(c=getchar()!=''') ai+=c; headlistcurnum.ch=(char

13、*)malloc(i+1)*sizeof(char); headlistcurnum.length=i; for(i=0;i<headlistcurnum.length;i+) headlistcurnum.chi=ai; sj+=curnum+; if(s0>=curnum|s1>=curnum) printf("參數(shù)不合法n"); else j=strcompare(headlists0,headlists1); if(j=0) printf("EQUALn"); else printf("UNEQUALn");

14、 3、求長void length() char c; int i,m,n,j=0; while(c=getchar()!='n') if(c>=48&&c<=57) i=0; bi+=c; while(c=getchar()>=48&&c<=57)/還是數(shù)字 bi+=c; bi='0' sj=atoi(b); j+; if(c=''') i=0; while(c=getchar()!=''') ai+=c; headlistcurnum.ch=(char*)m

15、alloc(i+1)*sizeof(char); headlistcurnum.length=i; for(i=0;i<headlistcurnum.length;i+) headlistcurnum.chi=ai; sj=curnum+; if(s0>=curnum) printf("參數(shù)不合法n"); return; printf("%dn",headlists0.length); 4、連接void concat() char c; int i,m,n,j=0; while(c=getchar()!='n') if(c&g

16、t;=48&&c<=57) i=0; bi+=c; while(c=getchar()>=48&&c<=57)/還是數(shù)字 bi+=c; bi='0' sj=atoi(b); j+; if(c=''') i=0; while(c=getchar()!=''') ai+=c; headlistcurnum.ch=(char*)malloc(i+1)*sizeof(char); headlistcurnum.length=i; for(i=0;i<headlistcurnum.le

17、ngth;i+) headlistcurnum.chi=ai; sj+=curnum+; if(s0>=curnum|s1>=curnum) printf("參數(shù)不合法n"); else printf("連接后串內(nèi)部名:%d 串值:",curnum); strconcat(headlistcurnum+,headlists0,headlists1); 5、子串定位void index() char c; int i,m,n,j=0; while(c=getchar()!='n') if(c>=48&&c&

18、lt;=57) i=0; bi+=c; while(c=getchar()>=48&&c<=57)/還是數(shù)字 bi+=c; bi='0' sj=atoi(b); j+; if(c=''') i=0; while(c=getchar()!=''') ai+=c; headlistcurnum.ch=(char*)malloc(i+1)*sizeof(char); headlistcurnum.length=i; for(i=0;i<headlistcurnum.length;i+) headlist

19、curnum.chi=ai; sj+=curnum+; if(s0>=curnum|s1>=curnum) printf("參數(shù)不合法n"); else printf("%dn",strindex(headlists0,headlists1,1); 6、顯示void display() int i,j; char c; while(c=getchar()!='n'); for(i=0;i<curnum;i+) printf("n內(nèi)部名%d ",i); for(j=0;j<headlisti.le

20、ngth;j+) printf("%c",headlisti.chj); 7、刪除void Delete() char c; int i,m,n,j=0; while(c=getchar()!='n') if(c>=48&&c<=57) i=0; bi+=c; while(c=getchar()>=48&&c<=57)/還是數(shù)字 bi+=c; bi='0' sj=atoi(b); j+; if(s0>=curnum) printf("參數(shù)不合法n"); else

21、 clearstring(headlists0); 8 求子串void sub() char c; int i,m,n,j=0; while(c=getchar()!='n') if(c>=48&&c<=57) i=0; bi+=c; while(c=getchar()>=48&&c<=57)/還是數(shù)字 bi+=c; bi='0' sj=atoi(b); j+; if(c=''') i=0; while(c=getchar()!=''') ai+=c; hea

22、dlistcurnum.ch=(char*)malloc(i+1)*sizeof(char); headlistcurnum.length=i; for(i=0;i<headlistcurnum.length;i+) headlistcurnum.chi=ai; sj+=curnum+; if(s0>=curnum) printf("參數(shù)不合法n"); return; j=substring(headlistcurnum,headlists0,s1,s2); if(j=1) printf("子串內(nèi)部名:%d ",curnum); for(i=

23、0;i<s2;i+) printf("%c",headlistcurnum.chi); curnum+; 9、替換void replace() char c; int i; char a20; while(c=getchar()!='n') if(c=''') i=0; while(c=getchar()!=''') ai+=c; headlistcurnum.ch=(char*)malloc(i+1)*sizeof(char); headlistcurnum.length=i; for(i=0;i<

24、;headlistcurnum.length;i+) headlistcurnum.chi=ai; curnum+; strcopy(headlistcurnum,headlistcurnum-3); strreplace(headlistcurnum-1,headlistcurnum-3,headlistcurnum-2); for(i=0;i<headlistcurnum-1.length;i+) printf("%C",headlistcurnum-1.chi); printf("n"); 3、主函數(shù)void main() char c; p

25、rintf("*n"); printf(" A:賦值 E：判相等 C：聯(lián)接 L：求長度 n S：求子串 I：子串定位 R：串替換 P:顯示n D：刪除 Q：退出n"); printf("*n"); printf("請輸入命令：n"); while(c=getchar()!='Q') switch(c) case 'E': compare();printf("串?dāng)?shù)：%dn",curnum); break; case 'A': strassign();

26、 printf("串?dāng)?shù)：%dn",curnum);break; case 'L': length(); printf("串?dāng)?shù)：%dn",curnum);break; case 'C': concat(); printf("n串?dāng)?shù)：%dn",curnum);break; case 'I': index(); printf("n串?dāng)?shù)：%dn",curnum);break; case 'P': display();printf("n");

27、 break; case 'D': Delete(); break; case 'S': sub(); break; case 'R': replace(); break; 四、調(diào)試分析五、用戶手冊1. 本程序的運行環(huán)境為DOS操作系統(tǒng)，執(zhí)行文件為：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計.exe.2. 進(jìn)入程序后即會顯示可以使用的命令和命令用途和對應(yīng)命令的語法格式的列表，用戶可以根據(jù)命令列表輸入正確的命令。如果輸入正確就會顯示相應(yīng)的結(jié)果，接著可以輸入下一條命令。如果輸入錯誤，會顯示相應(yīng)的錯誤的原因并提示重新輸入命令。3. 命令是以回車為結(jié)束的標(biāo)志。4. 本程序只能輸入

28、字符串，且字符串支持空格符，不過字符串必須用雙單引號括住。所以Delete命令需要輸入的數(shù)字也必須用雙單引號括住。但命令Substring并不需要如此，在提示“請輸入子串的開始位置:”和“請輸入子串的結(jié)束中位置:”直接輸入數(shù)字即可。5. 命令Subsring在輸出正確結(jié)果后會接著輸出“此命令不存在！請重新輸入！”此提示，此問題一直都沒有解決，也是該程序的缺陷，但是結(jié)果是正確的。6. 若要退出程序，請鍵入命令：Q。六、測試結(jié)果 (1)E 命令輸出的結(jié)果為:EQUAL (2)E abc abcd 命令輸出的結(jié)果為:UNEQUAL (3) I a 語法格式錯誤！請重新輸入！ (4)R aaa aab

29、 命令輸出的結(jié)果為：ba (5)R aaabca aab 命令輸出的結(jié)果為:aabaabaabbc (6)R aaaaaaaa aaaa ab 命令輸出的結(jié)果為:abab (7)A string 命令輸出的結(jié)果為: 新賦值的字符串的內(nèi)部名為:4，串值為:string七、實驗中出現(xiàn)的問題、解決方法和心得體會這個實驗是對串的操作的時間，實現(xiàn)串操作的基本函數(shù)，在接受命令的輸入格式方面，試了很多種方法。開始時嘗試過用getchar（）函數(shù)來接收命令，并根據(jù)接受到的指令進(jìn)行操作。在調(diào)試程序的過程中，遇到一些結(jié)果不正確或超出范圍的情況，又要重新返回相應(yīng)的函數(shù)進(jìn)行檢查和修改補(bǔ)充，才能使程序更加健壯和完整，才

30、能做出一個更加實用的軟件八、附錄源程序#include<stdio.h> #include<stdlib.h> #include<math.h> #include<malloc.h> typedef struct hstring char *ch; int length; hstring; hstring headlist100; int curnum=0; /系統(tǒng)中現(xiàn)有的串的數(shù)目int s3; /命令的串參數(shù)的內(nèi)部名（最多3）char a20; char b5; int strcompare(hstring s,hstring t) /若s&g

31、t;t,則返回值>0;若s=t,則返回值=0；若s<t,則返回值<0; int i; for(i=0;i<s.length&&i<t.length;+i) if(s.chi!=t.chi) return s.chi-t.chi; return s.length-t.length; void clearstring(hstring &s) /將s清為空串 if(s.ch) free(s.ch); s.ch=0; s.length=0; void strconcat(hstring &t,hstring s1,hstring s2) /

32、用t返回由s1和s2聯(lián)接而成的新串 int i,j; if(t.ch) free(t.ch); if(!(t.ch=(char*)malloc(s1.length+s2.length+1)*sizeof(char) printf("overflown");return; for(i=0;i<=s1.length-1;i+) t.chi=s1.chi; t.length=s1.length+s2.length; for(i=s1.length,j=0;i<=t.length-1;i+,j+) t.chi=s2.chj; for(i=0;i<t.length;

33、i+) printf("%c",t.chi); int substring(hstring &sub,hstring s,int pos,int len) /用sub返回串s的第pos個字符起長度為len的子串 /其中，1<=pos<=strlength(s)且0<=len<=strlength(s)-pos+1 int i,j; if(pos<1 | pos>s.length | len<0 | len>s.length-pos+1) printf("參數(shù)不合法n"); return 0; if(

34、!len)sub.ch=0; sub.length=0; else sub.ch=(char*)malloc(len+1)*sizeof(char); for(i=0,j=pos-1;i<=len-1;i+,j+) sub.chi=s.chj; sub.length=len; return 1; /else int strindex(hstring s,hstring t,int pos)/子串定位 int m,n,i; hstring sub; n=s.length; m=t.length; i=pos; if(m=0) return 0; while(i<=n-m+1) sub

35、string(sub,s,i,m); if(strcompare(sub,t)!=0) +i; else return i; /while return 0; void strcopy(hstring &t,hstring s) /復(fù)制；由串s復(fù)制得串t int i; if(!s.length) t.ch=0; t.length=0; else t.ch=(char*)malloc(s.length+1)*sizeof(char); for(i=0;i<=s.length-1;i+) t.chi=s.chi; /for t.length=s.length; curnum+; /e

36、lse int strempty(hstring s) if(s.length=0) return 1; else return 0; void strreplace(hstring &s,hstring t,hstring v) /將串s中所有子串t替換為v int i,j,k,l; for(i=0;i<=s.length-t.length;i+) for(j=i,k=0;t.chk && k<t.length && s.chj=t.chk;j+,k+); if(k=t.length)/找到了與t匹配的子串：分三種情況處理 if(t.len

37、gth=v.length) for(l=1;l<=t.length;l+)/新子串長度與原子串相同時：直接替換 s.chi+l-1=v.chl-1; else if(t.length<v.length)/新子串長度大于原子串時：先將后部右移 for(l=s.length-1;l>=i+t.length;l-) s.chl+v.length-t.length=s.chl; for(l=1;l<=v.length;l+) s.chi+l-1=v.chl-1; else/新子串長度小于原子串時：先將后部左移 for(l=i+v.length;l<=s.length+v.

38、length-t.length-1;l+) s.chl=s.chl-v.length+t.length; for(l=1;l<=v.length;l+) s.chi+l-1=v.chl-1; s.length=s.length-t.length+v.length; i+=v.length-1; /if /for void strassign() char c; int i; char a20; while(c=getchar()!='n') if(c=''') i=0; while(c=getchar()!=''') ai+

39、=c; headlistcurnum.ch=(char*)malloc(i+1)*sizeof(char); headlistcurnum.length=i; for(i=0;i<headlistcurnum.length;i+) headlistcurnum.chi=ai; curnum+; printf("內(nèi)部名：%d 串值:",curnum-1); for(i=0;i<=headlistcurnum-1.length-1;i+) printf("%c",headlistcurnum-1.chi); printf("n"

40、;); void getin() char c; int i,j=0; while(c=getchar()!='n') if(c>=48&&c<=57) i=0; bi+=c; while(c=getchar()>=48&&c<=57)/還是數(shù)字 bi+=c; bi='0' sj=atoi(b); j+; if(c=''') i=0; while(c=getchar()!=''') ai+=c; headlistcurnum.ch=(char*)malloc(i+1)*sizeof(char); headlistcurnum.length=i; for(i=0;i<headlistcurnum.length;i+) headlistcurnum.chi=ai; sj+=curnum+; void compare() getin(); int j=0; if(s0>=curnum|s1>=curnum) printf(&quo