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

1、第1章 緒 論習(xí)題一、問(wèn)答題1. 什么是數(shù)據(jù)結(jié)構(gòu)？2. 四類基本數(shù)據(jù)結(jié)構(gòu)的名稱與含義。3. 算法的定義與特性。4. 算法的時(shí)間復(fù)雜度。5. 數(shù)據(jù)類型的概念。6. 線性結(jié)構(gòu)與非線性結(jié)構(gòu)的差別。7. 面向?qū)ο蟪绦蛟O(shè)計(jì)語(yǔ)言的特點(diǎn)。8. 在面向?qū)ο蟪绦蛟O(shè)計(jì)中，類的作用是什么？9. 參數(shù)傳遞的主要方式及特點(diǎn)。10. 抽象數(shù)據(jù)類型的概念。二、判斷題1. 線性結(jié)構(gòu)只能用順序結(jié)構(gòu)來(lái)存放，非線性結(jié)構(gòu)只能用非順序結(jié)構(gòu)來(lái)存放。2. 算法就是程序。3. 在高級(jí)語(yǔ)言（如C、或 PASCAL）中，指針類型是原子類型。三、計(jì)算下列程序段中X=X+1的語(yǔ)句頻度f(wàn)or(i=1;i<=n;i+) for(j=1;j<

2、=i;j+)for(k=1;k<=j;k+) x=x+1;提示： i=1時(shí)： 1 = (1+1)×1/2 = (1+12)/2 i=2時(shí)： 1+2 = (1+2)×2/2 = (2+22)/2 i=3時(shí)： 1+2+3 = (1+3)×3/2 = (3+32)/2 i=n時(shí)： 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 =n3/6+n2/2+n/3區(qū)分

3、語(yǔ)句頻度和算法復(fù)雜度：O(f(n) = O(n3)四、試編寫算法求一元多項(xiàng)式Pn(x)=a0+a1x+a2x2+a3x3+anxn的值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)輸入和輸出。提示：float PolyValue(float a , float x, int

4、 n) 核心語(yǔ)句：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; 實(shí)習(xí)題設(shè)計(jì)實(shí)現(xiàn)抽象數(shù)據(jù)類型“有理數(shù)”。基本操作包括有理數(shù)的加法、減法、乘法、除法，以及求有理數(shù)的分子、分母。第一章答案1.3計(jì)算下列程序中x=x+1的語(yǔ)句頻度 for(i=1;i<=n;i+)for(j=1;j<=i;j+) for(k=1;k<=j;k+) x=x+1; 【解答】x=x+1的語(yǔ)句頻度為：T(n)=1+(1+2)+（1+2+3）+（1+2+n）=n(n+1)(n+2)/61.4試

5、編寫算法，求pn(x)=a0+a1x+a2x2+.+anxn的值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)輸入輸出?！窘獯稹浚?）通過(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ò)全

6、局變量隱式傳遞 優(yōu)點(diǎn)：減少實(shí)參與形參的個(gè)數(shù)，從而減少內(nèi)存空間以及傳遞數(shù)據(jù)時(shí)的時(shí)間消耗 缺點(diǎn)：函數(shù)通用性降低，移植性差算法如下：通過(guò)全局變量隱式傳遞參數(shù)PolyValue() int i,n;float x,a,p; printf(“nn=”); scanf(“%f”,&n); printf(“nx=”); scanf(“%f”,&x);for(i=0;i<n;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);

7、 算法的時(shí)間復(fù)雜度：T(n)=O(n)通過(guò)參數(shù)表中的參數(shù)顯式傳遞float PolyValue(float a , float x, int n) float p,s;int i;p=x; s=a0;for(i=1;i<=n;i+)s=s+ai*p; /*執(zhí)行次數(shù):n次*/ p=p*x;return(p);算法的時(shí)間復(fù)雜度：T(n)=O(n)第2章 線性表習(xí) 題2.1 描述以下三個(gè)概念的區(qū)別：頭指針，頭結(jié)點(diǎn)，首元素結(jié)點(diǎn)。2.2 填空：（1） 在順序表中插入或刪除一個(gè)元素，需要平均移動(dòng)一半元素，具體移動(dòng)的元素個(gè)數(shù)與插入或刪除的位置有關(guān)。（2） 在順序表中，邏輯上相鄰的元素，其物理位置相鄰。

8、在單鏈表中，邏輯上相鄰的元素，其物理位置相鄰。（3） 在帶頭結(jié)點(diǎn)的非空單鏈表中，頭結(jié)點(diǎn)的存儲(chǔ)位置由指示，首元素結(jié)點(diǎn)的存儲(chǔ)位置由指示，除首元素結(jié)點(diǎn)外，其它任一元素結(jié)點(diǎn)的存儲(chǔ)位置由其直接前趨的next域指示。2.3 已知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ǔ)句序列是：（4）、（1）。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ǔ)句有：

