數(shù)據(jù)結(jié)構(gòu)c語言描述耿國華答案解析

第1章緒論

習(xí)題

一、問答題

1.什么是數(shù)據(jù)結(jié)構(gòu)？

2.四類基本數(shù)據(jù)結(jié)構(gòu)的名稱與含義。

3.算法的定義與特性。

4.算法的時間復(fù)雜度。

5.數(shù)據(jù)類型的概念。

6.線性結(jié)構(gòu)與非線性結(jié)構(gòu)的差別。

7.面向?qū)ο蟪绦蛟O(shè)計語言的特點(diǎn)。

8.在面向?qū)ο蟪绦蛟O(shè)計中，類的作用是什么？

9.參數(shù)傳遞的主要方式及特點(diǎn)。

10.抽象數(shù)據(jù)類型的概念。

二、判斷題

1.線性結(jié)構(gòu)只能用順序結(jié)構(gòu)來存放，非線性結(jié)構(gòu)只能用非順

序結(jié)構(gòu)來存放。

2.算法就是程序。

3.在高級語言(如C、或PASCAL)中，指針類型是原子

類型。

三、計算下列程序段中X=X+1的語句頻度

for(i=1;i<=n;i++)

forQ=1;j<=i;j++)

for(k=1;k<=j;k++)

x=x+1;

[提示]:

i=1時：1=(1+1)X1/2=(1+12)/2

i=2時：1+2=(1+2)x2/2=(2+22)/2

i=3時：1+2+3=(1+3)x3/2=(3+32)/2

i=n時：1+2+3+......+n=(1+n)xn/2=(n+n2)/2

f(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ū)分語句頻度和算法復(fù)雜度：

O(f(n))=0(n3)

四、試編寫算法求一元多項(xiàng)式

Pn(x)=a()+aix+a2x2+a3x3+…anX”的值Pn(x0),并確定算法中的

每一語句的執(zhí)行次數(shù)和整個算法的時間復(fù)雜度,要求時間復(fù)雜度

盡可能的小，規(guī)定算法中不能使用求募函數(shù)。注意：本題中的輸

入ai(i=0,1,…,n),x和n,輸出為Pn(x(),通常算法的輸入和輸出

可采用下列兩種方式之一:

(1)通過參數(shù)表中的參數(shù)顯式傳遞；

(2)通過全局變量隱式傳遞。

試討論這兩種方法的優(yōu)缺點(diǎn)，并在本題算法中以你認(rèn)為較好

的一種方式實(shí)現(xiàn)輸入和輸出。

[提示]:floatPolyValue(floata[],floatx,intn)

{……}

核心語句：

p=1；(x的零次募)

s=0;

i從。到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è)計實(shí)現(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)/6

1.4試編寫算法，求Pn(x)=ao+aix+a2x2+…….+a?n的值Pn(Xo),并確定算法中每一語句的

執(zhí)行次數(shù)和整個算法的時間復(fù)雜度，要求時間復(fù)雜度盡可能小，規(guī)定算法中不能使用求

某函數(shù)。注意：本題中的輸入為含。=0,1,…n)、x和n,輸出為Pn(x())。算法的輸入和輸

出采用下列方法(1)通過參數(shù)表中的參數(shù)顯式傳遞(2)通過全局變量隱式傳遞。討論

兩種方法的優(yōu)缺點(diǎn)，并在算法中以你認(rèn)為較好的一種實(shí)現(xiàn)輸入輸出。

【解答】

(1)通過參數(shù)表中的參數(shù)顯式傳遞

優(yōu)點(diǎn)：當(dāng)沒有調(diào)用函數(shù)時，不占用內(nèi)存，調(diào)用結(jié)束后形參被釋放，實(shí)參維持，函數(shù)通

用性強(qiáng)，移置性強(qiáng)。

缺點(diǎn)：形參須與實(shí)參對應(yīng)，且返回值數(shù)量有限。

(2)通過全局變量隱式傳遞

優(yōu)點(diǎn)：減少實(shí)參與形參的個數(shù)，從而減少內(nèi)存空間以及傳遞數(shù)據(jù)時的時間消耗

缺點(diǎn)：函數(shù)通用性降低，移植性差

算法如下：通過全局變量隱式傳遞參數(shù)

PolyValue()

