1、3.4串的基本操作演示一、 需求分析 1用堆分配存儲表示實現Hstring 串類型的最小操作子集。 2實現串抽象類型的其余基本操作（如聯接、刪除等），且不能使用c語言本身提供的串函數，必須自己構造新的函數實現串的基本操作。 3本演示系統是一個命令解釋程序，循環往復的處理用戶輸入的每一條命令，直至終止程序的命令為止。 4參數的合法性必須嚴格檢查，要嚴格按照命令的輸入格式進行輸入，否則程序可能無法正確執行指令。二、概要設計 實現串的抽象數據類型和實現其基本操作，程序中將涉及下列抽象數據類型： 1定義串的基本主結構 ADT String 數據對象：D=ai| aicharcaterset,i=1,2

2、,n,n>=0 數據關系：R1=<ai-1,ai>|ai-1,aiD, i=1,2,n 基本操作： StrCompare(HString S,HString T) 初始條件：S和T是已存在的Hstring類型。 操作結果：比較其值，顯示結果“UNEQUAL”或“EQUAL”。 StrLength(HString S) 初始條件：S是已存在的Hstring類型。 操作結果：返回該串的長度。 Concat(HString S1,HString S2) 初始條件：S1和S2是已存在的Hstring類型。 操作結果：由S1和S2聯接成新串。 Index(HString S,HStri

3、ng t) 初始條件：S和T是已存在的Hstring類型。 操作結果：顯示第二個串在第一個串中首次出現的起始位置。 Replace(HString M, HString t, HString v) 初始條件：M、t和v是已存在的Hstring類型。 操作結果：將第一個串中所有出現的第二個串用第三個串替換，顯示結果串的內部名和串值，原串不變。 SubString(HString S,int pos,int len) 初始條件：S是已存在的Hstring類型。 操作結果：如果參數合法，則顯示子串的內部名和串值 。 Strprint(HString S) 初始條件：S是已存在的Hstring類型。

4、操作結果：顯示串S的內部名和串值 。 getin(int n) 初始條件：處理命令串S1, 操作結果：把串值存入串頭表中 Insert(int n) 初始條件：要給指定的串賦值,n為指定的串的內部名 操作結果：為指定內部名的串賦值 show() 初始條件：要求查看輸入格式 操作結果：輸出各種命令的輸入格式ADT String二存儲結構及相應的類型定義公用頭文件header.h#include <conio.h>#include <stdio.h>#include <stdlib.h>#include <string.h>#include <

5、ctype.h>#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -2#define MAXLEN 100#define MAXSIZE 50typedef int Status;（1）順序存儲結構typedef struct ResultType int CmdNo; /命令號或命令符int s3; /命令的串參數的內部名（最多3） int num2; /命令的數值參數（最多2個）ResultType,*Result ; typedef struct char * ch; /若為非空串，則按

6、串長分配存儲區，否則ch為NULLint length; /串長度int state; /狀態量HString,*String;typedef struct HString StrHead100; /串頭數組 int CurNum; /系統中現有的串的數目StrHeadList,*StrHead; 三、詳細設計 void StrCompare(HString S,HString T) /比較兩串的串值，顯示結果“UNEQUAL”或“EQUAL” int i; if(S.length!=T.length) /先判長度是否相等，若不相等則顯示“UNEQUAL” printf("“UNEQ

7、UAL”n");return; else for(i=0;i<S.length &&i<T.length;i+) /比較兩串的串值，遇到不等就顯示“UNEQUAL” if(S.chi!=T.chi) printf("“UNEQUAL”n");return; printf("“EQUAL”n"); /比較完后，相等則顯示“EQUAL”void Concat(HString S1,HString S2) /由S1和S2聯接成新串int i,j; j=KK->CurNum+; /為串頭指針分配位置，申請(S1.len

8、gth+S2.length)大小空間 if(KK->StrHeadj.ch=(char*)malloc(S1.length+S2.length) *sizeof(char)=NULL) exit(OVERFLOW); for(i=0;i<S1.length;i+) /先將串S1內容復制到新串 KK->StrHeadj.chi=S1.chi; for(i=0;i<S2.length;i+)/將串S2容復制到新串 KK->StrHeadj.chS1.length+i=S2.chi; KK->StrHeadj.length=S1.length+S2.length;

