《數(shù)據(jù)結(jié)構(gòu)——C語言描述》習題及答案 耿國華

1、【精品文檔】如有侵權，請聯(lián)系網(wǎng)站刪除，僅供學習與交流數(shù)據(jù)結(jié)構(gòu)C語言描述習題及答案 耿國華.精品文檔.第1章 緒 論習題一、問答題1. 什么是數(shù)據(jù)結(jié)構(gòu)？2. 四類基本數(shù)據(jù)結(jié)構(gòu)的名稱與含義。3. 算法的定義與特性。4. 算法的時間復雜度。5. 數(shù)據(jù)類型的概念。6. 線性結(jié)構(gòu)與非線性結(jié)構(gòu)的差別。7. 面向?qū)ο蟪绦蛟O計語言的特點。8. 在面向?qū)ο蟪绦蛟O計中，類的作用是什么？9. 參數(shù)傳遞的主要方式及特點。10. 抽象數(shù)據(jù)類型的概念。二、判斷題1. 線性結(jié)構(gòu)只能用順序結(jié)構(gòu)來存放，非線性結(jié)構(gòu)只能用非順序結(jié)構(gòu)來存放。2. 算法就是程序。3. 在高級語言（如C、或 PASCAL）中，指針類型是原子類型。三、計

2、算下列程序段中X=X+1的語句頻度for(i=1;i=n;i+) for(j=1;j=i;j+)for(k=1;k=j;k+) x=x+1;提示： i=1時： 1 = (1+1)1/2 = (1+12)/2 i=2時： 1+2 = (1+2)2/2 = (2+22)/2 i=3時： 1+2+3 = (1+3)3/2 = (3+32)/2 i=n時： 1+2+3+n = (1+n)n/2 = (n+n2)/2f(n) = (1+2+3+n) + (12 + 22 + 32 + + n2 ) / 2 = (1+n)n/2 + n(n+1)(2n+1)/6 / 2 =n(n+1)(n+2)/6 =n