{inti,n;

floatx,a[],p;

printf(<t\nn=,);

scanf("％f”,&n);

printf(<4\nx=J,);

scanf("％f”,&x);

for0=0;ivn;i++)

scanf(J<%fH,&a[i]);/*執(zhí)行次數(shù)：n次*/

P=a[0];

for(i=1;i<=n;i++)

{p=p+a[i]*x;/*執(zhí)行次數(shù)：n次7

x=x*x;}

printf("%f",p);

)

算法的時間復(fù)雜度：T(n)=O(n)

通過參數(shù)表中的參數(shù)顯式傳遞

floatPolyValue(floata[],floatx,intn)

(

floatp,s;

inti;

p=x；

s=a⑼；

for(i=1;i<=n;i++)

{s=s+a[i]*p;/*執(zhí)行次數(shù):n次*/

P=P*x；}

return(p);

)

算法的時間復(fù)雜度：T(n)=O(n)

第2章線性表

習(xí)題

2.1描述以下三個概念的區(qū)別：頭指針，頭結(jié)點(diǎn)，首元素結(jié)點(diǎn)。

2.2填空：

(1)在順序表中插入或刪除一個元素，需要平均移動一一半

—元素，具體移動的元素個數(shù)與插入或刪除的位置

有關(guān)。

(2)在順序表中，邏輯上相鄰的元素，其物理位置__________

—相鄰。在單鏈表中，邏輯上相鄰的元素，其物理位置—

__________相鄰。

(3)在帶頭結(jié)點(diǎn)的非空單鏈表中，頭結(jié)點(diǎn)的存儲位置由______

指示，首元素結(jié)點(diǎn)的存儲位置由____________指示,

除首元素結(jié)點(diǎn)外，其它任一元素結(jié)點(diǎn)的存儲位置由—其

直接前趨的next域—指示。

2.3已知L是無表頭結(jié)點(diǎn)的單鏈表，且P結(jié)點(diǎn)既不是首元素結(jié)

點(diǎn)，也不是尾元素結(jié)點(diǎn)。按要求從下列語句中選擇合適的語句序

列。

a.在P結(jié)點(diǎn)后插入S結(jié)點(diǎn)的語句序列是：_(4)、(1)一

b.在P結(jié)點(diǎn)前插入S結(jié)點(diǎn)的語句序列是：(7)、(11)、(8)、(4)、

(1)o

c.在表首插入S結(jié)點(diǎn)的語句序列是：(5)、(12)。

d.在表尾插入S結(jié)點(diǎn)的語句序列是：(11)、(9)、(1)、(6)。

供選擇的語句有：

(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)位置上，以保持線性表L的有序性。

［提示］:voidinsert(SeqList*L;ElemTypex)

<方法1>

（1）找出應(yīng)插入位置i,（2）移位，（3）……

<方法2>參P.229

2.5寫一算法，從順序表中刪除自第i個元素開始的k個元素。

[提示]:注意檢查i和k的合法性。

（集體搬遷，“新房”、“舊房”）

〈方法1〉以待移動元素下標(biāo)m（“舊房號”）為中心，

計算應(yīng)移入位置（“新房號”）：

for（m=i—1+k;m<=L—>last;m++）

L—>elem[m—k]=L—>elem[m];

〈方法2〉同時以待移動元素下標(biāo)m和應(yīng)移入位置j為中心：

〈方法3〉以應(yīng)移入位置j為中心，計算待移動元素下標(biāo)：

2.6已知線性表中的元素（整數(shù)）以值遞增有序排列，并以單鏈

表作存儲結(jié)構(gòu)。試寫一高效算法，刪除表中所有大于mink且小

于maxk的元素（若表中存在這樣的元素），分析你的算法的時

間復(fù)雜度（注意：mink和maxk是給定的兩個參變量，它們的

值為任意的整數(shù)）。

[提示]:注意檢查mink和maxk的合法性：mink<maxk

不要一個一個的刪除(多次修改next域)。

(1)找到第一個應(yīng)刪結(jié)點(diǎn)的前驅(qū)pre

(2)找到最后一個應(yīng)刪結(jié)點(diǎn)的后繼s,邊找邊釋放應(yīng)刪結(jié)點(diǎn)

(3)pre—>next=s;

2.7試分別以不同的存儲結(jié)構(gòu)實(shí)現(xiàn)線性表的就地逆置算法，即在

原表的存儲空間將線性表(a-i,82...,an)逆置為(an,a1)。

(1)以一維數(shù)組作存儲結(jié)構(gòu)，設(shè)線性表存于a(1:arrsize)

的前elenum個分量中。

(2)以單鏈表作存儲結(jié)構(gòu)。

[方法1]:在原頭結(jié)點(diǎn)后重新頭插一遍

[方法2]:可設(shè)三個同步移動的指針p,q,r,將q的后繼

r改為p

2.8假設(shè)兩個按元素值遞增有序排列的線性表A和B,均以單

鏈表作為存儲結(jié)構(gòu)，請編寫算法，將A表和B表歸并成一

個按元素值遞減有序的排列的線性表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;I*頭插法*/

(*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)—>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è)有一個循環(huán)鏈表的長度大于1,且表中既無頭結(jié)點(diǎn)也