9、 /(S1.length+S2.length)賦值給新串 printf("結果串的內部名和串值為：n");/顯示結果串名和串值 printf("%5d",j); printf("%c",' '); printf("'"); for(i=0;i<KK->StrHeadj.length;i+) printf("%c",KK->StrHeadj.chi); printf("'"); printf("n"); in

10、t StrLength(HString S)/返回S串的長度 return S.length;void Strprint(HString S) int i; printf("%c",' '); printf("'"); for(i=0;i<S.length;i+) /輸出串值printf("%c",S.chi); printf("'"); printf("n"); Status SubString(HString S,int pos,int len)/求串S

11、的子串int i,n; n=KK->CurNum+;/為串頭指針分配位置 if(pos<0|pos>S.length|len<0|len>S.length-pos+1)/判斷參數是否合法 printf("ERROR: 參數不合法n"); return ERROR; if(!len) /當子串長度為空 KK->StrHeadn.ch=NULL; KK->StrHeadn.length=0; else /申請len長度的空間存儲新串 KK->StrHeadn.ch=(char *)malloc(len *sizeof(char);

12、 for(i=0;i<=len-1;i+) KK->StrHeadn.chi=S.chpos-1+i; KK->StrHeadn.length=len; printf("子串的內部名和串值為：n");/顯示新串的內部名和串值 printf("%5d",n); Strprint(KK->StrHeadn); printf("n");return OK;Status Index(HString S,HString t) /顯示第二個串在第一個串中首次出現的起始位置 int m,i,j; if(t.length=0)

13、/若t串的長度為0，則參數非法 printf("參數非法n"); else for(i=0;i<=S.length-t.length+1;i+)/查找第二個串在第一個串中首次出現的起始位置for(j=i,m=0;m<t.length&&S.chj=t.chm;m+,j+); if(m=t.length) printf("第二個串在第一個串中首次出現的起始位置：n"); printf("%dn",i+1); return OK; if(i>=0) printf("該位置不存在n");

14、/若找不到 return ERROR;Status Replace(HString M, HString t, HString v)/將第一個串中所有出現的第二個串用第三個串替換，顯示結果串的內部名和串值，原串不變。int i,j,m,n,k,y=0; n=KK->CurNum+;/為串頭指針分配位置 if(M.length<0) return ERROR;/判斷 if(KK->StrHeadn.ch=(char*)malloc(M.length)*sizeof(char)=NULL) exit(OVERFLOW);/申請空間 for(i=0;i<M.length;i+

15、)/先將串M的值賦給新串 KK->StrHeadn.chi=M.chi; KK->StrHeadn.length=M.length; for(i=0;i<=KK->StrHeadn.length-t.length;i+)/新串與串t比較 for(j=i,m=0;m<t.length&&KK->StrHeadn.chj=t.chm;m+,j+); if(m=t.length)/在新串中找到和串t相等的子串 y=1; if(t.length>v.length)/串t的長度大于串v，修改新串內容 for(k=i,m=0;m<v.leng

16、th;k+,m+) KK->StrHeadn.chk=v.chm; for(k=i+v.length;k<KK->StrHeadn.length-t.length+v.length;k+) KK->StrHeadn.chk=KK->StrHeadn.chk-v.length+t.length; else if(t.length=v.length) /串t的長度等于串v，修改新串內容 for(j=i,m=0;m<v.length;m+,j+) KK->StrHeadn.chj=v.chm; else /串t的長度小于串v，修改新串內容if(KK->

17、StrHeadn.ch=(char*)realloc(KK->StrHeadn.ch,(KK->StrHeadn.length-t.length+v.length) *sizeof(char)=NULL) exit(OVERFLOW); for(k=KK->StrHeadn.length-t.length+v.length-1,m=KK->StrHeadn.length-1;k>=v.length+i;k-,m-) KK->StrHeadn.chk=KK->StrHeadn.chm; for(k=v.length+i-1,m=v.length-1;m&

18、gt;=0;k-,m-) KK->StrHeadn.chk=v.chm; KK->StrHeadn.length+=v.length-t.length; i=i+v.length-1; printf("結果串的內部名和串值為：n");/顯示新串內容 printf("%5d",n); Strprint(KK->StrHeadn); printf("n"); if(y=1) return TRUE; else return FALSE; void show()/命令輸入格式printf("輸入格式如下：n&qu

19、ot;); printf("(1)賦值。 格式例子：A 'hello'<enter>n"); printf("(2)判相等。 格式例子：E 'hello' 'hi' <enter>或只輸入E<enter>然后根據提示操作。n"); printf("(3)聯接。 格式例子：C 'hello' 'hi' <enter>或只輸入C<enter>然后根據提示操作。n"); printf("(4)

20、求長度。 格式例子：L 'hello' <enter>或只輸入L<enter>然后根據提示操作。n"); printf("(5)求子串。 格式例子：S 'hello'<enter>然后根據提示操作或只輸入E<enter>提示操作.n"); printf("(6)子串定位。格式例子：I 'hello' 'll' <enter>或只輸入I<enter>然后根據提示操作。n"); printf("(7)串替

21、換。 格式例子：R 'hello' 'll' 'hli'<enter>或只輸入R<enter>然后根據提示操作。n"); printf("(8)顯示。格式例子：只輸入P<enter>然后根據提示操作。 n"); printf("(9)刪除。格式例子：只輸入D<enter>然后根據提示操作。 n"); printf("(Q)退出。 格式例子：只輸入Q<enter>然后根據提示操作。 n");Status Insert(i

22、nt n) /為指定內部名的串賦值int i,j,k=0; char s250; if(sk=''') i=0; k+; while(sk!=''') s2i+=sk+; else printf("格式輸入錯誤！n");return ERROR; if(KK->StrHeadn.ch) KK->StrHeadn.ch=NULL; KK->StrHeadn.length=0; KK->StrHeadn.state=0; if(!(KK->StrHeadn.ch=(char *)malloc(i*si

23、zeof (char) exit(OVERFLOW); KK->StrHeadn.length=i; KK->StrHeadn.state=1; for(j=0;j<=i;j+) KK->StrHeadn.chj=s2j; return OK; void getin(int n) /處理命令串，n為要存入的串內部名int i,j; while(s1m=' ') m+; /s1為從鍵盤接收到的字符串，s1,m為局部變量，在getorder（）函數內有效，減少需要傳遞的參數 if(s1m=''') i=0; m+; while(s1m

24、!=''') si+=s1m+; if(!(KK->StrHeadn.ch=(char *)malloc(i*sizeof (char) exit(OVERFLOW); KK->StrHeadn.length=i; for(j=0;j<=i;j+) KK->StrHeadn.chj=sj; /將命令中的串值存入相應的串頭表函數的調用關系圖（只列出部分） endmainInitilizationgetorder() Getin()StrCompare()SubString()Concat()Index()Replace () Exit()四、調試分

25、析#include"header.h" StrHead KK; /定義StrHead類型的全局變量void main() char c; int i; Result p; Status InitResult(Result p); /命令分析函數的初始化 Status getorder(Result p); /命令處理函數void getin(int n); /命令串處理函數 void Strprint(); /輸出串值 void show(); /顯示輸入格式 void StrCompare(HString S,HString T); /串比較函數 void Concat(

26、HString S1,HString S2); /串聯接函數 int StrLength(HString S); /取串長度 Status SubString(HString S,int pos,int len); /取子串 Status Replace(HString M, HString t, HString v); /子串替換 Status Index(HString S,HString T); /子串定位Status Insert(int n) /為指定內部名的串賦值 KK=(StrHead )malloc(sizeof(StrHeadList); /申請空間for(i=0;i<

27、=100;i+) KK->StrHeadi.ch=NULL; KK->StrHeadi.length=0; KK->StrHeadi.state=0; KK->CurNum=0; p=(Result )malloc(sizeof(ResultType); /申請空間 do printf("*n"); printf("* 串的基本操作演示系統 *n"); printf("* A.進入系統 *n"); printf("* B.輸入格式 *n"); printf("* C.退出系統 *n

28、"); printf("*n");scanf("%c",&c);getchar();switch(c)case'A':InitResult(p);getorder(p);break; case'B': show();break; case'C': break; default: printf("輸入錯誤，請重新輸入！n"); break; while(c!='C'); char s1100,s50; /定義局部變量int m; /定義局部變量Status

29、 getorder(Result p) char s1100,s50; int i,j,n,m; do printf("請輸入指令：n"); gets(s1); m=0; switch(s1m) /判斷指令類型 case'A':while(KK->StrHeadKK->CurNum.state=1) KK->CurNum+; p->s0=KK->CurNum+; m+; getin(p->s0); /將串值賦入串頭表中 printf("新串的內部名和串值為：n"); printf("%5d&q

30、uot;,p->s0); Strprint(KK->StrHeadp->s0); /回顯新串 break case 'E': m+; /串比較 if(s1m='0') /比較內部已保存的串 printf("輸入第一個串的內部名：n"); scanf("%d",&p->s0);getchar(); printf("輸入第一個串的內部名：n"); scanf("%d",&p->s1);getchar(); if(p->s0<0|p

31、->s0>=KK->CurNum|p->s1<0|p->s1>=KK->CurNum)printf("超出當前串的范圍n");elseStrCompare(KK->StrHeadp->s0,KK->StrHeadp->s1); else while(KK->StrHeadKK->CurNum.state=1) KK->CurNum+; p->s0=KK->CurNum+;while(KK->StrHeadKK->CurNum.state=1) KK->Cu

32、rNum+; p->s1=KK->CurNum+; getin( p->s0); m+; getin(p->s1); StrCompare(KK->StrHeadp->s0,KK->StrHeadp->s1); break; case 'C': m+; /串聯接 if(s1m='0') /聯接內部已存在的串 printf("輸入第一個串的內部名：n"); scanf("%d",&p->s0);getchar(); printf("輸入第二個串的內部名：

33、n"); scanf("%d",&p->s1);getchar();if(p->s0<0|p->s0>=KK->CurNum|p->s1<0|p->s1>=KK->CurNum)printf("超出當前串的范圍n");elseConcat(KK->StrHeadp->s0,KK->StrHeadp->s1); else while(KK->StrHeadKK->CurNum.state=1) KK->CurNum+; p->

34、s0=KK->CurNum+; while(KK->StrHeadKK->CurNum.state=1) KK->CurNum+; p->s1=KK->CurNum+; getin( p->s0); m+; getin(p->s1); Concat(KK->StrHeadp->s0,KK->StrHeadp->s1); break; case 'L': m+; /求長度 if(s1m='0') /求內部已存在的串長度printf("輸入第一個串的內部名：n"); scan

35、f("%d",&p->s0); getchar(); if(p->s0<0|p->s0>=KK->CurNum)printf("超出當前串的范圍n"); else j=StrLength(KK->StrHeadp->s0); printf("串長度為：%dn",j); else /求新輸入的串長度 while(KK->StrHeadKK->CurNum.state=1) KK->CurNum+; p->s0=KK->CurNum+; getin( p

36、->s0); j=StrLength(KK->StrHeadp->s0); printf("串長度為：%dn",j); break; case 'S': m+; if(s1m='0') /求內部已存在的串的子串printf("輸入第一個串的內部名：n"); scanf("%d",&p->s0); getchar(); if(p->s0<0|p->s0>=KK->CurNum) printf("超出當前串的范圍n"); el

37、se printf("請輸入pos位置：n"); scanf("%d",&p->num0); getchar(); printf("請輸入len長度：n"); scanf("%d",&p->num1); getchar(); SubString(KK->StrHeadp->s0,p->num0,p->num1); else while(KK->StrHeadKK->CurNum.state=1) KK->CurNum+; p->s0=KK-

38、>CurNum+; getin( p->s0); printf("請輸入pos位置：n"); scanf("%d",&p->num0); getchar(); printf("請輸入len長度：n"); scanf("%d",&p->num1); getchar(); SubString(KK->StrHeadp->s0,p->num0,p->num1); break; case 'I': m+; /子串定位 if(s1m='0

39、') /求內部已存在的串的子串的位置 printf("輸入第一個串的內部名：n"); scanf("%d",&p->s0); getchar(); printf("輸入第二個串的內部名：n"); scanf("%d",&p->s1); getchar(); if(p->s0<0|p->s0>=KK->CurNum|p->s1<0|p->s1>=KK->CurNum)printf("超出當前串的范圍n"

40、); else Index(KK->StrHeadp->s0,KK->StrHeadp->s1); else while(KK->StrHeadKK->CurNum.state=1) KK->CurNum+; /求新輸入的串的子串的位置 p->s0=KK->CurNum+;while(KK->StrHeadKK->CurNum.state=1) KK->CurNum+; p->s1=KK->CurNum+; getin( p->s0); m+; getin(p->s1); Index(KK->

41、StrHeadp->s0,KK->StrHeadp->s1); break; case 'R': m+; / /替換串 if(s1m='0') /求內部已存在的串的替換 printf("輸入第一個串的內部名：n"); scanf("%d",&p->s0); getchar(); printf("輸入第二個串的內部名：n"); scanf("%d",&p->s1); getchar(); printf("輸入第三個串的內部名：n&

42、quot;); scanf("%d",&p->s2); getchar(); if(p->s0<0|p->s0>=KK->CurNum|p->s1<0|p->s1>=KK->CurNum|p->s2<0|p->s2>=KK->CurNum)printf("超出當前串的范圍n"); else Replace(KK->StrHeadp->s0,KK->StrHeadp->s1, KK->StrHeadp->s2); el

43、se while(KK->StrHeadKK->CurNum.state=1)KK->CurNum+; p->s0=KK->CurNum+;while(KK->StrHeadKK->CurNum.state=1) KK->CurNum+; p->s1=KK->CurNum+; while(KK->StrHeadKK->CurNum.state=1) KK->CurNum+; p->s2=KK->CurNum+; getin(p->s0); m+; getin(p->s1); m+; getin

44、(p->s2); Replace(KK->StrHeadp->s0,KK->StrHeadp->s1, KK->StrHeadp->s2); break; case 'P': printf("所有串的內部名和串值為：n");/顯示所有保留的串 for(i=0;i<100;i+) if(KK->StrHeadi.ch!=NULL) printf("%5d",i); Strprint(KK->StrHeadi) ; break; case 'D': printf(&q

45、uot;請輸入要刪除的串的內部名：n"); /刪除串 scanf("%d",&p->num0); getchar(); if(p->num0<0|p->num0>=KK->CurNum) printf("無此串！n"); else printf("刪除的串名和串值為：n"); printf("%5d",p->num0); printf("%c",' '); Strprint(KK->StrHeadp->num

46、0); KK->StrHeadp->num0.ch=NULL; KK->StrHeadp->num0.length=0; break; case 'W': printf("請輸入要賦值的串的內部名和串值（以空格隔開）：n"); scanf("%d%s",&p->num0,s); getchar(); if(p->num0<0|p->num0>=100) printf("無此串！n"); else Insert(p->num0); printf(&quo

47、t;新串的內部名和串值為：n"); printf("%5d",p->num0); Strprint(KK->StrHeadp->num0); break; case 'Q': break; default: printf("輸入錯誤！可返回上一界面查看輸入格式n"); while(s10!='Q'); return OK;（2） 測試數據： 賦值：A hello<enter> A nice to meet you! <enter> A too <enter>

48、顯示：P<enter> /回顯剛才輸入的三條語句 判相等：E 'hello' 'hi' <enter>或只輸入E<enter>然后根據提示操作 聯接： C 'hello' 'hi' <enter>或只輸入C<enter>然后根據提示操作 求長度：L 'hello' <enter>或只輸入L<enter>然后根據提示操作 求子串：S 'hello'<enter>然后根據提示操作或只輸入E<enter&

49、gt;提示操作. 子串定位：I 'hello' 'll' <enter>或只輸入I<enter>然后根據提示操作 刪除：輸入D<enter>然后根據提示操作 Eg. E <enter>,顯示“EQUAL” E dad <enter>,顯示“UNEQUAL” C <enter>,顯示 C hello, nice to meet you <enter>,顯示hello,nice to meet you I a <enter>,應報告：參數非法 I hello ll <

50、;enter>,顯示:3 S hello <enter>,然后根據提示輸入pos和len的值 R aaa aa b <enter>,顯示: ba R aaabc a aab <enter>,顯示: aabaabaabbcR aaaaaaaa aaaa ab <enter>,顯示: abab五、用戶手冊1本程序的運行環境為DOS操作系統，執行文件為project.exe。2進入程序后即顯示用戶歡迎界面，用戶可根據文字提示進行操作，本程序有兩種命令輸入格式（如E 'hello' 'hi' <enter>或只輸入E<enter>然后根據提示操作）