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

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告井岡山大學(xué)電子與信息工程學(xué)院數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 ( 20122013年度第一學(xué)期)課程名稱： 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 題 目 一： 4.2串基本操作演示系統(tǒng) 院 系： 計(jì)算機(jī)科學(xué)系 班 級(jí)： 10軟件本2班 姓 名： xxx 學(xué) 號(hào)： 100913017 指導(dǎo)教師： 孫凌宇老師 成 績(jī)： 2012 年 12 月 10 日成 績(jī) 評(píng) 定一、 指導(dǎo)教師評(píng)語(yǔ)二、 成績(jī)成績(jī)備注 指導(dǎo)教師： 日 期： 年 月 日設(shè)計(jì)題目<一>： 4.2串基本操作演示系統(tǒng)一、設(shè)計(jì)要求1問(wèn)題描述如果計(jì)算機(jī)語(yǔ)言沒(méi)有把串作為一個(gè)預(yù)先定義好的基本類型對(duì)待，又需要用該語(yǔ)言寫(xiě)一個(gè)涉及串操作的軟件系統(tǒng)時(shí)，用

2、戶必須自己實(shí)現(xiàn)串類型。試著實(shí)現(xiàn)串類型，并寫(xiě)一個(gè)串的基本操作演示系統(tǒng)。2需求分析實(shí)現(xiàn)若干串的常用基本操作，如串賦值、求串長(zhǎng)、串替換、串比較、求子串及串的模式匹配等。二、概要設(shè)計(jì)為了實(shí)現(xiàn)以上功能，可以從3個(gè)方面著手設(shè)計(jì)。1 主界面設(shè)計(jì)為了實(shí)現(xiàn)串基本操作演示系統(tǒng)各功能的管理，本系統(tǒng)設(shè)計(jì)一個(gè)含有多個(gè)菜單項(xiàng)的主控單，方便用戶使用。本系統(tǒng)主控菜單運(yùn)行界面如圖1所示。圖1串演示系統(tǒng)主菜單2 存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)使用串的堆分配存儲(chǔ)表示，結(jié)構(gòu)描述如下：typedef structchar *ch; /串存放的數(shù)組int curLen; /串的長(zhǎng)度HString;3 系統(tǒng)功能設(shè)計(jì)本系統(tǒng)設(shè)置了主界面菜單，并在主界面上完成7

3、個(gè)功能的結(jié)果顯示。7個(gè)功能的設(shè)計(jì)描述如下。(1)賦值（A-Assign）。由函數(shù)int strAssign()實(shí)現(xiàn)。當(dāng)用戶選擇A功能時(shí)，輸入待賦值的新串串值，系統(tǒng)完成串賦值并輸出新串值。(2)求長(zhǎng)度（L-Length）。由函數(shù)int StrLength()實(shí)現(xiàn)。當(dāng)用戶選擇L功能時(shí)，系統(tǒng)輸出串的長(zhǎng)度。(3)求子串（S-SubString）。由函數(shù)int substring()實(shí)現(xiàn)，參數(shù)pos和len分別代表子串sub在原串S上的起始位置和子串長(zhǎng)度。當(dāng)用戶選擇S功能時(shí)，系統(tǒng)輸出子串的串值。(4)子串定位（I-Index）。子串定位又稱串的模式匹配，由函數(shù)int Index()實(shí)現(xiàn)。當(dāng)用戶選擇I功能

4、時(shí)，系統(tǒng)根據(jù)用戶輸入的原串ob1和子串ob2的值輸出子串在原串上的位置。(5)替換（R-Replace）。由函數(shù)void Replace()實(shí)現(xiàn)。當(dāng)用戶選擇R功能時(shí)，系統(tǒng)根據(jù)用戶輸入的原串ob1、子串ob2和插入串ob3的值，輸出用插入串替換了原串中所有指定子串后的串值。(6)判相等（C-Compare）。由函數(shù)int Compare()實(shí)現(xiàn)。當(dāng)用戶選擇C功能時(shí)，系統(tǒng)根據(jù)用戶輸入的s1與s2的串值進(jìn)行比較。若s1>s2則顯示“s1>s2”；若s1=s2則顯示“s1=s2”；若s1<s2則顯示“s1<s2”。(7)退出（Q-Quit）。當(dāng)用戶選擇Q功能時(shí)，即退出串基本操作