9、（1）P->next=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遞增有序。試寫一算法，將X插入到L的適當(dāng)位置上，以保持線性

10、表L的有序性。提示：void insert(SeqList *L; ElemType x)< 方法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= i1+k; m<= L>last; m+) L>elem mk = L>elem m ;< 方法2 > 同時(shí)以待移動(dòng)元素

11、下標(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>

12、;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;2.7 試分別以不同的存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)線性表的就地逆置算法，即在原表的存儲(chǔ)空間將線性表（a1, a2., an）逆置為（an, an-1,., a1）。（1）以一維數(shù)組作存儲(chǔ)結(jié)構(gòu)，設(shè)線性表存于a(1:arrsize)的前elenum個(gè)分量中。（2）以單鏈表作存儲(chǔ)結(jié)構(gòu)。方法1：在

13、原頭結(jié)點(diǎn)后重新頭插一遍方法2：可設(shè)三個(gè)同步移動(dòng)的指針p, q, r，將q的后繼r改為p2.8 假設(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 >void merge(LinkList A; LinkList B; LinkList *C) pa=A>next; pb=B>next; *C=A; (*C)>next=NULL;while ( pa!=NULL && pb!=NU

14、LL ) if ( pa>data <= pb>data ) smaller=pa; pa=pa>next; smaller>next = (*C)>next; /* 頭插法 */ (*C)>next = smaller;else smaller=pb; pb=pb>next; smaller>next = (*C)>next; (*C)>next = smaller; while ( pa!=NULL) smaller=pa; pa=pa>next; smaller>next = (*C)>next; (*C

15、)>next = smaller;while ( pb!=NULL) smaller=pb; pb=pb>next; smaller>next = (*C)>next; (*C)>next = smaller;< 方法2 >LinkList merge(LinkList A; LinkList B) LinkList C；pa=A>next; pb=B>next; C=A; C>next=NULL; return C;2.9 假設(shè)有一個(gè)循環(huán)鏈表的長(zhǎng)度大于1，且表中既無(wú)頭結(jié)點(diǎn)也無(wú)頭指針。已知s為指向鏈表某個(gè)結(jié)點(diǎn)的指針，試編寫算法在鏈表中

16、刪除指針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=(a1, a2,am)，B=(b1, b2,bn)，試寫一個(gè)按下列規(guī)則合并A、B為線性表C的算法，使得： C= (a1, b1,am, bm, bm+1, ,bn) 當(dāng)mn時(shí)；或者 C= (a1, b1,an, bn, an+1, ,am) 當(dāng)m>n時(shí)。線

17、性表A、B、C均以單鏈表作為存儲(chǔ)結(jié)構(gòu)，且C表利用A表和B表中的結(jié)點(diǎn)空間構(gòu)成。注意：?jiǎn)捂湵淼拈L(zhǎng)度值m和n均未顯式存儲(chǔ)。提示：void merge(LinkList A; LinkList B; LinkList *C) 或：LinkList merge(LinkList A; LinkList B)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ì)二

18、進(jìn)制數(shù)加1的運(yùn)算 。提示：可將低位放在前面。2.14 設(shè)多項(xiàng)式P(x)采用課本中所述鏈接方法存儲(chǔ)。寫一算法，對(duì)給定的x值，求P(x)的值。提示：float PolyValue(Polylist p; float x) 實(shí)習(xí)題1 將若干城市的信息存入一個(gè)帶頭結(jié)點(diǎn)的單鏈表，結(jié)點(diǎn)中的城市信息包括城市名、城市的位置坐標(biāo)。要求：（1） 給定一個(gè)城市名，返回其位置坐標(biāo)；（2） 給定一個(gè)位置坐標(biāo)P和一個(gè)距離D，返回所有與P的距離小于等于D的城市。2 約瑟夫環(huán)問(wèn)題。約瑟夫問(wèn)題的一種描述是：編號(hào)為1，2，n的n個(gè)人按順時(shí)針?lè)较驀蝗Γ咳顺钟幸粋€(gè)密碼（正整數(shù)）。一開(kāi)始任選一個(gè)整數(shù)作為報(bào)數(shù)上限值m,從第一個(gè)人開(kāi)

