《數(shù)據(jù)結(jié)構(gòu)-C語(yǔ)言描述》習(xí)題及答案

第1章緒論ー、問(wèn)答題什么是數(shù)據(jù)結(jié)構(gòu)?四類基本數(shù)據(jù)結(jié)構(gòu)的名稱與含義。算法的定義與特性。4,算法的時(shí)間復(fù)雜度。數(shù)據(jù)類型的概念。線性結(jié)構(gòu)與非線性結(jié)構(gòu)的差別。面向?qū)ο蟪绦蛟O(shè)計(jì)語(yǔ)言的特點(diǎn)。在面向?qū)ο蟪绦蛟O(shè)計(jì)中，類的作用是什么?參數(shù)傳遞的主要方式及特點(diǎn)。抽象數(shù)據(jù)類型的概念。二、判斷題.線性結(jié)構(gòu)只能用順序結(jié)構(gòu)來(lái)存放，非線性結(jié)構(gòu)只能用非順序結(jié)構(gòu)來(lái)存放。.算法就是程序。.在高級(jí)語(yǔ)言(如C、或PASCAL)中，指針類型是原子類型。三、計(jì)算下列程序段中X=X+1的語(yǔ)句頻度f(wàn)or(i=l;i<=n;i++)for(j=l;j<=i;j++)for(k=l;k<=j;k++)x=x+l;［提示］:i=l時(shí):1=(l+l)xl/2=(l+r)/2i=2時(shí):1+2=(112)x2/2=(2+2?)/2i=3時(shí)：1+2+3=(1+3)x3/2=(3+32)/2i=n時(shí):1+2+3+ +n=(l+n)xn/2=(n+n2)/2f(n)=[(1+2+3+……+n)+(12+22+32+……+n2)]/2=[(l+n)n/2+n(n+l)(2n+l)/6]/2=n(n+l)(n+2)/6=n3/6+n2/2+n/3區(qū)分語(yǔ)句頻度和算法復(fù)雜度:O(f(n))=0(n3)四、試編寫算法求一元多項(xiàng)式Pn(x)=ao+aix+azx'+asxa…anx"的值Pn(xo)，并確定算法中的每ー語(yǔ)句的執(zhí)行次數(shù)和整個(gè)算法的時(shí)間復(fù)雜度，要求時(shí)間復(fù)雜度盡可能的小，規(guī)定算法中不能使用求森函數(shù)。注意:本題中的輸入ai(i=0,1,%n),x和n，輸出為Pn(xo),通常算法的輸入和輸出可采用下列兩種方式之一:(1)通過(guò)參數(shù)表中的參數(shù)顯式傳遞;(2)通過(guò)全局變量隱式傳遞。試討論這兩種方法的優(yōu)缺點(diǎn)，并在本題算法中以你認(rèn)為較好的ー種方式實(shí)現(xiàn)輸入和輸出〇[提示]:floatPolyValue(floata[],floatx,intn){ }核心語(yǔ)句:p=l;(x的零次幕)s=0;i從0到n循環(huán)s=s+a[i]*p;p=p*x;或:p=x;(X的一次嘉)s=a[0];i從1到n循環(huán)s=s+a[i]*p;P=P*x;實(shí)習(xí)題設(shè)計(jì)實(shí)現(xiàn)抽象數(shù)據(jù)類型“有理數(shù)”?；静僮靼ㄓ欣頂?shù)的加法、減法、乘法，除法，以及求有理數(shù)的分子、分母。第一章答案1.3計(jì)算下列程序中x=x+l的語(yǔ)句頻度f(wàn)or(i=l;i<=n;i++)for(j=l;j<=i;j++)for(k=l;k<=j;k++)x=x+l;【解答】x=x+l的語(yǔ)句頻度為:T(n)=l+(l+2)+(1+2+3)+……+(1+2+……+n)=n(n+l)(n+2)/6.4試編寫算法，求pr.(x)=ao+aix+azx2++a?x"的值pn(xo),并確定算法中每ー語(yǔ)句的執(zhí)行次數(shù)和整個(gè)算法的時(shí)間復(fù)雜度，要求時(shí)間復(fù)雜度盡可能小，規(guī)定算法中不能使用求寡函數(shù)。注意:本題中的輸入為ai(i=0,1,…n)、x和n,揄出為PKxo)。算法的輸入和輸出采用下列方法(1)通過(guò)參數(shù)表中的參數(shù)顯式傳遞(2)通過(guò)全局變量隱式傳遞。討論兩種方法的優(yōu)缺點(diǎn)，并在算法中以你認(rèn)為較好的ー種實(shí)現(xiàn)輸入輸出。【解答】(1)通過(guò)參數(shù)表中的參數(shù)顯式傳遞優(yōu)點(diǎn):當(dāng)沒有調(diào)用函數(shù)時(shí)，不占用存，調(diào)用結(jié)束后形參被釋放，實(shí)參維持，函數(shù)通用性強(qiáng)，移置性強(qiáng)。缺點(diǎn):形參須與實(shí)參對(duì)應(yīng)，且返回值數(shù)量有限。(2)通過(guò)全局變量隱式傳遞優(yōu)點(diǎn):減少實(shí)參與形參的個(gè)數(shù)，從而減少存空間以及傳遞數(shù)據(jù)時(shí)的時(shí)間消耗缺點(diǎn):函數(shù)通用性降低，移植性差算法如下:通過(guò)全局變量隱式傳遞參數(shù)PolyValueO{inti,n;floatx,a[],p;printf("\nn=");scanf("%f",&n);printf("\nx=");scanf("%f",&x);for(i=0;i<n;i++)scanf("%f",&a[i]); /*執(zhí)行次數(shù):n次?/P=a[0];for(i=l;i<=n;i++){p=p+a[i]*x; /*執(zhí)行次數(shù):n次?/x=x*x;}printf(,p);算法的時(shí)間復(fù)雜度:T(n)=O(n)通過(guò)參數(shù)表中的參數(shù)顯式傳遞floatPolyValue(floata[],floatx,intn)(floatp,s;inti;P=x;s二a[0];for(i=l;i<=n;i++){s=s+a[i]*p; /*執(zhí)行次數(shù):n次?/P=P*x;}return(p);)算法的時(shí)間復(fù)雜度:T(n)=0(n)第2章線性表習(xí)題.! 描述以下三個(gè)概念的區(qū)別:頭指針，頭結(jié)點(diǎn)，首元素結(jié)點(diǎn)。填空:在順序表中插入或刪除ー個(gè)元素，需要平均移動(dòng) 一半元素，具體移動(dòng)的元素個(gè)數(shù)與 插入或刪除的位置 有關(guān)?在順序表中，邏輯上相鄰的元素，其物理位置 相鄰。在單鏈表中，邏輯上相鄰的元素，其物理位置 相鄰。在帶頭結(jié)點(diǎn)的非空單鏈表中，頭結(jié)點(diǎn)的存儲(chǔ)位置由指示，首元素結(jié)點(diǎn)的存儲(chǔ)位置由指示，除首元素結(jié)點(diǎn)外，其它任一元素結(jié)點(diǎn)的存儲(chǔ)位置由其直接前趨的next域指示。已知L是無(wú)表頭結(jié)點(diǎn)的單鏈表，且P結(jié)點(diǎn)既不是首元素結(jié)點(diǎn)，也不是尾元素結(jié)點(diǎn)。按要求從下列語(yǔ)句中選擇合適的語(yǔ)句序列。a.在P結(jié)點(diǎn)后插入S結(jié)點(diǎn)的語(yǔ)句序列是:⑷、⑴ 。b.在P結(jié)點(diǎn)前插入S結(jié)點(diǎn)的語(yǔ)句序列是:(7)、(在)、(8)、(4)、(1)。c,在表首插入S結(jié)點(diǎn)的語(yǔ)句序列是:(5)、(12)。d,在表尾插入S結(jié)點(diǎn)的語(yǔ)句序列是:(11)、(9)、⑴、(6)。供選擇的語(yǔ)句有:P->next=S;P->next=P->next->next;P->next=S->next;S->next=P->next;S->next=L;S->next=NULL;Q=P;while(P->next!=Q)P=P->next;whi1e(P->next!=NULL)P=P->next;P=Q；P=L;L=S;L=P;已知線性表L遞增有序。試寫ー算法，將X插入到L的適當(dāng)位置上，以保持線性表L的有序性。[提示]:voidinsert(SeqList*L;ElemTypex)く方法1〉(1)找出應(yīng)插入位置i，(2)移位'(3)……く方法2>參P.229寫ー算法，從順序表中刪除自第i個(gè)元素開始的k個(gè)元素。[提示]:注意檢查i和k的合法性。(集體搬遷，"新房"'"舊房")方法1>以待移動(dòng)元素下標(biāo)m(“舊房號(hào)”)為中心，計(jì)算應(yīng)移入位置(“新房號(hào)”)：for(m=i—1+k;m<=L—>last;m++)L—>elem[m—k]=L—>elem[m];方法2>同時(shí)以待移動(dòng)元素下標(biāo)m和應(yīng)移入位置j為中心:方法3>以應(yīng)移入位置j為中心，計(jì)算待移動(dòng)元素下標(biāo):2.6已知線性表中的元素(整數(shù))以值遞增有序排列，并以單鏈表作存儲(chǔ)結(jié)構(gòu)。試寫一高效算法?刪除表中所有大于mink且小于maxk的元素(若表中存在這樣的元素)，分析你的算法的時(shí)間復(fù)雜度(注意:mink和maxk是給定的兩個(gè)參變量，它們的值為任意的整數(shù))。［提示］:注意檢查mink和maxk的合法性:mink<maxk不要一個(gè)ー個(gè)的刪除(多次修改next域)。(1)找到第一個(gè)應(yīng)刪結(jié)點(diǎn)的前驅(qū)prepre=L; p=L—>next;while(p!=NULL&&p—>data<=mink){pre=p;p=p—>next;}(2)找到最后ー個(gè)應(yīng)刪結(jié)點(diǎn)的后繼s，邊找邊釋放應(yīng)刪結(jié)點(diǎn)s=p;while(s!=NULL&&s—>data<maxk){t=s;s=s—>next;free(t);}(3)pre—>next=s;試分別以不同的存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)線性表的就地逆置算法，即在原表的存儲(chǔ)空間將線性表(ai,a2...,an)逆置為(an,an-i,...,ai)°(1)以ー維數(shù)組作存儲(chǔ)結(jié)構(gòu)，設(shè)線性表存于a(l:arrsize)的前elenum個(gè)分量中。(2)以單鏈表作存儲(chǔ)結(jié)構(gòu)。［方法I］:在原頭結(jié)點(diǎn)后重新頭插一遍［方法2］:可設(shè)三個(gè)同步移動(dòng)的指針p,q,r，將q的后繼r改為p假設(shè)兩個(gè)按元素值遞增有序排列的線性表A和B，均以單鏈表作為存儲(chǔ)結(jié)構(gòu)，請(qǐng)編寫算法，將A表和B表歸并成一個(gè)按元素值遞減有序的排列的線性表C，并要求利用原表(即A表和B表的)結(jié)點(diǎn)空間存放表C.［提示］:參P.28例2-1く方法1>voidmerge(LinkListA;LinkListB;LinkList*C)pa=A—>next;pb=B—>next;*C=A;(*C)ー)next二NULL;while(pa!=NULL&&pb!=NULL)if(pa—>data<=pb—>data)sma11er=pa;pa=pa—>next;/?頭插法?/smaller—/?頭插法?/(*C)—>next=smaller;}else(sma11er=pb;pb=pb—>next;smaller—>next=(*C)—>next;(*C)—>next=smaller;})while(pa!=NULL){sma11er=pa;pa=pa—>next;smaller—>next=(*C)—>next;(*C)—>next=smaller;Iwhile(pb!=NULL){sma11er=pb;pb=pb—>next;smaller—>next=(*C)—>next;(*C)—>next=smaller;)く方法2>LinkListmerge(LinkListA;LinkListB)LinkListC；pa=A—>next;pb=B—>next;C=A;C—>next=NULL;returnC;假設(shè)有一個(gè)循環(huán)鏈表的長(zhǎng)度大于1，且表中既無(wú)頭結(jié)點(diǎn)也無(wú)頭指針。已知s為指向鏈表某個(gè)結(jié)點(diǎn)的指針，試編寫算法在鏈表中刪除指針s所指結(jié)點(diǎn)的前趨結(jié)點(diǎn)。［提示］:設(shè)指針P指向S結(jié)點(diǎn)的前趨的前趨，則P與S有何關(guān)系?已知有單鏈表表示的線性表中含有三類字符的數(shù)據(jù)元素(如字母字符、數(shù)字字符和其它字符)，試編寫算法來(lái)構(gòu)造三個(gè)以循環(huán)鏈表表示的線性表，使每個(gè)表中只含同一類的字符，且利用原表中的結(jié)點(diǎn)空間作為這三個(gè)表的結(jié)點(diǎn)空間'頭結(jié)點(diǎn)可另辟空間。設(shè)線性表A=(ai,az,…,a.)，B=(b,レ,…，bn)，試寫ー個(gè)按下列規(guī)則合并A、B為線性表C的算法，使得:C=(ai,bi,?,,,a?,b?,tw…，bn)當(dāng)mWn時(shí);或者 C=(ai,bi,…，a”，bn,a?i,…,疝)當(dāng)m>n時(shí)。線性表A、B、C均以單鏈表作為存儲(chǔ)結(jié)構(gòu)，且C表利用A表和B表中的結(jié)點(diǎn)空間構(gòu)成。注意:單鏈表的長(zhǎng)度值m和n均未顯式存儲(chǔ)。［提示］:voidmerge(LinkListA;LinkListB;LinkList*C)或:LinkListmerge(LinkListA;LinkListB)將一個(gè)用循環(huán)鏈表表示的稀疏多項(xiàng)式分解成兩個(gè)多項(xiàng)式，使這兩個(gè)多項(xiàng)式中各自僅含奇次項(xiàng)或偶次項(xiàng)，并要求利用原鏈表中的結(jié)點(diǎn)空間來(lái)構(gòu)成這兩個(gè)鏈表。［提示］:注明用頭指針還是尾指針。建立一個(gè)帶頭結(jié)點(diǎn)的線性鏈表，用以存放輸入的二進(jìn)制數(shù)，鏈表中每個(gè)結(jié)點(diǎn)的data域存放一個(gè)二進(jìn)制位。并在此鏈表上實(shí)現(xiàn)對(duì)二進(jìn)制數(shù)加1的運(yùn)算。［提示］:可將低位放在前面。設(shè)多項(xiàng)式P(x)采用課本中所述方法存儲(chǔ)。寫ー算法，對(duì)給定的x值，求P(x)的值。［提示］:floatPolyValue(Polylistp;floatx)［ }實(shí)習(xí)題?將若干城市的信息存入ー個(gè)帶頭結(jié)點(diǎn)的單鏈表，結(jié)點(diǎn)中的城市信息包括城市名、城市的位置坐標(biāo)。要求：給定一個(gè)城市名，返回其位置坐標(biāo);給定一個(gè)位置坐標(biāo)P和一個(gè)距離D，返回所有與P的距離小于等于D的城市。2?約瑟夫環(huán)問(wèn)題。約瑟夫問(wèn)題的ー種描述是:編號(hào)為1，2，…，n的n個(gè)人按順時(shí)針方向圍坐一圈，每人持有一個(gè)密碼(正整數(shù))。ー開始任選ー個(gè)整數(shù)作為報(bào)數(shù)上限值m,從第一個(gè)人開始順時(shí)針自!開始順序報(bào)數(shù)，報(bào)到m時(shí)停止報(bào)數(shù)。報(bào)m的人出列，將他的密碼作為新的m值，從他在順時(shí)針方向上的下一個(gè)人開始重新從1報(bào)數(shù)，如此下去，直至所有的人全部出列為止。試設(shè)計(jì)ー個(gè)程序，求出出列順序。利用單向循環(huán)鏈表作為存儲(chǔ)結(jié)構(gòu)模擬此過(guò)程，按照出列順序打印出各人的編號(hào)。例如m的初值為20；n=7，7個(gè)人的密碼依次是:3T出列的順序?yàn)?，1，4,7,2,3,5。第二章答案實(shí)習(xí)題ニ:約瑟夫環(huán)冋題約瑟夫問(wèn)題的ー種描述為:編號(hào)1,2,…，n的n個(gè)人按順時(shí)針方向圍坐ー圈?每個(gè)人持有一個(gè)密碼(正整數(shù))。ー開始任選ー個(gè)報(bào)數(shù)上限值01,從第一個(gè)人開始順時(shí)針自1開始順序報(bào)數(shù)，報(bào)到m時(shí)停止報(bào)數(shù)。報(bào)m的人出列，將他的密碼作為新的m值，從他在順時(shí)針方向上的下一個(gè)人開始重新從1報(bào)數(shù)，如此下去，直至所有的人全部出列為止。試設(shè)計(jì)ー個(gè)程序，求出出列順序。利用單向循環(huán)鏈表作為存儲(chǔ)結(jié)構(gòu)模擬此過(guò)程，按照出列順序打印出各人的編號(hào)°例如，m的初值為20；n=7，7個(gè)人的密碼依次是:3,1,7,2,4,8,4，出列順序?yàn)?,1,4,7,2,3,5?！窘獯稹克惴ㄈ缦?typedefstructNode(intpassword;intnum;structNode*next;}Node,*Linklist;voidJosephusO{LinklistL;Node*p,*r,*q;intm,n,C,j;L=(Node*)ma11oc(sizeof(Node));/*初始化單向循環(huán)鏈表?/if(L==NULL){printf("\n鏈表申請(qǐng)不到空間!")；return;}L->next=NULL;

r=L;printf("請(qǐng)輸入數(shù)據(jù)n的值(n>0):");scanf(H%d",&n);for(j=l;j<=n;j++) /?建立鏈表?/(p=(Node*)malloc(sizeof(Node));if(p!=NULL){printf(w請(qǐng)輸入第％d個(gè)人的密碼:"，j);scanf(u%d\&C);p->password=C;p->num=j;r->next=p;r=p;)}r->next=L->next;printfC請(qǐng)輸入第一個(gè)報(bào)數(shù)上限值m(m>O):H);scanf(n%d\&m);printf(M****************糕***********************、ゼ)；printf("出列的順序?yàn)?\nH);q=L;p=L->next;while(n!=l) /*計(jì)算出列的順序?/{j=l；while(j<m) /?計(jì)算當(dāng)前出列的人選p*/q=p; /*q為當(dāng)前結(jié)點(diǎn)p的前驅(qū)結(jié)點(diǎn)?/p=p->next;j++；"獲得新密碼*/printf("獲得新密碼*/n-q->next=p->next; /*p出列*/r=p;p=p->next;free(r);)printf(M%d\n\p->num);}2.7試分別以不同的存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)單線表的就地逆置算法，即在原表的存儲(chǔ)空間將線性表(ai,a2,,,,,a?)逆置為(a[】,an-i,ai)°【解答】(1)用ー維數(shù)組作為存儲(chǔ)結(jié)構(gòu)voidinvert(SeqList禮,int*num)intj;ElemTypetmp;for(j=0;j<=(*num-l)/2;j++)(tmp=L[j];L[j]=L[*num-j-l];L[*num-j-l]=tmp;}}}(2)用單鏈表作為存儲(chǔ)結(jié)構(gòu)voidinvert(LinkListL){Node*p,*q,*r;if(L->next==NULL)return; /?鏈表為空?/p=L->next;q=p->next;p->next=NULL; /?摘下第一個(gè)結(jié)點(diǎn)，生成初始逆置表?/while(q!=NULL) /?從第二個(gè)結(jié)點(diǎn)起依次頭插入當(dāng)前逆置表?/r=q->next;q->next=L->next;Lー）next二q;q=r;2.11將線性表A=(al,a2,……am),B=(bl,b2,……bn)合并成線性表C,C=(al,bl, am,bm,bm+1, bn)當(dāng)mく=n時(shí)?或C=(al,bl, an,bn,an+1, am)當(dāng)m>n時(shí),線性表A、B、C以單鏈表作為存儲(chǔ)結(jié)構(gòu)，且C表利用A表和B表中的結(jié)點(diǎn)空間構(gòu)成。注意:單鏈表的長(zhǎng)度值m和n均未顯式存儲(chǔ)?！窘獯稹克惴ㄈ缦?LinkListmerge(LinkListA,LinkListB,LinkListC){Node米pa,*qa,*pb,*qb,*p;pa=A->next; /*pa表示A的當(dāng)前結(jié)點(diǎn)?/pb=B->next;p二A;/米利用p來(lái)指向新連接的表的表尾，初始值指向表A的頭結(jié)點(diǎn)?/while(pa!=NULL&&pb!=NULL) /?利用尾插法建立連接之后的鏈表*/(qa=pa->next;qb=qb->next;p->next=pa;/?交替選擇表A和表B中的結(jié)點(diǎn)連接到新鏈表中;*/p=pa;p->next=pb;p=pb;pa=qa;pb=qb;}if(pa!=NULL)p-〉next=pa; /*A的長(zhǎng)度大于B的長(zhǎng)度?/if(pb!二NULL)p->next=pb; /*B的長(zhǎng)度大于A的長(zhǎng)度?/C=A;return(C);第3章限定性線性表ー棧和隊(duì)列習(xí)題按圖3.1(b)所示鐵道(兩側(cè)鐵道均為單向行駛道)進(jìn)行車廂調(diào)度，回答:(1)如進(jìn)站的車廂序列為123，則可能得到的出站車廂序列是什么?123、213、132、231'321(312)(2)如進(jìn)站的車廂序列為123456，能否得到435612和135426的出站序列，并說(shuō)明原因。(即寫出以飛”表示進(jìn)棧、以“X”表示出棧的棧操作序列)。SXSSXSSXXXSX或S1X1S2S3X3S4S5X5X4X2S6X6設(shè)隊(duì)列中有A、B、C、D、E這5個(gè)元素，其中隊(duì)首元素為A。如果對(duì)這個(gè)隊(duì)列重復(fù)執(zhí)行下列4步操作:輸出隊(duì)首元素;把隊(duì)首元素值插入到隊(duì)尾;刪除隊(duì)首元素;再次刪除隊(duì)首元素。直到隊(duì)列成為空隊(duì)列為止，則是否可能得到輸出序列:A'C'E'C'C (2)A'C'EA'C'E'C'C'C (4)A'C'E'C［提示］:A'B、C'D'E(輸出隊(duì)首元素A)A、B、C、D、E、A(把隊(duì)首元素A插入到隊(duì)尾)B、C、D、E、A(刪除隊(duì)首元素A)C、D、E、A(再次刪除隊(duì)首元素B)C、D、E、A(輸出隊(duì)首元素C)C、D、E、A、C(把隊(duì)首元素C插入到隊(duì)尾)D、E、A、C(刪除隊(duì)首元素C)E、A、C(再次刪除隊(duì)首元素D)給出棧的兩種存儲(chǔ)結(jié)構(gòu)形式名稱，在這兩種棧的存儲(chǔ)結(jié)構(gòu)中如何判別?？张c棧滿?按照四則運(yùn)算加、減、乘、除和寡運(yùn)算(f)優(yōu)先關(guān)系的慣例，畫出對(duì)下列算術(shù)表達(dá)式求值時(shí)操作數(shù)棧和運(yùn)算符棧的變化過(guò)程:A-B*C/D+EtF試寫ー個(gè)算法，判斷依次讀入的ー個(gè)以為結(jié)束符的字母序列遙否為形如‘序列1&序列2’模式的字符序列。其中序列1和序列2中都不含字符'&'，且序列2是序列1的逆序列。例如，'a+b&b+a’是屬該模式的字符序列，而‘1+3&3—1t則不是。［提示］:邊讀邊入棧，直到&邊讀邊出棧邊比較，直到…….假設(shè)表達(dá)式由單字母變量和雙目四則運(yùn)算算符構(gòu)成。試寫ー個(gè)算法，將一個(gè)通常書寫形式(中綴)且書寫正確的表達(dá)式轉(zhuǎn)換為逆波攔式(后綴)。［提示］:例:中綴表達(dá)式:a+b 后綴表達(dá)式:ab+中綴表達(dá)式:a+bxc 后綴表達(dá)式:abcx+中爆表達(dá)式:a+bxc-d 后綴表達(dá)式:abcx+d-中綴表達(dá)式:a+bxc-d/e 后綴表達(dá)式：abcx+de/-中綴表達(dá)式:a+bx(c-d)-e/f 后綴表達(dá)式:abcd-x+ef/-? 后綴表達(dá)式的計(jì)算過(guò)程:(簡(jiǎn)便)順序掃描表達(dá)式，(1)如果是操作數(shù)，直接入棧;(2)如果是操作符op，則連續(xù)退棧兩次，得操作數(shù)X,Y，計(jì)算XopY，并將結(jié)果入棧。? 如何將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式?順序掃描中綴表達(dá)式，(1)如果是操作數(shù)，直接輸出;(2)如果是操作符op，則與棧頂操作符opi比較:如果op2>opl?則op2入棧;如果op?=opi,則脫括號(hào);如果0P2くopi?則輸出opi；.假設(shè)以帶頭結(jié)點(diǎn)的循環(huán)鏈表表示隊(duì)列，并且只設(shè)ー個(gè)指針指向隊(duì)尾元素結(jié)點(diǎn)(注意不設(shè)頭指針)，試編寫相應(yīng)的隊(duì)列初始化、入隊(duì)列和出隊(duì)列的算法。［提示］:參P.56P.70先畫圖.typedefLinkListCLQueue;intInitQueue(CLQueue*Q)intEnterQueue(CLQueueQ,QueueElementTypex)intDe1eteQueue(CLQueueQ,QueueE1ementType*x).要求循環(huán)隊(duì)列不損失ー個(gè)空間全部都能得到利用,設(shè)置ー個(gè)標(biāo)志域tag,以tag為0或1來(lái)區(qū)分頭尾指針相同時(shí)的隊(duì)列狀態(tài)的空與滿，請(qǐng)編寫與此結(jié)構(gòu)相應(yīng)的入隊(duì)與出隊(duì)算法。[提示]:初始狀態(tài):frontニニ〇,rearニニ〇,tagニニ〇隊(duì)空條件:front==rear,tagニニ〇隊(duì)滿條件:front==rear,tag==l其它狀態(tài):front!=rear,tag==O(或1、2)入隊(duì)操作:…(入隊(duì))if(front==rear)tag二1；(或直接tag二1)出隊(duì)操作:…(出隊(duì))tag二。;[問(wèn)題]:如何明確區(qū)分隊(duì)空、隊(duì)滿、非空非滿三種情況?.簡(jiǎn)述以下算法的功能(其中棧和隊(duì)列的元素類型均為int)：voidproc_l(StackS)(iinti,n,A[255];n=0;while(!EmptyStack(S))(n++;Pop(&S,&A[n]);)for(i=l;i<=n;i++)Push(&S,A[i]);將棧S逆序。voidproc_2(StackS,inte)StackT;intd;lnitStack(&T);while(!EmptyStack(S))(Pop(&S,&d);if(d!=e)Push(&T,d);}while(JEmptyStack(T))(Pop(&T,&d);Push(&S,d);})刪除棧S中所有等于e的元素。voidproc_3(Queue*Q)(StackS;intd;lnitStack(&S);while(!EmptyQueue(*Q))(DeleteQueueCQ,&d);Push(&S,d);)while(!EmptyStack(S))(Pop(&S,&d);EnterQueue(Q，d)將隊(duì)列Q逆序。實(shí)習(xí)題1?回文判斷。稱正讀與反讀都相同的字符序列為“回文”序列。試寫ー個(gè)算法，判斷依次讀入的ー個(gè)以為結(jié)束符的字母序列，是否為形如‘序列1&序列2'模式的字符序列。其中序列1和序列2中都不含字符'&'，且序列2是序列1的逆序列。例如，'a+b&b+a'是屬該模式的字符序列，而‘1+3&3-1’則不是。2?停車場(chǎng)管理。設(shè)停車場(chǎng)是ー個(gè)可停放n輛車的狹長(zhǎng)通道，且只有一個(gè)大門可供汽車進(jìn)出。在停車場(chǎng)，汽車按到達(dá)的先后次序，由北向南依次排列（假設(shè)大門在最南端）。若車場(chǎng)已停満n輛車，則后來(lái)的汽車需在門外的便道上等候，當(dāng)有車開走時(shí)，便道上的第一輛車即可開入。當(dāng)停車場(chǎng)某輛車要離開時(shí)，在它之后進(jìn)入的車輛必須先退出車場(chǎng)為它讓路，待該輛車開出大門后，其它車輛再按原次序返回車場(chǎng)。每輛車離開停車場(chǎng)時(shí)，應(yīng)按其停留時(shí)間的長(zhǎng)短交費(fèi)（在便道上停留的時(shí)間不收費(fèi)）。試編寫程序，模擬上述管理過(guò)程。要求以順序棧模擬停車場(chǎng)，以鏈隊(duì)列模擬便道。從終端讀入汽車到達(dá)或離去的數(shù)據(jù)，每組數(shù)據(jù)包括三項(xiàng):①是“到達(dá)"還是"離去"；②汽車牌照:③“到達(dá)”或“離去”的時(shí)刻。與每組輸入信息相應(yīng)的輸出信息為:如果是到達(dá)的車輛，則輸出其在停車場(chǎng)中或便道上的位置;如果是離去的車輛，則輸出其在停車場(chǎng)中停留的時(shí)間和應(yīng)交的費(fèi)用。（提示:需另設(shè)ー個(gè)棧，臨時(shí)停放為讓路而從車場(chǎng)退出的車?）車庫(kù)暫時(shí)退車道 疝便道3?商品貨架管理。商品貨架可以看成一個(gè)棧，棧頂商品的生產(chǎn)日期最早，棧底商品的生產(chǎn)日期最近。上貨時(shí)，需要倒貨架，以保證生產(chǎn)日期較近的商品在較下的位置。用隊(duì)列和棧作為周轉(zhuǎn)，實(shí)現(xiàn)上述管理過(guò)程。第三章答案3.1按3.1(b)所示鐵道(兩側(cè)鐵道均為單向行駛道)進(jìn)行車廂調(diào)度，回答:(1)如進(jìn)站的車廂序列為123，則可能得到的出站車廂序列是什么?(2)如進(jìn)站的車廂序列為123456，能否得到435612和135426的出站序列，并說(shuō)明原因(即寫出以“S”表示進(jìn)棧、“X”表示出棧的棧序列操作)。【解答】(1)可能得到的出站車廂序列是:123、132ヽ213、231ヽ321。(2)不能得到435612的出站序列。因?yàn)橛蠸(1)S(2)S(3)S(4)X(4)X(3)S(5)X(5)S(6)S(6)，此時(shí)按照“后進(jìn)先出”的原則，出棧的順序必須為X(2)X(1)°能得到135426的出站序列咽為有S(1)X(1)S(2)S(3)X(3)S(4)S(5)X(5)X(4)X(2)X(1)。給出棧的兩種存儲(chǔ)結(jié)構(gòu)形式名稱，在這兩種棧的存儲(chǔ)結(jié)構(gòu)中如何判別棧空與棧滿?【解答】(1)順序棧 (top用來(lái)存放棧頂元素的下標(biāo))判斷棧S空:如果S->top==-l表示?？铡Ｅ袛鄺CS満:如果S->top==Stack_Size-1表示棧満。(2)鏈棧(top為棧頂指針，指向當(dāng)前棧頂元素前面的頭結(jié)點(diǎn))判斷?？?如果top->next==NULL表示棧空。判斷棧滿:當(dāng)系統(tǒng)沒有可用空間時(shí)，申請(qǐng)不到空間存放要進(jìn)棧的元素，此時(shí)棧滿。照四則運(yùn)算加、減、乘、除和賽運(yùn)算的優(yōu)先慣例，畫出對(duì)下列表達(dá)式求值時(shí)操作數(shù)棧和運(yùn)算符棧的變化過(guò)程:A-B*C/D+EtF【解答】寫ー個(gè)算法，判斷依次讀入的ー個(gè)以為結(jié)束符的字母序列，是否形如‘序列1&序列2'的字符序列。序列1和序列2中都不含‘&'，且序列2是序列1的逆序列。例如，’a+b&b+a'是屬于該模式的字符序列，而‘1+3&3-1,則不是。【解答】算法如下:intIsHuiWenOStack*S;Charch,temp;InitStack(&S);Printf("\n請(qǐng)輸入字符序列:");Ch=getchar();/?/?序列1入棧*/Push(&S,ch);ch=getchar();}do /?判斷序列2是否是序列1的逆序列?/(ch=getchar();Pop(&S,&temp);if(ch!=temp) /?序列2不是序列1的逆序列?/(return(FALSE);printf("\nN0”);)}while(ch!=&&!IsEmpty(&S))if(ch== &&IsEmpty(&S)){return(TRUE);printf("\nYES");} /?序列2是序列1的逆序列?/else{return(FALSE);printf("\nN0");}}/*IsHuiWen()*/3.8要求循環(huán)隊(duì)列不損失ー個(gè)空間全部都能得到利用，設(shè)置ー個(gè)標(biāo)志tag,以tag為0或1來(lái)區(qū)分頭尾指針相同時(shí)的隊(duì)列狀態(tài)的空與滿，請(qǐng)編寫與此相應(yīng)的入隊(duì)與出隊(duì)算法?！窘獯稹咳腙?duì)算法:intEnterQueue(SeqQueue*Q,QueueE1ementTypex){/?將元素x入隊(duì)米/if(Q->front==Q->front&&tagニニ1) /?隊(duì)滿?/return(FALSE);if(Q->front==Q->front&&tag==0) /*x入隊(duì)前隊(duì)空，x入隊(duì)后重新設(shè)置標(biāo)志tag=l;Q->e1ememt[Q->rear]=x;Q->rear=(Q->rear+1)%MAXSIZE; /*設(shè)置隊(duì)尾指針*/Return(TRUE);}出隊(duì)算法:intDeleteQueue(SeqQueue*Q,QueueE1ementType*x){/米刪除隊(duì)頭元素，用x返回其值*/if(Q->front==Q->rear&&tag==O)/米隊(duì)空米/return(FALSE);*x=Qー)element[Q->front];Q->front=(Q->front+l)%MAXSIZE; /*重新設(shè)置隊(duì)頭指針*/if(Q->front==Q->rear)tag=0; /*隊(duì)頭元素出隊(duì)后隊(duì)列為空，重新設(shè)置標(biāo)志域:/Return(TUUE);}編寫求解Hanoi問(wèn)題的算法，并給出三個(gè)盤子搬動(dòng)時(shí)的遞歸調(diào)用過(guò)程?！窘獯稹克惴?voidhanoi(intn,charx,chary,charz){/?將塔座X上按直徑由小到大且至上而下編號(hào)為1至リn的n個(gè)圓盤按規(guī)則搬到塔座Z上，Y可用做輔助塔座"/if(n==1)move(x,1,z);else{Hanoi(n-l,x,z,y);move(x,n,z);Hanoi(n-1,y,x,z);Hanoi(3,A,B,C)的遞歸調(diào)用過(guò)程Hanoi(2,A,C,B):Hanoi(1,A,B,C)move(A->C)Move(A->B)Hanoid,C,A,B)move(C->B)1號(hào)搬到B3號(hào)搬至リ3號(hào)搬至リCHanoi(2,B,A,C)Hanoi(1,B,C,A) move(B->A)1號(hào)搬到AMove(B->C)Hanoi(1,A,B,C)move(A->C)習(xí)題.設(shè)s='IAMASTUDENT',t='GOOD',q='WORKER,。給出下列操作的結(jié)果:StrLength(s);SubStringCsubl,s,1,7);SubString(sub2,s,7,1)；Strlndex(s,'A',4);StrReplace(s,'STUDENT',q);StrCat(StrCat(subl,t),StrCat(sub2,q));［參考答案］StrLength(s)=14;subl="IAMA_*;sub2='_*;Strlndex(s,'A',4)=6;StrReplace(s,'STUDENT',q)='IAMAWORKER';StrCat(StrCat(subl,t),StrCat(sub2,q))='IAMAGOODWORKER';.編寫算法，實(shí)現(xiàn)串的基本操作StrReplace(S,T,V)。.假設(shè)以塊鏈結(jié)構(gòu)表示串，塊的大小為1，且附設(shè)頭結(jié)點(diǎn)。試編寫算法，實(shí)現(xiàn)串的下列基本操作:StrAsignCS,chars)；StrCopy(S,T)；StrCompare(S,T)；StrLength(S)；StrCat(S,T)；SubString(Sub,S,pos,len)°［說(shuō)明］:用單鏈表實(shí)現(xiàn)。.敘述以下每對(duì)術(shù)語(yǔ)的區(qū)別:空串和空格串;串變量和串常量;主串和子串;串變量的名字和串變量的值。.已知：S="(xyz)*",T="(x+z)*y"。試?yán)寐?lián)接、求子串和置換等操作，將S轉(zhuǎn)換為T..S和T是用結(jié)點(diǎn)大小為1的單鏈表存儲(chǔ)的兩個(gè)串，設(shè)計(jì)ー個(gè)算法將串S中首次與T匹配的子串逆置。.S是用結(jié)點(diǎn)大小為4的單鏈表存儲(chǔ)的串,分別編寫算法在第k個(gè)字符后插入串T，及從第k個(gè)字符刪除!en個(gè)字符。以下算法用定長(zhǎng)順序串:.寫下列算法:(1)將順序串r中所有值為chi的字符換成ch2的字符。(2)將順序串r中所有字符按照相反的次序仍存放在r中。(3)從順序串r中刪除其值等于ch的所有字符。(4)從順序串rl中第index個(gè)字符起求出首次與串r2相同的子串的起始位置。(5)從順序串r中刪除所有與串rl相同的子串。.寫ー個(gè)函數(shù)將順序串si中的第i個(gè)字符到第j個(gè)字符之間的字符用s2串替換。［提示］:(1)用靜態(tài)順序串(2)先移位，后復(fù)制.寫算法，實(shí)現(xiàn)順序串的基本操作StrCompare(s,t)°.寫算法，實(shí)現(xiàn)順序串的基本操作StrReplace(&s,t,v)。［提示］:(1)被替換子串定位(相當(dāng)于第9題中i)(2)被替換子串后面的字符左移或右移(為替換子串準(zhǔn)備房間)(3)替換子串入住(復(fù)制)(4)重復(fù)上述，直到……第四章答案4.I設(shè)s='1AMASTUDENT'，t='GOOD"，q='WORKER,。給出下列操作的結(jié)果:【解答】StrLength(s)=14;SubString(subl,s,1,7) subl='IAMA';SubString(sub2,s,7,1) sub2='';Strlndex(s,4,'A')=6;StrReplace(s,'STUDENT',q); s='IAMAWORKER,;StrCat(StrCat(subl,t),StrCat(sub2,q))subl='IAMAGOODWORKER,。4.2編寫算法，實(shí)現(xiàn)串的基本操作StrReplace(S,T,V)。【解答】算法如下:intstrRep1ace(SStringS,SStringT,SStringV){/?用串V替換S中的所有子串T*/intpos,i;pos=strIndex(S,1,T);/*求S中子intpos,i;pos=strIndex(S,1,T);/*求S中子串T第一次出現(xiàn)的位置*/if(pos==0)return(O);while(pos!=0)/