第4章串習題練習答案

簡述下列每對術語的區別
　　空串和空白串串常量和串變量主串和子串靜態分配的順序串和動態分配的順序串目標串和模式串有效位移和無效位移

答
　●空串是指不包含任何字符的串它的長度為零
　　空白串是指包含一個或多個空格的串空格也是字符

　●串常量是指在程序中只可引用但不可改變其值的串
　　串變量是可以在運行中改變其值的

　●主串和子串是相對的一個串中任意個連續字符組成的串就是這個串的子串而包含子串的串就稱為主串

　●靜態分配的順序串是指串的存儲空間是確定的即串值空間的大小是靜態的在編譯時刻就被確定
　　動態分配的順序串是在編譯時不分配串值空間在運行過程中用malloc和free等函數根據需要動態地分配和釋放字符數組的空間(這個空間長度由分配時確定也是順序存儲空間)

　●目標串和模式串:在串匹配運算過程中將主串稱為目標串而將需要匹配的子串稱為模式串兩者是相對的

　●有效位移和無效位移在串定位運算中模式串從目標的首位開始向右位移每一次合法位移後如果模式串與目標中相應的字符相同則這次位移就是有效位移(也就是從此位置開始的匹配成功)反之若有不相同的字符存在則此次位移就是無效位移(也就是從此位置開始的匹配失敗)

假設有如下的串說明

　　char s[]=StocktomCA s[]=March s[] *p;

　()在執行如下的每個語句後p的值是什麼?
　　p=stchr(st); p=strchr(s); p=strchr(s);
　()在執行下列語句後s的值是什麼?
　　strcpy(ss); strcat(s); strcat(ss);
　()調用函數strcmp(ss)的返回值是什麼?
　()調用函數strcmp(&s[]ton)的返回值是什麼?
　()調用函數stlen(strcat(ss))的返回值是什麼?