無頭指針。已知s為指向鏈表某個結(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ù)字字符和其它字符)，試編寫算法來構(gòu)造三個

以循環(huán)鏈表表示的線性表，使每個表中只含同一類的字符，且利

用原表中的結(jié)點(diǎn)空間作為這三個表的結(jié)點(diǎn)空間，頭結(jié)點(diǎn)可另辟空

間。

2.11設(shè)線性表A=(a］，a2,…,am),B=(b.,b2，…,bn),試寫一個按

下列規(guī)則合并A、B為線性表C的算法，使得：

C=(ai,bi，…,am,bm,bm+i,...,bn)當(dāng)m<n時；

或者C=(ai,bi.....an,bn,an+i,...,am)當(dāng)m>n時。

線性表A、B、C均以單鏈表作為存儲結(jié)構(gòu)，且C表利用A

表和B表中的結(jié)點(diǎn)空間構(gòu)成。注意：單鏈表的長度值m和n均

未顯式存儲。

［提示］:voidmerge(LinkListA;LinkListB;LinkList

*C)

或：LinkListmerge(LinkListA;LinkListB)

2.12將一個用循環(huán)鏈表表示的稀疏多項(xiàng)式分解成兩個多項(xiàng)式,

使這兩個多項(xiàng)式中各自僅含奇次項(xiàng)或偶次項(xiàng),并要求利用原鏈表

中的結(jié)點(diǎn)空間來構(gòu)成這兩個鏈表。

［提示］:注明用頭指針還是尾指針。

2.13建立一個帶頭結(jié)點(diǎn)的線性鏈表，用以存放輸入的二進(jìn)制數(shù),

鏈表中每個結(jié)點(diǎn)的data域存放一個二進(jìn)制位。并在此鏈表上實(shí)

現(xiàn)對二進(jìn)制數(shù)加1的運(yùn)算。

［提示］:可將低位放在前面。

2.14設(shè)多項(xiàng)式P(x)采用課本中所述鏈接方法存儲。寫一算法，

對給定的X值，求P(x)的值。

［提示］:floatPolyValue(Polylistp;floatx){.......}

實(shí)習(xí)題

1.將若干城市的信息存入一個帶頭結(jié)點(diǎn)的單鏈表，結(jié)點(diǎn)中的

城市信息包括城市名、城市的位置坐標(biāo)。要求：

(1)給定一個城市名，返回其位置坐標(biāo)；

(2)給定一個位置坐標(biāo)P和一個距離D,返回所有與P的

距離小于等于D的城市。

2.約瑟夫環(huán)問題。

約瑟夫問題的一種描述是：編號為1,2,…，n的n個人

按順時針方向圍坐一圈，每人持有一個密碼(正整數(shù))。一開始

任選一個整數(shù)作為報數(shù)上限值m,從第一個人開始順時針自1開

始順序報數(shù)，報到m時停止報數(shù)。報m的人出列，將他的密碼

作為新的m值，從他在順時針方向上的下一個人開始重新從1

報數(shù)，如此下去，直至所有的人全部出列為止。試設(shè)計一個程序,

求出出列順序。

利用單向循環(huán)鏈表作為存儲結(jié)構(gòu)模擬此過程,按照出列順序

打印出各人的編號。

例如m的初值為20；n=7,7個人的密碼依次是：3,1,7,

2,4,8,4,出列的順序?yàn)?,1,4,7,2,3,5。

第二章答案

約瑟夫環(huán)問題

約瑟夫問題的一種描述為：編號1,2，…,n的n個人按順時針方向圍坐一圈，每個人持有一

個密碼（正整數(shù)）。一開始任選一個報數(shù)上限值m,從第一個人開始順時針自1開始順序報

數(shù)，報到m時停止報數(shù)。報m的人出列，將他的密碼作為新的m值，從他在順時針方向上

的下一個人開始重新從1報數(shù)，如此下去，直至所有的人全部出列為止。試設(shè)計一個程序,

求出出列順序。利用單向循環(huán)鏈表作為存儲結(jié)構(gòu)模擬此過程，按照出列順序打印出各人的編

號。

例如m的初值為20；n=7,7個人的密碼依次是：3,1,7,2,4,8,4,出列順序?yàn)?,1,4,7,2,3,5。

【解答】算法如下：

typedefstructNode

intpassword;

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鏈表申請不到空間!】return;}

L->next=NULL;

r=L;

printf("請輸入數(shù)據(jù)n的值(n>0):");

scanf("%d",&n);

for(j=1;j<=n;j++)/*建立鏈表*/

