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

第1章緒論習(xí)題ー、問(wèn)答題.什么是數(shù)據(jù)結(jié)構(gòu)?.四類基本數(shù)據(jù)結(jié)構(gòu)的名稱與含義。.算法的定義與特性。.算法的時(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=(1+1)X1/2=(1+12)/2i=2時(shí):1+2=(1+2)X2/2=(2+2?)/2i=3時(shí)：1+2+3=(1+3)X3/2=(3+32)/2i=n時(shí)：1+2+3+ +n=(1+n)Xn/2=(n+n2)/2f(n)=[(1+2+3+……+n)+(I2+22+32+……+n2)]/2=[(1+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ù)雜度:0(f(n))=0(n3)四、試編寫算法求一元多項(xiàng)式Pn(x)=a<)+aix+a2x2+a3x3+…Mx"的值Pn(xo),并確定算法中的每ー語(yǔ)句的執(zhí)行次數(shù)和整個(gè)算法的時(shí)間復(fù)雜度,要求時(shí)間復(fù)雜度盡可能的小,規(guī)定算法中不能使用求嘉函數(shù)。注意:本題中的輸入出入=0,1,…,n),x和n,輸出為Pn(xo).通常算法的輸入和輸出可采用下列兩種方式之一:通過(guò)參數(shù)表中的參數(shù)顯式傳遞;通過(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ù)的分子、分母。第一章答案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+1的語(yǔ)句頻度為:T(n)=1+(1+2)+(1+2+3)+ + (1+2+ +n)=n(n+1)(n+2)/64試編寫算法,求Pn(x)=ao+aix+a2x2+ +aH的值pn(x0),并確定算法中每ー語(yǔ)句的執(zhí)行次數(shù)和整個(gè)算法的時(shí)間復(fù)雜度,要求時(shí)間復(fù)雜度盡可能小,規(guī)定算法中不能使用求裏函數(shù)。注意:本題中的輸入為ai(i=0,1,…n)、x和n,輸出為Pn(x0)〇算法的輸入和輸出采用下列方法(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)沒(méi)有調(diào)用函數(shù)時(shí),不占用內(nèi)存,調(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ù),從而減少內(nèi)存空間以及傳遞數(shù)據(jù)時(shí)的時(shí)間消耗缺點(diǎn):函數(shù)通用性降低,移植性差算法如下:通過(guò)全局變量隱式傳遞參數(shù)PolyValue(){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[〇];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)。填空：（1）在順序表中插入或刪除ー個(gè)元素,需要平均移動(dòng) 一半元素,具體移動(dòng)的元素個(gè)數(shù)與 插入或刪除的位置一有關(guān)。（2）在順序表中,邏輯上相鄰的元素,其物理位置 相鄰。在單鏈表中,邏輯上相鄰的元素,其物理位置 ー相鄰。（3）在帶頭結(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ǔ)句序列是: 在）、（點(diǎn)。b.在P結(jié)點(diǎn)前插入S結(jié)點(diǎn)的語(yǔ)句序列是:（7）、（11）、（8）、（4）、（1）。c,在表首插入S結(jié)點(diǎn)的語(yǔ)句序列是:（5）、（12）。d,在表尾插入S結(jié)點(diǎn)的語(yǔ)句序列是:（11）、（9）、（1）、（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;while(P->next!=NULL)P=P->next;P=Q;P=L;L=S;L=P;2.4已知線性表L遞增有序。試寫ー算法,將X插入到L的適當(dāng)位置上,以保持線性表L的有序性。[提ホ]:voidinsert(SeqList*L;ElemTypex)<方法1>(1)找出應(yīng)插入位置i,(2)移位,(3)……<方法2〉參P.2292.5寫ー算法,從順序表中刪除自第i個(gè)元素開(kāi)始的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域）。找到第一個(gè)應(yīng)刪結(jié)點(diǎn)的前驅(qū)pre找到最后ー個(gè)應(yīng)刪結(jié)點(diǎn)的后繼s,邊找邊釋放應(yīng)刪結(jié)點(diǎn)(3)pre(3)pre—>next=s;試分別以不同的存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)線性表的就地逆置算法,即在原表的存儲(chǔ)空間將線性表（a1,a2...,an）逆置為（a?,an,...,aj。以ー維數(shù)組作存儲(chǔ)結(jié)構(gòu),設(shè)線性表存于a（l:arrsize）的前elenum個(gè)分量中。以單鏈表作存儲(chǔ)結(jié)構(gòu)。［方法1］:在原頭結(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){smaller=pa;pa=pa—>next;smaller—>next=(*C)—>next; /?頭插法?/(*C)—>next=smaller;}else{smaller=pb;pb=pb—>next;(*C)—>next=smaller;)while(pa!=NULL){smaller=pa;pa=pa—>next;smaller—>next=(*C)—>next;(*C)—>next=smaller;)while(pb!=NULL){smaller=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;2.9假設(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)系?2.10已知有單鏈表表示的線性表中含有三類字符的數(shù)據(jù)元素(如字母字符、數(shù)字字符和其它字符),試編寫算法來(lái)構(gòu)造三個(gè)以循環(huán)鏈表表示的線性表,使每個(gè)表中只含同一類的字符,且利用原表中的結(jié)點(diǎn)空間作為這三個(gè)表的結(jié)點(diǎn)空間,頭結(jié)點(diǎn)可另辟空間。2.11設(shè)線性表A=(ai,a2, a.),B=(bbb2,???,bn),試寫ー個(gè)按下列規(guī)則合并A、B為線性表C的算法,使得:C=(abbb???,a.,bB,b吁し???,bj當(dāng)mWn時(shí);或者C=(abレ,…,へ,bn,a?+i,…，a.)當(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*0或:LinkListmerge(LinkListA;LinkListB)2.12將一個(gè)用循環(huán)鏈表表示的稀疏多項(xiàng)式分解成兩個(gè)多項(xiàng)式,使這兩個(gè)多項(xiàng)式中各自僅含奇次項(xiàng)或偶次項(xiàng),并要求利用原鏈表中的結(jié)點(diǎn)空間來(lái)構(gòu)成這兩個(gè)鏈表。［提示］:注明用頭指針還是尾指針。2.13建立一個(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)算。［提示］:可將低位放在前面。2.14設(shè)多項(xiàng)式P(x)采用課本中所述鏈接方法存儲(chǔ)。寫ー算法,對(duì)給定的x值,求P(x)的值。［提示］:floatPolyValue(Polylistp;floatx){ }實(shí)習(xí)題將若干城市的信息存入ー個(gè)帶頭結(jié)點(diǎn)的單鏈表,結(jié)點(diǎn)中的城市信息包括城市名、城市的位置坐標(biāo)。要求：(1)給定一個(gè)城市名,返回其位置坐標(biāo);(2)給定一個(gè)位置坐標(biāo)P和一個(gè)距離D,返回所有與P的距離小于等于D的城市。約瑟夫環(huán)問(wèn)題。約瑟夫問(wèn)題的ー種描述是:編號(hào)為1,2,…，n的n個(gè)人按順時(shí)針?lè)较驀`圈,每人持有一個(gè)密碼（正整數(shù)）。ー開(kāi)始任選ー個(gè)整數(shù)作為報(bào)數(shù)上限值叫從第一個(gè)人開(kāi)始順時(shí)針自1開(kāi)始順序報(bào)數(shù),報(bào)到m時(shí)停止報(bào)數(shù)。報(bào)m的人出列,將他的密碼作為新的m值,從他在順時(shí)針?lè)较蛏系南乱粋€(gè)人開(kāi)始重新從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〇第二章答案約瑟夫環(huán)問(wèn)題約瑟夫問(wèn)題的ー種描述為:編號(hào)1,2,???,n的n個(gè)人按順時(shí)針?lè)较驀`圈,每個(gè)人持有一個(gè)密碼（正整數(shù)）。ー開(kāi)始任選ー個(gè)報(bào)數(shù)上限值叫從第一個(gè)人開(kāi)始順時(shí)針自1開(kāi)始順序報(bào)數(shù),報(bào)到m時(shí)停止報(bào)數(shù)。報(bào)m的人出列,將他的密碼作為新的m值,從他在順時(shí)針?lè)较蛏系南漏`個(gè)人開(kāi)始重新從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〇【解答】算法如下:typedefstructNodeintpassword;intnum;structNode*next;}Node,*Linklist;voidJosephus(){LinklistL;Node*p,*r,*q;intm,n,C,j;L=(Node*)malloc(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("%d",&n);for(j=l;j〈=n;j++)/?建立鏈表?/{p=(Node*)malloc(sizeof(Node));if(p!=NULL)(printf("請(qǐng)輸入第％d個(gè)人的密碼:",j)；scanf("%d",&C);p->password=C;pー〉num=j;r->next=p;r-p;))r->next=Lー〉next;printf(〃請(qǐng)輸入第一個(gè)報(bào)數(shù)上限值m(m〉0):〃)；scanf("%d",&m);printf(〃*****************************************\n〃),printf("出列的順序?yàn)?\n");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,p->num);m=p->password;/?獲得新密碼?/n一;q->next=p->next; /*p出列*/r=p;p=p->next;free(r);)printf("%d\n”,p->num);}2.y試分別以不同的存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)單線表的就地逆置算法,即在原表的存儲(chǔ)空間將線性表(aba2,-,an)逆置為⑸,ス,…,aノ?！窘獯稹?1)用ー維數(shù)組作為存儲(chǔ)結(jié)構(gòu)voidinvert(SeqList*L,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、C以單鏈表作為存儲(chǔ)結(jié)構(gòu),且C表利用A表和B表中的結(jié)點(diǎn)空間構(gòu)成。注意:單鏈表的長(zhǎng)度值m和n均未顯式存儲(chǔ)?！窘獯稹克惴ㄈ缦?LinkList merge(LinkList A, 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)站的車廂序列為!23,則可能得到的出站車廂序列是什么?123、213、132、231、321（312）⑵如進(jìn)站的車廂序列為!23456,能否得到435612和135426的出站序列,并說(shuō)明原因。（即寫出以“S”表示進(jìn)棧、以“X”表示出棧的棧操作序列）。SXSSXSSXXXSX或S1X1S2S3X3S4S5X5X4X2S6X6.設(shè)隊(duì)列中有A、B、C、D、E這5個(gè)元素,其中隊(duì)首元素為A。如果對(duì)這個(gè)隊(duì)列重復(fù)執(zhí)行下列4步操作:（1）輸出隊(duì)首元素;（2）把隊(duì)首元素值插入到隊(duì)尾;（3）刪除隊(duì)首元素;（4）再次刪除隊(duì)首元素。直到隊(duì)列成為空隊(duì)列為止,則是否可能得到輸出序列:（1）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)算（t）優(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—1’則不是。［提示］:(1)邊讀邊入棧,直到&(2)邊讀邊出棧邊比較,直到…….假設(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)如果是操作符。P2,則與棧頂操作符。小比較:如果op，>0P1,則叩2入棧;如果。P2=0P1,則脫括號(hào);如果0P2<0P1,則輸出0P1；.假設(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)intDeleteQueue(CLQueueQ,QueueElementType*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==0,rear==O,tag==O隊(duì)空條件:front==rear,tag==O隊(duì)滿條件:front==rear,tag==l其它狀態(tài):front!=rear,tag==0（或1、2）入隊(duì)操作：??…（入隊(duì)）if（front==rear）tag=l；（或直接tag=l）出隊(duì)操作：??（出隊(duì)）tag=0；［問(wèn)題］:如何明確區(qū)分隊(duì)空、隊(duì)滿、非空非滿三種情況?9.簡(jiǎn)述以下算法的功能（其中棧和隊(duì)列的元素類型均為int）：voidproc_l（StackS）{inti,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;InitStack(&T);while(!EmptyStack(S)){Pop(&S,&d);if(d!=e)Push(&T,d);)while(!EmptyStack(T)){Pop(&T,&d);Push(&S,d);))刪除棧S中所有等于e的元素。voidproc_3(Queue*Q){StackS;intd;InitStack(&S);whiledEmptyQueue(*Q))DeleteQueue(Q,&d);Push(&S,d);}whiledEmptyStack(S)){Pop(&S,&d);EnterQueue(Q,d)})將隊(duì)列Q逆序。實(shí)習(xí)題回文判斷。稱正讀與反讀都相同的字符序列為“回文’‘序列。試寫ー個(gè)算法,判斷依次讀入的ー個(gè)以@為結(jié)束符的字母序歹!b是否為形如‘序列1&序列牙模式的字符序列。其中序列1和序列2中都不含字符且序列2是序列1的逆序列。例如,'a+b&b+a，是屬該模式的字符序列,而’1+3&3—'1'則不是。停車場(chǎng)管理。設(shè)停車場(chǎng)是ー個(gè)可停放n輛車的狹長(zhǎng)通道,且只有一個(gè)大門可供汽車進(jìn)出。在停車場(chǎng)內(nèi),汽車按到達(dá)的先后次序,由北向南依次排列(假設(shè)大門在最南端)。若車場(chǎng)內(nèi)已停滿n輛車,則后來(lái)的汽車需在門外的便道上等候,當(dāng)有車開(kāi)走時(shí),便道上的第一輛車即可開(kāi)入。當(dāng)停車場(chǎng)內(nèi)某輛車要離開(kāi)時(shí),在它之后進(jìn)入的車輛必須先退出車場(chǎng)為它讓路,待該輛車開(kāi)出大門后,其它車輛再按原次序返回車場(chǎng)。每輛車離開(kāi)停車場(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á)”還是“離去”；②汽車牌照號(hào)碼;③'‘到達(dá)”或“離去”的時(shí)刻。與每組輸入信息相應(yīng)的輸出信息為:如果是到達(dá)的車輛，則輸出其在停車場(chǎng)中或便道上的位置;如果是離去的車輛,則輸出其在停車場(chǎng)中停留的時(shí)間和應(yīng)交的費(fèi)用。（提示:需另設(shè)ー個(gè)棧,臨時(shí)停放為讓路而從車場(chǎng)退出的車。）車庫(kù)暫時(shí)退車道 あ 便道商品貨架管理。商品貨架可以看成一個(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)站的車廂序列為!23456,能否得到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的出站序列。因?yàn)橛蠸(1)X(1)S(2)S(3)X(3)S(4)S(5)X(5)X(4)X(2)X(1)。3.3給出棧的兩種存儲(chǔ)結(jié)構(gòu)形式名稱,在這兩種棧的存儲(chǔ)結(jié)構(gòu)中如何判別?？张c棧滿?【解答】(1)順序棧 (top用來(lái)存放棧頂元素的下標(biāo))判斷棧S空:如果Sー＞top==T表示?？?。判斷棧S滿:如果S-＞top==Stack_Size-l表示棧滿。(2)鏈棧(top為棧頂指針,指向三前棧頂元素前面的頭結(jié)點(diǎn))判斷?？?如果topー＞next==NULL表示棧空。判斷棧滿:當(dāng)系統(tǒng)沒(méi)有可用空間時(shí),申請(qǐng)不到空間存放要進(jìn)棧的元素,此時(shí)棧滿。3. 4照四則運(yùn)算加、減、乘、除和裏運(yùn)算的優(yōu)先慣例,畫出對(duì)下列表達(dá)式求值時(shí)操作數(shù)棧和運(yùn)算符棧的變化過(guò)程:A-B*C/D+EtF【解答】

