數(shù)據(jù)結(jié)構(gòu)部分課后習(xí)題答案1

第一章緒論

一、問答題

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è)計語言的特點。

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

9.敘述參數(shù)傳遞的主要方式及特點。

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

二、判斷題(在各題后填寫“J”或“X”)

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

2.算法就是程序。()

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

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

fbr(i=l;i<=n;i++)

forO=lj<=ij++)

fbr(k=l;k<=j;k++)

x=x+l;

【解答】

i=l時：1=(l+l)xl/2=(l+l2)/2

i=2時：1+2=(1+2)x272=(2+2?)/2

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

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

x=x+1的語句頻度為：

f(n)=[(1+2+3+...+n)+(l2+22+32+.....+n2)]/2

=[(l+n)xn/2+n(n+1)(2n+1)/6]/2

=n(n+l)(n+2)/6

=n76+n2/2+n/3

區(qū)分語句頻度和算法復(fù)雜度：

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

四、試編寫算法,求一元多項式Pn(x尸ao+a送+a2X%3x3+...anxn的值Pn(Xo)，并確定算法中的

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

使用求塞函數(shù)。注意:本題中的輸入式i=0J…,n),x和n,輸出為Pn(XQ)。通常算法的輸入和

輸出可采用下列兩種方式之一：

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

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

試討論這兩種方法的優(yōu)缺點，并在本題算法中以你認(rèn)為較好的一種方式實現(xiàn)輸入和輸出

[解答]

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

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

用性強，移置性強。

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

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

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

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

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

PolyValue()

{inti,n;

floatx,aQ,p；

printtnnn=M);

scanf("％f”,&n);

printfCnx=")；

scanf(u%f",&x);

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

scanf(u%f",&a[i]);/*執(zhí)行次數(shù)：n次*/

P=a⑼；

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

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

x=x*x;}

printf(-%f\p);

)

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

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

floatPolyValue(floata[],floatx,intn)

(

floatp,s;

inti;

p=x;

s=a[0];

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

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

P=P*x;}

return(p);

)

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

第二章線性表

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

2.2填空：

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

素個數(shù)與插入或刪除的位置有關(guān)。

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

輯上相鄰的元素，其物理位置相鄰。

(3)在帶頭結(jié)點的非空單鏈表中，頭結(jié)點的存儲位置由指示，首元素結(jié)點

的存儲位置由指示，除首元素結(jié)點外，其它任一元素結(jié)點的存儲位置

由—其直接前趨的next域—指示。

23已知L是無表頭結(jié)點的單鏈表，HP結(jié)點既不是首元素結(jié)點，也不是尾元素結(jié)點。按要

求從下列語句中選擇合適的語句序列。

a.在P結(jié)點后插入S結(jié)點的語句序列是：—(4)、⑴

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

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