p=(Node*)malloc(sizeof(Node));

if(p!=NULL)

(

printf("請輸入第％d個人的密碼:"J);

scanf("％d”,&C);

p->password=C;

p->num=j;

r->next=p;

r=p；

)

}

r->next=L->next;

printf("請輸入第一個報數(shù)上限值m(m>0):");

scanf("%d",&m);

printf(M*****************************************\nH),

printf(咄列的順序?yàn)?\n");

q=L；

p=L->next;

while(n!=1)/*計算出列的順序*/

(

j=1；

while(j<m)/*計算當(dāng)前出列的人選p*/

(

q=p；/*q為當(dāng)前結(jié)點(diǎn)p的前驅(qū)結(jié)點(diǎn)*/

p=p->next;

j++；

)

printf("%d->",p->num);

m=p->password;/*獲得新密碼*/

n—；

q->next=p->next;/*p出歹!]*/

r=p；

p=p->next;

free(r);

)

printf("%d\n",p->num);

)

2.7試分別以不同的存儲結(jié)構(gòu)實(shí)現(xiàn)單線表的就地逆置算法，即在原表的存儲空間將線性表

(ai,a2,…,aQ逆置為但門自-力…向)。

【解答】(1)用一維數(shù)組作為存儲結(jié)構(gòu)

voidinvert(SeqList*L,int*num)

(

intj;

ElemTypetmp;

for(j=0;j<=(*num-1)/2;j++)

{tmp=L[j];

L[j]=L[*num-j-1];

L[*num-j-1]=tmp;}

)

(2)用單鏈表作為存儲結(jié)構(gòu)

voidinvert(LinkListL)

(

Node*p,*q,*r;

if(L->next==NULL)return;/*鏈表為空*/

p=L->next;

q=p->next;

p->next=NULL;/*摘下第一個結(jié)點(diǎn)，生成初始逆置表7

while(q!=NULL)/*從第二個結(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+1,........bn)當(dāng)m<=n時，或C=(a1,b1,.......an,bn,an+1,.......am)

當(dāng)m>n時,線性表A、B、C以單鏈表作為存儲結(jié)構(gòu)，且C表利用A表和B表中的結(jié)點(diǎn)空間

構(gòu)成。注意：單鏈表的長度值m和n均未顯式存儲。

【解答】算法如下：

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來指向新連接的表的表尾，初始值指向表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的長度大于B的長度*/

if(pb!=NULL)p->next=pb;/*B的長度大于A的長度*/

C=A;

Return(C);

)

第3章限定性線性表一棧和隊列

習(xí)題

1.按圖3.1(b)所示鐵道(兩側(cè)鐵道均為單向行駛道)進(jìn)行車

廂調(diào)度，回答：

⑴如進(jìn)站的車廂序列為123,則可能得到的出站車廂

序列是什么？123、213、132、231、321(312)

⑵如進(jìn)站的車廂序列為123456,能否得到435612和

135426的出站序列，并說明原因。(即寫出以“S”表示

進(jìn)棧、以“X”表示出棧的棧操作序列)。

SXSSXSSXXXSX或

S1X1S2S3X3S4S5X5X4X2S6X6

2.設(shè)隊列中有A、B、C、D、E這5個元素，其中隊首元

素為Ao如果對這個隊列重復(fù)執(zhí)行下列4步操作：

