數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 串的基本操作演示

1、3.4串的基本操作演示一、 需求分析 1用堆分配存儲(chǔ)表示實(shí)現(xiàn)Hstring 串類(lèi)型的最小操作子集。 2實(shí)現(xiàn)串抽象類(lèi)型的其余基本操作（如聯(lián)接、刪除等），且不能使用c語(yǔ)言本身提供的串函數(shù)，必須自己構(gòu)造新的函數(shù)實(shí)現(xiàn)串的基本操作。 3本演示系統(tǒng)是一個(gè)命令解釋程序，循環(huán)往復(fù)的處理用戶輸入的每一條命令，直至終止程序的命令為止。 4參數(shù)的合法性必須嚴(yán)格檢查，要嚴(yán)格按照命令的輸入格式進(jìn)行輸入，否則程序可能無(wú)法正確執(zhí)行指令。二、概要設(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

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

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

4、操作結(jié)果：顯示串S的內(nèi)部名和串值 。 getin(int n) 初始條件：處理命令串S1, 操作結(jié)果：把串值存入串頭表中 Insert(int n) 初始條件：要給指定的串賦值,n為指定的串的內(nèi)部名 操作結(jié)果：為指定內(nèi)部名的串賦值 show() 初始條件：要求查看輸入格式 操作結(jié)果：輸出各種命令的輸入格式ADT String二存儲(chǔ)結(jié)構(gòu)及相應(yīng)的類(lèi)型定義公用頭文件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）順序存儲(chǔ)結(jié)構(gòu)typedef struct ResultType int CmdNo; /命令號(hào)或命令符int s3; /命令的串參數(shù)的內(nèi)部名（最多3） int num2; /命令的數(shù)值參數(shù)（最多2個(gè)）ResultType,*Result ; typedef struct char * ch; /若為非空串，則按

6、串長(zhǎng)分配存儲(chǔ)區(qū)，否則ch為NULLint length; /串長(zhǎng)度int state; /狀態(tài)量HString,*String;typedef struct HString StrHead100; /串頭數(shù)組 int CurNum; /系統(tǒng)中現(xiàn)有的串的數(shù)目StrHeadList,*StrHead; 三、詳細(xì)設(shè)計(jì) void StrCompare(HString S,HString T) /比較兩串的串值，顯示結(jié)果“UNEQUAL”或“EQUAL” int i; if(S.length!=T.length) /先判長(zhǎng)度是否相等，若不相等則顯示“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聯(lián)接成新串int i,j; j=KK->CurNum+; /為串頭指針?lè)峙湮恢?，申?qǐng)(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內(nèi)容復(fù)制到新串 KK->StrHeadj.chi=S1.chi; for(i=0;i<S2.length;i+)/將串S2容復(fù)制到新串 KK->StrHeadj.chS1.length+i=S2.chi; KK->StrHeadj.length=S1.length+S2.length;

9、 /(S1.length+S2.length)賦值給新串 printf("結(jié)果串的內(nèi)部名和串值為：n");/顯示結(jié)果串名和串值 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串的長(zhǎng)度 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+;/為串頭指針?lè)峙湮恢?if(pos<0|pos>S.length|len<0|len>S.length-pos+1)/判斷參數(shù)是否合法 printf("ERROR: 參數(shù)不合法n"); return ERROR; if(!len) /當(dāng)子串長(zhǎng)度為空 KK->StrHeadn.ch=NULL; KK->StrHeadn.length=0; else /申請(qǐng)len長(zhǎng)度的空間存儲(chǔ)新串 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èi)部名和串值為：n");/顯示新串的內(nèi)部名和串值 printf("%5d",n); Strprint(KK->StrHeadn); printf("n");return OK;Status Index(HString S,HString t) /顯示第二個(gè)串在第一個(gè)串中首次出現(xiàn)的起始位置 int m,i,j; if(t.length=0)

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

14、/若找不到 return ERROR;Status Replace(HString M, HString t, HString v)/將第一個(gè)串中所有出現(xiàn)的第二個(gè)串用第三個(gè)串替換，顯示結(jié)果串的內(nèi)部名和串值，原串不變。int i,j,m,n,k,y=0; n=KK->CurNum+;/為串頭指針?lè)峙湮恢?if(M.length<0) return ERROR;/判斷 if(KK->StrHeadn.ch=(char*)malloc(M.length)*sizeof(char)=NULL) exit(OVERFLOW);/申請(qǐng)空間 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的長(zhǎng)度大于串v，修改新串內(nèi)容 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的長(zhǎng)度等于串v，修改新串內(nèi)容 for(j=i,m=0;m<v.length;m+,j+) KK->StrHeadn.chj=v.chm; else /串t的長(zhǎng)度小于串v，修改新串內(nèi)容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("結(jié)果串的內(nèi)部名和串值為：n");/顯示新串內(nèi)容 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>然后根據(jù)提示操作。n"); printf("(3)聯(lián)接。 格式例子：C 'hello' 'hi' <enter>或只輸入C<enter>然后根據(jù)提示操作。n"); printf("(4)

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

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