d.在表尾插入S結(jié)點的語句序列是：(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->ncxt=NULL;

(7)Q=P;

(8)whilc(P->ncxt!=Q)P=P->ncxt;

(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

的有序性。

StatusInsertSqList(SqList&va,intx)〃把x插入遞增有序表va中

(

if(va.length+1>va.listsize)returnERROR;

va.length++;

fbr(i=va.length-1;va.elem[i]>x&&i>=0;i-)

va.clem[i+l]=va.clcm[i];

va.elem[i+l]=x;

returnOK;

}//lnsertSqList

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

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

(集體搬遷，“新房”、“舊房”)

v方法1>以待移動元素卜標(biāo)m(“舊房號”)為中心,

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

fbr(m=i—l+k;m<=L—>last;m++)

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

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

<方法2>以應(yīng)移入位置j為中心，計算待移動元素卜標(biāo)：

2.6已知線性表中的元素(整數(shù))以值遞增有序排列，并以單鏈表作存儲結(jié)構(gòu)。試寫一高效

算法，刪除表中所有大于mink且小于maxk的元素(若表中存在這樣的元素)，分析你的算

法的時間復(fù)雜度(注意：mink和maxk是給定的兩個參變量，它們的值為任意的整數(shù))。

StatusDelete_Between(Linklist&L,intmink,intmaxk)〃刪除元素遞增排列的鏈表L

中值大于mink且小于maxk的所有元素

(

P=L;

while(p->next->data<=mink)p=p->next;//p是最后一個不大于mink的元素

if(p->next)〃如果還有比mink更大的元素

{

q=p->next;

while(q->data<maxk)q=q->next;//q是第一個不小于maxk的元素

p->next=q;

)

}//Delete_Between

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

aj...,3n)逆置為(an，az,...,a1)。

（1）以一維數(shù)組作存儲結(jié)構(gòu)，設(shè)線性表存于a（1:arrsizc）的前clcnum個分量中。

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

［方法1］：在原頭結(jié)點后重新頭插?遍

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

2.8假設(shè)兩個按元素值遞增有序排列的線性表A和B,均以單鏈表作為存儲結(jié)構(gòu)，請編

寫算法，將A表和B表歸并成一個按元素值遞減有序的排列的線性表C,并要求利

用原表（即A表和B表的）結(jié)點空間存放表C.

［提示］:參P28例2-1

<方法1>

voidmerge（LinkListA;LinkListB;LinkList*C）

pa=A—>ncxt;pb=B—>ncxt;

*C=A;(*C)—>next=NULL;

while(pa!=NULL&&pb!=NULL)

{if(pa—>data<=pb—>data)

{smaller=pa;pa=pa—>next;

smaller—>ncxt=(*C)—>ncxt;/*頭插法*/

(*C)—>ncxt=smaller;

}

else

{smaller=pb;pb=pb—>next;

smaller—>next=(*C)—>next;

(*C)—>next=smaller;

}

while(pa!=NULL)

{smaller=pa;pa=pa->ncxt;

smaller->next=(*C)->next;

(*C)—>next=smaller;

}

while(pb!=NULL)

{smal!cr=pb;pb=pb—>next;

smaller—>next=(*C)—>ncxt;

(*C)—>next=smaller;

}

<方法2>

LinkListmcrgc(LinkListA;LinkListB)

LinkListC；

pa=A—>next;pb=B—>next;

C=A;C—>next=NULL;

returnC;

while(pa||pb)

{

if(pa->data<pb->data||!pb)

{_

pc=pa;q=pa?>next;pa?>next=pre;pa=q;〃將A的元素插入新表

else

pc=pb;q=pb->next;pb->next=pre;pb=q;//^B的元素插入新表

}

pre=pc;

}

C=A;A->next=pc;//構(gòu)造新表頭

}//reverse_merge

分析:本將去的思想是，按從小到大的順序依次把A和B的元素插入新

表的頭部pc處，最后處理A或B的剩余元素.

2.9假設(shè)有?個循環(huán)鏈表的長度大于1,且表中既無頭結(jié)點也無頭指針。已知s為指向鏈

表某個結(jié)點的指針，試編寫算法在鏈表中刪除指針s所指結(jié)點的前趨結(jié)點。

［提示］:設(shè)指針p指向s結(jié)點的前趨的前趨，則p與s有何關(guān)系？

StatusDelete_Pre(CiLNode*s)〃刪除單循環(huán)鏈表中結(jié)點s的直接前驅(qū)

(

p=s;

while(p->next->next!=s)p=p->next;〃找至Us的前驅(qū)的前驅(qū)p

p->next=s;

returnOK;

}//Delete_Pre

2.10已知有單鏈表表示的線性表中含有三類字符的數(shù)據(jù)元素(如字母字符、數(shù)字字符和其

它字符)，試編寫算法來構(gòu)造三個以循環(huán)鏈表表示的線性表，使每個表中只含同一類的字符,

且利用原表中的結(jié)點空間作為這三個表的結(jié)點空間，頭結(jié)點可另辟空間。

StatusLinkList_Divide(LinkList&L,CiList&A,CiList&B,CiList&C)〃把單鏈表L

的元素按類型芬為三個循環(huán)鏈表.CiList為帶頭結(jié)點的單循環(huán)鏈表類型.

{

s=L->next;

A=(CiList*)malloc(sizeof(CiLNode));p=A;

B=(CiList*)malloc(sizeof(CiLNode));q=B;

C=(CiList*)malloc(sizeof(CiLNode));r=C;〃建立頭結(jié)點

while(s)

{

iisalphabet(s->data))

{

p->next=s;p=s;

)

elseif(isdigit(s->data))

{

q->next=s;q=s;

)

else

(

r->next=s;r=s;

)

}//while

p->next=A;q->ncxt=B;r->next=C;//完成循環(huán)鏈表

}//LinkList_Divide

2.11設(shè)線性表A=(ai,a2,…,am)，B=(bl,b2.…,bn),試寫一個按下列規(guī)則合并A、B為線性表C

的算法，使得：

C=(ahbi,…,am,bm>b—....,bn)當(dāng)m<n時;