(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.給出棧的兩種存儲結(jié)構(gòu)形式名稱，在這兩種棧的存儲結(jié)構(gòu)

中如何判別?？张c棧滿？

4.按照四則運(yùn)算加、減、乘、除和嘉運(yùn)算（t）優(yōu)先關(guān)系的

慣例,畫出對下列算術(shù)表達(dá)式求值時操作數(shù)棧和運(yùn)算符棧

的變化過程：

A-B*C/D+EfF

5.試寫一個算法，判斷依次讀入的一個以@為結(jié)束符的字母

序列，是否為形如'序列1&序列T模式的字符序列。

其中序列1和序列2中都不含字符，&二且序列2是序列

1的逆序列。例如，'a+b&b+a，是屬該模式的字符序列,

而'1+3&3—1'則不是。

偎示］:

（1）邊讀邊入棧，直到&

（2）邊讀邊出棧邊比較，直到……

6.假設(shè)表達(dá)式由單字母變量和雙目四則運(yùn)算算符構(gòu)成。試寫

一個算法，將一個通常書寫形式（中綴）且書寫正確的表

達(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á)式的計算過程：(簡便)

順序掃描表達(dá)式，

(1)如果是操作數(shù)，直接入棧；

(2)如果是操作符。p,則連續(xù)退棧兩次，得操作數(shù)X,

Y,計算XopY,并將結(jié)果入棧。

?如何將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式？

順序掃描中綴表達(dá)式，

(1)如果是操作數(shù)，直接輸出；

(2)如果是操作符OP2,則與棧頂操作符。出比較：

如果OP2>OP1，則。P2入棧；

如果Op2=Opi,則脫括號；

如果op2Vop1，則輸出OP1；

7.假設(shè)以帶頭結(jié)點(diǎn)的循環(huán)鏈表表示隊列，并且只設(shè)一個指針

指向隊尾元素結(jié)點(diǎn)(注意不設(shè)頭指針)，試編寫相應(yīng)的隊

列初始化、入隊列和出隊列的算法。

［提示］:參P.56P.70先畫圖.

typedefLinkListCLQueue;

intlnitQueue(CLQU6U6*Q)

intEnterQueue(CLQueueQ,QueueElementTypex)

intDeleteQueue(CLQueueQ,QueueElementType*x)

8.要求循環(huán)隊列不損失一個空間全部都能得到利用，設(shè)置

一個標(biāo)志域tag,以tag為0或1來區(qū)分頭尾指針相同時

的隊列狀態(tài)的空與滿,請編寫與此結(jié)構(gòu)相應(yīng)的入隊與出隊

算法。

［提示］:

初始狀態(tài)：front==0,rear==O,tag==O

隊空條件：front==rear,tag==O

隊滿條件：front==rear,tag==1

其它狀態(tài)：front!=rear,tag==0(或1、2)

入隊操作：

???

…(入隊)

if(front==rear)tag=1；(或直接tag=1)

出隊操作:

…(出隊)

tag=O；

[問題]:如何明確區(qū)分隊空、隊滿、非空非滿三種情況？

9.簡述以下算法的功能(其中棧和隊列的元素類型均為

int)：

(1)voidproc_1(StackS)

{inti,n,A[255];

n=0;

while(!EmptyStack(S))

{n++;Pop(&S,&A[n]);}

for(i=1;i<=n;i++)

Push(&S,A[i]);

)

將棧S逆序。

(2)voidproc_2(StackS,inte)

{StackT;intd;

lnitStack(&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)voidproc_3(Queue*Q)

{StackS;intd;

lnitStack(&S);

while(!EmptyQueue(*Q))

{

DeleteQueue(Q,&d);

Push(&S,d);

)

while(!EmptyStack(S))

{Pop(&S,&d);

EnterQueue(Q?d)

}

}

將隊列Q逆序。

實(shí)習(xí)題

1.回文判斷。稱正讀與反讀都相同的字符序列為“回文”

序列。

試寫一個算法,判斷依次讀入的一個以@為結(jié)束符的

字母序列，是否為形如'序列1&序列2,模式的字符序

歹（I。其中序列1和序列2中都不含字符且序列2

是序列1的逆序列。例如，'a+b&b+a，是屬該模式的字

符序列，而'1+3&3—1'則不是。

2.停車場管理。

設(shè)停車場是一個可停放n輛車的狹長通道，且只有

一個大門可供汽車進(jìn)出。在停車場內(nèi)，汽車按到達(dá)的先后

次序，由北向南依次排列（假設(shè)大門在最南端）。若車場

內(nèi)已停滿n輛車，則后來的汽車需在門外的便道上等候,

當(dāng)有車開走時，便道上的第一輛車即可開入。當(dāng)停車場內(nèi)

某輛車要離開時,在它之后進(jìn)入的車輛必須先退出車場為

它讓路，待該輛車開出大門后，其它車輛再按原次序返回

車場。每輛車離開停車場時，應(yīng)按其停留時間的長短交費(fèi)

（在便道上停留的時間不收費(fèi)）。

試編寫程序，模擬上述管理過程。要求以順序棧模擬

停車場，以鏈隊列模擬便道。從終端讀入汽車到達(dá)或離去

的數(shù)據(jù)，每組數(shù)據(jù)包括三項(xiàng)：①是“到達(dá)”還是“離去”;

②汽車牌照號碼；③“到達(dá)”或“離去”的時刻。與每組

輸入信息相應(yīng)的輸出信息為：如果是到達(dá)的車輛，則輸出

其在停車場中或便道上的位置；如果是離去的車輛，則輸

出其在停車場中停留的時間和應(yīng)交的費(fèi)用。（提示：需另

設(shè)一個棧，臨時停放為讓路而從車場退出的車。）

車庫

暫時退車道30便道

3.商品貨架管理。

商品貨架可以看成一個棧，棧頂商品的生產(chǎn)日期最早，棧

底商品的生產(chǎn)日期最近。上貨時，需要倒貨架，以保證生

產(chǎn)日期較近的商品在較下的位置。用隊列和棧作為周轉(zhuǎn),

實(shí)現(xiàn)上述管理過程。

第三章答案

3.1按3.1（b）所示鐵道（兩側(cè)鐵道均為單向行駛道）進(jìn)行車廂調(diào)度，回答：

(1)如進(jìn)站的車廂序列為123,則可能得到的出站車廂序列是什么？

(2)如進(jìn)站的車廂序列為123456,能否得到435612和135426的出站序列，并說

明原因(即寫出以“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),此時按照“后進(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給出棧的兩種存儲結(jié)構(gòu)形式名稱，在這兩種棧的存儲結(jié)構(gòu)中如何判別?？张c棧滿？

【解答】(1)順序棧(top用來存放棧頂元素的下標(biāo))

判斷棧S空：如果S->top==-1表示棧空。

判斷棧S滿：如果S->top==Stack_Size-1表示棧滿。

(2)鏈棧(top為棧頂指針，指向贏棧頂元素前面的頭結(jié)點(diǎn))

如斷棧空：如果top->nex』=NULL表示?？铡?/p>

判斷棧滿：當(dāng)系統(tǒng)沒有可用空間時，申請不到空間存放要進(jìn)棧的元素，此時棧滿。

3.4照四則運(yùn)算加、減、乘、除和幕運(yùn)算的優(yōu)先慣例，畫出對下列表達(dá)式求值時操作數(shù)棧

和運(yùn)算符棧的變化過程：A-B*C/D+EtF

【解答】

3.5寫一個算法，判斷依次讀入的一個以@為結(jié)束符的字母序列，是否形如'序列1&序列

2,的字符序列。序列1和序列2中都不含，&',且序列2是序列1的逆序列。例

如，’a+b&b+a'是屬于該模式的字符序列，而'1+3&3-1'則不是。

【解答】算法如下：

intlsHuiWen()

Stack*S;

Charch,temp;

lnitStack(&S);

Printf("\n請輸入字符序列：”);

Ch=getchar();

While(ch!=&)/*序歹U1入棧*/

{Push(&S,ch);

ch=getchar();

)

do/*判斷序列2是否是序列1的逆序列*/

{ch=getchar();

Pop(&S,&temp);

if(ch!=temp)/*序列2不是序列1的逆序列*/

{return(FALSE);printf(AnNOn);}

}while(ch!=@&&!lsEmpty(&S))

if(ch==@&&lsEmpty(&S))

{return(TRUE);pnntf(AnYES,,);J/*序列2是序列1的逆序列*/

else

{return(FALSE);printf(,,\nNOn);}

}/*lsHuiWen()*/

3.8要求循環(huán)隊列不損失一個空間全部都能得到利用，設(shè)置一個標(biāo)志tag,以tag為?；?來

區(qū)分頭尾指針相同時的隊列狀態(tài)的空與滿，請編寫與此相應(yīng)的入隊與出隊算法。

【解答】入隊算法：

intEnterQueue(SeqQueue*Q,QueueElementTypex)

{/*將元素x入隊*/

if(Q->front==Q->front&&tag==1)/*隊滿*/

return(FALSE);

if(Q->front==Q->front&&tag==0)/*x入隊前隊空，x入隊后重新設(shè)置標(biāo)志*/

tag=1;

Q->elememt[Q->rear]=x;

Q->rear=(Q->rear+1)%MAXSIZE;/*設(shè)置隊尾指針*/

Return(TRUE);

出隊算法：

intDeleteQueue(SeqQueue*Q,QueueElementType*x)

{/*刪除隊頭元素，用x返回其值*/

if(Q->front==Q->rear&&tag==0)/*隊空*/

return(FALSE);

*x=Q->element[Q->front];

Q->front=(Q->front+1)%MAXSIZE;/*重新設(shè)置隊頭指針*/

if(Q->front==Q->rear)tag=0;/*隊頭元素出隊后隊列為空，重新設(shè)置標(biāo)志域*/

Return(TUUE);

)

編寫求解Hanoi問題的算法，并給出三個盤子搬動時的遞歸調(diào)用過程。

【解答】算法：

voidhanoi(intn,charx,chary,charz)

{/*將塔座X上按直徑由小到大且至上而下編號為1到n的n個圓盤按規(guī)則搬到塔座Z

上，丫可用做輔助塔座*/

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)用過程:

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號搬到C

Hanoi(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號搬至【JC

第4章串

習(xí)題

,,,,

1.設(shè)s=，lAMASTUDENT,t=GOOD,q=WORKERo給出下

列操作的結(jié)果：

StrLength(s);SubString(sub1,s,1,7);

SubString(sub2,s,7,1);

Strlndex(s,,A,,4);StrReplace(s,STUDENT,q);

StrCat(StrCat(sub1,t),StrCat(sub2,q));

［參考答案］

StrLength(s)=14;sub1='IAMA_';sub2=

Strlndex(s,,A,,4)=6;

StrReplace(s,,STUDENT,,q)='IAMAWORKER5;

StrCat(StrCat(sub1,t),StrCat(sub2,q))='IAMAGOOD

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)；

StrLength(S)；StrCat(S,T)；SubString(Sub,S,pos,len)o

［說明］:用單鏈表實(shí)現(xiàn)。

4.敘述以下每對術(shù)語的區(qū)別：空串和空格串；串變量和串常

量；主串和子串；串變量的名字和串變量的值。

5.已知：S=”(xyz)*",T="(x+z)*y”。試?yán)寐?lián)接、求子串和

置換等操作，將S轉(zhuǎn)換為T.

6.S和T是用結(jié)點(diǎn)大小為1的單鏈表存儲的兩個串，設(shè)計一

個算法將串S中首次與T匹配的子串逆置。

7.S是用結(jié)點(diǎn)大小為4的單鏈表存儲的串，分別編寫算法在第

k個字符后插入串T,及從第k個字符刪除len個字符。

以下算法用定長順序串：

8.寫下列算法：

(1)將順序串r中所有值為ch1的字符換成ch2的字符。

(2)將順序串r中所有字符按照相反的次序仍存放在r中。

(3)從順序串r中刪除其值等于ch的所有字符。

(4)從順序串r1中第index個字符起求出首次與串己相同的

子串的起始位置。

(5)從順序串r中刪除所有與串r1相同的子串。

9.寫一個函數(shù)將順序串s1中的第i個字符到第j個字符之間

的字符用s2串替換。

［提示］:(1)用靜態(tài)順序串(2)先移位，后復(fù)制

10.寫算法，實(shí)現(xiàn)順序串的基本操作StrCompare(s,t)o

11.寫算法，實(shí)現(xiàn)順序串的基本操作StrReplace(&s,t,v)o

［提示］:

(1)被替換子串定位(相當(dāng)于第9題中D

(2)被替換子串后面的字符左移或右移(為替換子串準(zhǔn)備房

間)

(3)替換子串入住(復(fù)制)

(4)重復(fù)上述，直到……

第四章答案

4.1設(shè)s='lAMASTUDENT',t='GOOD',q=,WORKER'?給出下列操作的結(jié)果：

【解答】StrLength(s)=14;

SubString(sub1,s,1,7)sub1='lAMA

SubString(sub2,s,7,1)sub2='

Strlndex(s,4,,A,)=6;

StrReplace(s,'STUDENT',q);s='lAMAWORKER,;

StrCat(StrCat(sub1,t),StrCat(sub2,q))sub1='lAMAGOODWORKER'。

4.2編寫算法，實(shí)現(xiàn)串的基本操作StrReplace(S,T,V)o

【解答】算法如下：

intstrReplace(SStringS,SStringT,SStringV)

{/*用串V替換S中的所有子串T*1

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的長度等于串V的長度*/

for(i=0;i<=V.len;i++)/*用V替換T*/

S->ch[pos+i]=V.ch[i];

case>0:/*串T的長度大于串V的長度*/

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個位置*/

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的長度小于串V的長度*/

if(S->len-T.len+V.len)<=MAXLEN/*插入后串長小于MAXLEN*/

{/*將S中子串T后的所有字符后移V.len-T.len個位置*/

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替換T7

S->ch[pos+i]=V.ch[i];

S->len=S->len-T.len+V.len;}

else

/*替換后串長,MAXLEN,但串V可以全部替換*/

if(pos+V.len<=MAXLEN)

{for(i=MAXLEN-1;i>=pos+T.len;i-)

S->ch[i]=s->ch[i-T.len+V.len]

for(i=0;i<=V.len;i++)/*用V替換T7

S->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()7

pos=Strlndex(S,pos+V.len5T);/*求S中下一個子串T的位置*/

}/*while()7

return(1);

}/*StrReplace()*/

附加題：用鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)定位函數(shù)。

【解答】

typedefstructNode

{chardata;

structNode*next;

}Node,*Lstring;

intstrlndex(LstringS,intpos,LstringT)

/*從串S的pos序號起，串T第一次出現(xiàn)的位置7

(

Node*p,*q,*Ppos;

int『0,,j=0;

if(T->next==NULL||S->next==NULL)return(O);

p=S->next;

q=T->next;

while(p!=NULL&&j<pos)/*p指向串S中第pos個字符*/

{p=p->next;j++;}

ifQ!=pos)return(O);

while(p!=NULL&&q!=NULL)

Ppos=p;/*Ppos指向當(dāng)前匹配的起始字符*/

if(p->data==q->data)

{p=p->next;q=q->next;}

else/*從Ppos指向字符的下一個字符起從新匹配*/

{p=Ppos->next;

q=T->head->next;

i++；}

)

if(q==NULL)return(pos+i);/*匹配成功*/

elsereturn(O);/*失敗*/

)

第五章數(shù)組和廣義表

參考題

實(shí)習(xí)題

習(xí)題

1.假設(shè)有6行8列的二維數(shù)組A,每個元素占用6個字節(jié)，存

儲器按字節(jié)編址。已知A的基地址為1000,計算：

(1)數(shù)組A共占用多少字節(jié)；(288)

(2)數(shù)組A的最后一個元素的地址；(1282)

(3)按行存儲時，元素A36的地址；(1126)

(4)按列存儲時，元素A36的地址；(1192)

［注意］:本章自定義數(shù)組的下標(biāo)從1開始。

2.設(shè)有三對角矩陣(a.)nxn,將其三條對角線上的元素逐行地存于

數(shù)組B(1:3n-2)中，使得B[k]=aij,求：

(1)用i,j表示k的下標(biāo)變換公式；

(2)用k表示i,j的下標(biāo)變換公式。

i=k/3+1,j=k%3+i-1=k%3+k/3

或：

i=k/3+1,j=k-2X(k/3)

2.假設(shè)稀疏矩陣A和B均以三元組表作為存儲結(jié)構(gòu)。試寫出矩

陣相加的算法，另設(shè)三元組表C存放結(jié)果矩陣。

[提示]:參考P.28例、P.47例。

4.在稀疏矩陣的快速轉(zhuǎn)置算法5.2中，將計算position[col]的方法

稍加改動，使算法

只占用一個輔助向量空間。

[提示]:

(1)position!k]中為第k列非零元素個數(shù)，k=1,2,n