19、始順時(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。第二章 答案 實(shí)習(xí)題二：約瑟夫環(huán)問(wèn)題約瑟夫問(wèn)題的一種描述為：編號(hào)1,2,n的n個(gè)人按順時(shí)針?lè)较驀蝗?，每個(gè)人持有一個(gè)密碼（正整數(shù)）。一開(kāi)始任選一個(gè)報(bào)數(shù)上限值m,從第一個(gè)人開(kāi)始順時(shí)針自1開(kāi)始順序報(bào)數(shù)，報(bào)到m時(shí)停

20、止報(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。【解答】算法如下： typedef struct Nodeint password;int num;struct Node *next;  Node,*Linklist; void Josephus()  Linkl

21、ist L;  Node *p,*r,*q;  int m,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",&

22、;n);  for(j=1;j<=n;j+)                              /*建立鏈表*/            p=(Node*)malloc(sizeof(Node);&

23、#160;     if (p!=NULL)                         printf("請(qǐng)輸入第%d個(gè)人的密碼:",j);          scanf("%d",&C); 

24、60;        p->password=C;          p->num=j;          r->next=p;         r=p;          r-&g

25、t;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!=1)               

26、;         /*計(jì)算出列的順序*/         j=1;       while(j<m)                    /*計(jì)算當(dāng)前出列的人選p*/  

27、                   q=p;               /*q為當(dāng)前結(jié)點(diǎn)p的前驅(qū)結(jié)點(diǎn)*/              p=p->next;

28、0;             j+;              printf("%d->",p->num);       m=p->password;          &

29、#160;      /*獲得新密碼*/       n- -;                        q->next=p->next;    /*p出列*/     &

30、#160; r=p;       p=p->next;       free(r);       printf("%dn",p->num); 2.7試分別以不同的存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)單線表的就地逆置算法，即在原表的存儲(chǔ)空間將線性表（a1,a2,an）逆置為(an,an-1,a1)?！窘獯稹浚?）用一維數(shù)組作為存儲(chǔ)結(jié)構(gòu)     void  inv

31、ert(SeqList  *L,  int  *num)    int  j;  ElemType  tmp;for (j=0;j<=(*num-1)/2;j+) tmp=Lj;Lj=L*num-j-1;L*num-j-1=tmp; （2）用單鏈表作為存儲(chǔ)結(jié)構(gòu)   void  invert (LinkList  L)  Node  *p, *q, *r;    if(L->next =NULL)  ret

32、urn;          /*鏈表為空*/    p=L->next;        q=p->next;               p->next=NULL;        &

33、#160;     /* 摘下第一個(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=(a1,a2,am), B=(b1,b2,bn)合并成線性表C, C=(a1,b1,am,bm,bm+

34、1,.bn)  當(dāng)m<=n時(shí)，或 C=(a1,b1, 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)成。注意：?jiǎn)捂湵淼拈L(zhǎng)度值m和n均未顯式存儲(chǔ)。【解答】算法如下：LinkList  merge(LinkList  A,  LinkList B,  LinkList  C) Node  *pa, *qa, *pb, *qb, *p;  pa=A->next;      

35、60;             /*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; 

36、 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)度大于

37、B的長(zhǎng)度*/ if(pb!=NULL)   p->next=pb;      /*B的長(zhǎng)度大于A的長(zhǎng)度*/C=A;    return(C); 第3章 限定性線性表 棧和隊(duì)列習(xí) 題1. 按圖3.1(b)所示鐵道（兩側(cè)鐵道均為單向行駛道）進(jìn)行車廂調(diào)度，回答： 如進(jìn)站的車廂序列為123，則可能得到的出站車廂序列是什么？ 123、213、132、231、321（312） 如進(jìn)站的車廂序列為123456，能否得到435612和135426的出站序列，并說(shuō)明原因。（即寫出以“S”表示進(jìn)棧、