或者C=(ahb(，…,an,bn,an+i,當(dāng)m>n時。

線性表A、B、C均以單鏈表作為存儲結(jié)構(gòu)，且C表利用A表和B表中的結(jié)點空間構(gòu)成。

注意：單鏈表的長度值m和n均未顯式存儲。

［提示］:voidnierge(LinkListA;LinkListB;LinkList*C)

或：LinkListmerge(LinkListA;LinkListB)

voidmerge1(LinkList&A,LinkList&B,LinkList&C)〃把鏈表A和B合并為C,A和

B的元素間隔排列，且使用原存儲空間

{

p=A->next;q=B->next;C=A;

while(p&&q)

{

s=p->next;p->next=q;〃將B的元素插入

於)

(

t=q->next;q->next=s;//iflA非空，將A的元素插入

}

p=s；q=t;

}/ZwhiIe

}//merge1

2.12將…個用循環(huán)鏈表表示的稀疏多項式分解成兩個多項式，使這兩個多項式中各自僅含

奇次項或偶次項，并要求利用原鏈表中的結(jié)點空間來構(gòu)成這兩個鏈表。

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

voidDivide_LinkedPoly(LinkedPoly&L,&A,&B)//把循環(huán)鏈表存儲的稀疏多項式L

拆成只含碗欠項的A和只含偶次項的B

{

p=L->next;

A=(PolyNode*)malloc(sizeof(PolyNode));

B=(PolyNode*)malloc(sizeof(PolyNode));

pa=A;pb=B;

whi!e(p!=L)

if(p->data.exp!=2*(p->data.exp/2))

pa->next=p;pa=p;

)

else

{

pb->next=p;pb=p;

}

p=p->next;

}//while

pa->next=A;pb->next=B;

}//Divide_LinkedPoly

2.13建立一個帶頭結(jié)點的線性鏈表，用以存放輸入的二進制數(shù)，徒表中每個結(jié)點的data域

存放一個二進制位。并在此鏈表上實現(xiàn)對二進制數(shù)加1的運算。

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

2.14設(shè)多項式P(x)采用課本中所述鏈接方法存儲。寫一算法，對給定的x值，求P(x)的值。

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

第三章棧和隊列

1.按圖3.1(b)所示鐵道(兩側(cè)鐵道均為單向行駛道)進行車廂調(diào)度，回答：

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

⑵如進站的車廂序列為123456,能否得到435612和135426的出站序列，并說明原因。

(即寫出以“S”表示進棧、以“X”表示出棧的棧操作序列)。

【解答】

(1)可能得到的出站車廂序列是：123、132、213、231、3210

(2)不能得到435612的出站序列。

因為有S(1)S(2)S(3)S(4)X(4)X(3)S(5)X(5)S(6)S(6),此時按照“后進先出”的原

則,出棧的順序必須為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).

2.設(shè)隊列中有A、B、C、D、E這5個元素，其中隊首元素為A。如果對這個隊列重復(fù)執(zhí)

行下列4步操作：

(1)輸出隊首元素；

(2)把隊首元素值插入到隊尾：

(3)刪除隊首元素：

(4)再次刪除隊首元素。

直到隊列成為空隊列為止，則是否可能得到輸出序列：

(I)A、C、E、C、C(2)A、C、E

(3)A、C、E、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.按照四則運算加、減、乘、除和:耗運算（t）優(yōu)先關(guān)系的慣例，畫出對下列算術(shù)表達式

求值時操作數(shù)棧和運算符棧的變化過程：

A-B*C/D+EtF

【解答】

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

序歹U2'模式的字符序列。其中序列I和序列2中都不含字符，且序列2是序列1

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

［提示］:

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

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

intIsReverse()〃判斷輸入的字符串中⑻前和后部分是否為逆串，是則返回1,否

則返回0

(

InitStack(s);

while((e=getchar())!-&1)

push(s,e);

while((e=getchar())!=,@r)

{

if(StackEmpty(s))return0;

pop(s,c);

if(e!=c)return0;

)

if(!StackEmpty(s))return0;

return1;

}//IsReverse

6.假設(shè)表達式由單字母變量和雙目四則運算算符構(gòu)成。試寫一個算法，將,個通常書寫形

式(中綴)且書寫正確的表達式轉(zhuǎn)換為逆波蘭式(后綴)。

voidNiBoLan(char*str,char*new)//把中綴表達式str轉(zhuǎn)換成逆波蘭式

new