(2)position[0]=1;(第1列中第一個非零元素的正確位置)

(3)position[k]=position[k-1]+position[k],k=1,

2,n

(4)position[k]=position[k-1],k=n,n-1,,1

5.寫一個在十字鏈表中刪除非零元素au的算法。

［提示］:“刪除”兩次，釋放一次。

6.畫出下面廣義表的兩種存儲結(jié)構(gòu)圖示:

((((a),b)),(((),d),(e,f)))

0|e||0|f

第一種存儲結(jié)構(gòu)(自底向上看)

7.求下列廣義表運(yùn)算的結(jié)果：

(1)HEAD[((a,b),(c,d))];

(2)TAIL[((a,b),(c,d))];

(3)TAIL[HEAD[((a,b),(c,d))]];

(4)HEAD[TAIL[HEAD[((a,b),(c,d))]]];b

(5)TAIL[HEAD[TAIL[((a,b),(c,d))]]];(d)

參考題

8.試設(shè)計一個算法，將數(shù)組A(0:n-1)中的元素循環(huán)右移k位，并

要求只用一個元素大小的附加存儲，元素移動或交換次數(shù)為0(n)。

9.假設(shè)按低下標(biāo)優(yōu)先(以最左的下標(biāo)為主序)存儲整數(shù)數(shù)組A(1:8,

1:2,1:4,1:7)時，第一個元素的字節(jié)地址是100,每個整數(shù)占4個

