串基本操作的演示

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

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

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

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

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

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

7、<回車(chē)>,應(yīng)顯示aabaabaabbc。 (7)R Faaaaaaaa aaaa ab,<回車(chē)>,應(yīng)顯示Fabab。二、概要設(shè)計(jì) 實(shí)現(xiàn)串的抽象數(shù)據(jù)類(lèi)型和實(shí)現(xiàn)其基本操作，程序中將涉及下列抽象數(shù)據(jù)類(lèi)型： 1定義串的基本主結(jié)構(gòu) ADT String 數(shù)據(jù)對(duì)象：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類(lèi)型。 操作結(jié)

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

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

10、tgetin(int n) 初始條件：處理命令串S1, 操作結(jié)果：把串值存入串頭表中 ADT String三、詳細(xì)設(shè)計(jì)1、自定義數(shù)據(jù)類(lèi)型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、求長(zhǎng)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：求長(zhǎng)度 n S：求子串 I：子串定位 R：串替換 P:顯示n D：刪除 Q：退出n"); printf("*n"); printf("請(qǐng)輸入命令：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)試分析五、用戶(hù)手冊(cè)1. 本程序的運(yùn)行環(huán)境為DOS操作系統(tǒng)，執(zhí)行文件為：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì).exe.2. 進(jìn)入程序后即會(huì)顯示可以使用的命令和命令用途和對(duì)應(yīng)命令的語(yǔ)法格式的列表，用戶(hù)可以根據(jù)命令列表輸入正確的命令。如果輸入正確就會(huì)顯示相應(yīng)的結(jié)果，接著可以輸入下一條命令。如果輸入錯(cuò)誤，會(huì)顯示相應(yīng)的錯(cuò)誤的原因并提示重新輸入命令。3. 命令是以回車(chē)為結(jié)束的標(biāo)志。4. 本程序只能輸入

28、字符串，且字符串支持空格符，不過(guò)字符串必須用雙單引號(hào)括住。所以Delete命令需要輸入的數(shù)字也必須用雙單引號(hào)括住。但命令Substring并不需要如此，在提示“請(qǐng)輸入子串的開(kāi)始位置:”和“請(qǐng)輸入子串的結(jié)束中位置:”直接輸入數(shù)字即可。5. 命令Subsring在輸出正確結(jié)果后會(huì)接著輸出“此命令不存在！請(qǐng)重新輸入！”此提示，此問(wèn)題一直都沒(méi)有解決，也是該程序的缺陷，但是結(jié)果是正確的。6. 若要退出程序，請(qǐng)鍵入命令：Q。六、測(cè)試結(jié)果 (1)E 命令輸出的結(jié)果為:EQUAL (2)E abc abcd 命令輸出的結(jié)果為:UNEQUAL (3) I a 語(yǔ)法格式錯(cuò)誤！請(qǐng)重新輸入！ (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七、實(shí)驗(yàn)中出現(xiàn)的問(wèn)題、解決方法和心得體會(huì)這個(gè)實(shí)驗(yàn)是對(duì)串的操作的時(shí)間，實(shí)現(xiàn)串操作的基本函數(shù)，在接受命令的輸入格式方面，試了很多種方法。開(kāi)始時(shí)嘗試過(guò)用getchar（）函數(shù)來(lái)接收命令，并根據(jù)接受到的指令進(jìn)行操作。在調(diào)試程序的過(guò)程中，遇到一些結(jié)果不正確或超出范圍的情況，又要重新返回相應(yīng)的函數(shù)進(jìn)行檢查和修改補(bǔ)充，才能使程序更加健壯和完整，才

30、能做出一個(gè)更加實(shí)用的軟件八、附錄源程序#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個(gè)字符起長(zhǎng)度為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+)/新子串長(zhǎng)度與原子串相同時(shí)：直接替換 s.chi+l-1=v.chl-1; else if(t.length<v.length)/新子串長(zhǎng)度大于原子串時(shí)：先將后部右移 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/新子串長(zhǎng)度小于原子串時(shí)：先將后部左移 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