第一章緒論

一、問(wèn)答題

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

2.敘述四類(lèi)基本數(shù)據(jù)結(jié)構(gòu)的名稱(chēng)與含義。

3.敘述算法的定義與特性。

4.敘述算法的時(shí)間復(fù)雜度。

5.敘述數(shù)據(jù)類(lèi)型的概念。

6.敘述線(xiàn)性結(jié)構(gòu)與非線(xiàn)性結(jié)構(gòu)的差別。

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

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

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

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

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

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

2.算法就是程序。()

3.在高級(jí)語(yǔ)言(如C或PASCAL)中，指針類(lèi)型是原子類(lèi)型。()

三、計(jì)算下列程序段中X=X+1的語(yǔ)句頻度

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

forO=lj<=ij++)

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

x=x+l;

【解答】

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

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

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

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

x=x+1的語(yǔ)句頻度為：

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

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

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

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

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

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

(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)，且返網(wǎ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,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);

)

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

通過(guò)參數(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);

)

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

第二章線(xiàn)性表

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

2.2填空：

(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域—指示。

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

求從下列語(yǔ)句中選擇合適的語(yǔ)句序列。

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

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ǔ)句有：

(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已知線(xiàn)性表L遞增有序。試寫(xiě)一算法，將X插入到L的適當(dāng)位置上，以保持線(xiàn)性表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寫(xiě)一算法，從順序表中刪除自第i個(gè)元素開(kāi)始的k個(gè)元素。

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

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

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

計(jì)算應(yīng)移入位置(“新房號(hào)”)：

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

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

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

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

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

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

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

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

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

(

P=L;

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

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

{

q=p->next;

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

p->next=q;

)

}//Delete_Between

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

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

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

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

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

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

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

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

用原表（即A表和B表的）結(jié)點(diǎn)空間存放表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è)有?個(gè)循環(huán)鏈表的長(zhǎng)度大于1,且表中既無(wú)頭結(jié)點(diǎn)也無(wú)頭指針。已知s為指向鏈

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

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

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

(

p=s;

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

p->next=s;

returnOK;

}//Delete_Pre

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

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

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

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

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

{

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é)點(diǎn)

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è)線(xiàn)性表A=(ai,a2,…,am)，B=(bl,b2.…,bn),試寫(xiě)一個(gè)按下列規(guī)則合并A、B為線(xiàn)性表C

的算法，使得：

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

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

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

注意：?jiǎn)捂湵淼拈L(zhǎng)度值m和n均未顯式存儲(chǔ)。

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

或：LinkListmerge(LinkListA;LinkListB)

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

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

{

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將…個(gè)用循環(huán)鏈表表示的稀疏多項(xiàng)式分解成兩個(gè)多項(xiàng)式，使這兩個(gè)多項(xiàng)式中各自?xún)H含

奇次項(xiàng)或偶次項(xiàng)，并要求利用原鏈表中的結(jié)點(diǎn)空間來(lái)構(gòu)成這兩個(gè)鏈表。

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

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

拆成只含碗欠項(xiàng)的A和只含偶次項(xiàng)的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建立一個(gè)帶頭結(jié)點(diǎn)的線(xià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ǔ)。寫(xiě)一算法，對(duì)給定的x值，求P(x)的值。

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

第三章棧和隊(duì)列

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

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

⑵如進(jìn)站的車(chē)廂序列為123456,能否得到435612和135426的出站序列，并說(shuō)明原因。

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

【解答】

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

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

2.設(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ì)列為止，則是否可能得到輸出序列：