{

p=str;q=new;〃為方便起見，設(shè)str的兩端都加上了優(yōu)先級最低的特殊

符號

InitStack(s);//s為運算符棧

while(*p)

(

if(*p是字母))*q++=*p；〃直接輸出

else

c=gettop(s);

if(*p優(yōu)先級比c高)push(s,*p);

else

(

while(gettop⑸優(yōu)先級不比*p低)

(

pop(s,c);*(q++)=c;

}//while

push(s,*p);〃運算符在棧內(nèi)遵循越往棧頂優(yōu)先級越高的原則

}//else

}//else

p++；

}//while

}//NiBoLan//參見編譯原理教材

7.假設(shè)以帶頭結(jié)點的循環(huán)鏈表表示隊列，并且只設(shè)?個指針指向隊尾元素結(jié)點(注意不設(shè)

頭指針)，試編寫相應(yīng)的隊列初始化、入隊列和出隊列的算法。

voidInitCiQucue(CiQueue&Q)//初始化循環(huán)鏈表表示的隊列Q

(

Q=(CiLNode*)malloc(sizeof{CiLNode));

Q->next=Q;

}//InitCiQueue

voidEnCiQueue(CiQueue&Q,intx)〃把元素x插入循環(huán)鏈表表示的隊列Q,Q指向

隊尾元素,Q->next指向頭結(jié)點,Q->next->next指向隊頭元素