5、演示系統(tǒng)，有main()函數(shù)中的if語(yǔ)句實(shí)現(xiàn)。三、模塊設(shè)計(jì)1模塊設(shè)計(jì)本程序包含兩個(gè)模塊：主程序模塊、串操作模塊。其調(diào)用關(guān)系如圖2所示。主程序模塊串操作模塊圖2 模塊調(diào)用關(guān)系示意圖2系統(tǒng)子程序及功能設(shè)計(jì)(1) int initString(HString *T) /串類的初始化函數(shù)(2) int strAssign(HString *T,char *chars) /串賦值函數(shù)，調(diào)用malloc函數(shù)分配內(nèi)存空間(3) int StrLength(HString S) /求串長(zhǎng)函數(shù)(4) int substring(HString &Sub,HString S,int pos,int len

6、)/求串S的子串，pos代表子串sub的起始字符序號(hào)（位置），len代表子串sub的長(zhǎng)度(5) int Index(HString &ob1,HString &ob2,int pos)/從第pos個(gè)字符起的子串定位（串的模式匹配）函數(shù)，調(diào)用(3).(6) void Replace(HString &ob1,HString &ob2,HString &ob3)/將原串ob1的所有子串ob2都替換為插入串ob3，調(diào)用（3）和（5）(7) int Compare(HString s1, HString s2) /串比較函數(shù)，調(diào)用（3）(8) void main

7、() /主函數(shù)，設(shè)定界面，調(diào)用操作模塊函數(shù)4 函數(shù)主要調(diào)用關(guān)系圖串基本操作演示系統(tǒng)8個(gè)子程序之間的主要調(diào)用關(guān)系如圖3所示。圖中字母是各函數(shù)的編號(hào)。8 main()23675413圖3 系統(tǒng)函數(shù)調(diào)用關(guān)系圖四、詳細(xì)設(shè)計(jì)1數(shù)據(jù)類型定義(1) 字符串的定義typedef structchar *ch; /串存放的數(shù)組int curLen; /串的長(zhǎng)度HString;(2) 全局變量聲明#define OK 1 /操作成功#define OVERFLOW 0 /溢出#define ERROR 0 /出錯(cuò)2系統(tǒng)主要子程序詳細(xì)設(shè)計(jì)(1)主程序模塊設(shè)計(jì)主函數(shù)。設(shè)定用戶操作界面，調(diào)用操作模塊函數(shù)。void ma