38、以“X”表示出棧的棧操作序列）。SXSS XSSX XXSX 或 S1X1S2S3X3S4S5X5X4X2S6X62. 設(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、E（3） A、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

39、） 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）3. 給出棧的兩種存儲(chǔ)結(jié)構(gòu)形式名稱，在這兩種棧的存儲(chǔ)結(jié)構(gòu)中如何判別?？张c棧滿？4. 按照四則運(yùn)算加、減、乘、除和冪運(yùn)算（）優(yōu)先關(guān)系的慣例，畫出對(duì)下列算術(shù)表達(dá)式求值時(shí)操作數(shù)棧和運(yùn)算符棧的變化過(guò)程： AB5. 試寫一個(gè)算法，判斷依次讀入的一個(gè)以為結(jié)束符的字母序列，是否為形如序列1&序列2模式的字符序列。其中序列1和序列2中都不含字符&，且序列2是序列1的逆序列。例如，a+b&b+

40、a是屬該模式的字符序列，而+&則不是。提示：（1） 邊讀邊入棧，直到&（2） 邊讀邊出棧邊比較，直到6. 假設(shè)表達(dá)式由單字母變量和雙目四則運(yùn)算算符構(gòu)成。試寫一個(gè)算法，將一個(gè)通常書寫形式（中綴）且書寫正確的表達(dá)式轉(zhuǎn)換為逆波蘭式（后綴）。提示：例：中綴表達(dá)式：a+b 后綴表達(dá)式: ab+中綴表達(dá)式：a+b×c 后綴表達(dá)式: abc×+中綴表達(dá)式：a+b×c-d 后綴表達(dá)式: abc×+d-中綴表達(dá)式：a+b×c-d/e 后綴表達(dá)式: abc×+de/-中綴表達(dá)式：a+b×(c-d)-e/f 后綴表達(dá)式: abcd

41、-×+ef/-· 后綴表達(dá)式的計(jì)算過(guò)程：（簡(jiǎn)便）順序掃描表達(dá)式，（1）如果是操作數(shù)，直接入棧；（2）如果是操作符op，則連續(xù)退棧兩次，得操作數(shù)X, Y，計(jì)算X op Y，并將結(jié)果入棧。· 如何將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式？順序掃描中綴表達(dá)式，（1）如果是操作數(shù)，直接輸出；（2）如果是操作符op2，則與棧頂操作符op1比較：如果op2 > op1，則op2入棧；如果op2 = op1，則脫括號(hào)；如果op2 < op1，則輸出op1；7. 假設(shè)以帶頭結(jié)點(diǎn)的循環(huán)鏈表表示隊(duì)列，并且只設(shè)一個(gè)指針指向隊(duì)尾元素結(jié)點(diǎn)（注意不設(shè)頭指針），試編寫相應(yīng)的隊(duì)列初始化、入隊(duì)列和

42、出隊(duì)列的算法。提示： 參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)隊(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=0, tag=0 隊(duì)空條件：front=rea

43、r, tag=0 隊(duì)滿條件：front=rear, tag=1 其它狀態(tài)：front !=rear, tag=0（或1、2） 入隊(duì)操作：（入隊(duì)）if (front=rear) tag=1；（或直接tag=1）出隊(duì)操作：（出隊(duì)）tag=0；問(wèn)題：如何明確區(qū)分隊(duì)空、隊(duì)滿、非空非滿三種情況？9. 簡(jiǎn)述以下算法的功能（其中棧和隊(duì)列的元素類型均為int）：（1）void proc_1(Stack S) iint i, n, A255; n=0; while(!EmptyStack(S) n+; Pop(&S, &An); for(i=1; i<=n; i+) Push(&S

44、, Ai); 將棧S逆序。（2）void proc_2(Stack S, int e) Stack T; int d;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的元素。（3）void proc_3(Queue *Q) Stack S; int d;InitStack(&S); while(!EmptyQueue(*

45、Q) DeleteQueue(Q, &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是屬該模式的字符序列，而+&則不是。2 停車場(chǎng)管理。設(shè)停車場(chǎng)是一個(gè)可停放n輛車的狹長(zhǎng)通道，且只有一個(gè)大門可供汽車

46、進(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á)的車輛，

47、則輸出其在停車場(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ō)明原因

48、（即寫出以“S”表示進(jìn)棧、“X”表示出棧的棧序列操作）?！窘獯稹浚?）可能得到的出站車廂序列是：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

49、->top=-1表示棧空。判斷棧S滿：如果S->top=Stack_Size-1表示棧滿。（2） 鏈棧（top為棧頂指針，指向當(dāng)前棧頂元素前面的頭結(jié)點(diǎn)）判斷?？眨喝绻鹴op->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+EF【解答】3.5 寫一個(gè)算法，判斷依次讀入的一個(gè)以為結(jié)束符的字母序列，是否形如序列1&序列2的字符序列。序列1和序列2中都不含&，且序列2是序列1 的逆序列。例如，a

50、+b&b+a是屬于該模式的字符序列，而1+3&3-1則不是。【解答】算法如下： int IsHuiWen() Stack *S; Char ch,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(FALS

51、E); 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)隊(duì)列不損失一個(gè)空間全部都能得到利用，設(shè)置一個(gè)標(biāo)志tag,以tag為0或1來(lái)區(qū)分頭尾指針相同時(shí)的隊(duì)列狀態(tài)的空與滿，請(qǐng)編寫與此相應(yīng)的入隊(duì)與出隊(duì)算法?！窘獯稹咳腙?duì)算法：int EnterQueue(SeqQueue

52、 *Q, QueueElementType x) /*將元素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=1;Q->elememtQ->rear=x;Q->rear=(Q->rear+1)%MAXSIZE; /*設(shè)置隊(duì)尾指針*/Return(TRUE); 出隊(duì)算法： int DeleteQueue( SeqQueue *Q , Qu

53、eueElementType *x) /*刪除隊(duì)頭元素，用x返回其值*/if(Q->front=Q->rear && tag=0) /*隊(duì)空*/ return(FALSE);*x=Q->elementQ->front;Q->front=(Q->front+1)%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ò)程?！窘獯稹克惴ǎ?void hanoi

54、 (int n ,char x, char y, char z) /*將塔座X上按直徑由小到大且至上而下編號(hào)為1到n的n個(gè)圓盤按規(guī)則搬到塔座Z上，Y可用做輔助塔座*/ if(n = =1) move(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)用過(guò)程：Hanoi(2,A,C,B): Hanoi(1,A,B,C) move(A->C) 1號(hào)搬到C Move(A->B) 2號(hào)搬到B Hanoi(1,C,A,B) move(C->B) 1號(hào)搬到B Move(A-

55、>C) 3號(hào)搬到CHanoi(2,B,A,C) Hanoi(1,B,C,A) move(B->A) 1號(hào)搬到A Move(B->C) 2號(hào)搬到C Hanoi(1,A,B,C) move(A->C) 1號(hào)搬到C第4章串習(xí)題1. 設(shè)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), StrCa