{

p=(CiLNode*)malloc(sizeof([CiLNodc));

p->data=x;

p->next=Q->next;〃直接把p加在Q的后面

Q->next=p;

Q=p;〃修改尾指針

)

StatusDeCiQueue(CiQueue&Q,intx)〃從循環(huán)鏈表表示的隊列Q頭部刪除元素x

(

if(Q==Q->next)returnINFEASIBLE;〃隊歹U已空

p=Q->next->next;

x=p->data;

Q->next->next=p->next;

frcc(p);

returnOK;

}//DeCiQueue

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

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

[提示]:

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

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

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

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

入隊操作：

…(入隊)

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

出隊操作：

…(出隊)

tag=0：

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

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

(1)voidproc!(StackS)

{inti,n,A[255];

n=0;

whilc(!EtnptyStack(S))

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

fbr(i=l;i<=n;i-H-)

Push(&S.A[i]);

}

將棧S逆序。

(2)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的元素。

(3)voidproc_3(Queue*Q)

{StackS;intd;

InitStack(&S);

while(!EmptyQueue(*Q))

(

DclctcQucuc(Q,&d);

Push(&S,d);

)

while(!EmptyStack(S))

{Pop(&S,&d);

EnterQueue(Q,d)

}

}

將隊列Q逆序。

第四章串

1.設(shè)s=YAMASTUDENT：t=,GOOD,,q=,WORKER\給出卜.列操作的結(jié)果:

StrLcngth(s);SubString(sub1,s,1,7);SubString(sub2,s,7,1);

StrIndex(s；A\4);StrReplace(s,'STUDENT\q);

StrCat(StrCat(subl.t),StrCat(sub2,q));

[參考答案]

StrLength(s)=14;

SubString(sub1,s,1,7)sub1=IAMA';

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

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

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

StrCat(StrCat(sub1,t),StrCat(sub2,q))sub^*IAMAGOODWORKER'。

2.編寫算法，實現(xiàn)申的基本操作StrReplace(S,T,V).

StrCat(S,T)；SubString(Sub,S,pos,len)。

intString_Replace(Stringtype&S,StringtypeT,StringtypeV);〃將串S中所有子串T

替換為日并返回置換次數(shù)

{

fbr(n=0,i=l;i<=S[0]-T[0]4-l;i-H-)

(

fbr(j=i,k=l;T[k]&&S[j]=T[k]j-H-,k++);

if(k>T[O])〃找至IJ了qT匹配的子串:分三種情況處理

(

if(T[0]=V[0])

fbr(l=1：1〈=T[O];I++)〃新子串長度與原子串相同時:直接替換

S[i+l-l]=V[l];

elseif(T[0]W[0])〃新子串長度大于原子串時:先將后部右移

{

fbr(I=S[0];l>=i+T[0];l-)

S[l+V[0]-T[0]]=S[l];

fbr(l=l;l<=V[O];l++)

S[i+l-l]=V[l];

}

else〃新子串長度小于原子串時:先將后部左移

(

fdr(l=i+V[O];K=S[O]+V[O]-T[O];l++)

S[I]=S[1-V[O]+T[O]];

fdr(l=l;l<=V[O];l++)

S[i+l-l]=V[l];

}

S[O]=S[O]-T[O]+V[O];

i+=V[O];n++;

}//if

}//fbr

returnn;

}//String_Replace

3.假設(shè)以塊鏈結(jié)構(gòu)表示串，塊的大小為1,且附設(shè)頭結(jié)點。

試編寫算法，實現(xiàn)串的下列基本操作：

StrAsign(S,chars)：StrCopy(S,T)；StrCompare(S,T)：StrLength(S)；StrCat(S,T):

SubString(Sub.S,pos.len)<,

[說明]:用單鏈表實現(xiàn)。

StrAsign(S,chars)；StrCopy(S,T)；StrCompare(S,T)；StrLength(S)；

typedefstruct{

charch;

LStrNode*next;

}LStrNode,*LString;〃鏈串結(jié)構(gòu)

voidStringAssign(LString&s,LStringt)〃把串l賦值給串s

{

s=malloc(sizeof(LStrNode));

fbr(q=s,p=t->ncxt;p;p=p->next)

{

r=(LStrNode*)malloc(sizeof^LStrNode));

r->ch=p->ch;

q->next=r;q=r;

}

q->next=NULL;

}//StringAssign

voidStringCopy(LString&s,LStringt)〃把串t復(fù)制為串s.與前一個程序的區(qū)別在于,

串s業(yè)已存在.

fbr(p=s->next,q=t->next;p&&q;p=p->next,q=q->next)

{

p->ch=q->ch;pre=p;

while(q)

(

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

p->ch=q->ch;

prc->next=p;pre=p;

)

p->next=NULL;

}//StringCopy

charStringCompare(LStrings,LStringt)〃串的比較,s>t時返回正數(shù),s=t時返回O,s<t

時返回負(fù)數(shù)

(

fbr(p=s->next,q=t->next;p&&q&&p->ch=q->ch;p=p->next,q=q->next);

if(!p&&!q)return0;

elseif(!p)return-(q->ch);

elseif(!q)returnp->ch;

elsereturnp->ch-q->ch;

}//StringCompare

intStringLen(LStrings)//求串s的長度(元素個數(shù))

{

for(i=O,p=s->next;p;p=p->next,i++);

returni;

}//StringLen

LString*Concat(LStrings,LStringt)〃連接串s和串t形成新串，并返回指針

{

p=malloc(sizeof(LStrNode));

fbr(q=p,r=s->next;r;r=r->next)

(

q->next=(LStrNode*)malloc(sizeof(LStrNode));

q=q->next;

q->ch=r->ch;

}〃fbr〃復(fù)制串s

fbr(r=t->next;r;r=r->next)

{

q->next=(LStrNodc*)malloc(sizeof(LStrNodc));

q=q->next;

q->ch=r->ch;

}//fbr〃復(fù)制串t

q->next=NULL;

returnp;

}//Concat

LString*SubString(LStrings,intstart,intlen)〃返回一個串淇值等于串s從start位

置起長為len而子串

{

p=malloc(sizeof(LStrNode));q=p;

for(r=s;start;start-,r=r->next);〃找至Ustart所對應(yīng)的結(jié)點指針r

fbr(i=l;i<=len;i4-+,r=r->next)

{

q->next=(LStrNode*)malloc(sizeof(LStrNode));

q=q->next;

q->ch=r->ch;

}〃復(fù)制串t

q->next=NULL;

returnp;

}//Sub_String

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

字和串變量的值。

charStrCompare(Stringtypes,Stringtypet)〃串的比較,s>t時返回正數(shù),s=t時返回

O,s〈t時返回負(fù)數(shù)

{

for(i=1;i<=s[O]&&i<=t[O]&&s[i]=t[i];i-H-);

if|i>s[O]&&i>t[O])return0;

elseif(i>s[0])return-t[i];

elseif(i>t[0])returns[i];

elsereturns[i]-t[i];

}//StrComparc

5.已知：S=”(xyz)*",T="(x+z)*y”。試?yán)寐?lián)接、求子附和置換等操作，將S轉(zhuǎn)換為

T.

intHString_Replace(HString&S,HStringT,HStringV)//堆結(jié)構(gòu)串上的置換操作，返

回置換次藪