8、in()輸出操作菜單；Switch (1)輸出操作序號(hào)c；switch (c)調(diào)用相應(yīng)函數(shù)執(zhí)行相應(yīng)操作；輸出操作結(jié)果；(2)求子串int substring(HString &Sub,HString S,int pos,int len)/´串sub返回串S的第pos個(gè)字符起長(zhǎng)度為len的子串int i;if(pos<0|pos>S.curLen|len<0|len>S.curLen-pos) /若位置或長(zhǎng)度不合法，退出printf("輸入不合法n"); exit(OVERFLOW); /退出elseif(Sub.ch) free(S

9、ub.ch); /釋放子串sub原有空間if(!len) /若長(zhǎng)度len為0 /就愛(ài)那個(gè)子串置為空串Sub.ch=NULL;Sub.curLen=0;else /若長(zhǎng)度len不為0Sub.ch=(char*)malloc(len*sizeof(char);for(i=0; i<len; i+) /從串S的第pos個(gè)字符開(kāi)始依次復(fù)制其后長(zhǎng)度為len的字符串sub中Sub.chi=S.chpos-1+i; Sub.curLen=len; /修改串sub的串長(zhǎng)return OK;(3)子串定位（串的模式匹配）int Index(HString &ob1,HString &ob2

10、,int pos) /判斷從第pos個(gè)字符起，ob2是否為ob1的子串 /若是返回ob2在ob1中的起始位置，否則返回-1 if(pos<0|pos>ob1.curLen) /若輸入的數(shù)值pos不在ob1的串長(zhǎng)范圍內(nèi)printf("輸入有誤n");exit(ERROR);for(int i=pos-1; i<=StrLength(ob1)-StrLength(ob2); i+) /從ob1的第pos個(gè)字符起查找子串ob2int j=0; /從ob2的第一個(gè)字符起開(kāi)始查找 while(j<StrLength(ob2) /j控制查找位置，逐個(gè)字符查找，直

11、到超出子串串長(zhǎng)if(ob1.chi+j=ob2.chj) /若找到匹配字符j+; /則依次向后查找else break; /一旦失配，則跳出查找，此時(shí)j還未能達(dá)到子串串長(zhǎng)if(j=StrLength(ob2) /若j達(dá)到子串串長(zhǎng)，即ob2的所有字符都能和ob1匹配return i; /返回ob2在ob1的起始位置i return -1; /ob2不是ob1的子串，返回-1(4)串替換void Replace(HString &ob1,HString &ob2,HString &ob3) /將原串ob1的所有子串ob2都替換為插入串ob3printf("原串：&

12、quot;); for(int i=0; i<ob1.curLen; i+)printf("%c",ob1.chi); printf("n 子串："); for(int j=0; j<ob2.curLen; j+)printf("%c",ob2.chj); printf("n"); printf("插入串："); for(int k=0; k<ob3.curLen; k+)printf("%c",ob3.chk); printf("n")

13、; int len=StrLength(ob2); /ob2的長(zhǎng)度 while(Index(ob1,ob2,0)!=-1) /當(dāng)ob2是ob1的子串，替換所有的ob2 int len2=StrLength(ob3)+StrLength(ob1)-StrLength(ob2); /新串的長(zhǎng)度int i=Index(ob1,ob2,0); /調(diào)用子串定位函數(shù)char *p=new charStrLength(ob1)-i-len+1; /臨時(shí)數(shù)組char *q=new charlen2; /存儲(chǔ)新串的數(shù)組 for(int j=i+len; j<StrLength(ob1); j+)pj=ob

14、1.chj; /將不用替換的后部分存入數(shù)組pfor(int k=0; k<i; k+)qk=ob1.chk; /將不用替換的前部分存入數(shù)組qfor(int m=i; m<i+StrLength(ob3); m+)qm=ob3.chm-i; /替換子串int b=i+len;for(int n=i+StrLength(ob3); n<len2; n+) /將不用替換的后部分存入數(shù)組qqn=pb;b+; /數(shù)組q存儲(chǔ)著新串 ob1.curLen=len2;for(int l=0; l<len2; l+)ob1.chl=ql; /將新串賦值給ob1做循環(huán)替換printf(&q

15、uot;新串："); for(int h=0; h<ob1.curLen; h+)printf("%c",ob1.chh); (5)串比較int Compare(HString s1, HString s2)/若s1<s2則返回值<0; 若s1=s2則返回值=0; 若s1>s2則返回值>0int i;for(i=0; i<s1.curLen&&i<s2.curLen; +i)if(s1.chi!=s2.chi)return (s1.chi-s2.chi);return (s1.curLen-s2.curLe

16、n);五、測(cè)試分析系統(tǒng)運(yùn)行主界面如圖1所示。各子系統(tǒng)測(cè)試運(yùn)行結(jié)果如下。1. 賦值（A-Assign）在主菜單下，輸入A hello!并回車，運(yùn)行結(jié)果如圖4所示。圖4字符串賦值2. 求長(zhǎng)度（L-Lengh）在主菜單下，輸入L student并回車，運(yùn)行結(jié)果如圖5所示。圖5求字符串長(zhǎng)度3. 求子串（S-SubString）在主菜單下，輸入S student 2 5 并回車，運(yùn)行結(jié)果如圖6所示。圖6求子串4. 子串定位（I-Index）在主菜單下，分別輸入I microsoftvisualc+ soft 1并回車和I microsoftvisualc+ soft 8，運(yùn)行結(jié)果如圖7所示。圖7子串定位

17、5. 替換（R-Replace）在主菜單下，輸入R chicken c t并回車，運(yùn)行結(jié)果如圖8所示。圖8字符串替換6. 判相等（C-Compare）在主菜單下，分別輸入C on in并回車和C on on并回車，運(yùn)行結(jié)果如圖9所示。圖9判兩串相等7. 退出（Q-Quit）在主菜單下，輸入Q并回車，退出串基本操作演示系統(tǒng)。六、用戶手冊(cè) (1)本程序執(zhí)行文件為“串的基本操作演示.exe”。(2)進(jìn)入本系統(tǒng)之后，隨即顯示系統(tǒng)主菜單界面。用戶可在該界面下按提示信息輸入命令。七、調(diào)試報(bào)告(1) 我不喜歡敲代碼，寫(xiě)一個(gè)簡(jiǎn)單的程序時(shí)竟然老是出錯(cuò)，難一點(diǎn)的，復(fù)雜一點(diǎn)的程序竟然無(wú)從下手，程序的架構(gòu)根本不懂，以

18、至于程序存在許多bug，不過(guò)只要按著提示操作，還是可以完成相應(yīng)的功能。(2)如果有興趣還可以對(duì)次程序進(jìn)行深入研究，進(jìn)行修改，添加等一些串的其他功能。八、程序清單#include <stdlib.h>#include <iostream>#include <conio.h>#define OK 1#define OVERFLOW 0 #define ERROR 0using namespace std; /使用名稱空間std/*串的堆分配存儲(chǔ)表示typedef struct char *ch; /串存放的數(shù)組 int curLen; /串的長(zhǎng)度HString;

19、/*1. 初始化字符串T int initString(HString *T) (*T).ch=NULL;(*T).curLen=0;return OK;/*2. 串賦值函數(shù)int strAssign(HString *T,char *chars) /生成一個(gè)值等于串常量chars的串T并用指針?lè)祷?*chars為指針(數(shù)組名) int i,j; if(*T).ch) free(*T).ch); /釋放T原有空間 i=strlen(chars); /數(shù)組chars的長(zhǎng)度 if(!i) /若chars為空串，生成空串的堆分配存儲(chǔ)表示 (*T).ch=NULL; (*T).curLen=0; el

20、se / chars不為空串 if(!(*T).ch=(char *)malloc(i*sizeof(char) exit(OVERFLOW); /分配串的堆空間，若失敗則退出 for(j=0; j<i; j+) (*T).chj=charsj; (*T).curLen=i; return OK;/*3. 求串長(zhǎng)函數(shù)int StrLength(HString S) return S.curLen; /直接返回串長(zhǎng)/*4. 求子串函數(shù)int substring(HString &Sub,HString S,int pos,int len)/串Sub返回串S的第pos個(gè)字符起長(zhǎng)度為l

21、en的子串int i;if(pos<0|pos>S.curLen|len<0|len>S.curLen-pos) /若位置或長(zhǎng)度不合法，退出printf("輸入不合法n"); exit(OVERFLOW); /退出elseif(Sub.ch) free(Sub.ch); /釋放子串sub原有空間if(!len) /若長(zhǎng)度len為0 /將子串置為空串Sub.ch=NULL;Sub.curLen=0;else /若長(zhǎng)度len不為0Sub.ch=(char*)malloc(len*sizeof(char);for(i=0; i<len; i+) /從

22、串S的第pos個(gè)字符開(kāi)始依次復(fù)制其后長(zhǎng)度為len的字符串到串Sub中Sub.chi=S.chpos-1+i; Sub.curLen=len; /修改串Sub的串長(zhǎng)return OK;/*5. 子串定位函數(shù)（串的模式匹配）int Index(HString &ob1,HString &ob2,int pos) /判斷從第pos個(gè)字符起，ob2是否為ob1的子串/若是返回ob2在ob1中的起始位置，否則返回-1 if(pos<0|pos>ob1.curLen) /若輸入的數(shù)值pos個(gè)字符起，ob2是否為ob1的子串printf("輸入有誤n");ex

23、it(ERROR);for(int i=pos-1; i<=StrLength(ob1)-StrLength(ob2); i+) /從ob1的第pos個(gè)字符起查找子串ob2int j=0; /從ob2的第一個(gè)字符起開(kāi)始查找 while(j<StrLength(ob2) /j控制查找位置，逐個(gè)字符查找，直到超出子串串長(zhǎng)if(ob1.chi+j=ob2.chj) /若找到匹配字符j+; /則依次向后查找else break; /一旦失配，則跳出查找，此時(shí)j還未能達(dá)到子串串長(zhǎng)if(j=StrLength(ob2) /若j達(dá)到子串串長(zhǎng)，即ob2的所有字符都能和ob1匹配return i;

24、/返回ob2在ob1的起始位置i return -1; /ob2不是ob1的子串，返回-1/*6. 串替換函數(shù)void Replace(HString &ob1,HString &ob2,HString &ob3) /將原串ob1的所有子串ob2都替換為插入串ob3printf("原串："); for(int i=0; i<ob1.curLen; i+)printf("%c",ob1.chi); printf("n子串："); for(int j=0; j<ob2.curLen; j+)printf

25、("%c",ob2.chj); printf("n"); printf("插入串："); for(int k=0; k<ob3.curLen; k+)printf("%c",ob3.chk); printf("n"); int len=StrLength(ob2); /ob2的長(zhǎng)度 while(Index(ob1,ob2,0)!=-1) /當(dāng)ob2是ob1的子串，替換所有的ob2 int len2=StrLength(ob3)+StrLength(ob1)-StrLength(ob2);

26、/新串的長(zhǎng)度int i=Index(ob1,ob2,0); /調(diào)用子串定位函數(shù)char *p=new charStrLength(ob1)-i-len+1; /臨時(shí)數(shù)組char *q=new charlen2; /存儲(chǔ)新串的數(shù)組 for(int j=i+len; j<StrLength(ob1); j+)pj=ob1.chj; /將不用替換的后部分存入數(shù)組pfor(int k=0; k<i; k+)qk=ob1.chk; /將不用替換的前部分存入數(shù)組qfor(int m=i; m<i+StrLength(ob3); m+)qm=ob3.chm-i; /替換子串int b=i+

27、len;for(int n=i+StrLength(ob3); n<len2; n+) /將不用替換的后部分存入數(shù)組qqn=pb;b+; /數(shù)組q存儲(chǔ)著新串 ob1.curLen=len2;for(int l=0; l<len2; l+)ob1.chl=ql; /將新串賦值給ob1做循環(huán)替換printf("新串："); for(int h=0; h<ob1.curLen; h+)printf("%c",ob1.chh); /*7. 串比較函數(shù)int Compare(HString s1, HString s2)/若s1<s2則返回

28、值<0; 若s1=s2則返回值=0; 若s1>s2則返回值>0int i;for(i=0; i<s1.curLen&&i<s2.curLen; +i)if(s1.chi!=s2.chi)return (s1.chi-s2.chi);return (s1.curLen-s2.curLen);/8. 主函數(shù)void main() printf("*串基本操作演示系統(tǒng)*n"); printf("* . 賦值 格式為: A 串值 *n"); printf("* . 求長(zhǎng)度 格式為: L 串值 *n"

29、;); printf("* . 求子串 格式為: S 串值 數(shù)1 數(shù)2 *n"); printf("* . 子串定位 格式為: I 串值1 串值2 數(shù)1 *n"); printf("* . 串替換 格式為: R 串值1 串值2 串值3 *n"); printf("* . 串比較 格式為: C 串值1 串值2 *n"); printf("* . 退出 格式為: Q *n"); printf("*n"); while(1)char c;printf("請(qǐng)看菜單輸入您要進(jìn)

30、行的操作并回車(全部用大寫(xiě)):"); cin>>c; /輸入大寫(xiě)字母 if(c='Q') break; /退出串基本操作演示系統(tǒng) switch(c) /用switch語(yǔ)句對(duì)輸入的大寫(xiě)字母進(jìn)行多向選擇 case'A': char cnew50; HString str; initString(&str); /初始化串str scanf("%s",cnew); strAssign(&str,cnew); /調(diào)用串生成函數(shù) printf("字符串為:"); for(int i=0;i <

31、;str.curLen; i+) printf("%c",str.chi); printf("n"); break; case 'L': char cnew50; scanf("%s",cnew); HString str; initString(&str); /初始化串str strAssign(&str,cnew); /調(diào)用串生成函數(shù) printf("長(zhǎng)度為：%dn",StrLength(str); /調(diào)用StrLength函數(shù) break; case 'S':

32、char cnew50; int pos,len; cin>>cnew>>pos>>len; HString sub,str; initString(&sub); /初始化串sub initString(&str); /初始化串str strAssign(&str,cnew); /調(diào)用串生成函數(shù) substring(sub,str,pos,len); /調(diào)用子串函數(shù) printf("子串為:"); for(int i=0; i<sub.curLen; i+) printf("%c",sub.chi); printf("n"); break; case '