串的基本操作

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告井岡山大學(xué)電子與信息工程學(xué)院

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告（2012——2013年度第一學(xué)期）課程名稱： 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計題目一：4.2串基本操作演示系統(tǒng)院系：計算機科學(xué)系班級：10軟件本2班姓名：xxx學(xué)號：100913017指導(dǎo)教師：孫凌宇老師成績：2012年12月10日成績評定、指導(dǎo)教師評語、成績備注指導(dǎo)教師：日期：年月日

設(shè)計題目＜一＞： 4.2串基本操作演示系統(tǒng)一、設(shè)計要求1．問題描述如果計算機語言沒有把串作為一個預(yù)先定義好的基本類型對待，又需要用該語言寫一個涉及串操作的軟件系統(tǒng)時，用戶必須自己實現(xiàn)串類型。試著實現(xiàn)串類型，并寫一個串的基本操作演示系統(tǒng)。2．需求分析實現(xiàn)若干串的常用基本操作，如串賦值、求串長、串替換、串比較、求子串及串的模式匹配等。為了實現(xiàn)以上功能，可以從3個方面著手設(shè)計。1．主界面設(shè)計為了實現(xiàn)串基本操作演示系統(tǒng)各功能的管理，本系統(tǒng)設(shè)計一個含有多個菜單項的主控單，方便用戶使用。本系統(tǒng)主控菜單運行界面如圖1所示?！鮸x艸C:\Docu>entsandSettings\Ad*inistrator\桌面\fuzhihui\4.2串的基本操作演呂呂呂ALsIRcQ111.+■H+■H士宜士宜+宜+宜□|x艸C:\Docu>entsandSettings\Ad*inistrator\桌面\fuzhihui\4.2串的基本操作演呂呂呂ALsIRcQ111.+■H+■H士宜士宜+宜+宜-呂呂呂呂呂呂位度聖養(yǎng)值長番替比岀賦親退晴看菜單輸入您要進行的操作并回車龍全部用大寫〉:圖1串演示系統(tǒng)主菜單2．存儲結(jié)構(gòu)設(shè)計使用串的堆分配存儲表示，結(jié)構(gòu)描述如下：typedefstruct{char*ch; //串存放的數(shù)組intcurLen; //串的長度}HString;3．系統(tǒng)功能設(shè)計本系統(tǒng)設(shè)置了主界面菜單，并在主界面上完成7個功能的結(jié)果顯示。7個功能的設(shè)計描述如下。賦值(A-Assign)。由函數(shù)intstrAssign()實現(xiàn)。當用戶選擇A功能時，輸入待賦值的新串串值，系統(tǒng)完成串賦值并輸出新串值。求長度(L-Length)。由函數(shù)intStrLength()實現(xiàn)。當用戶選擇L功能時，系統(tǒng)輸出串的長度。求子串(S-SubString)。由函數(shù)intsubstring()實現(xiàn)，參數(shù)pos和len分別代表子串sub在原串S上的起始位置和子串長度。當用戶選擇S功能時，系統(tǒng)輸出子串的串值。子串定位(I-Index)。子串定位又稱串的模式匹配，由函數(shù)intIndex()實現(xiàn)。當用戶選擇I功能時，系統(tǒng)根據(jù)用戶輸入的原串ob1和子串ob2的值輸出子串在原串上的位置。替換(R-Replace)。由函數(shù)voidReplace()實現(xiàn)。當用戶選擇R功能時，系統(tǒng)根據(jù)用戶輸入的原串ob1、子串ob2和插入串ob3的值，輸出用插入串替換了原串中所有指定子串后的串值。判相等(C-Compare)。由函數(shù)intCompare()實現(xiàn)。當用戶選擇C功能時，系統(tǒng)根據(jù)用戶輸入的s1與s2的串值進行比較。若s1>s2則顯示“s1>s2”；若s1=s2則顯示“s1=s2”；若s1<s2則顯示“s1<s2”。退出(Q-Quit)。當用戶選擇Q功能時，即退出串基本操作演示系統(tǒng)，有main()函數(shù)中的if語句實現(xiàn)。三、模塊設(shè)計1．模塊設(shè)計本程序包含兩個模塊：主程序模塊、串操作模塊。其調(diào)用關(guān)系如圖2所示。主程序模塊 >串操作模塊圖2模塊調(diào)用關(guān)系示意圖2．系統(tǒng)子程序及功能設(shè)計intinitString(HString*T) //串類的初始化函數(shù)intstrAssign(HString*T,char*chars) //串賦值函數(shù)，調(diào)用malloc函數(shù)分配內(nèi)存空間intStrLength(HStringS) //求串長函數(shù)intsubstring(HString&Sub,HStringS,intpos,intlen)//求串S的子串，pos代表子串sub的起始字符序號(位置)，len代表子串sub的長度intIndex(HString&obl,HString&ob2,intpos)〃從第pos個字符起的子串定位(串的模式匹配)函數(shù)，調(diào)用(3).voidReplace(HString&obl,HString&ob2,HString&ob3)〃將原串ob1的所有子串ob2都替換為插入串ob3，調(diào)用(3)和(5)intCompare(HStringsl,HStrings2) //串比較函數(shù)，調(diào)用(3)voidmain() //主函數(shù)，設(shè)定界面，調(diào)用操作模塊函數(shù)4．函數(shù)主要調(diào)用關(guān)系圖串基本操作演示系統(tǒng)8個子程序之間的主要調(diào)用關(guān)系如圖3所示。圖中字母是各函數(shù)四、詳細設(shè)計1．數(shù)據(jù)類型定義(1)字符串的定義typedefstruct

char*ch;intcurLen;}HString;(2)全局變量聲明#defineOK1#defineOVERFLOW0//串存放的數(shù)組//串的長度////串存放的數(shù)組//串的長度//操作成功//溢出2．系統(tǒng)主要子程序詳細設(shè)計(1)主程序模塊設(shè)計主函數(shù)。設(shè)定用戶操作界面，調(diào)用操作模塊函數(shù)。voidmain(){輸出操作菜單；Switch(1){輸出操作序號c；switch(c){調(diào)用相應(yīng)函數(shù)執(zhí)行相應(yīng)操作；輸出操作結(jié)果；}}}(2)求子串intsubstring(HString&Sub,HStringS,intpos,intlen){/串sub返回串S的第pos個字符起長度為len的子串inti;if(pos<0||pos>S.curLen||len<0||len>S.curLen-pos){ //若位置或長度不合法，退出