解
　() stchr(*sc)函數的功能是查找字符c在串s中的位置若找到則返回該位置否則返回NULL
　因此:
　　執行p=stchr(st);後p的值是指向第一個字符t的位置 也就是p==&s[]
　　執行p=strchr(s);後p的值是指向s串中第一個所在的位置也就是p==&s[]
` 　執行p=strchr(s);之後p的返回值是NULL

　()strcpy函數功能是串拷貝strcat函數的功能是串聯接所以:
　　在執行strcpy(ss); 後s的值是StocktomCA
　　在執行strcat(s); 後s的值變成StocktomCa
　　在執行完strcat(ss);後s的值就成了StocktomCaMarch

　()函數strcmp(串串)的功能是串比較按串的大小進行比較返回大於等於或小於的值以表示串比串 大串等於串 串小於串因此在調用函數strcmp(ss)後返回值是大於的數(字符比較是以ascii碼值相比的)

　()首先我們要知道&s[]是一個地址當放在函數strcmp中時它就表示指向以它為首地址的一個字符串所以在strcmp( &s[]ton)中前一個字符串值是tomCA用它和ton比較應該是後者更大所以返回值是小於的數

　()strlen是求串長的函數我們先將ss聯接起來值是StocktomCAMarch 數一數有幾個字符?是不是個(空格也是一個)? 所以返回值是

設T[n]=adaabaabcaabaaP[m]=aab當用模式串匹配目標串T時請給出所有的有效位移算法NaiveStrMatch(TP)返回的位移是哪一個位移

解
　　所有的有效位移i的值為
　　算法NaveStrMatch(TP)的返回值是第一個有效位移因此是

利用C的庫函數strlenstrcpy和strcat寫一算法void StrInsert(char *S char *T int i)將串T插入到串S的第i個位置上若i大於S的長度則插入不執行

解
　　算法如下
　void StrInsert(char *S char *T int i)
　　{//將串T插入到串S的第i個位置上
　　　char *Temp;
　　　if(i<=strlen(S))
　　　　{
　　　　　Temp=(char *)malloc(sizeof(char[Maxsize]));// 設置一個臨時串 
　　　　　strcpy(Temp&S[i]);//將第i位起以後的字符拷貝到臨時串中
　　　　　strcpy(&S[i] T);//將串T拷貝到串S的第i個位置處覆蓋後面的字符
　　　　　strcat(STemp);//把臨時串中的字符聯接到串S後面
　　　　　free( Temp );
　　　　}
　　}

利用C的庫函數strlen 和strcpy(或strncpy)寫一算法void StrDelete(char *Sint i int m)刪去串S中從位置i開始的連續m個字符若i≥strlen(S)則沒有字符被刪除若i+m≥strlen(S)則將S中從位置i開始直至末尾的字符均刪去

解
　　算法如下
　void StrDelete(char *S int i int m)
　　{ //串刪除
　　　char Temp[Maxsize];//定義一個臨時串
　　　if(i+m<strlen(S)) 
　　　　{
　　　　　strcpy (Temp &S[i+m]);//把刪除的字符以後的字符保存到臨時串中
　　　　　strcpy( &S[i]Temp);//用臨時串中的字符覆蓋位置i之後的字符
　　　　}
　　　else if(i+m>=strlen(S)&& i<strlen(S))
　　　　{
　　　　　strcpy(&S[i]\);//把位置i的元素置為\表示串結束
　　　　}
　　}

以HString為存儲表示寫一個求子串的算法

解
　　HString 是指以動態分配順序串為存儲表示其定義為
　　　typedef struct {
　　　　char *ch;
　　　　int length;
　　　}HString;

　　void *substr( HString *subHString *sint posint len)
　　　{//用sub返回串s的第pos個字符起長度為len的子串sub初始時為一空串
　　　　//pos的合法位置為<=pos<=s>length
　　　　int i; 
　　　　if (pos<||pos>s>length||len<=)
　　　　　Error(parameter error!);//參數不合法子串為空串
　　　　if (s>length<pos+len)//s串中沒有足夠的元素
　　　　　sub>len=s>lengthpos;//設置子串的串長
　　　　else sub>length=len; //設置子串的串長 
　　　　sub>ch=(char *)malloc(len*sizeof(char));//為sub>ch申請結點空間
　　　　for(i=;i<sub>length;i++)//將s串中pos位置開始的共sub>length個字符復制到sub串中
　　　　　sub>ch[i]=s>ch[pos+i];
　　　}

一個文本串可用事先給定的字母映射表進行加密例如設字母映射表為

　　a b c d e f g h i j k l m n o p q r s t u v w x y z 

　　n g z q t c o b m u h e l k p d a w x f y i v r s j 

　　則字符串encrypt被加密為tkzwsdf試寫一算法將輸入的文本串進行加密後輸出另寫一算法將輸入的已加密的文本串進行解密後輸出

解
　　加密算法可以用兩個串中字符的一一對應關系來實現當輸入一個字符時由算法在串Original中查找其位置然後用串Cipher中相應位置的字符去替換原來的字符就可以了解密算法則恰恰相返
　　設字母映射表的存儲結構如下
　#define MaxStrSize
　typedef struct{
　　　char Original[MaxStrSize]; //可容納個字符並依次存儲在Original[n]中
　　　char Cipher[MaxStrSize]; //可容納個字符並依次對應Original表中的密碼
　　　int length;
　　}SeqString; 

　void Encrypt( SeqString codetable)
　　{//加密算法
　　　char ch;
　　　int i;
　　　while((ch=getchar())!=\)
　　　　{ i=;
　　　　　while (i<codetablelength&&ch!=codetableOriginal[i])
　　　　　　　i++;
　　　　　if (i>=codetablelength)
　　　　　　　Error(data error!);
　　　　　else 
　　　　　　　printf(%ccodetableCipher[i]);
　　　　}
　　　printf(\n);
　　}

　void Decipher(SeqString Original SeqString Cipher char* T)
　　{//解密算法
　　　char ch;
　　　while((ch=getchar())!=\)
　　　　{ i=;
　　　　　while (i<codetablelength&&ch!=codetableCipher[i])
　　　　　　　i++;
　　　　　if (i>=codetablelength)
　　　　　　　Error(data error!);
　　　　　else 
　　　　　　　printf(%ccodetableOriginal[i]);
　　　　}
　　　printf(\n);
　　}

寫一算法void StrReplace(char *T char *P char *S)將T中首次出現的子串P替換為串S注意S和P的長度不一定相等可以使用已有的串操作

解
　　由於S和P的長度不一定相等所以在替換時可能要移動字符元素我們可以用到前面設計的一系列算法算法如下
　void StrReplace (char *T char *P char *S)
　　{//串替換
　　　int i m;
　　　m=strlen (P);//取得子串長度
　　　i=StrMatch(TP);//取得串匹配位置
　　　StrDelete( T
From:http://tw.wingwit.com/Article/program/sjjg/201311/23952.html