(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(輸出隊(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)

3.給出棧的兩種存儲(chǔ)結(jié)構(gòu)形式名稱(chēng)，在這兩種棧的存儲(chǔ)結(jié)構(gòu)中如何判別?？张c棧滿(mǎn)？

4.按照四則運(yùn)算加、減、乘、除和:耗運(yùn)算（t）優(yōu)先關(guān)系的慣例，畫(huà)出對(duì)下列算術(shù)表達(dá)式

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

A-B*C/D+EtF

【解答】

5.試寫(xiě)個(gè)算法，判斷依次讀入的一個(gè)以@為結(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è)表達(dá)式由單字母變量和雙目四則運(yùn)算算符構(gòu)成。試寫(xiě)一個(gè)算法，將,個(gè)通常書(shū)寫(xiě)形

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

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

new

{

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

符號(hào)

InitStack(s);//s為運(yùn)算符棧

while(*p)

(

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

else

c=gettop(s);

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

else

(

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

(

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

}//while

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

}//else

}//else

p++；

}//while

}//NiBoLan//參見(jiàn)編譯原理教材

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

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

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

(

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

Q->next=Q;

}//InitCiQueue

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

隊(duì)尾元素,Q->next指向頭結(jié)點(diǎn),Q->next->next指向隊(duì)頭元素

{

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)鏈表表示的隊(duì)列Q頭部刪除元素x

(

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

p=Q->next->next;

x=p->data;

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

frcc(p);

returnOK;

}//DeCiQueue

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

來(lái)區(qū)分頭尾指針相同時(shí)的隊(duì)列狀態(tài)的空與滿(mǎn)，請(qǐng)編寫(xiě)與此結(jié)構(gòu)相應(yīng)的入隊(duì)與出隊(duì)算法。

[提示]:

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

隊(duì)空條件：front=rcar,tag=O

隊(duì)滿(mǎn)條件：fronl=rear,tag=1

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

入隊(duì)操作：

…(入隊(duì))

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

出隊(duì)操作：

…(出隊(duì))

tag=0：

[問(wèn)題]:如何明確區(qū)分隊(duì)空、隊(duì)滿(mǎn)、非空非滿(mǎn)三種情況？

9.簡(jiǎn)述以下算法的功能(其中棧和隊(duì)列的元素類(lèi)型均為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)

}

}

將隊(duì)列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ě)算法，實(shí)現(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++)〃新子串長(zhǎng)度與原子串相同時(shí):直接替換

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

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

{

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〃新子串長(zhǎng)度小于原子串時(shí):先將后部左移

(

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é)點(diǎn)。

試編寫(xiě)算法，實(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)。

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.與前一個(gè)程序的區(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í)返回正數(shù),s=t時(shí)返回O,s<t

時(shí)返回負(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的長(zhǎng)度(元素個(gè)數(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)〃返回一個(gè)串淇值等于串s從start位

置起長(zhǎng)為len而子串

{

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

for(r=s;start;start-,r=r->next);〃找至Ustart所對(duì)應(yīng)的結(jié)點(diǎn)指針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.敘述以下每對(duì)術(shù)語(yǔ)的區(qū)別：空串和空格;畏串變量和串常量；主串和子串；串變量的名

字和串變量的值。

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

O,s〈t時(shí)返回負(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++)//新子串長(zhǎng)度與原子串相同時(shí):宜接替換

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

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

|

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〃新子串長(zhǎng)度小于原子串時(shí):先將后部左移

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é)點(diǎn)大小為1的單鏈表存儲(chǔ)的兩個(gè)申，設(shè)計(jì)?個(gè)算法將串S中首次與T

匹配的子串逆置。

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

從第k個(gè)字符刪除Icn個(gè)字符。

以下算法用定長(zhǎng)順序串：

8.寫(xiě)下列算法：

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

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

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

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

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

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

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

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

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

偎示］:

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

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

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

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

實(shí)習(xí)題

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

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

位置。

（1）利用CONCAT.LEN、SUB和EQUAL四種基本運(yùn)算來(lái)實(shí)現(xiàn)。

（2）以順序串作為存儲(chǔ)結(jié)構(gòu)來(lái)實(shí)現(xiàn)。

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

而t中沒(méi)百的字符構(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,每個(gè)元素占用6個(gè)字優(yōu)存儲(chǔ)器按字節(jié)編址。已知A的

基地址為1000,計(jì)算：

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

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

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

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

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

2.設(shè)有三對(duì)角矩陣(a.p將其三條對(duì)角線(xiàn)上的元素逐行地存于數(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均以三元組表作為存儲(chǔ)結(jié)構(gòu)。試寫(xiě)出矩陣相加的算法，另設(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)〃對(duì)矩陣的每一行進(jìn)行加法

{

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中，將計(jì)算p。siti。n［c。l］的方法稍加改動(dòng)，使算法

只占用一個(gè)輔助向量空間。

5.寫(xiě)一個(gè)在十字鏈表中刪除非零元素a,的算法。

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

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

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

111?八?r5TH

JA

111i---1-口ii-i

第一種存儲(chǔ)結(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)

實(shí)習(xí)題

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

則稱(chēng)此元素為該矩陣中的一個(gè)日鞍點(diǎn)。假設(shè)以二維數(shù)組存儲(chǔ)矩陣，試編寫(xiě)算法求

出矩陣中的所有馬鞍點(diǎn)。

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

{

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)//判斷這個(gè)(些)最小值是否鞍點(diǎn)

(

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ù)和二叉樹(shù)

1.試分別畫(huà)出具有3個(gè)結(jié)點(diǎn)的樹(shù)和3個(gè)結(jié)點(diǎn)的二叉樹(shù)的所有不同形態(tài)。

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

3.已知一棵度為k的樹(shù)中有川個(gè)度為1的結(jié)點(diǎn)，m個(gè)度為2的結(jié)點(diǎn)....m個(gè)度為k的

結(jié)點(diǎn)，則該樹(shù)中有多少個(gè)葉子結(jié)點(diǎn)？

［提示］:參考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è)棵二叉樹(shù)的先序序列為EBADCFHGIKJ,中序序歹U為ABCDEFGHIJK,請(qǐng)畫(huà)出該二

叉樹(shù)。

［提示］:參考P.148

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

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

結(jié)點(diǎn)。

6.給出滿(mǎn)足下列條件的所有二義樹(shù)：

a)前序和中序相同

b)中序和后序相同

c)前序和后序相同

［提示］:去異存同。

a)DLR與LDR的相同點(diǎn)：DR,如果無(wú)L,則完全相同，如果無(wú)LR,…。

b)LDR與LRD的相同點(diǎn)：LD,如果無(wú)R,則完全相同。

c)DLR與LRD的相同點(diǎn)：D,如果無(wú)LR,則完全相同。