printf("輸入不合法\n");printf("輸入不合法\n");exit(OVERFLOW);}else{if(Sub.ch)free(Sub.ch);if(!len){Sub.ch=NULL;Sub.curLen=0;}else//退出//釋放子串sub原有空間〃若長度len為0//就愛那個子串置為空串〃若長度len不為0{Sub.ch=(char*)malloc(len*sizeof(char));for(i=0;i<len;i++){ //從串S的第pos個字符開始依次復(fù)制其后長度為len的字符串sub中Sub.ch[i]=S.ch[pos-1+i];Sub.curLen=len; //修改串sub的串長}}returnOK;}}(3)子串定位(串的模式匹配)intIndex(HString&ob1,HString&ob2,intpos){ 〃判斷從第pos個字符起，ob2是否為obi的子串〃若是返回ob2在obi中的起始位置，否則返回-1if(pos<0||pos>obi.curLen){〃若輸入的數(shù)值pos不在obi的串長范圍內(nèi)printf("輸入有誤\n");exit(ERROR);

for(inti=pos-1;i<=StrLength(ob1)-StrLength(ob2);i++){ //從ob1的第pos個字符起查找子串ob2intj=0; 〃從ob2的第一個字符起開始查找while(j<StrLength(ob2)) //j控制查找位置，逐個字符查找，直到超出子串串長if(ob1.ch[i+j]==ob2.ch[j])//若找到匹配字符j++; //則依次向后查找}return}return-1;//ob2不是ob1的子串，返回-1}(4)串替換}(4)串替換voidReplace(HString&ob1,HString&ob2,HString&ob3){ 〃將原串obi的所有子串ob2都替換為插入串ob3printf("原串：“)；for(inti=0;i<obi.curLen;i++)printf("%c",obi.ch[i]);printf("\n子串：");for(intj=0;j<ob2.curLen;j++)printf("%c",ob2.ch[j]);printf("\n");printf("插入串：")；for(intk=0;k<ob3.curLen;k++)printf("%c",ob3.ch[k]);printf("\n");intlen=StrLength(ob2);while(Index(obi,ob2,0)!=-i)//ob2的長度//當ob2是obi的子串，替換所有的ob2elsebreak; //一旦失配，則跳出查找，此時j還未能達到子串串長}if(j==StrLength(ob2))//若j達到子串串長，即ob2的所有字符都能和obi匹配returni;〃返回ob2在obi的起始位置i

intlen2=StrLength(ob3)+StrLength(ob1)-StrLength(ob2);inti=Index(ob1,ob2,0);intlen2=StrLength(ob3)+StrLength(ob1)-StrLength(ob2);char*p=newchar[StrLength(ob1)-i-len+1];char*q=newchar[len2];for(intj=i+len;j<StrLength(ob1);j++)p[j]=ob1.ch[j];for(intk=0;k<i;k++)q[k]=ob1.ch[k];for(intm=i;m<i+StrLength(ob3);m++)q[m]=ob3.ch[m-i];intb=i+len;for(intn=i+StrLength(ob3);n<len2;n++){ //將不用替換的后部分存入數(shù)組qq[n]=p[b];b++;}ob1.curLen=len2;for(intl=0;l<len2;l++)ob1.ch[l]=q[l];}printf("新串：")；for(inth=0;h<ob1.curLen;h++)printf("%c",ob1.ch[h])；}(5)串比較intCompare(HStrings1,HStrings2)//新串的長度//調(diào)用子串定位函數(shù)//臨時數(shù)組//存儲新串的數(shù)組〃將不用替換的后部分存入數(shù)組p〃將不用替換的前部分存入數(shù)組q//替換子串//數(shù)組//新串的長度//調(diào)用子串定位函數(shù)//臨時數(shù)組//存儲新串的數(shù)組〃將不用替換的后部分存入數(shù)組p〃將不用替換的前部分存入數(shù)組q//替換子串//數(shù)組q存儲著新串〃將新串賦值給obi做循環(huán)替換inti;for(i=0；i<si.curLen&&i<s2.curLen；++i)if(s1.ch[i]!=s2.ch[i])

return(s1.ch[i]-s2.ch[i]);return(s1.curLen-s2.curLen);}五、測試分析系統(tǒng)運行主界面如圖1所示。各子系統(tǒng)測試運行結(jié)果如下。1.賦值(A-Assign)在主菜單下，輸入Ahello!并回車，運行結(jié)果如圖4所示。grC:\Docu>entsandSettings\Ad*inistrator\桌面\fuzhihui\4.2串的基本搽作return(s1.ch[i]-s2.ch[i]);return(s1.curLen-s2.curLen);}五、測試分析系統(tǒng)運行主界面如圖1所示。各子系統(tǒng)測試運行結(jié)果如下。1.賦值(A-Assign)在主菜單下，輸入Ahello!并回車，運行結(jié)果如圖4所示。grC:\Docu>entsandSettings\Ad*inistrator\桌面\fuzhihui\4.2串的基本搽作---I串窗呂呂呂位度聖養(yǎng)值長舌替比岀為為為為為為為式式式式式式式1i14-M+■H+■M+■H+■M+■H-呂呂呂呂呂呂-ALsIRcQ數(shù)2<2數(shù)1慣翥蕃里輸入您要進行的操作并回車煌部用大寫5hello?于役串為：hello!需著菜單輸入您要進行的操作并回車徒部用大寫〉.■|口兇圖4字符串賦值2.求長度（L-Lengh）在主菜單下，輸入Lstudent并回車，運行結(jié)果如圖5所示。c**C:\Docu>entsandSettings\Ad?inistrator\桌面\fuzhihui\4.2串的基本操件---式式式式式式式111*+宜+包士宜士宜+宜+宜-呂呂呂呂呂呂student夢單嚴要進行的操作并回鋰部用大寫口

魯菜單輸入您要進行的操作并回車￡全部用大寫〉.student圖5求字符串長度求子串(S-SubString)在主菜單下，輸入Sstudent25并回車，運行結(jié)果如圖6所示g*C:\DocuMentsandSettings\AdAinistrator\桌面\fuzhihui\4.2串的基本操件---二一一值長番替比岀一一賦親rHw退二ffffff靂菜請子請為為為為為為為式式式式式式式111.+宜士宜士宜士宜士宜士宜-呂呂呂呂呂呂?-?■44-M-二一一值長番替比岀一一賦親rHw退二ffffff靂菜請子請為為為為為為為式式式式式式式111.+宜士宜士宜士宜士宜士宜-呂呂呂呂呂呂?-?■44-M-數(shù)2?2數(shù)1I串窗44-M-44-M-?-M-?-M-?-M-student圖6求子串子串定位(ITndex)在主菜單下，分別輸入Imicrosoftvisualc++soft1并回車和Imicrosoftvisualc++soft8，運行結(jié)果如圖7所示。c：\^C:\DocuAentsandSettIngs\Ad>inistrator\桌面\fuzhihui\4.2串的基本操件---|~|~Jk.31值

數(shù)串222

4-Hf-Mfnrl

呂呂呂-M-SJk.31值

數(shù)串222

4-Hf-Mfnrl

呂呂呂-M-S二O二PXC二iXmX二I二:X>一二芍?二乍-X」\二-4丿二Rn二X咅X._￡二J.3X<二-RTX習(xí)X叵X卜干二+hXE—二申111演呂呂呂呂呂呂ALsIRC< 羽為為為為為為為十操墓式式式式式式式二的行■■毎活進$2進*要串要MI8一一您位您己一您值長番替比出二入的入「?賦0^|+^<退一一輸」 =單原單二二二二i菜二二二r一請子請從請4<氐4<回侍的是的行不行:串-I圖7子串定位替換(R-Replace)在主菜單下，輸入Rchickenct并回車，運行結(jié)果如圖8所示

w*C:\DocuMentsandSettings\Ad>inistrator\桌面\fuzhihui\4-2串的基本操作值長番替比岀<1+^*退式式式式式式式ill.+■>+■H+■H+■M+■H+■H-呂呂呂呂呂呂-ALsIRcQ數(shù)w*C:\DocuMentsandSettings\Ad>inistrator\桌面\fuzhihui\4-2串的基本操作值長番替比岀<1+^*退式式式式式式式ill.+■>+■H+■H+■M+■H+■H-呂呂呂呂呂呂-ALsIRcQ數(shù)2值2數(shù)11串窗w-*e**香X入請原子聾請ti箱h牡I:t:串：菜chicken口|其圖8字符串替換6.判相等(C-Compare)在主菜單下，分別輸入Conin并回車和Conon并回車，運行結(jié)果如圖9所示。c：\^C:\DocuAentsandSettIngs\Ad>inistrator\桌面\fuzhihui\4.2串的基本操件-度聖叢

值長舌替比岀

賦^退宜凱1匚匚匚匚匚匚彩數(shù)；1演呂呂呂呂呂呂^malsircq< 本為為為為為為為基式式式式式式式31值

數(shù)串on

oninon話耆耒單輸入您要進行的操作并回車龍全部用大寫〉嗆供斷曲結(jié)果:串1》串on

oninon青著杲單輸入您要進行的操作并回車￡全部用大寫〉:C去嚼商結(jié)果:串"串2畚署菜單輸入您要進行的操作并回車＜全部用大寫〉.圖9判兩串相等7.退出(Q-Quit)在主菜單下，輸入Q并回車，退出串基本操作演示系統(tǒng)。六、用戶手冊本程序執(zhí)行文件為“串的基本操作演示.exe”進入本系統(tǒng)之后，隨即顯示系統(tǒng)主菜單界面。用戶可在該界面下按提示信息輸入命令七、調(diào)試報告(1)我不喜歡敲代碼，寫一個簡單的程序時竟然老是出錯，難一點的，復(fù)雜一點的程序竟然無從下手，程序的架構(gòu)根本不懂，以至于程序存在許多bug，不過只要按著提示操作，

還是可以完成相應(yīng)的功能。(2)如果有興趣還可以對次程序進行深入研究，進行修改，添加等一些串的其他功能八、程序清單#include<stdlib.h>#include<iostream>#include<conio.h>#defineOK1#defineOVERFLOW0#defineERROR0usingnamespacestd; //使用名稱空間std//****串的堆分配存儲表示typedefstruct//串存放的數(shù)組//串存放的數(shù)組//串的長度char*ch;intcurLen;}HString;//****1.初始化字符串TintinitString(HString*T){(*T).ch=NULL;(*T).curLen=0;returnOK;}//****2.串賦值函數(shù)intstrAssign(HString*T,char*chars){//生成一個值等于串常量chars的串T并用指針返回,*chars為指針(數(shù)組名)inti,j;if((*T).ch)free((*T).ch); //釋放T原有空間

i=strlen(chars);//數(shù)組chars的長度if(!i){(*T).ch=NULL;//若chars為空串，生成空串的堆分配存儲表示(*T).curLen=0;}else{//chars不為空串if(!((*T).ch=(char*)malloc(i*sizeof(char))))exit(OVERFLOW); //分配串的堆空間，若失敗則退出for(j=0;j<i;j++)(*T).ch[j]=chars[j];(*T).curLen=i;}returnOK;}//****3.求串長函數(shù)intStrLength(HStringS){returnS.curLen; //直接返回串長}//****4.求子串函數(shù)intsubstring(HString&Sub,HStringS,intpos,intlen){//串Sub返回串S的第pos個字符起長度為len的子串inti;if(pos<0||pos>S.curLen||len<0||len>S.curLen-pos){//若位置或長度不合法，退出//退出//釋放子串sub原有空間//退出//釋放子串sub原有空間exit(OVERFLOW);}else{if(Sub.ch)free(Sub.ch);if(!len) //若長度len為0{ //將子串置為空串Sub.ch=NULL;Sub.curLen=0;}else//若長度len不為0{Sub.ch=(char*)malloc(len*sizeof(char));for(i=0;i<len;i++){//從串S的第pos個字符開始依次復(fù)制其后長度為len的字符串到串Sub中Sub.ch[i]=S.ch[pos-1+i];Sub.curLen=len; //修改串Sub的串長}}returnOK;}}//****5.子串定位函數(shù)(串的模式匹配)intIndex(HString&ob1,HString&ob2,intpos){ //判斷從第pos個字符起，ob2是否為ob1的子串//若是返回ob2在ob1中的起始位置，否則返回-1if(pos<0||pos>ob1.curLen){〃若輸入的數(shù)值pos個字符起，ob2是否為obi的子串printf("輸入有誤\n");exit(ERROR);}for(inti=pos-1;iv=StrLength(ob1)-StrLength(ob2);i++){ 〃從obi的第pos個字符起查找子串ob2intj=0; 〃從ob2的第一個字符起開始查找while(j<StrLength(ob2)) //j控制查找位置，逐個字符查找，直到超出子串串長

if(ob1.ch[i+j]==ob2.ch[j])//若找到匹配字符j++; //則依次向后查找}return}return-1;//ob2不是ob1的子串，返回-1elsebreak; //一旦失配，則跳出查找，此時j還未能達到子串串長}if(j==StrLength(ob2))〃若j達到子串串長，即ob2的所有字符都能和obi匹配returni；//返回ob2在ob1的起始位置i}//****6.串替換函數(shù)voidReplace(HString&ob1,HString&ob2,HString&ob3){ //將原串ob1的所有子串ob2都替換為插入串ob3printf(“原串：“)；for(inti=0;i<ob1.curLen;i++)printf("%c",ob1.ch[i])；printf("\n子串：“)；for(intj=0；j<ob2.curLen；j++)printf("%c",ob2.ch[j])；printf("\n")；printf("插入串：")；for(intk=0；k<ob3.curLen；k++)printf("%c",ob3.ch[k])；printf("\n")；intlen=StrLength(ob2)； //ob2的長度while(Index(ob1,ob2,0)!=-1) //當ob2是ob1的子串，替換所有的ob2{intlen2=StrLength(ob3)+StrLength(ob1)-StrLength(ob2)；//新串的長度inti=Index(ob1,ob2,0)； //調(diào)用子串定位函數(shù)char*p=newchar[StrLength(ob1)-i-len+1]； //臨時數(shù)組char*q=newchar[len2]； //存儲新串的數(shù)組for(intj=i+len；j<StrLength(ob1)；j++)

p[j]=ob1.ch[j];for(intk=0;k<i;k++)p[j]=ob1.ch[j];for(intk=0;k<i;k++)q[k]=ob1.ch[k];for(intm=i;m<i+StrLength(ob3);m++)q[m]=ob3.ch[m-i];intb=i+len;〃將不用替換的后部分存入數(shù)組p//將不用替換的前部分存入數(shù)組q//替換子串for(intn=i+StrLength(ob3);nvlen2;n++){ 〃將不用替換的后部分存入數(shù)組qq[n]=p[b];b++; //數(shù)組q存儲著新串}ob1.curLen=len2;for(intl=0;l<len2;l++)ob1.ch[l]=q[l]; //將新串賦值給ob1做循環(huán)替換}printf("新串：")；for(inth=0;h<ob1.curLen;h++)printf("%c",ob1.ch[h]);}//****7.串比較函數(shù)intCompare(HStrings1,HStrings2){ //若s1<s2則返回值<0;若s1=s2則返回值=0;若s1>s2則返回值>0inti;for(i=0;i<s1.curLen&&i<s2.curLen;++i)if(s1.ch[i]!=s2.ch[i])return(s1.ch[i]-s2.ch[i]);return(s1.curLen-s2.curLen);}//8.主函數(shù)voidmain(){printf(f串基本操作演示系統(tǒng)—***************、『）；printf(printf("**f.賦值格式為:A串值**\n");printf("**一.求長度格式為:L串值**\n");printf("**f.求子串格式為:S串值數(shù)1數(shù)2**\n");printf("**f.子串定位格式為:I串值1串值2數(shù)1**\n");printf("**f.串替換格式為:R串值1串值2串值3**\n");printf("**f.串比較格式為:C串值1串值2**\n");printf("**f.退出格式為:Q**\n");while(1){charc;printf(“請看菜單輸入您要進行的操作并回車(全部用大寫):");cin>>c; //輸入大寫字母if(c=='Q')break;//退出串基本操作演示系統(tǒng)switch(c) //用switch語句對輸入的大寫字母進行多向選擇{case'A':{charcnew[50];HStringstr;initString(&str); //初始化串strscanf("%s",cnew);strAssign(&str,cnew);//調(diào)用串生成函數(shù)printf("字符串為:")；for(inti=0;i<str.curLen;i++)printf("%c",str.ch[i]);printf("\n");break;}case'L':

cha