(

for(n=0,i=0;i<=S.length-T.length;i++)

{

fbr(j=i,k=0;k<T.length&&S.ch[j]=T.ch[k]j++,k4-+)；

if(k=T.kmgth)〃找到了與T匹配的子串:分三種情況處理

{

if(T.length=V.length)

fbr(I=1;l〈=T.length;l++)//新子串長度與原子串相同時:宜接替換

S.ch[i+l-l]=V.ch[l-l];

elseif(T.length〈V.length)〃新子串長度大于原子串時:先將后部右移

|

fbr(l=S.length-1;l>=i+T.length;l")

S.ch[l+V.length-T.length]=S.ch[l];

fdr(l=O;l<V.length;l++)

S[i+l]=V[l];

else〃新子串長度小于原子串時:先將后部左移

fdr(l=i+V.length;l<S.length+V.length-T.length;l++)

S.ch[l]=S.ch[l-V.iength+T.length];

fbr(l=O;l<V.length;l-H-)

S[M]=V[1];

}

S.length+=V.length-T.length;

i+=V.length;n++;

}//if

}//fbr

returnn;

}//HString_Rcplacc

6.S和T是用結(jié)點大小為1的單鏈表存儲的兩個申，設(shè)計?個算法將串S中首次與T

匹配的子串逆置。

7.S是用結(jié)點大小為4的單鏈表存儲的串，分別編寫算法在第k個字符后插入由T,及

從第k個字符刪除Icn個字符。

以下算法用定長順序串：

8.寫下列算法：

（1）將順序串1?中所有值為chi的字符換成ch2的字符。

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

<3）從順序串1?中刪除其值等于ch的所有字符。

（4）從順序串rl中第index個字符起求出首次與串r2相同的子串的起始位置。

<5）從順序串「中刪除所行與串rl相同的子串。

9.寫一個函數(shù)將順序串si中的第i個字符到第j個字符之間的字符用s2串替換。

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

10.寫算法，實現(xiàn)順序串的基本操作Sti€ompare（s,t）。

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

偎示］:

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

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

<3）替換子串入?。◤?fù)制）

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

實習(xí)題

I.?、已知串S和T,試以以下兩種方式編寫算法，求得所有包含在S中而不包

含在T中的字符構(gòu)成的新申R,以及新申R中每個字符在串S中第?次出現(xiàn)的

位置。

（1）利用CONCAT.LEN、SUB和EQUAL四種基本運算來實現(xiàn)。

（2）以順序串作為存儲結(jié)構(gòu)來實現(xiàn)。

voidString_Subtract（Stringtypes.Stringtypet,Stringtype&r）〃求所有包含在串s中

而t中沒百的字符構(gòu)成的新串r

StrAssign(r,M);

for(i=1;i<=Strlen(s);i++)

StrAssign(c,SubString(s,i,1));

fdr(j=l;j<i&&StrComparc(c,SubString(sJ』));j4T);〃判斷s的當(dāng)前字符c是否第

一次出現(xiàn)

{

fbr(k=l;kv=Strlen(t)&&StrCompare(c,Substring。,k,l));k++);〃判斷當(dāng)前字符是

否包含在t中

if(k>Strlen(t))StrAssign(r,Concat(r,c));

)

}//fbr

}//String_Subtract

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

1.假設(shè)有6行8列的二維數(shù)組A,每個元素占用6個字優(yōu)存儲器按字節(jié)編址。已知A的

基地址為1000,計算：

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

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

(3)按行存儲時，元素A36的地址：(H26)

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

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

2.設(shè)有三對角矩陣(a.p將其三條對角線上的元素逐行地存于數(shù)組B(l:3n-2)中，使得

B[k]=ajj,求：

(1)用ij表示k的卜.標(biāo)變換公式：

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

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

或：

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

3.假設(shè)稀疏矩陣A和B均以三元組表作為存儲結(jié)構(gòu)。試寫出矩陣相加的算法，另設(shè)三元組

表C存放結(jié)果矩陣。

voidTSMatrix_Add(TSMatrixA,TSMatrixB,TSMatrix&C)〃三元組表示的稀疏矩

陣加法

(

C.mu=A.mu;C.nu=A.nu;C.tu=O;

pa=l;pb=l;pc=l;

for(x=l;x<=A.mu;xH)〃對矩陣的每一行進行加法

{

while(A.data[pa].i<x)pa++;

while(B.data[pb].i<x)pb++;

while(A.data[pa].i==x&&B.data[pb].i==x)//行列值都相等的元素

if(A.data[pa].j=B.data[pb].j)

ce=A.data[pa].e+B.data[pb].e;

if(ce)〃和不為0

(

C.data[pc].i=x;

C.data[pc].j=A.data[pa].j;

C.data[pc].e=ce;

pa++;pb++;pc++;

)

}//if

elseif(A.data[pa].j>B.data[pb].j)

|

C.data[pc].i=x;

C.data[pc].j=B.data[pb].j;

C.data[pc].e=B.data[pb].e;

pb++；pc++;

}

else

{

C.data[pc].i=x;

C.data[pc].j=A.data[pa].j;

C.data[pc].e=A.data[pa].e

pa++；pc-w-;

)

}//while