56、t(sub2,q);參考答案StrLength(s)=14; sub1= I AM A_; sub2= _; StrIndex(s,A,4)=6; StrReplace(s,STUDENT,q)= I AM A WORKER; StrCat(StrCat(sub1,t), StrCat(sub2,q)= I AM A GOOD WORKER;2. 編寫算法，實(shí)現(xiàn)串的基本操作StrReplace(S,T,V)。3. 假設(shè)以塊鏈結(jié)構(gòu)表示串，塊的大小為1，且附設(shè)頭結(jié)點(diǎn)。試編寫算法，實(shí)現(xiàn)串的下列基本操作：StrAsign(S,chars)； StrCopy(S,T)； StrCompare(S,T)；

57、 StrLength(S)； StrCat(S,T)； SubString(Sub,S,pos,len)。說(shuō)明：用單鏈表實(shí)現(xiàn)。4. 敘述以下每對(duì)術(shù)語(yǔ)的區(qū)別：空串和空格串；串變量和串常量；主串和子串；串變量的名字和串變量的值。5. 已知：S=”(xyz)*”,T=”(x+z)*y”。試?yán)寐?lián)接、求子串和置換等操作，將S轉(zhuǎn)換為T.6. S和T是用結(jié)點(diǎn)大小為1的單鏈表存儲(chǔ)的兩個(gè)串，設(shè)計(jì)一個(gè)算法將串S中首次與T匹配的子串逆置。7. S是用結(jié)點(diǎn)大小為4的單鏈表存儲(chǔ)的串,分別編寫算法在第k個(gè)字符后插入串T，及從第k個(gè)字符刪除len個(gè)字符。以下算法用定長(zhǎng)順序串：8. 寫下列算法：（1） 將順序串r中所有值為

58、ch1的字符換成ch2的字符。（2） 將順序串r中所有字符按照相反的次序仍存放在r中。（3） 從順序串r中刪除其值等于ch的所有字符。（4） 從順序串r1中第index 個(gè)字符起求出首次與串r2相同的子串的起始位置。（5） 從順序串r中刪除所有與串r1相同的子串。9. 寫一個(gè)函數(shù)將順序串s1中的第i個(gè)字符到第j個(gè)字符之間的字符用s2串替換。提示：（1）用靜態(tài)順序串 （2）先移位，后復(fù)制10. 寫算法，實(shí)現(xiàn)順序串的基本操作StrCompare(s,t)。11. 寫算法，實(shí)現(xiàn)順序串的基本操作StrReplace(&s,t,v)。提示：（1）被替換子串定位（相當(dāng)于第9題中i）（2）被替換子串后面的字符左移或右移（為替換子串準(zhǔn)備房間）（3）替換子串入住（復(fù)制）（4）重復(fù)上述，直到第四章答案4.1 設(shè)s=I AM A STUDENT，t=GOOD， q=WORKER。給出下列操作的結(jié)果：【解答】StrLength(s)=14;SubString(sub1,s,1,7) sub1=I AM A ;SubString(sub2,s,7,1) sub2= ;St