22、nt n) /為指定內(nèi)部名的串賦值int i,j,k=0; char s250; if(sk=''') i=0; k+; while(sk!=''') s2i+=sk+; else printf("格式輸入錯(cuò)誤！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為要存入的串內(nèi)部名int i,j; while(s1m=' ') m+; /s1為從鍵盤(pán)接收到的字符串，s1,m為局部變量，在getorder（）函數(shù)內(nèi)有效，減少需要傳遞的參數(shù) 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; /將命令中的串值存入相應(yīng)的串頭表函數(shù)的調(diào)用關(guān)系圖（只列出部分） endmainInitilizationgetorder() Getin()StrCompare()SubString()Concat()Index()Replace () Exit()四、調(diào)試分

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

26、HString S1,HString S2); /串聯(lián)接函數(shù) int StrLength(HString S); /取串長(zhǎng)度 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) /為指定內(nèi)部名的串賦值 KK=(StrHead )malloc(sizeof(StrHeadList); /申請(qǐng)空間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); /申請(qǐng)空間 do printf("*n"); printf("* 串的基本操作演示系統(tǒng) *n"); printf("* A.進(jìn)入系統(tǒng) *n"); printf("* B.輸入格式 *n"); printf("* C.退出系統(tǒng) *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("輸入錯(cuò)誤，請(qǐng)重新輸入！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("請(qǐng)輸入指令：n"); gets(s1); m=0; switch(s1m) /判斷指令類(lèi)型 case'A':while(KK->StrHeadKK->CurNum.state=1) KK->CurNum+; p->s0=KK->CurNum+; m+; getin(p->s0); /將串值賦入串頭表中 printf("新串的內(nèi)部名和串值為：n"); printf("%5d&q

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

31、->s0>=KK->CurNum|p->s1<0|p->s1>=KK->CurNum)printf("超出當(dāng)前串的范圍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+; /串聯(lián)接 if(s1m='0') /聯(lián)接內(nèi)部已存在的串 printf("輸入第一個(gè)串的內(nèi)部名：n"); scanf("%d",&p->s0);getchar(); printf("輸入第二個(gè)串的內(nèi)部名：

33、n"); scanf("%d",&p->s1);getchar();if(p->s0<0|p->s0>=KK->CurNum|p->s1<0|p->s1>=KK->CurNum)printf("超出當(dāng)前串的范圍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+; /求長(zhǎng)度 if(s1m='0') /求內(nèi)部已存在的串長(zhǎng)度printf("輸入第一個(gè)串的內(nèi)部名：n"); scan

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

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

37、se printf("請(qǐng)輸入pos位置：n"); scanf("%d",&p->num0); getchar(); printf("請(qǐng)輸入len長(zhǎng)度：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("請(qǐng)輸入pos位置：n"); scanf("%d",&p->num0); getchar(); printf("請(qǐng)輸入len長(zhǎng)度：n"); scanf("%d",&p->num1); getchar(); SubString(KK->StrHeadp->s0,p->num0,p->num1); break; case 'I': m+; /子串定位 if(s1m='0

39、') /求內(nèi)部已存在的串的子串的位置 printf("輸入第一個(gè)串的內(nèi)部名：n"); scanf("%d",&p->s0); getchar(); printf("輸入第二個(gè)串的內(nèi)部名：n"); scanf("%d",&p->s1); getchar(); if(p->s0<0|p->s0>=KK->CurNum|p->s1<0|p->s1>=KK->CurNum)printf("超出當(dāng)前串的范圍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') /求內(nèi)部已存在的串的替換 printf("輸入第一個(gè)串的內(nèi)部名：n"); scanf("%d",&p->s0); getchar(); printf("輸入第二個(gè)串的內(nèi)部名：n"); scanf("%d",&p->s1); getchar(); printf("輸入第三個(gè)串的內(nèi)部名：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("超出當(dāng)前串的范圍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èi)部名和串值為：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;請(qǐng)輸入要?jiǎng)h除的串的內(nèi)部名：n"); /刪除串 scanf("%d",&p->num0); getchar(); if(p->num0<0|p->num0>=KK->CurNum) printf("無(wú)此串！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("請(qǐng)輸入要賦值的串的內(nèi)部名和串值（以空格隔開(kāi)）：n"); scanf("%d%s",&p->num0,s); getchar(); if(p->num0<0|p->num0>=100) printf("無(wú)此串！n"); else Insert(p->num0); printf(&quo

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

48、顯示：P<enter> /回顯剛才輸入的三條語(yǔ)句 判相等：E 'hello' 'hi' <enter>或只輸入E<enter>然后根據(jù)提示操作 聯(lián)接： C 'hello' 'hi' <enter>或只輸入C<enter>然后根據(jù)提示操作 求長(zhǎng)度：L 'hello' <enter>或只輸入L<enter>然后根據(jù)提示操作 求子串：S 'hello'<enter>然后根據(jù)提示操作或只輸入E<enter&

49、gt;提示操作. 子串定位：I 'hello' 'll' <enter>或只輸入I<enter>然后根據(jù)提示操作 刪除：輸入D<enter>然后根據(jù)提示操作 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>,應(yīng)報(bào)告：參數(shù)非法 I hello ll <

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