3、3/6+n2/2+n/3區(qū)分語句頻度和算法復雜度：O(f(n) = O(n3)四、試編寫算法求一元多項式Pn(x)=a0+a1x+a2x2+a3x3+anxn的值Pn(x0)，并確定算法中的每一語句的執(zhí)行次數(shù)和整個算法的時間復雜度，要求時間復雜度盡可能的小，規(guī)定算法中不能使用求冪函數(shù)。注意：本題中的輸入ai(i=0,1,n), x和n，輸出為Pn(x0).通常算法的輸入和輸出可采用下列兩種方式之一：（1） 通過參數(shù)表中的參數(shù)顯式傳遞；（2） 通過全局變量隱式傳遞。試討論這兩種方法的優(yōu)缺點，并在本題算法中以你認為較好的一種方式實現(xiàn)輸入和輸出。提示：float PolyValue(float a

4、, float x, int n) 核心語句：p=1; (x的零次冪)s=0;i從0到n循環(huán)s=s+ai*p; p=p*x; 或：p=x; (x的一次冪)s=a0;i從1到n循環(huán)s=s+ai*p; p=p*x; 實習題設計實現(xiàn)抽象數(shù)據(jù)類型“有理數(shù)”。基本操作包括有理數(shù)的加法、減法、乘法、除法，以及求有理數(shù)的分子、分母。第一章答案1.3計算下列程序中x=x+1的語句頻度 for(i=1;i=n;i+)for(j=1;j=i;j+) for(k=1;k=j;k+) x=x+1; 【解答】x=x+1的語句頻度為：T(n)=1+(1+2)+（1+2+3）+（1+2+n）=n(n+1)(n+2)/61.

5、4試編寫算法，求pn(x)=a0+a1x+a2x2+.+anxn的值pn(x0),并確定算法中每一語句的執(zhí)行次數(shù)和整個算法的時間復雜度，要求時間復雜度盡可能小，規(guī)定算法中不能使用求冪函數(shù)。注意：本題中的輸入為ai(i=0,1,n)、x和n,輸出為Pn(x0)。 算法的輸入和輸出采用下列方法（1）通過參數(shù)表中的參數(shù)顯式傳遞（2）通過全局變量隱式傳遞。討論兩種方法的優(yōu)缺點，并在算法中以你認為較好的一種實現(xiàn)輸入輸出?！窘獯稹浚?）通過參數(shù)表中的參數(shù)顯式傳遞 優(yōu)點：當沒有調(diào)用函數(shù)時，不占用內(nèi)存，調(diào)用結(jié)束后形參被釋放，實參維持，函數(shù)通用性強，移置性強。 缺點：形參須與實參對應，且返回值數(shù)量有限。（2）通

6、過全局變量隱式傳遞 優(yōu)點：減少實參與形參的個數(shù)，從而減少內(nèi)存空間以及傳遞數(shù)據(jù)時的時間消耗 缺點：函數(shù)通用性降低，移植性差算法如下：通過全局變量隱式傳遞參數(shù)PolyValue() int i,n;float x,a,p; printf(“nn=”); scanf(“%f”,&n); printf(“nx=”); scanf(“%f”,&x);for(i=0;in;i+) scanf(“%f ”,&ai); /*執(zhí)行次數(shù)：n次 */ p=a0; for(i=1;i=n;i+) p=p+ai*x; /*執(zhí)行次數(shù)：n次*/ x=x*x;printf(“%f”,p);算法的時間復雜度：T(n)=O(n)

7、通過參數(shù)表中的參數(shù)顯式傳遞float PolyValue(float a , float x, int n)float p,s;int i;p=x; s=a0;for(i=1;inext=S;（2）P-next= P-next-next;（3）P-next= S-next;（4）S-next= P-next;（5）S-next= L;（6）S-next= NULL;（7）Q= P;（8）while(P-next!=Q) P=P-next;（9）while(P-next!=NULL) P=P-next;（10）P= Q;（11）P= L;（12）L= S;（13）L= P;2.4 已知線性表L遞

8、增有序。試寫一算法，將X插入到L的適當位置上，以保持線性表L的有序性。提示：void insert(SeqList *L; ElemType x) （1）找出應插入位置i，（2）移位，（3） 參P. 2292.5 寫一算法，從順序表中刪除自第i個元素開始的k個元素。提示：注意檢查i和k的合法性。 （集體搬遷，“新房”、“舊房”） 以待移動元素下標m（“舊房號”）為中心，計算應移入位置（“新房號”）： for ( m= i1+k; mlast; m+) Lelem mk = Lelem m ; 同時以待移動元素下標m和應移入位置j為中心： 以應移入位置j為中心，計算待移動元素下標：2.6已知線性

9、表中的元素（整數(shù)）以值遞增有序排列，并以單鏈表作存儲結(jié)構(gòu)。試寫一高效算法，刪除表中所有大于mink且小于maxk的元素（若表中存在這樣的元素），分析你的算法的時間復雜度（注意：mink和maxk是給定的兩個參變量，它們的值為任意的整數(shù)）。 提示：注意檢查mink和maxk的合法性：mink next;while (p!=NULL & pdata next; （2）找到最后一個應刪結(jié)點的后繼s，邊找邊釋放應刪結(jié)點s=p;while (s!=NULL & sdata next; free(t); （3）prenext = s;2.7 試分別以不同的存儲結(jié)構(gòu)實現(xiàn)線性表的就地逆置算法，即在原表的存儲空

10、間將線性表（a1, a2., an）逆置為（an, an-1,., a1）。（1）以一維數(shù)組作存儲結(jié)構(gòu)，設線性表存于a(1:arrsize)的前elenum個分量中。（2）以單鏈表作存儲結(jié)構(gòu)。方法1：在原頭結(jié)點后重新頭插一遍方法2：可設三個同步移動的指針p, q, r，將q的后繼r改為p2.8 假設兩個按元素值遞增有序排列的線性表A和B，均以單鏈表作為存儲結(jié)構(gòu)，請編寫算法，將A表和B表歸并成一個按元素值遞減有序的排列的線性表C，并要求利用原表（即A表和B表的）結(jié)點空間存放表C.提示：參P.28 例2-1void merge(LinkList A; LinkList B; LinkList *C

11、)pa=Anext; pb=Bnext; *C=A; (*C)next=NULL;while ( pa!=NULL & pb!=NULL )if ( padata data )smaller=pa; pa=panext; smallernext = (*C)next; /* 頭插法 */ (*C)next = smaller;elsesmaller=pb; pb=pbnext; smallernext = (*C)next; (*C)next = smaller;while ( pa!=NULL)smaller=pa; pa=panext; smallernext = (*C)next; (*

12、C)next = smaller;while ( pb!=NULL)smaller=pb; pb=pbnext; smallernext = (*C)next; (*C)next = smaller;LinkList merge(LinkList A; LinkList B)LinkList C；pa=Anext; pb=Bnext; C=A; Cnext=NULL; return C;2.9 假設有一個循環(huán)鏈表的長度大于1，且表中既無頭結(jié)點也無頭指針。已知s為指向鏈表某個結(jié)點的指針，試編寫算法在鏈表中刪除指針s所指結(jié)點的前趨結(jié)點。提示：設指針p指向s結(jié)點的前趨的前趨，則p與s有何關系？2.1

13、0 已知有單鏈表表示的線性表中含有三類字符的數(shù)據(jù)元素（如字母字符、數(shù)字字符和其它字符），試編寫算法來構(gòu)造三個以循環(huán)鏈表表示的線性表，使每個表中只含同一類的字符，且利用原表中的結(jié)點空間作為這三個表的結(jié)點空間，頭結(jié)點可另辟空間。2.11 設線性表A=(a1, a2,am)，B=(b1, b2,bn)，試寫一個按下列規(guī)則合并A、B為線性表C的算法，使得： C= (a1, b1,am, bm, bm+1, ,bn) 當mn時；或者 C= (a1, b1,an, bn, an+1, ,am) 當mn時。線性表A、B、C均以單鏈表作為存儲結(jié)構(gòu)，且C表利用A表和B表中的結(jié)點空間構(gòu)成。注意：單鏈表的長度值m和

14、n均未顯式存儲。提示：void merge(LinkList A; LinkList B; LinkList *C) 或：LinkList merge(LinkList A; LinkList B)2.12 將一個用循環(huán)鏈表表示的稀疏多項式分解成兩個多項式，使這兩個多項式中各自僅含奇次項或偶次項，并要求利用原鏈表中的結(jié)點空間來構(gòu)成這兩個鏈表。提示：注明用頭指針還是尾指針。2.13 建立一個帶頭結(jié)點的線性鏈表，用以存放輸入的二進制數(shù)，鏈表中每個結(jié)點的data域存放一個二進制位。并在此鏈表上實現(xiàn)對二進制數(shù)加1的運算 。提示：可將低位放在前面。2.14 設多項式P(x)采用課本中所述鏈接方法存儲。寫

15、一算法，對給定的x值，求P(x)的值。提示：float PolyValue(Polylist p; float x) 實習題1 將若干城市的信息存入一個帶頭結(jié)點的單鏈表，結(jié)點中的城市信息包括城市名、城市的位置坐標。要求：（1） 給定一個城市名，返回其位置坐標；（2） 給定一個位置坐標P和一個距離D，返回所有與P的距離小于等于D的城市。2 約瑟夫環(huán)問題。約瑟夫問題的一種描述是：編號為1，2，n的n個人按順時針方向圍坐一圈，每人持有一個密碼（正整數(shù)）。一開始任選一個整數(shù)作為報數(shù)上限值m,從第一個人開始順時針自1開始順序報數(shù)，報到m時停止報數(shù)。報m的人出列，將他的密碼作為新的m值，從他在順時針方向上

16、的下一個人開始重新從1報數(shù)，如此下去，直至所有的人全部出列為止。試設計一個程序，求出出列順序。利用單向循環(huán)鏈表作為存儲結(jié)構(gòu)模擬此過程，按照出列順序打印出各人的編號。例如m的初值為20；n=7，7個人的密碼依次是：3，1，7，2，4，8，4，出列的順序為6，1，4，7，2，3，5。第二章 答案實習題二：約瑟夫環(huán)問題約瑟夫問題的一種描述為：編號1,2,n的n個人按順時針方向圍坐一圈，每個人持有一個密碼（正整數(shù)）。一開始任選一個報數(shù)上限值m,從第一個人開始順時針自1開始順序報數(shù)，報到m時停止報數(shù)。報m的人出列，將他的密碼作為新的m值，從他在順時針方向上的下一個人開始重新從1報數(shù)，如此下去，直至所有的

17、人全部出列為止。試設計一個程序，求出出列順序。利用單向循環(huán)鏈表作為存儲結(jié)構(gòu)模擬此過程，按照出列順序打印出各人的編號。例如，m的初值為20；n=7，7個人的密碼依次是：3,1,7,2,4,8,4，出列順序為6,1,4,7,2,3,5?！窘獯稹克惴ㄈ缦拢簍ypedef struct Nodeint password;int num;struct Node *next; Node,*Linklist;void Josephus() Linklist L; Node *p,*r,*q; int m,n,C,j; L=(Node*)malloc(sizeof(Node); /*初始化單向循環(huán)鏈表*/ i

18、f(L=NULL) printf(n鏈表申請不到空間!);return; L-next=NULL; r=L; printf(請輸入數(shù)據(jù)n的值(n0):); scanf(%d,&n); for(j=1;jpassword=C; p-num=j; r-next=p; r=p; r-next=L-next;printf(請輸入第一個報數(shù)上限值m(m0):); scanf(%d,&m); printf(*n); printf(出列的順序為:n); q=L; p=L-next; while(n!=1) /*計算出列的順序*/ j=1; while(jnext; j+; printf(%d-,p-num)

19、; m=p-password; /*獲得新密碼*/ n- -; q-next=p-next; /*p出列*/ r=p; p=p-next; free(r); printf(%dn,p-num);2.7試分別以不同的存儲結(jié)構(gòu)實現(xiàn)單線表的就地逆置算法，即在原表的存儲空間將線性表（a1,a2,an）逆置為(an,an-1,a1)?！窘獯稹浚?）用一維數(shù)組作為存儲結(jié)構(gòu) void invert(SeqList *L, int *num) int j; ElemType tmp;for (j=0;jnext =NULL) return; /*鏈表為空*/ p=L-next; q=p-next; p-nex

20、t=NULL; /* 摘下第一個結(jié)點，生成初始逆置表 */while(q!=NULL) /* 從第二個結(jié)點起依次頭插入當前逆置表 */r=q-next;q-next=L-next;L-next=q;q=r;2.11將線性表A=(a1,a2,am), B=(b1,b2,bn)合并成線性表C, C=(a1,b1,am,bm,bm+1,.bn) 當mn時,線性表A、B、C以單鏈表作為存儲結(jié)構(gòu)，且C表利用A表和B表中的結(jié)點空間構(gòu)成。注意：單鏈表的長度值m和n均未顯式存儲?！窘獯稹克惴ㄈ缦拢篖inkList merge(LinkList A, LinkList B, LinkList C)Node *p

21、a, *qa, *pb, *qb, *p; pa=A-next; /*pa表示A的當前結(jié)點*/ pb=B-next; p=A; / *利用p來指向新連接的表的表尾，初始值指向表A的頭結(jié)點*/while(pa!=NULL & pb!=NULL) /*利用尾插法建立連接之后的鏈表*/qa=pa-next; qb=qb-next; p-next=pa; /*交替選擇表A和表B中的結(jié)點連接到新鏈表中；*/p=pa;p-next=pb;p=pb; pa=qa;pb=qb;if(pa!=NULL) p-next=pa; /*A的長度大于B的長度*/ if(pb!=NULL) p-next=pb; /*B的

22、長度大于A的長度*/C=A; return(C);第3章 限定性線性表 棧和隊列習 題1. 按圖3.1(b)所示鐵道（兩側(cè)鐵道均為單向行駛道）進行車廂調(diào)度，回答： 如進站的車廂序列為123，則可能得到的出站車廂序列是什么？ 123、213、132、231、321（312） 如進站的車廂序列為123456，能否得到435612和135426的出站序列，并說明原因。（即寫出以“S”表示進棧、以“X”表示出棧的棧操作序列）。SXSS XSSX XXSX 或 S1X1S2S3X3S4S5X5X4X2S6X62. 設隊列中有A、B、C、D、E這5個元素，其中隊首元素為A。如果對這個隊列重復執(zhí)行下列4步操

23、作：（1） 輸出隊首元素；（2） 把隊首元素值插入到隊尾；（3） 刪除隊首元素；（4） 再次刪除隊首元素。直到隊列成為空隊列為止，則是否可能得到輸出序列：（1） A、C、E、C、C （2） A、C、E（3） A、C、E、C、C、C （4） A、C、E、C提示： A、B、C、D、E （輸出隊首元素A） A、B、C、D、E、A （把隊首元素A插入到隊尾） B、C、D、E、A （刪除隊首元素A） C、D、E、A （再次刪除隊首元素B） C、D、E、A （輸出隊首元素C） C、D、E、A、C （把隊首元素C插入到隊尾） D、E、A、C （刪除隊首元素C） E、A、C （再次刪除隊首元素D）3. 給出棧

24、的兩種存儲結(jié)構(gòu)形式名稱，在這兩種棧的存儲結(jié)構(gòu)中如何判別?？张c棧滿？4. 按照四則運算加、減、乘、除和冪運算（）優(yōu)先關系的慣例，畫出對下列算術表達式求值時操作數(shù)棧和運算符棧的變化過程： AB5. 試寫一個算法，判斷依次讀入的一個以為結(jié)束符的字母序列，是否為形如序列1&序列2模式的字符序列。其中序列1和序列2中都不含字符&，且序列2是序列1的逆序列。例如，a+b&b+a是屬該模式的字符序列，而+&則不是。提示：（1） 邊讀邊入棧，直到&（2） 邊讀邊出棧邊比較，直到6. 假設表達式由單字母變量和雙目四則運算算符構(gòu)成。試寫一個算法，將一個通常書寫形式（中綴）且書寫正確的表達式轉(zhuǎn)換為逆波蘭式（后綴）。

25、提示：例：中綴表達式：a+b 后綴表達式: ab+中綴表達式：a+bc 后綴表達式: abc+中綴表達式：a+bc-d 后綴表達式: abc+d-中綴表達式：a+bc-d/e 后綴表達式: abc+de/-中綴表達式：a+b(c-d)-e/f 后綴表達式: abcd-+ef/- 后綴表達式的計算過程：（簡便）順序掃描表達式，（1）如果是操作數(shù)，直接入棧；（2）如果是操作符op，則連續(xù)退棧兩次，得操作數(shù)X, Y，計算X op Y，并將結(jié)果入棧。 如何將中綴表達式轉(zhuǎn)換為后綴表達式？順序掃描中綴表達式，（1）如果是操作數(shù)，直接輸出；（2）如果是操作符op2，則與棧頂操作符op1比較：如果op2 op

26、1，則op2入棧；如果op2 = op1，則脫括號；如果op2 op1，則輸出op1；7. 假設以帶頭結(jié)點的循環(huán)鏈表表示隊列，并且只設一個指針指向隊尾元素結(jié)點（注意不設頭指針），試編寫相應的隊列初始化、入隊列和出隊列的算法。提示： 參P.56 P.70 先畫圖.typedef LinkList CLQueue;int InitQueue(CLQueue * Q)int EnterQueue(CLQueue Q, QueueElementType x)int DeleteQueue(CLQueue Q, QueueElementType *x)8. 要求循環(huán)隊列不損失一個空間全部都能得到利用,

27、設置一個標志域tag , 以tag為0或1來區(qū)分頭尾指針相同時的隊列狀態(tài)的空與滿，請編寫與此結(jié)構(gòu)相應的入隊與出隊算法。提示： 初始狀態(tài)：front=0, rear=0, tag=0 隊空條件：front=rear, tag=0 隊滿條件：front=rear, tag=1 其它狀態(tài)：front !=rear, tag=0（或1、2） 入隊操作：（入隊）if (front=rear) tag=1；（或直接tag=1）出隊操作：（出隊）tag=0；問題：如何明確區(qū)分隊空、隊滿、非空非滿三種情況？9. 簡述以下算法的功能（其中棧和隊列的元素類型均為int）：（1）void proc_1(Stack

28、S) iint i, n, A255; n=0; while(!EmptyStack(S)n+; Pop(&S, &An); for(i=1; itop=-1表示?？铡Ｅ袛鄺滿：如果S-top=Stack_Size-1表示棧滿。（2） 鏈棧（top為棧頂指針，指向當前棧頂元素前面的頭結(jié)點）判斷?？眨喝绻鹴op-next=NULL表示?？铡Ｅ袛鄺M：當系統(tǒng)沒有可用空間時，申請不到空間存放要進棧的元素，此時棧滿。3.4 照四則運算加、減、乘、除和冪運算的優(yōu)先慣例，畫出對下列表達式求值時操作數(shù)棧和運算符棧的變化過程：A-B*C/D+EF【解答】3.5 寫一個算法，判斷依次讀入的一個以為結(jié)束符的字母

29、序列，是否形如序列1&序列2的字符序列。序列1和序列2中都不含&，且序列2是序列1 的逆序列。例如，a+b&b+a是屬于該模式的字符序列，而1+3&3-1則不是。【解答】算法如下： int IsHuiWen() Stack *S; Char ch,temp; InitStack(&S); Printf(“n請輸入字符序列：”); Ch=getchar();While( ch!=&) /*序列1入棧*/Push(&S,ch); ch=getchar();do /*判斷序列2是否是序列1的逆序列*/ch=getchar(); Pop(&S,&temp); if(ch!= temp) /*序列2不是

30、序列1的逆序列*/ return(FALSE); printf(“nNO”); while(ch!= & !IsEmpty(&S)if(ch = = & IsEmpty(&S) return(TRUE); printf(“nYES”); /*序列2是序列1的逆序列*/else return(FALSE); printf(“nNO”); /*IsHuiWen()*/3.8 要求循環(huán)隊列不損失一個空間全部都能得到利用，設置一個標志tag,以tag為0或1來區(qū)分頭尾指針相同時的隊列狀態(tài)的空與滿，請編寫與此相應的入隊與出隊算法?！窘獯稹咳腙犓惴ǎ篿nt EnterQueue(SeqQueue *Q,

31、QueueElementType x) /*將元素x入隊*/ if(Q-front=Q-front & tag=1) /*隊滿*/ return(FALSE); if(Q-front=Q-front & tag=0) /*x入隊前隊空，x入隊后重新設置標志*/ tag=1;Q-elememtQ-rear=x;Q-rear=(Q-rear+1)%MAXSIZE; /*設置隊尾指針*/Return(TRUE);出隊算法： int DeleteQueue( SeqQueue *Q , QueueElementType *x) /*刪除隊頭元素，用x返回其值*/if(Q-front=Q-rear &

32、tag=0) /*隊空*/ return(FALSE);*x=Q-elementQ-front;Q-front=(Q-front+1)%MAXSIZE; /*重新設置隊頭指針*/if(Q-front=Q-rear) tag=0; /*隊頭元素出隊后隊列為空，重新設置標志域*/Return(TUUE); 編寫求解Hanoi問題的算法，并給出三個盤子搬動時的遞歸調(diào)用過程?！窘獯稹克惴ǎ?void hanoi (int n ,char x, char y, char z) /*將塔座X上按直徑由小到大且至上而下編號為1到n的n個圓盤按規(guī)則搬到塔座Z上，Y可用做輔助塔座*/ if(n = =1) mo

33、ve(x,1,z); else Hanoi(n-1,x,z,y); move(x, n, z); Hanoi(n-1, y,x,z);Hanoi(3,A,B,C)的遞歸調(diào)用過程：Hanoi(2,A,C,B): Hanoi(1,A,B,C) move(A-C) 1號搬到C Move(A-B) 2號搬到B Hanoi(1,C,A,B) move(C-B) 1號搬到B Move(A-C) 3號搬到CHanoi(2,B,A,C) Hanoi(1,B,C,A) move(B-A) 1號搬到A Move(B-C) 2號搬到C Hanoi(1,A,B,C) move(A-C) 1號搬到C第4章串習題1. 設

34、s=I AM A STUDENT, t=GOOD, q=WORKER。給出下列操作的結(jié)果：StrLength(s); SubString(sub1,s,1,7); SubString(sub2,s,7,1);StrIndex(s,A,4); StrReplace(s,STUDENT,q); StrCat(StrCat(sub1,t), StrCat(sub2,q);參考答案StrLength(s)=14; sub1= I AM A_; sub2= _; StrIndex(s,A,4)=6; StrReplace(s,STUDENT,q)= I AM A WORKER; StrCat(StrCa

35、t(sub1,t), StrCat(sub2,q)= I AM A GOOD WORKER;2. 編寫算法，實現(xiàn)串的基本操作StrReplace(S,T,V)。3. 假設以塊鏈結(jié)構(gòu)表示串，塊的大小為1，且附設頭結(jié)點。試編寫算法，實現(xiàn)串的下列基本操作：StrAsign(S,chars)； StrCopy(S,T)； StrCompare(S,T)； StrLength(S)； StrCat(S,T)； SubString(Sub,S,pos,len)。說明：用單鏈表實現(xiàn)。4. 敘述以下每對術語的區(qū)別：空串和空格串；串變量和串常量；主串和子串；串變量的名字和串變量的值。5. 已知：S=”(xyz)

36、*”,T=”(x+z)*y”。試利用聯(lián)接、求子串和置換等操作，將S轉(zhuǎn)換為T.6. S和T是用結(jié)點大小為1的單鏈表存儲的兩個串，設計一個算法將串S中首次與T匹配的子串逆置。7. S是用結(jié)點大小為4的單鏈表存儲的串,分別編寫算法在第k個字符后插入串T，及從第k個字符刪除len個字符。以下算法用定長順序串：8. 寫下列算法：（1） 將順序串r中所有值為ch1的字符換成ch2的字符。（2） 將順序串r中所有字符按照相反的次序仍存放在r中。（3） 從順序串r中刪除其值等于ch的所有字符。（4） 從順序串r1中第index 個字符起求出首次與串r2相同的子串的起始位置。（5） 從順序串r中刪除所有與串r1

37、相同的子串。9. 寫一個函數(shù)將順序串s1中的第i個字符到第j個字符之間的字符用s2串替換。提示：（1）用靜態(tài)順序串 （2）先移位，后復制10. 寫算法，實現(xiàn)順序串的基本操作StrCompare(s,t)。11. 寫算法，實現(xiàn)順序串的基本操作StrReplace(&s,t,v)。提示：（1）被替換子串定位（相當于第9題中i）（2）被替換子串后面的字符左移或右移（為替換子串準備房間）（3）替換子串入?。◤椭疲?）重復上述，直到第四章答案4.1 設s=I AM A STUDENT，t=GOOD， q=WORKER。給出下列操作的結(jié)果：【解答】StrLength(s)=14;SubString(su

38、b1,s,1,7) sub1=I AM A ;SubString(sub2,s,7,1) sub2= ;StrIndex(s,4,A)=6;StrReplace(s,STUDENT,q); s=I AM A WORKER;StrCat(StrCat(sub1,t),StrCat(sub2,q) sub1=I AM A GOOD WORKER。4.2編寫算法，實現(xiàn)串的基本操作StrReplace(S,T,V)。 【解答】算法如下：int strReplace(SString S,SString T, SString V)/*用串V替換S中的所有子串T */ int pos,i; pos=strI

39、ndex(S,1,T); /*求S中子串T第一次出現(xiàn)的位置*/ if(pos = = 0) return(0); while(pos!=0) /*用串V替換S中的所有子串T */ switch(T.len-V.len) case 0: /*串T的長度等于串V的長度*/ for(i=0;ichpos+i=V.chi; case 0: /*串T的長度大于串V的長度*/ for(i=pos+t.ien;ilen;i-) /*將S中子串T后的所有字符 S-chi-t.len+v.len=S-chi; 前移T.len-V.len個位置*/ for(i=0;ichpos+i=V.chi; S-len=S-len-T.len+V.len; case len-T.len+V.len)len-T.le