'+'=OPTR；＜生成A-T(2)>運(yùn)篁結(jié)果T(3)OPTR為空’+，'+'=OPTR；＜生成A-T(2)>運(yùn)篁結(jié)果T(3)OPTR為空’+，進(jìn)後運(yùn)算結(jié)果T(4)T(3)運(yùn)算結(jié)果T(5)右邊界<OPTR；t'生成EtF右邊界'#,vOPTR：+'生成T(3)+T(4)3. 5寫ー個(gè)算法,判斷依次讀入的ー個(gè)以@為結(jié)束符的字母序列,是否形如‘序列1&序列2，的字符序列。序列1和序列2中都不含且序列2是序列1的逆序列。例如,'a+b&b+a’是屬于該模式的字符序列,而’1+3&3T’則不是。【解答】算法如下:intIsHuiWen(){Stack*S;Charch,temp;InitStack(&S);Printf("\n請(qǐng)輸入字符序列:")；Ch=getchar();While(ch!=&) /?序列1入棧?/{Push(&S,ch);ch=getchar();}do /?判斷序列2是否是序列1的逆序列?/{ch=getchar();Pop(&S,&temp);if(ch!=temp) /?序列2不是序列1的逆序列?/{return(FALSE);printf(a\nN0");}}while(ch!&&!IsEmpty(&S))if(ch==@ &&IsEmpty(&S)){return(TRUE);printf("\nYES");} /*序列2是序列1的逆序列?/else{return(FALSE);printf("\nNO");}}/*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,QueueElementTypex){/?將元素x入隊(duì)?/if(Q->front==Qー>front&&tag==l)/?隊(duì)滿?/return(FALSE);if(Q-〉front==Qー〉front&&tag==0) /*x入隊(duì)前隊(duì)空,x入隊(duì)后重新設(shè)置標(biāo)志?/tag=l;Q->elememt[Q-〉rear]=x;Qー〉rear=(Q-〉rear+l)%MAXSlZE; /?設(shè)置隊(duì)尾指針?/Return(TRUE);出隊(duì)算法:intDeleteQueue(SeqQueue*Q,QueueElementType*x){/?刪除隊(duì)頭元素,用x返回其值?/if(Q-〉front==Qー〉rear&&tag==0) /?隊(duì)空?/return(FALSE);*x=Q-〉element[Q-〉front];Qー〉front=(Qー〉front+l)%MAXSlZE; /?重新設(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上,丫可用做輔助塔座?/if(n==1)move(x,1,z);else{Hanoi(n-l,x,z,y);move(x,n,z);Hanoi(n-l,y,x,z);Hanoi(2,A,C,B):Hanoi(2,A,C,B):Hanoi(1,A,B,C)Move(A->B)Hanoi(1,C,A,B)Move(A->C)Hanoi(2,B,A,C)Hanoi(1,B,C,A)Move(B->C)Hanoi(1,A,B,C)move(A->C) 1號(hào)搬到C2號(hào)搬到Bmove(C->B) 1號(hào)搬到B3號(hào)搬到Cmove(B->A) 1號(hào)搬到A2號(hào)搬到C