字節(jié)，問元素A(4,2,3,5)的存儲地址是什么？

10.高下標(biāo)優(yōu)先(以最右的下標(biāo)為主序)存儲整數(shù)數(shù)組A(1:8,1:2,

1:4,1:7)時，順序列出數(shù)組A的所有元素。

11.試編寫一個以三元組形式輸出用十字鏈表表示的稀疏矩陣中非

零元素及其下標(biāo)的算法。

實(shí)習(xí)題

1.若矩陣Amxn中的某個元素aij是第i行中的最小值，同時又是

第j列中的最大值，則稱此元素為該矩陣中的一個馬鞍點(diǎn)。假設(shè)

以二維數(shù)組存儲矩陣，試編寫算法求出矩陣中的所有馬鞍點(diǎn)。

第五章答案

5.2設(shè)有三對角矩陣A”n,將其三條對角線上的元素逐行的存于數(shù)組B[1..3n-2]中，使得

B[k]=aij,求：(1)用i,j表示k的下標(biāo)變換公式；(2)用k表示i、j的下標(biāo)變換公式。

【解答】(1)k=2(i-1)+j

(2)i=[k/3]+1,j=[k/3]+k%3([]取整，％取余)

5.4在稀疏矩陣的快速轉(zhuǎn)置算法5.2中，將計算position[