while(A.data[pa]=x)//fiAA中剩余的元素(第x行)

{

C.data[pc].i=x;

C.data[pc].j=A.data[pa].j;

C.data[pc].e=A.data[pa].e

pa++;pc++;

}

while(B.data[pb]==x)//jffiAB中剩余的元素(第x行)

{

C.data[pc].i=x;

C.data[pc].j=B.data[pb].j;

C.data[pc].e=B.data[pb].e;

pb++;pc++;

}

}//fbr

C.tu=pc;

}//TSMatrix_Add

4.在稀疏矩陣的快速轉(zhuǎn)置算法5.2中，將計算p。siti。n［c。l］的方法稍加改動，使算法

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

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

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

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

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

111?八?r5TH

JA

111i---1-口ii-i

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

7.求下列廣義表運算的結(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)

實習(xí)題

若矩陣中的某個元素a”是第i行中的最小值，同時又是第j列中的最大值,

則稱此元素為該矩陣中的一個日鞍點。假設(shè)以二維數(shù)組存儲矩陣，試編寫算法求

出矩陣中的所有馬鞍點。

voidGet_Saddle(intA[m][n])〃求矩陣A中的馬鞍點

{

for(i=0;i<m;i++)

{

fbr(min=A[i][O],j=O;j<n;j++)

if(A[i][j]<min)min=A[i][j];〃求一?行中的最小值

for(j=0^<nj-H-)

if(A[i][j]=min)//判斷這個(些)最小值是否鞍點

(

fbr(flag=1,k=0;k<m;k-H-)

if(min<A[k][j])flag=0;

printf("Foundasaddleelement!\nA[%d][%d]=%d",ij,A[i][j]);

)

}//fbr

}//Get_Saddle

第六章數(shù)和二叉樹

1.試分別畫出具有3個結(jié)點的樹和3個結(jié)點的二叉樹的所有不同形態(tài)。

2.對題1所得各種形態(tài)的二叉樹，分別寫出前序、中序和后序遍歷的序列。

3.已知一棵度為k的樹中有川個度為1的結(jié)點，m個度為2的結(jié)點....m個度為k的

結(jié)點，則該樹中有多少個葉子結(jié)點？

［提示］:參考P.H6性質(zhì)3

■:n=no+ii|+...+W

B=ni+2n2+3n3+...+knk

n=B+1

/.no+ni+....+叫=m+2由+3由+...+knk+l

n0=n2+2n3+....+(k-l)nk+1

4.假設(shè)棵二叉樹的先序序列為EBADCFHGIKJ,中序序歹U為ABCDEFGHIJK,請畫出該二

叉樹。

［提示］:參考P.148

5已知二叉樹有50個葉子結(jié)點，則該二叉樹的總結(jié)點數(shù)至少應(yīng)有多少個？

［提示］:可參考哈夫曼樹的結(jié)構(gòu)，共i層有i個葉子結(jié)點，i-1個度為2的結(jié)點，無度為1的

結(jié)點。

6.給出滿足下列條件的所有二義樹：

a)前序和中序相同

b)中序和后序相同

c)前序和后序相同

［提示］:去異存同。

a)DLR與LDR的相同點：DR,如果無L,則完全相同，如果無LR,…。

b)LDR與LRD的相同點：LD,如果無R,則完全相同。

c)DLR與LRD的相同點：D,如果無LR,則完全相同。

