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

1、 根據(jù)提示操作。n);printf(5)求子串。格式例子：Shelloventerprintf(5)求子串。Eventer提示操作.n);printf(6)子串定位。格式例子：Ihellollventer或只輸入Iventer然后根據(jù)提示操作。n);printf(7)串替換。格式例子：Rhellollhliventer或只輸入Rventer然后根據(jù)提示操作。n);printf(8)顯示。格式例子：只輸入Pventer然后根據(jù)提示操作。n);printf(9)刪除。格式例子：只輸入Dventer然后根據(jù)提示操作。StatusInsert(intn)/StatusInsert(intn)/為指定內(nèi)

2、部名的串賦值n);printf(Q)退出。格式例子：只輸入Qventer然后根據(jù)提示操作。n);inti,j,k=0;chars250;if(sk=)i=0;k+;while(sk!=)s2i+=sk+;elseprintf(格式輸入錯誤！n);returnERROR;if(KK-StrHeadn.ch)KK-StrHeadn.ch=NULL;KK-StrHeadn.length=0;KK-StrHeadn.state=0;if(!(KK-StrHeadn.ch=(char*)malloc(i*sizeof(char)exit(OVERFLOW);KK-StrHeadn.length=i;KK

3、-StrHeadn.state=1;for(j=0;jStrHeadn.chj=s2j;returnOK;voidgetin(intn)處理命令串，n為要存入的串內(nèi)部名inti,j;while(s1m=)m+;/s1為從鍵盤接收到的字符串，s1,m為局部變量，在getorder()函數(shù)內(nèi)有效，減少需要傳遞的參數(shù)if(s1m=)i=0;m+;while(s1m!=)si+=s1m+;if(!(KK-StrHeadn.ch=(char*)malloc(i*sizeof(char)exit(OVERFLOW);KK-StrHeadn.length=i;for(j=0;jStrHeadn.chj=sj

4、;/將命令中的串值存入相應(yīng)的串頭表函數(shù)的調(diào)用關(guān)系圖(只列出部分)四、調(diào)試分析#includeheader.hStrHeadKK;voidmain()charc;inti;四、調(diào)試分析#includeheader.hStrHeadKK;voidmain()charc;inti;/定義StrHead類型的全局變量Resultp;StatusInitResult(Resultp);Statusgetorder(Resultp);voidgetin(intn);voidStrprint();voidshow();/命令分析函數(shù)的初始化/命令處理函數(shù)/命令串處理函數(shù)/輸出串值/顯示輸入格式voidStr

5、Compare(HStringS,HStringT);/串比較函數(shù)voidConcat(HStringS1,HStringS2);/串聯(lián)接函數(shù)intStrLength(HStringS);/取串長度StatusSubString(HStringS,intpos,intlen);/取子串StatusReplace(HStringM,HStringt,HStringv);/子串替換StatusIndex(HStringS,HStringT);/子串定位StatusInsert(intn)/為指定內(nèi)部名的串賦值KK=(StrHead)malloc(sizeof(StrHeadList);/申請空間f

6、or(i=0;iStrHeadi.ch=NULL;KK-StrHeadi.length=0;KK-StrHeadi.state=0;printf(*串的基本操作演示系統(tǒng)*n);printf(*A.進(jìn)入系統(tǒng)*n);printf(*B.輸入格式*n);printf(*C.退出系統(tǒng)*n);/申請空間/申請空間/scanf(%c,&c);getchar();switch(c)caseA:InitResult(p);getorder(p);break;caseB:show();break;caseC:break;default:printf(輸入錯誤，請重新輸入！n);break;while(c!=C)

7、;chars1100,s50;/定義局部變量intm;/定義局部變量Statusgetorder(Resultp)chars1100,s50;inti,j,n,m;doprintf(請輸入指令：n);gets(s1);m=0;switch(s1m)/判斷指令類型KK-CurNum+;caseA:while(KK-StrHeadKK-CurNum.state=1)KK-CurNum+;p-s0=KK-CurNum+;m+;getin(p-s0);/將串值賦入串頭表中printf(噺串的內(nèi)部名和串值為：n);printf(%5d,p-s0);Strprint(KK-StrHeadp-s0);/回顯

8、新串breakcaseE:m+;/串比較if(s1m=0)/比較內(nèi)部已保存的串printf(輸入第一個串的內(nèi)部名：n);scanf(%d,&p-s0);getchar();printf(輸入第一個串的內(nèi)部名：n);scanf(%d,&p-s1);getchar();if(p-s0s0=KK-CurNum|p-s1s1=KK-CurNum)printf(超出當(dāng)前串的范圍n);elseStrCompare(KK-StrHeadp-s0,KK-StrHeadp-s1);elsewhile(KK-StrHeadKK-CurNum.state=1)KK-CurNum+;p-s0=KK-CurNum+;w

9、hile(KK-StrHeadKK-CurNum.state=1)KK-CurNum+;p-s1=KK-CurNum+;getin(p-s0);m+;getin(p-s1);StrCompare(KK-StrHeadp-s0,KK-StrHeadp-s1);break;caseC:m+;/串聯(lián)接if(s1m=0)/聯(lián)接內(nèi)部已存在的串printf(輸入第一個串的內(nèi)部名：n);scanf(%d,&p-s0);getchar();printf(輸入第二個串的內(nèi)部名：n);scanf(%d,&p-s1);getchar();if(p-s0s0=KK-CurNum|p-s1s1=KK-CurNum)pr

10、intf(超出當(dāng)前串的范圍n);elseConcat(KK-StrHeadp-s0,KK-StrHeadp-s1);elsewhile(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);Concat(KK-StrHeadp-s0,KK-StrHeadp-s1);break;caseL:m+;/求長度if(s1m=0)/求內(nèi)部已存在的串長度printf(輸入第一個

11、串的內(nèi)部名：n);scanf(%d,&p-s0);getchar();if(p-s0s0=KK-CurNum)printf(超出當(dāng)前串的范圍n);elsej=StrLength(KK-StrHeadp-s0);printf(串長度為：dn,j);else/求新輸入的串長度while(KK-StrHeadKK-CurNum.state=1)KK-CurNum+;p-s0=KK-CurNum+;getin(p-s0);j=StrLength(KK-StrHeadp-s0);printf(串長度為：%dn,j);break;caseS:m+;if(s1m=0)/求內(nèi)部已存在的串的子串printf(輸

12、入第一個串的內(nèi)部名：n);scanf(%d,&p-s0);getchar();if(p-s0s0=KK-CurNum)printf(超出當(dāng)前串的范圍n);elseprintf(請輸入pos位置：n);scanf(%d,&p-num0);getchar();printf(請輸入len長度：n);scanf(%d,&p-num1);getchar();SubString(KK-StrHeadp-s0,p-num0,p-num1);elsewhile(KK-StrHeadKK-CurNum.state=1)KK-CurNum+;p-s0=KK-CurNum+;getin(p-s0);printf(請

13、輸入pos位置：n);scanf(%d,&p-num0);getchar();printf(請輸入len長度：n);scanf(%d,&p-num1);getchar();SubString(KK-StrHeadp-s0,p-num0,p-num1);break;caseI:m+;/子串定位if(s1m=0)/求內(nèi)部已存在的串的子串的位置printf(輸入第一個串的內(nèi)部名：n);scanf(%d,&p-s0);getchar();printf(“輸入第二個串的內(nèi)部名：n);scanf(%d,&p-s1);getchar();if(p-s0s0=KK-CurNum|p-s1s1=KK-CurNu

14、m)printf(超出當(dāng)前串的范圍n);elseIndex(KK-StrHeadp-s0,KK-StrHeadp-s1);elsewhile(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-StrHeadp-s0,KK-StrHeadp-s1);break;caseR:m+;/替換串if(s1m=0)/求內(nèi)部已存在的

15、串的替換printf(輸入第一個串的內(nèi)部名：n);scanf(%d,&p-s0);getchar();printf(輸入第二個串的內(nèi)部名：n);scanf(%d,&p-s1);getchar();printf(輸入第三個串的內(nèi)部名：n);scanf(%d,&p-s2);getchar();if(p-s0s0=KK-CurNum|p-s1s1=KK-CurNum|p-s2s2=KK-CurNum)printf(超出當(dāng)前串的范圍n);elseReplace(KK-StrHeadp-s0,KK-StrHeadp-s1,KK-StrHeadp-s2);elsewhile(KK-StrHeadKK-Cu

16、rNum.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(p-s2);Replace(KK-StrHeadp-s0,KK-StrHeadp-s1,KK-StrHeadp-s2);break;caseP:printf(“所有串的內(nèi)部名和串值為：n);顯示所有保留的

17、串for(i=0;iStrHeadi.ch!=NULL)printf(%5d,i);Strprint(KK-StrHeadi);break;caseD:printf(“請輸入要刪除的串的內(nèi)部名：n);刪除串scanf(%d,&p-num0);getchar();if(p-num0num0=KK-CurNum)printf(無此串！n);elseprintf(刪除的串名和串值為：n);printf(%5d,p-num0);printf(%c,);Strprint(KK-StrHeadp-num0);KK-StrHeadp-num0.ch=NULL;KK-StrHeadp-num0.length=

18、0;break;caseW:printf(請輸入要賦值的串的內(nèi)部名和串值(以空格隔開)：n);scanf(%d%s,&p-num0,s);getchar();if(p-num0num0=100)printf(無此串！n);elseInsert(p-num0);printf(新串的內(nèi)部名和串值為：n);printf(%5d,p-num0);Strprint(KK-StrHeadp-num0);break;caseQ:break;default:printf(輸入錯誤！可返回上一界面查看輸入格式n);while(s10!=Q);returnOK;(2)測試數(shù)據(jù)：賦值：AhelloventerAni

19、cetomeetyou!，venterAtooventer顯示：Pventer/回顯剛才輸入的三條語句判相等：Ehellohiventer或只輸入Eventer然后根據(jù)提示操作聯(lián)接：Chellohiventer或只輸入Cventer然后根據(jù)提示操作求長度：Lhelloventer或只輸入Lventer然后根據(jù)提示操作求子串：Shelloventer然后根據(jù)提示操作或只輸入Eventer提示操作.子串定位：Ihellollventer或只輸入Iventer然后根據(jù)提示操作刪除：輸入Dventer然后根據(jù)提示操作Eg.Eventer，顯示“EQUAL”Edadventer，顯示“UNEQUAL”C

20、“，venter，顯示，Chello,nicetomeetyouventer，顯示hello,nicetomeetyouIaventer,應(yīng)報告：參數(shù)非法Ihellollventer，顯示:3Shelloventer，然后根據(jù)提示輸入pos和len的值Raaaaabventer，顯示：baRaaabcaaabventer，顯示:aabaabaabbcRaaaaaaaaaaaaabventer，顯示：abab五、用戶手冊1本程序的運(yùn)行環(huán)境為DOS操作系統(tǒng)，執(zhí)行文件為project.exe。2進(jìn)入程序后即顯示用戶歡迎界面，用戶可根據(jù)文字提示進(jìn)行操作，本程序有兩種命令輸入格式（如Ehellohive

21、nter或只輸入Eventer然后根據(jù)提示操作），具體可查看程序的輸入格式。3本程序區(qū)分大小寫，輸入指令時請注意。4.本程序支持內(nèi)部名操作，如在聯(lián)接串的時候，可以先輸入Cventer，然后按提示輸入內(nèi)部名，即可完成操作?；蛘呖梢灾苯虞斎隒hellonicetomeetyouventer，結(jié)果串為hellonicetomeetyou；其它的函數(shù)也可以進(jìn)行類似操作。5本程序是命令解釋程序，循環(huán)往復(fù)地處理用戶鍵入的每一條指令，直至終止程序的命令為止（本程序退出指令為Qventer）。六、測試結(jié)果下面是運(yùn)行程序的操作流程（從運(yùn)行窗口復(fù)制的）：project.exe1比較串相等時，因為要比較的兩個串都已

22、存入串頭表中。因此，開始可以先比較兩串的長度，若不等則馬上顯示“UNEQUAL”并返回。長度相等則逐個比較串值，遇到不等則馬上顯示“UNEQUAL“并返回，比較完相等則顯示“UNEQUAL”。2在串聯(lián)接時，方法挺簡單。只需申請兩串長度之和的空間，然后按順序賦值到新串即可。注釋：上圖為執(zhí)行各項基本操作的效果圖，可見驗證結(jié)果的正確性。1上圖是直接輸入串值的命令，這樣可以方便的一次性輸入完指令。滿足了程序的基本要求。2在子串定位函數(shù)中，要注意檢查參數(shù)的合法性，當(dāng)?shù)诙€串是空串時要正確處理這種情況。3在子串替換時，要注意設(shè)置循環(huán)結(jié)束的條件，如果設(shè)置不對，曾出現(xiàn)過RDaaaDaaDbD，結(jié)果卻為bD的錯

23、誤結(jié)果，改正后結(jié)果正確。晴輸入指令:幘輸入要賦值的串的內(nèi)部名和串值以空格隔開1:B,liello,斷串的內(nèi)部名和串值為：3JhelloJ猜輸入指令：P所有串的內(nèi)部名和串值為：3JhelloJ惰輸入指令：慣輸入要賦值的串的內(nèi)部名和串值（以空格隔開）:pfchangef新串的內(nèi)部名和串值為：31change1情輸入指令：P祈有串的內(nèi)部名和串值為：1change1情輸入指令：pt*aaabc*1aJ*aabJ卡吉果串的內(nèi)部名和串值為：aabaabaabbc幘輸入指令：P所有串的內(nèi)部名和串值為：01aaabc1JaJJaabf1change1*aabaabaabbc*慎輸入指令：扁入兩個串的內(nèi)部名以逗

24、號隔開）：UNEQUAL”律輸入指令：常入兩個串的內(nèi)部名以逗號隔開）：注釋：上圖為各項操ey嗣墮中巴密二一廊呂忌駕四龜莖1_在這里可以看出，本程序增加了Insert（）函r,_口r,_口j以在指定本程序還支持內(nèi)部名操作，如上圖所示，可以根據(jù)要求輸入內(nèi)部名，即可完成相應(yīng)的串操作，這樣可以對已存入的串進(jìn)行聯(lián)接、比較等操作，這樣就大大增強(qiáng)了程序的實用性和可操作性。七、附錄源程序文件名菜單：header.h/類型和變量說明main.c/主程序文件八、時間復(fù)雜度分析1由于本程序采用數(shù)組的順序存儲結(jié)構(gòu)，雖然要開始定義一個較大的存儲空間(如定義：HStringStrHead100),但由于每個Hstring

25、類型的結(jié)構(gòu)體才兩個元素，花費(fèi)的整體空間并不比鏈?zhǔn)酱鎯Y(jié)構(gòu)(要開辟指針域，花費(fèi)一定空間)大多少，更重要的是采用數(shù)組的順序存儲結(jié)構(gòu)執(zhí)行串的基本操作非常方便，不必如鏈?zhǔn)侥菢訌念^指針出發(fā)查找，時間復(fù)雜度為O(n)，可以通過內(nèi)部名直接找到某一個串，時間復(fù)雜度為O(1)。因此在執(zhí)行諸如串的基本操作上很方便。假設(shè)串值的平均長度為n,則StrCompare的時間復(fù)雜度為o(n)；Concat的時間復(fù)雜度為o(n+n)；Index的時間復(fù)雜度為o(n*n)；Replace的時間復(fù)雜度為o(n*n*n)；SubString的時間復(fù)雜度為o(n)；在錯誤處理方面，本程序在幾個方面做了考慮。比如在賦值指令時，如果輸入

26、的命令為Aadas,這樣雖然可以知道是賦值指令,但串值不能正確賦入相應(yīng)的串中，這時系統(tǒng)應(yīng)該報錯；再者，在支持內(nèi)部名操作的指令中，如果輸入的內(nèi)部名超出范圍，則應(yīng)該報錯，其它類似的地方也應(yīng)采取相應(yīng)的處理方式。由于本程序采用字符數(shù)組s1來接收輸入的命令，為了處理數(shù)據(jù)的方便，采用了定義局部變量的方法，這樣可以減少需要傳遞的參數(shù)個數(shù)。比如在一條替換指令中有三個串，在賦值的時候采用同一個函數(shù)getin(intn)函數(shù)就可以完成三個串的賦值，而且只需傳遞目的串的內(nèi)部名一個參數(shù)就足夠啦。因為s1是在getorder函數(shù)的，把s1m定義為局部變量后就可以直接在getin函數(shù)調(diào)用，減少傳遞的參數(shù)，還可以使m增加到相應(yīng)的位置，為下個getin函數(shù)取用方便且正