(如果去D,則為空樹(shù)〉

7.n個(gè)結(jié)點(diǎn)的K叉樹(shù),若用具有k個(gè)child域的等長(zhǎng)鏈結(jié)點(diǎn)存儲(chǔ)樹(shù)的一個(gè)結(jié)點(diǎn)，則空的Child

域有多少個(gè)？

［提示］:參考P.119

8.畫(huà)出與下列已知序列對(duì)應(yīng)的樹(shù)T：

樹(shù)的先根次序訪問(wèn)序列為GFKDA1EBCHJ；

樹(shù)的后根次序訪問(wèn)序列為DIAEKFCJHBG.

［提示］:

(1)先畫(huà)出對(duì)應(yīng)的二叉樹(shù)

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

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

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

(1)請(qǐng)為這8個(gè)字母設(shè)計(jì)哈夫曼編碼，

(2)求平均編碼長(zhǎng)度。

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

否可不用遞歸且不用棧來(lái)完成?請(qǐng)簡(jiǎn)述原因.

［提示］:無(wú)右子的“左下端”

H.畫(huà)出和下列樹(shù)對(duì)應(yīng)的二叉樹(shù)：

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

13.編寫(xiě)遞歸算法：對(duì)于二叉樹(shù)中每一個(gè)元素值為x的結(jié)點(diǎn)，刪去以它為根的子樹(shù)，并釋放

相應(yīng)的空間。

［提示］:

［方法IJ：(1)按先序查找；(2)超前查看了結(jié)點(diǎn)(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é)點(diǎn)(3)用指針參數(shù)：

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

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

(參示例程序)

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

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

［提示］:

(1)先查看線(xiàn)索，無(wú)線(xiàn)索時(shí)用下面規(guī)律：

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

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

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

（參例題）

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

［提示］:

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

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

17.對(duì)以孩子?兄弟鏈表表示的樹(shù)編寫(xiě)計(jì)算樹(shù)的深度的算法。

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

課本）

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

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

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

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

值。

［提中］:

［方法一］:

（1）利用隊(duì)列，初值為根

（2）出隊(duì)訪問(wèn)，并將左、右子入隊(duì)，直到隊(duì)空

（3）記錄每一層中最后一個(gè)結(jié)點(diǎn)在隊(duì)中的位置

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

（5）第1層最后一個(gè)結(jié)點(diǎn)在隊(duì)中的位置為0

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

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

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

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

23.二叉樹(shù)按照二叉鏈表方式存儲(chǔ)，編寫(xiě)算法將二叉樹(shù)左右子樹(shù)進(jìn)行交換。

第七章圖

7.1已知如圖所示的有向圖，請(qǐng)給出該圖的：

（1）每個(gè)頂點(diǎn)的入度、出度；

（2）鄰接矩陣；

（3）鄰接表：

<4）逆鄰接表；