(如果去D,則為空樹〉

7.n個結(jié)點的K叉樹,若用具有k個child域的等長鏈結(jié)點存儲樹的一個結(jié)點，則空的Child

域有多少個？

［提示］:參考P.119

8.畫出與下列已知序列對應(yīng)的樹T：

樹的先根次序訪問序列為GFKDA1EBCHJ；

樹的后根次序訪問序列為DIAEKFCJHBG.

［提示］:

(1)先畫出對應(yīng)的二叉樹

(2)樹的后根序列與對應(yīng)二叉樹的中序序列相同

9.假設(shè)用于通訊的電文僅由8個字母組成，字母在電文中出現(xiàn)的頻率分別為：

0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10

(1)請為這8個字母設(shè)計哈夫曼編碼，

(2)求平均編碼長度。

10.已知二叉樹采用二叉鏈表存放，要求返回二叉樹T的后序序列中的第一個結(jié)點的指針，是

否可不用遞歸且不用棧來完成?請簡述原因.

［提示］:無右子的“左下端”

H.畫出和下列樹對應(yīng)的二叉樹：

12.已知二叉樹按照二義鏈表方式存儲，編寫算法，計算二叉樹中葉子結(jié)點的數(shù)目。

13.編寫遞歸算法：對于二叉樹中每一個元素值為x的結(jié)點，刪去以它為根的子樹，并釋放

相應(yīng)的空間。

［提示］:

［方法IJ：(1)按先序查找；(2)超前查看了結(jié)點(3)按后序釋放：

voidDelSubTree(BiTree*bt,DataTypex)

(

if(*bt!=NULL&&(?bt)->data=x)

{FreeTree(*bt);

*bt=NULL;

}

elseDclTrcc(*bt,x)

voidDelTree(BiTreebt,DataTypex)

{if(bt)

{if(bt->LChiid&&bt->LChild->data=x)

{FreeTree(bt->LChild);

bt->LChi!d=NULL;

if(bt->RChild&&bt->RChild->data=x)

{FreeTree(bt->RChild);

bt->RChild=NULL;

DelTree(bt->LChild,x);

DelTree(bt->RChild,x);

}

}

［方法2］：(1)先序查找：(2)直接查看當(dāng)前根結(jié)點(3)用指針參數(shù)：

［方法3］：(1)先序查找：(2)直接查看當(dāng)前根結(jié)點

(3)通過函數(shù)值，返回刪除后結(jié)果；

(參示例程序)

14.分別寫函數(shù)完成：在先序線索二叉樹T中，查找給定結(jié)點*p在先序序列中的后繼。在

后序線索二義樹T中，查找給定結(jié)點*p在后序序列中的前驅(qū)。

［提示］:

(1)先查看線索，無線索時用下面規(guī)律：

（2）結(jié)點*p在先序序列中的后繼為其左子或右子：

（3）結(jié)點*p在后序序列中的前驅(qū)也是其左子或右子。

15.分別寫出算法，實現(xiàn)在中序線索二叉樹中查找給定結(jié)點*p在中序序列中的前驅(qū)與后繼。

（參例題）

16.編寫算法，對一棵以孩子-兄弟鏈表表示的樹統(tǒng)計其葉子的個數(shù)。

［提示］:

（1）可將孩子-兄弟鏈表劃分為根、首子樹、兄弟樹，遞歸處理。

（2）可利用返回值，或全局變量。

17.對以孩子?兄弟鏈表表示的樹編寫計算樹的深度的算法。

18.已知二叉樹按照二叉鏈表方式存儲,利用棧的基本操作寫出后序遍歷非遞歸的算法。（參

課本）

19.設(shè)一叉樹按二叉鏈表存放，寫算法判別一棵二叉樹是否是一棵1E則二叉樹。正則二叉樹

是指：在二叉樹中不存在子樹個數(shù)為1的結(jié)點。

［提示］:可利用任何遞歸、非遞歸遍歷算法。

20.計算二.叉樹最大寬度的算法。二叉樹的最大寬度是指：二叉樹所有層中結(jié)點個數(shù)的最大

值。

［提中］:

［方法一］:

（1）利用隊列，初值為根

（2）出隊訪問，并將左、右子入隊，直到隊空

（3）記錄每一層中最后一個結(jié)點在隊中的位置

（4）第i層最后一個結(jié)點的右子，必是第i+1層的最后一個結(jié)點

（5）第1層最后一個結(jié)點在隊中的位置為0

［方法二］:利用層號和全局?jǐn)?shù)組，任意遍歷、統(tǒng)計

21.已知二叉樹按照二叉鏈表方式存儲,利用棧的基本操作寫出先序遍歷非遞歸形式的算法。

22.證明：給定棵二義樹的前序序列與中序序列，可唯?確定這棵二義樹：

給定一棵一叉樹的后序序列與中序序列，可唯一確定這棵二叉樹；

23.二叉樹按照二叉鏈表方式存儲，編寫算法將二叉樹左右子樹進行交換。

第七章圖

7.1已知如圖所示的有向圖，請給出該圖的：

（1）每個頂點的入度、出度；

（2）鄰接矩陣；

（3）鄰接表：

<4）逆鄰接表；