move(A->C) 1號(hào)搬到C第4章 串習(xí)題.設(shè)s='IAMASTUDENT),t='GOOD*,q='WORKER,〇給出下列操作的結(jié)果:StrLength(s); SubString(subl,s,1,7);SubString(sub2,s,7,1);StrIndex(s,fA',4);StrReplace(s,rSTUDENT*,q);StrCat(StrCat(subl,t),StrCat(sub2,q));［參考答案］StrLength(s)=14;subl=*IAMA_';sub2=* ;Strindex(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)表示串,塊的大小為L(zhǎng)且附設(shè)頭結(jié)點(diǎn)。試編寫算法,實(shí)現(xiàn)串的下列基本操作:StrAsign(S,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è)字符刪除len個(gè)字符。以下算法用定長(zhǎng)順序串:寫下列算法:（1）將順序串r中所有值為chi的字符換成ch2的字符。（2）將順序串r中所有字符按照相反的次序仍存放在r中。<3）從順序串r中刪除其值等于ch的所有字符。從順序串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）〇［提示］：被替換子串定位（相當(dāng)于第9題中i）被替換子串后面的字符左移或右移（為替換子串準(zhǔn)備房間）替換子串入?。◤?fù)制）重復(fù)上述,直到……第四章答案4.1設(shè)s='IAMASTUDENT',t='GOOD',q='WORKER,〇給出下列操作的結(jié)果:【解答】StrLength(s)=14;SubString(subl,s,1,7) subl='IAMA';SubString(sub2,s,7,1) sub2='';Strindex(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)〇【解答】算法如下:intStrReplace(SStringS,SStringT,SStringV){/?用串V替換S中的所有子串T*/intpos,i;pos=strlndex(S,1,T); /*求S中子串T第一次出現(xiàn)的位置?/if(pos==0)return(0);while(pos!=0) /?用串V替換S中的所有子串T*/{switch(T.len-V.len)(case0: /?串T的長(zhǎng)度等于串V的長(zhǎng)度?/for(i=0;i〈=V.len;i++) /*用V替換WS->ch[pos+i]=V.ch[i];case>0: /?串T的長(zhǎng)度大于串V的長(zhǎng)度?/for(i=pos+t.ien;iくS-〉len;i-) /*將S中子串T后的所有字符S->ch[i-t.len+v.len]=S->ch[i];前移T.len-V.len個(gè)位置?/for(i=0;i<=V.len;i++)/?用V替換T*/S->ch[pos+i]=V.ch[i];S->len=S->len-T.len+V.len;case<0: /?串T的長(zhǎng)度小于串V的長(zhǎng)度?/if(S->len-T.len+V.len)<=MAXLEN /?插入后串長(zhǎng)小于MAXLEN*/{/?將S中子串T后的所有字符后移V.len-T.len個(gè)位置?/for(i=S->len-T.len+V.len;i>=pos+T.len;i—)S->ch[i]=S->ch[i-T.len+V.len];for(i=0;i<=V.len;i++)/?用V替換T*/S->ch[pos+i]=V.ch[i];S->len=Sー〉len-T.len+V.len;}else{ /?替換后串長(zhǎng))MAXLEN,但串V可以全部替換?/if(pos+V.len<=MAXLEN){for(i=MAXLENT;i〉=pos+T.len;i一)S->ch[i]=s->ch[i-T.len+V.len]for(i=0;i<=V.len;i++)/?用V替換WS->ch[pos+i]=V.ch[i];S->len=MAXLEN;}else /?串V的部分字符要舍棄?/{for(i=0;iくMAXLEN-pos;i++)S->ch[i+pos]=V.ch[i];S->len=MAXLEN;}}/"switch〇*/pos=Strlndex(S,pos+V.len,T); /?求S中下一個(gè)子串T的位置?/}/*while()*/return(1);}/*StrReplace()*/附加題:用鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)定位函數(shù)?！窘獯稹縯ypedefstructNode{chardata;structNode*next;}Node,*Lstring;intstrindex(LstringS,intpos,LstringT)/?從串S的pos序號(hào)起,串T第一次出現(xiàn)的位置?/{Node*p,*q,*Ppos;inti=0,,j=0;if(T->next==NULL||S->next==NULL)return(0);p=Sー)next;q=Tー)next;while(p!=NULL&&j<pos)/*p指向串S中第pos個(gè)字符?/{p=pー〉next;j+