數(shù)據(jù)結(jié)構(gòu)課后習題第一二三四五六七章

第一章緒論

1.1簡述下列概念：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)類型、數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、線性結(jié)構(gòu)、非線性結(jié)構(gòu)。

?數(shù)據(jù)：指能夠被計算機識別、存儲和加工處理的信息載體。

?數(shù)據(jù)元素：就是數(shù)據(jù)的基本單位，在某些情況下，數(shù)據(jù)元素也稱為元素、結(jié)點、頂點、記錄。數(shù)據(jù)元素有時可以由若

干數(shù)據(jù)項組成。

?數(shù)據(jù)類型：是一個值的集合以及在這些值上定義的一組操作的總稱。通常數(shù)據(jù)類型可以看作是程序設(shè)計語言中已實現(xiàn)

的數(shù)據(jù)結(jié)構(gòu)。

?數(shù)據(jù)結(jié)構(gòu)：指的是數(shù)據(jù)之間的相互關(guān)系，即數(shù)據(jù)的組織形式。一般包括三個方面的內(nèi)容:數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)

和數(shù)據(jù)的運算。

?邏輯結(jié)構(gòu)：指數(shù)據(jù)元素之間的邏輯關(guān)系。

?存儲結(jié)構(gòu)：數(shù)據(jù)元素及其關(guān)系在計算機存儲器內(nèi)的表示，稱為數(shù)據(jù)的存儲結(jié)構(gòu).

?線性結(jié)構(gòu)：數(shù)據(jù)邏輯結(jié)構(gòu)中的一類。它的特征是若結(jié)構(gòu)為非空集，則該結(jié)構(gòu)有且只有一個開始結(jié)點和一個終端結(jié)點，

并且所有結(jié)點都有且只有?個直接前趨和一個直接后繼。線性表就是一個典型的線性結(jié)構(gòu)。棧、隊列、串等都是線性

結(jié)構(gòu)。

?非線性結(jié)構(gòu)：數(shù)據(jù)邏輯結(jié)構(gòu)中的另一大類，它的邏輯特征是一個結(jié)點可能有多個直接前趨和直接后繼。數(shù)組、廣義表、

樹和圖等數(shù)據(jù)結(jié)構(gòu)都是非線性結(jié)構(gòu)。

1.2試舉?個數(shù)據(jù)結(jié)構(gòu)的例子、敘述其邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、運算三個方面的內(nèi)容。

答：

例如有一張學生體檢情況登記表，記錄了一個班的學生的身高、體重等各項體檢信息。這張登記表中，每個學生

的各項體檢信息排在一行上。這個表就是一個數(shù)據(jù)結(jié)構(gòu)。每個記錄（有姓名，學號，身高和體重等字段）就是一個結(jié)點，

對于整個表來說，只有一個開始結(jié)點（它的前面無記錄）和一個終端結(jié)點（它的后面無記錄），其他的結(jié)點則各有一個也只

有一個直接前趨和直接后繼（它的前面和后面均有且只有一個記錄）。這幾個關(guān)系就確定了這個表的邏輯結(jié)構(gòu)是線性結(jié)

構(gòu)。

這個表中的數(shù)據(jù)如何存儲到計算機里，并且如何表示數(shù)據(jù)元素之間的關(guān)系呢？即用一片連續(xù)的內(nèi)存單元來存放這些

記錄（如用數(shù)組表示）還是隨機存放各結(jié)點數(shù)據(jù)再用指針進行鏈接呢？這就是存儲結(jié)構(gòu)的問題。

在這個表的某種存儲結(jié)構(gòu)基礎(chǔ)上，可實現(xiàn)對這張表中的記錄進行查詢，修改，刪除等操作。對這個表可以進行哪

些操作以及如何實現(xiàn)這些操作就是數(shù)據(jù)的運算問題了。

1.3常用的存儲表示方法有咖兒種？

答：

常用的存儲表示方法有四種：

?順序存儲方法：它是把邏輯上相鄰的結(jié)點存儲在物理位置相鄰的存儲單元里，結(jié)點間的邏輯關(guān)系由存儲單元的鄰接

關(guān)系來體現(xiàn)。由此得到的存儲表示稱為順序存儲結(jié)構(gòu)，通常借助程序語言的數(shù)組描述。

?鏈接存儲方法：它不要求邏輯上相鄰的結(jié)點在物理位置上亦相鄰，結(jié)點間的邏輯關(guān)系是由附加的指針字段表示。由

此得到的存儲表示稱為鏈式存儲結(jié)構(gòu)，通常借助于程序語言的指針類型描述。

?索引存儲方法：除建立存儲結(jié)點信息外，還建立附加的索引表來標識結(jié)點的地址。組成索引表的索引項由結(jié)點的關(guān)

鍵字和地址組成。若每個結(jié)點在索引表中都有一個索引項，則該索引表稱之為稠密索引(DenseIndex)。若一組結(jié)點在

索引表中只對應(yīng)一個索引項，則該索引表稱為稀疏索引。

?散列存儲方法：就是根據(jù)結(jié)點的關(guān)鍵字直接計算出該結(jié)點的存儲地址

1.4設(shè)三個函數(shù)f,g,h分別為f(n)=100n3+n2+1000.g(n)=25n3+5000n2,h(n)=nl.5+5000nlgn請判斷下列關(guān)系是否成立：

(l)f(n)=O(g(n))

(2)g(n)=O(f(n))

⑶h(n)=0(nl.5)

(4)h(n)=O(nlgn)

分析：

數(shù)學符號"0”的嚴格的數(shù)學定義：

若T(n)和f(n)是定義在正整數(shù)集合上的兩個函數(shù)，則T(n)=0(f(n))表示存在正的常數(shù)C和nO,使得當nNnO

時都滿足gT(n)<C?f(n)?

通俗地說，就是當n-8時，f(n)的函數(shù)值增長速度與T(n)的增長速度同階。一般，一個函數(shù)的增長速度與該函數(shù)

的最高次階同階。

即：

O(f(n))=n3

O(g(n))=n3

0(h(n))=nl.5

所以答案為：

答：

?(1)成立。

?(2)成立。

?(3)成立。

?(4)不成立。

1.5設(shè)有兩個算法在同一機器上運行，其執(zhí)行時間分別為100n2和2n,要使前者快于后者，n至少要多大？

分析：

要使前者快于后者，即前者的時間消耗低于后者，即：

100n2<2n

求解上式，可得

答：

n=15

1.6設(shè)n為正整數(shù)，利用大“O”記號，將卜.列程序段的執(zhí)行時間表示為n的函數(shù)。

⑴i=l;k=0;

while(i<n)

{k=k+10*i;i++;

)

分析：

i=l;//l

k=0;//I

while(i<n)//n

{k=k+10*i;//n-1

i++;//n-1

)

由以上列出的各語句的頻度，可得該程序段的時間消耗：

T(n)=l+l+n+(n-l)+(n-l)=3n

可表示為T(n)=O(n)

(2)i=0;k=0;

do{

k=k+10*i;i++;

)

while(i<n);

分析：

i=O;//l

k=0;//I

do{//n

k=k+10*i;//n

i++;〃n

)

while(i<n);//n

由以上列出的各語句的頻度，可得該程序段的時間消耗：

T(n)=1+1+n+n+n+n=4n+2

可表示為T(n)=O(n)

⑶i=l；j=O；

while(i-Fj<=n)

(

if(i>j)j++;

elsei++;

)

分析：

通過分析以上程序段，可將i+j看成一個控制循環(huán)次數(shù)的變量，且每執(zhí)行一次循環(huán)，i+j的值加1。該程序段的主要

時間消耗是while循環(huán)，而while循環(huán)共做了n次，所以該程序段的執(zhí)行時間為：

T(n)=O(n)

(4)x=n;//n>l

while(x>=(y+l)*(y+l))

y++;

分析：

由x=n且x的值在程序中不變，又while的循環(huán)條件(x>=(y+l)*(y+l))可知：當(y+l)*(y+l)剛超過n的值時退出循

環(huán)。

由(y+l)*(y+l)<n得：y<r1Ao.5-1

所以，該程序段的執(zhí)行時間為：

向下取整(nN).5-l)

(5)x=91;y=100;

while(y>0)

if(x>100)

{x=x-10;y-;}

elsex++;

分析：

x=91;//l

y=100;//l

while(y>0)//1101

if(x>100)//1100

{x=x-10;//100

y-;//100

)

else

x++;//1000

以上程序段右側(cè)列出了執(zhí)行次數(shù)。該程序段的執(zhí)行時間為：

T(n)=O(1)

1.7算法的時間復雜度僅旨問題的規(guī)模相關(guān)嗎？

答：

算法的時間復雜度不僅與問題的規(guī)模相關(guān)，還與輸入實例中的初始狀態(tài)有關(guān)。但在最壞的情況下，其時間復雜度

就是只與求解問題的規(guī)模相關(guān)的。我們在討論時間復雜度時，一般就是以最壞情況下的時間復雜度為準的。

1.8按增長率由小至大的順序排列下列各函數(shù):

2100,(3/2)n,(2/3)n,nn,n0.5,n!,2n,Ign,nlgn,n(3/2)

答：

常見的時間復雜度按數(shù)量級遞增排列，依次為:常數(shù)階0(1)、對數(shù)階0(log2n)、線性階0(n)、線性對數(shù)階0(nlog2n)、

平方階0(n2)、立方階0(n3)、k次方階0(nk)、指數(shù)階0(2n)。

先將題中的函數(shù)分成如下幾類：

常數(shù)階:2100

對數(shù)階：Ign

K次方階:n0.5、n(3/2)

指數(shù)階(按指數(shù)由小到大排):nlgn、(3/2)n、2n>n!、nn

注意：(2/3)\i由于底數(shù)小于1,所以是一個遞減函數(shù)，其數(shù)量級應(yīng)小于常數(shù)階。

根據(jù)以上分析按增長率由小至大的順序可排列如下：

(2/3)n<2100<Ign<n0.5<n(3/2)<nlgn<(3/2)n<2n<n!<nn

1.9有時為了比較兩個同數(shù)量級算法的優(yōu)劣，須突出主項的常數(shù)因子，而將低次項用大"0"記號表示。例如，設(shè)

Tl(n)=1.39nlgn+100n+256=L39nlgn+0(n),T2(n)=2.0nlgn-2n=2.01gn+O(n),這兩個式子表示，當n足夠大時Tl(n)優(yōu)于

T2(n),因為前者的常數(shù)因子小于后者。請用此方法表示下列函數(shù)，并指出當n足夠大時，哪一個較優(yōu)，哪一個較劣？

函數(shù)大"O”表示優(yōu)劣

(l)Tl(n)=5n2-3n+601gn5n2+O(n)較差

(2)T2(n)=3n2+1000n+31gn3n2+O(n)其次

(3)T3(n)=8n2+31gn8n2+O(lgn)最差

(4)T4(n)=1.5n2+6000nlgnL5n2+O(nlgn)最優(yōu)

第二章線性表

2.6卜述算法的功能是什么？

LinkListDemo(LinkListL){//L是無頭結(jié)點單鏈表

ListNode*Q,*P;

if(L&&L->next){

Q=L;L=L->next;P=L;

while(P->next)P=P->next;

P->next=Q;Q->next=NULL;

)

returnL;

)//Demo

答：

該算法的功能是：將開始結(jié)點摘下鏈接到終端結(jié)點之后成為新的終端結(jié)點，而原來的第二個結(jié)點成為新的開始結(jié)

點，返回新鏈表的頭指針。

關(guān)閉

2.7設(shè)線性表的n個結(jié)點定義為(aO,al,...an-l),重寫順序表上實現(xiàn)的插入和刪除算法：InsertList和DeleteList.

解：算法如下：

#defineListSize100〃假定表空間大小為100

typedefintDataType;//假定DataType的類型為int型

typedefstruct{

DataTypedata[ListSize];//向量data用于存放表結(jié)點

intlength;//當前的表長度

}Seqlist;

〃以上為定義表結(jié)構(gòu)

voidInsertList(Seqlist*L,Datatypex,inti)

(

〃將新結(jié)點x插入L所指的順序表的第i個結(jié)點ai的位置上，即插入的合法位置為：0<=i<=L->length

intj；

if(i<0IIi>L->length)

Eiror("positionerror");〃非法位置，退出，該函數(shù)定義見教材P7.

if(L->length>=ListSize)

ErrorC4overflowH);

for(j=L->length-1;j>=i;j—)

L->data[j+1]=L->data|j);

L->data[i]=x;

L->length++;

)

voidDeleteList(Seqlist*L,inti)

{〃從L所指的順序表中刪除第i個結(jié)點ai,合法的刪除位置為0<=i<=L->length-l

intj;

if(i<0IIi>=L->length)

Error(”positionerror");

for(j=i;j<L->length;j++)

L->data[j]=L->data[j+1];〃結(jié)點前移

L->length-;〃表長減小

)

關(guān)閉

2.8試分別用順序袤和單鏈表作為存儲結(jié)構(gòu)，實現(xiàn)將線性表(aO,al,...an-l)就地逆置的操作，所謂“就地”指輔助空間應(yīng)為

0(1)。

答：

1.順序表：

要將該表逆置，可以將表中的開始結(jié)點與終端結(jié)點互換，第二個結(jié)點與倒數(shù)第二個結(jié)點互換，如此反復，就可將

整個表逆置了。算法如下：

〃順序表結(jié)構(gòu)定義同上題

voidReverseList(Seqlist*L)

(

DataTypetemp;〃設(shè)置臨時空間用于存放data

inti;

for(i=0;i<=L->length/2;i++)//L->length/2為整除運算

{temp=L->data[i];//交換數(shù)據(jù)

L->data[i]=L->data[L->length-1-i];

L->data[L->length-1-i]=temp;

)

2.鏈表：

分析：

可以用交換數(shù)據(jù)的方式來達到逆置的目的。但是由于是單鏈表，數(shù)據(jù)的存取不是隨機的，因此算法效率太低。可

以利用指針改指來達到表逆置的目的。具體情況入下：

(1)當鏈表為空表或只有一個結(jié)點時，該鏈表的逆置鏈表與原表相同.

(2)當鏈表含2個以上結(jié)點時，可將該鏈表處理成只含第一結(jié)點的帶頭結(jié)點鏈表和一個無頭結(jié)點的包含該鏈表剩余

結(jié)點的鏈表。然后，將該無頭結(jié)點鏈表中的所有結(jié)點順著鏈表指針，由前往后將每個結(jié)點依次從無頭結(jié)點鏈表中摘下,

作為第一個結(jié)點插入到帶頭結(jié)點鏈表中。這樣就可以得到逆置的鏈表。算法是這樣的：

結(jié)點結(jié)構(gòu)定義如下：

typedefcharDataType；〃假設(shè)結(jié)點的數(shù)據(jù)域類型的字符

typedefstructnode{〃結(jié)點類型定義

DataTypedata;〃結(jié)點的數(shù)據(jù)域

structnode*next;〃結(jié)點的指針域

JListNode;

typedefListNode*LinkList;

ListNode*p;

LinkListhead;

LinkListReverseList(LinkListhead)

{〃將head所指的單鏈表(帶頭結(jié)點)逆置

ListNode*p產(chǎn)q，設(shè)置兩個臨時指針變量if(head->next&&head->next->next)

{〃當鏈表不是空表或單結(jié)點時

p=head->next;

q=p->next;

p->next二NULL;〃將開始結(jié)點變成終端結(jié)點

while(q)

{〃每次循環(huán)將后一個結(jié)點變成開始結(jié)點

p=q；

q=q->next;

p->next=head->next;

head->next=p;

}

returnhead;

)

returnhead;〃如是空表或單結(jié)點表，直接返回head

關(guān)閉

2.9設(shè)順序表L是一個遞增有序表，試寫一算法，將x插入L中，并使L仍是一個有序表。

答：

因已知順序表L是遞增有序表，所以只要從順序表終端結(jié)點(設(shè)為i位置元素)開始向前尋找到第一個小于或等于

x的元素位置i后插入該位置即可。

在尋找過程中，由于大于x的元素都應(yīng)放在x之后，所以可邊尋找，邊后移元素，當找到第一個小于或等于x的

元素位置i時，該位置也空出來了。

算法如下：

〃順序表存儲結(jié)構(gòu)如題2.7

voidInsertincreaseList(Seqlist*L,Datatypex)

inti;

if(L->length>=ListSize)

Error("overflow")；

for(i=L->length;i>0&&L->data[i-1]>x;i—)

L->data[i]=L->data[i];〃比較并移動元素

L->data[i]=x;

L->length++;

關(guān)閉

2.10設(shè)順序表L是一個遞減有序表，試寫一算法，將x插入其后仍保持L的有序性。

答:

與上題相類似，只要從終端結(jié)點開始往前找到第一個比x大（或相等）的結(jié)點數(shù)據(jù)，在這個位置插入就可以了。（邊

尋找，邊移動）算法如下：

voidInsertDecreaseList(Seqlist*L,Datatypex)

(

inti;

if(L->length>=ListSize)

ErrorC^overflow");

for(i=L->length;i>0&&L->data[i-1]<x;i-)

L->data[i]=L->data[i];〃比較并移動元素

L->data[i]=x;

L->length++;

關(guān)閉

2.11寫一算法在單鏈表上實現(xiàn)線性表的ListLength（L）運算。

解:

由于在單鏈表中只給出一個頭指針，所以只能用遍歷的方法來數(shù)單鏈表中的結(jié)點個數(shù)了。算法如下:

intListLength(LinkListL)

intlen=0;

ListNode*p;

p=L;〃設(shè)該表有頭結(jié)點

while(p->next)

p=p->next;

len++;

)

returnlen;

關(guān)閉

2.12已知LI和L2分別指向兩個單鏈表的頭結(jié)點，且已知其長度分別為m和n。試寫一算法將這兩個鏈表連接在一起,

請分析你的算法的時間復雜度。

解：

分析：

由于要進行的是兩單鏈表的連接，所以應(yīng)找到放在前面的那張表的表尾結(jié)點，再將后表的開始結(jié)點鏈接到前表的

終端結(jié)點后即可。該算法的主要時間消耗是用在尋找第一張表的終端尾結(jié)點上。這兩張單鏈表的連接順序無要求，并

且已知兩表的表長，則為了提高算法效率，可選表長小的單鏈表在前的方式連接。

具體算法如下：

LinkListLink(LinkListLI,LinkListL2,intm,intn)

{〃將兩個單鏈表連接在一起

ListNode*p,*q,*s;

//s指向短表的頭結(jié)點,q指向長表的開始結(jié)點，回收長表頭結(jié)點空間

if(m<=n)

{s=L1;q=L2->next;free(L2);}

else{s=L2;q=L1->next;free(L1);}

p=s；

while(p->next)p=p?>next;〃查找短表終端結(jié)點

p->next=q;〃將長表的開始結(jié)點鏈接在短表終端結(jié)點后

returns;

本算法的主要操作時間花費在查找短表的終端結(jié)點上，所以本算的法時間復雜度為：

O(min(m,n))

關(guān)閉

2.13設(shè)A和B是兩個單鏈表，其表中元素遞增仃序。試寫一算法將A和B歸并成一個按元素值遞減有序的單鏈表C,

并要求輔助空間為0(1),請分析算法的時間復雜度。

解：

根據(jù)已知條件，A和B是兩個遞增有序表，所以可以先取A表的表頭建立空的C表。然后同時掃描A表和B表,

將兩表中最大的結(jié)點從對應(yīng)表中摘下，并作為開始結(jié)點插入C表中。如此反復，直到A表或B表為空。最后將不為空

的A表或B表中的結(jié)點依次摘下并作為開始結(jié)點插入C表中。這時，得到的C表就是由A表和B表歸并成的一個按

元素值遞減有序的單鏈表C。并且輔助空間為0(1)。

算法如下：

LinkListMergeSort(LinkListA,LinkListB)

{〃歸并兩個帶頭結(jié)點的遞增有序表為一個帶頭結(jié)點遞減有序表

ListNode*pa,*pb,*q,*C;

pa=A?>next;〃pa指向A表開始結(jié)點

C=A;C->next=NULL;〃取A表的表頭建立空的C表

pb=B->next;〃pb指向B表開始結(jié)點

free(B);〃回收B表的頭結(jié)點空間

while(pa&&pb)

(

if(pb->data<=pa->data)

{〃當B中的元素小于等于A中當前元素時，將pa表的開始結(jié)點摘下

q=pa;pa=pa->next;

)

else

{〃當B中的元素大于A中當前元素時，將pb表的開始結(jié)點摘下

q=pb;pb=pb->next;}

q->next=C->next;C?>next=q;〃將摘下的結(jié)點q作為開始結(jié)點插入C表

)

〃若pa表非空，則處理pa表

while(pa){

q=pa;pa=pa->next;

q->next=C->next;C->next=q;}

〃若pb表非空，則處理pb表

while(pb){

q=pb;pa=pb->next;

q->next=C->next;C->next=q;}

retum(C);

該算法的時間復雜度分析如下：

算法中有三個while循環(huán)，其中第二個和第三個循環(huán)只執(zhí)行一個。每個循環(huán)做的工作都是對鏈表中結(jié)點掃描處理。

整個算法完成后，A表和B表中的每個結(jié)點都被處理了一遍。所以若A表和B表的表長分別是m和n,則該算法的時

間復雜度O(m+n)

關(guān)閉

2.14已知單鏈表L是一個遞增仃序表，試寫一高效算法，刪|除表中值大于min且小于max的結(jié)點(若表中有這樣的結(jié)點),

同時釋放被刪結(jié)點的空間，這里min和max是兩個給定的參數(shù)。請分析你的算法的時間復雜度。

解：

要解這樣的問題，我們首先想到的是拿鏈表中的元素一個個地與max和min比較，然后刪除這個結(jié)點。由于為已

知其是有序鏈表，則介于min和max之間的結(jié)點必為連續(xù)的?段元素序列。所以我們只要先找到所有大于min結(jié)點中

的最小結(jié)點的直接前趨結(jié)點*p后，依次刪除小于max的結(jié)點，直到第一個大于等于max結(jié)點*q位置，然后將*p結(jié)點

的直接后繼指針指向*q結(jié)點。

算法如下：

voidDeleteList(LinkListL,DataTypemin,DataTypemax)

(

ListNode*p,*q,*s;

P=L;

while(p->next&&p->next->data<=min)

〃找比min大的前一個元素位置

p=p->next;

q=p->next;〃p指向第一個不大于min結(jié)點的直接前趨，q指向第一個大于min的結(jié)點

while(q&&q->data<max)

{s=q;q=q->next;

free(s);〃刪除結(jié)點，釋放空間

)

p.>next=q;/^f5*p結(jié)點的直接后繼指針指向*q結(jié)點

)

關(guān)閉

2.15寫一算法將單鏈表中值重復的結(jié)點刪除，使所得的結(jié)果表中各結(jié)點值均不相同解：

本題可以這樣考慮，先取開始結(jié)點中的值，將它與其后的所有結(jié)點值一一比較，發(fā)現(xiàn)相同的就刪除掉，然后再取

第二結(jié)點的值，重復上述過程直到最后一個結(jié)點。

具體算法：

voidDeleteList(LinkListL)

(

ListNode*p,*q,*s;

p=L-next;

while(p->next&&p->next->next)

(

q=p；〃由于要做刪除操作，所以q指針指向要刪除元素的直接前趨

while(q->next)

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

{s=q->next;q->next=s->next;free(s);〃刪除與*p的值相同的結(jié)點

)

elseq=q->next;

p=p->next;

)

)

關(guān)閉

2.16假設(shè)在長度大于1的單循環(huán)鏈表中，既無頭結(jié)點也無頭指針。s為指向鏈表中某個結(jié)點的指針，試編寫算法刪除結(jié)

點*s的直接前趨結(jié)點。

解：

已知指向這個結(jié)點的指針是*S,那么要刪除這個結(jié)點的直接前趨結(jié)點，就只要找到一個結(jié)點，它的指針域是指向*S

的直接前趨，然后用后刪結(jié)點法，將結(jié)點*S的直接前趨結(jié)點刪除即可。

算法如下：

voidDeleteNode(ListNode*s)

{〃刪除單循環(huán)鏈表中指定結(jié)點的直接前趨結(jié)點

ListNode*p,*q;

p=s;

while(p->next->next!=s)

p=p->next;

〃刪除結(jié)點

q=p->next;

p->next=q->next;

free(p);〃釋放空間

)

注意：

若單循環(huán)鏈表的長度等于1,則只要把表刪空即可。

關(guān)閉

2.17已知由單鏈表表示的線性表中，含有三類字符的數(shù)據(jù)元素(如：字母字符、數(shù)字字符和其它字符)，試編寫算法構(gòu)造

三個以循環(huán)鏈表表示的線性表，使每個表中只含同一類的字符，且利用原表中的結(jié)點空間作為這三個表的結(jié)點空間，

頭結(jié)點可另辟空間。

解：

要解決這樣的問題，只要新建三個頭結(jié)點，然后在原來的單鏈表中依次查詢，找到■■類字符結(jié)點時，就摘下此結(jié)

點鏈接到相應(yīng)頭結(jié)點指明的新鏈表中就是了。

算法如下：

〃設(shè)已建立三個帶頭結(jié)點的空循環(huán)鏈表A,B,C且A、B、C分別是尾指針.

voidDivideList(LinkListL,LinkListA,LinkListB,LinkListC)

{

ListNode*p=L->next,*q;

while(p)

{

if(p->data>=,a'&&p->data<='z'llp->data>=*A'&&p->data<=,Z,)

(

q=p->next;

p=p->next;〃指向下一結(jié)點

q->next=A->next;〃將字母結(jié)點鏈到A表中

A->next=q;A=q;

elseif(p->data>='0,&&p->data<=,9')

{〃分出數(shù)字結(jié)點

q=p->next;

p=p->next;〃指向下一結(jié)點

q->next=B->next;〃將數(shù)字結(jié)點鏈到B表中

B->next=q;B=q;

)

else{〃分出其他字符結(jié)點

q=p->next;

p=p->next;〃指向下一?結(jié)點

q->next=C->next;〃將其他結(jié)點鏈到C表中

C->next=q;C=q;

)

)

}〃結(jié)束

關(guān)閉

2.18設(shè)有一個雙鏈表，每個結(jié)點中除有prior、data和next三個域外，還有一個訪問頻度域freq,在鏈表被起用之前，

其值均初始化為零。每當在鏈表進行一次LocateNode(L,x)運算時，令元素值為x的結(jié)點中f&q域的值加1,并調(diào)整表

中結(jié)點的次序，使其按訪問頻度的遞減序排列，以便使頻繁訪問的結(jié)點總是靠近表頭。試寫一符合上述要求的

LocateNode運算的算法c

解：

LocateNode運算的基本思想就是在雙向鏈表中查找值為x的結(jié)點，具體方法與單鏈表中查找一樣。找到結(jié)點*p后

給freq域的值加1。由于原來比*p結(jié)點查找頻度高的結(jié)點都排它前面，所以，接下去要順著前趨指針找到第一個頻度

小于或等于*p結(jié)點頻度的結(jié)點*q后，將*p結(jié)點從原來的位置刪除，并插入到*口后就可以了。

算法如下：

〃雙向鏈表的存儲結(jié)構(gòu)

typedefstructdlistnode{

DataTypedata;

structdlistnode"prior,*next;

intfreq;

JDListNode;

typedefDListNode*DLinkList;

voidLocateNode(LinkListL,DataTypex)

(

ListNode*p,*q;

p=L->next;〃帶有頭結(jié)點

while(p&&p->data!=x)

p=p->next;

if(!p)ERROR(MxisnotinL");〃雙鏈表中無值為x的結(jié)點

else{p->freq++;//freq力fl1

q=p->prior;〃以q為掃描指針尋找第一個頻度大于或等于*p頻度的結(jié)點

while(q!=L&&q->freq<p->freq)

q=q->prior;

if(q->next!=p)〃若*q結(jié)點和*p結(jié)點不為直接前趨直接后繼關(guān)系，

〃則將*p結(jié)點鏈到*q結(jié)點后

{p->prior->next=p->next;//W*p從原來位置摘下

p->next->prior=p->prior;

q->next->prior=p;//W*p插入*q之后。

p->next=q->next;

q->next=p;

p->prior=q;

)

)

)

關(guān)閉

第三章棧和隊列

3.1設(shè)將整數(shù)1,2,3,4依次進棧，但只要出棧時棧非空，則可將出棧操作按任何次序夾入其中，請回答下述問題：

(1)若入、出棧次序為Push(l),Pop(),Push⑵,Push(3),Pop(),Pop(),Push(4),Pop(),則出棧的數(shù)字序列為何(這里Push(i)

表示i進棧，Pop()表示出棧)？

(2)能否得到出棧序列1423和1432?并說明為什么不能得到或者如何得到。

(3)請分析1,2,3,4的24種排歹中，哪些序列是可以通過相應(yīng)的入出棧操作得到的。

答：

(1)出棧序列為：為24

(2)不能得到1423序列。因為要得到14的出棧序列,則應(yīng)做Push。),Pop(),Push⑵,Push⑶,Push(4),Pop()。這樣，3在棧

頂，2在棧底，所以不能得到23的出棧序列。能得到1432的出棧序列。具體操作為：

Push(l),Pop(),Push(2),Push(3),Push(4),Pop(),Pop(),Pop()o

(3)在1,2,3,4的24種排列中，可通過相應(yīng)入出棧操作得到的序列是：

1234,1243,1324,1342,1432,2134,2143,2314,2341,2431,3214,3241,3421,4321

不能得到的序列是：

1423,2413,3124,3142,3412,4123,4132,4213,4231,4312

關(guān)閉

3.2鏈棧中為何不設(shè)置頭結(jié)點？

答：

鏈棧不需要在頭部附加頭結(jié)點，因為棧都是在頭部進行操作的，如果加了頭結(jié)點，等于要對頭結(jié)點之后的結(jié)點進行操

作，反而使算法更復雜，所以只要有鏈表的頭指針就可以了。

關(guān)閉

3.3循環(huán)隊列的優(yōu)點是什么？如何判別它的空和滿？

答：

循環(huán)隊列的優(yōu)點是：它可以克服順序隊列的“假上溢”現(xiàn)象，能夠使存儲隊列的向量空間得到充分的利用。判別循環(huán)

隊列的“空“或”滿"不能以頭尾指針是否相等來確定，一般是通過以下幾種方法：一是另設(shè)一布爾變量來區(qū)別隊列的空和

滿。二是少用一個元素的空間，每次入隊前測試入隊后頭尾指針是否會重合，如果會重合就認為隊列已滿。三是設(shè)置一

計數(shù)器記錄隊列中元素總數(shù)，不僅可判別空或滿，還可以得到隊列中元素的個數(shù)。

關(guān)閉

3.4設(shè)長度為n的鏈隊用單循環(huán)鏈表表示，若設(shè)頭指針，則入隊出隊操作的時間為何？若只設(shè)尾指針呢？

答：

當只設(shè)頭指針時，出隊的時間為1,而入隊的時間需要n,因為每次入隊均需從頭指針開始查找，找到最后一個元

素時方可進行入隊操作。若只設(shè)尾指針，則出入隊時間均為1。因為是循環(huán)鏈表，尾指針所指的下一個兀素就是頭指針

所指元素，所以出隊時不需要遍歷整個隊列。

關(guān)閉

3.5指出下述程序段的功能是什么？

(1)voidDemol(SeqStack*S){

inti;arr[64];n=0;

while(StackEmpty(S))arr[n++]=Pop(S);

for(i=0,i<n;i++)Push(S,arr[i]);

}//Demo1

(2)SeqStackS1,S2,tmp;

DataTypex;

…〃假設(shè)棧tmp和S2已做過初始化

while(!StackEmpty(&S1))

(

x=Pop(&Sl);

Push(&tmp,x);

)

while(!StackEmpty(&tmp))

(

x=Pop(&tmp);

Push(&Sl,x);

Push(&S2,x);

(3)voidDemo2(SeqStack*S,intm)

{〃設(shè)DataType為int型

SeqStackT;inti;

InitStack(&T);

while(!StackEmpty(S))

if((i=Pop(S))!=m)Push(&T,i);

while(!StackEmpty(&T))

(

i=Pop(&T);Push(Sj);

(4)voidDemo3(CirQueue*Q)

{//設(shè)DataType為int型

intx;SeqStackS;

InitStack(&S);

while(!QueueEmpty(Q))

{x=DeQueue(Q);Push(&S,x);}

while(!StackEmpty(&s))

{x=Pop(&S);EnQueue(Q,x);}

}//Demo3

⑸CirQueueQI,Q2;//設(shè)DataType為int型intx,i,n=0;

…〃設(shè)QI已有內(nèi)容，Q2已初始化過

while(!QueueEmpty(&Q1))

{x=DeQueue(&Q1);EnQueue(&Q2,x);n++;}

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

{x=DeQueue(&Q2);

EnQueue(&Q1,x);EnQueue(&Q2,x);}

答：

(1)程序段的功能是將一棧中的元素按反序重新排列，也就是原來在棧頂?shù)脑胤诺綏５?，棧底的元素放到棧頂?/p>

此棧中元素個數(shù)限制在64個以內(nèi)。

(2)程序段的功能是利用tmp棧將一個非空棧si的所有元素按原樣復制到一個棧s2當中去。

(3)程序段的功能是利用棧T,將一個非空棧S中值等于m的元素全部刪去。

(4)程序段的功能是將一個循環(huán)隊列Q經(jīng)過S棧的處理，反向排列，原來的隊頭變成隊尾，原來的隊尾變成隊頭。

(5)這段程序的功能是將隊列1的所有元素復制到隊列2中去，但其執(zhí)行過程是先把隊列1的元素全部出隊，進入

隊列2,然后再把隊列2的元素復制到隊列1中。

關(guān)閉

3.6同文是指正讀反讀均相同的字符序列，如“abba”和“abdba〃均是回文，但“good”不是回文。試寫一個算法判定給定的

字符向量是否為回文。(提示：將一半字符入棧)

解：

根據(jù)提示，算法可設(shè)計為:

〃以下為順序棧的存儲結(jié)構(gòu)定義

#defineStackSize100〃假定預(yù)分配的?？臻g最多為100個元素

typedefcharDataType；〃假定棧元素的數(shù)據(jù)類型為字符

typedefstruct{

DataTypedata[StackSize];

inttop;

}SeqStack;

intIsHuiwen(char*t)

{〃判斷t字符向量是否為回文，若是，返回1,否則返回0

SeqStacks;

inti,len;

chartemp;

InitStack(&s);

len=strlen(t);〃求向量長度

for(i=0;i<len/2;i++)〃將一半字符入棧

Push(&s,t[i]);

while(!EmptyStack(&s))

{〃每彈出一個字符與相應(yīng)字符比較

temp=Pop(&s);

if(temp!=S[i])return0;〃不等則返回0

elsei++;

)

return1;〃比較完畢均相等則返回1

)

關(guān)閉

3.7利用棧的基本操作，寫一個將棧S中所有結(jié)點均刪去的算法voidClearStack(SeqStack*S),并說明S為何要作為指

針參數(shù)？

解：

算法如下

voidClearStack(SeqStack*S)

{〃刪除棧中所有結(jié)點

S->Top=-1;〃其實只是將棧置空

)

因為要置空的是棧S,如果不用指針來做參數(shù)傳遞，那么函數(shù)進行的操作不能對原來的棧產(chǎn)生影響，系統(tǒng)將會在內(nèi)

存中開辟另外的單元來對形參進行函數(shù)操作。結(jié)果等于什么也沒有做。所以想要把函數(shù)操作的結(jié)果返回給實參的話，

就只能用指針來做參數(shù)傳遞了。

關(guān)閉

3.8利用棧的基本操作，寫一個返回S中結(jié)點個數(shù)的算法intStackSize(SeqStackS),并說明S為何不作為指針參數(shù)?

解：

算法如下：

intStackSize(SeqStackS)

{〃計算棧中結(jié)點個數(shù)

intn=0;

if(!EmptyStack(&S))

{

Pop(&S);

n++;

)

returnn;

上述算法的目的只要得到s棧的結(jié)點個數(shù)就可以了。并不能改變棧的結(jié)構(gòu)。所以S不用指針做參數(shù)，以避免對原

來的棧中元素進行任何改變。系統(tǒng)會把原來的棧按值傳遞給形參，函數(shù)只對形參進行操作，最后返回元素個數(shù)。

關(guān)閉

3.9設(shè)計算法判斷一個算術(shù)表達式的圓括號是否正確配對。(提示：對表達式進行掃描，凡遇到'(，就進棧，遇')'就退掉棧

頂?shù)?('，表達式被掃描完畢，棧改為空。

解：

根據(jù)提示，可以設(shè)計算法如下：

intPairBracket(char*SR)

{〃檢查表達式ST中括號是否配對

inti;

SeqStackS;〃定義一個棧InitStack(&s);

for(i=0;i<strlen(SR);i++)

(

if(S[i]=='C)Push(&S,SR[i]);〃遇(時進棧

if(S[i]==))〃遇)

if(!StackEmpty(S))〃棧不為空時，將棧頂元素出棧

Pop(&s);

elsereturn0;〃不匹配，返回0

)

ifEmptyStack(&s)return1;〃匹配,返回1

elsereturn0;〃不匹配，返回0

關(guān)閉

3.10?個雙向棧S是在同一向量空間內(nèi)實現(xiàn)的兩個棧，它們的棧底分別設(shè)在向量空間的兩端。試為此雙向棧設(shè)計初始

化InitStack(3)、入棧Push(S,i,x)和出棧Pop(S,i)等徵法，其中i為。或1,用以表小棧號。

解:

雙向棧其實和單向棧原理相同，只是在一個向量空間內(nèi)，好比是兩個頭對頭的棧放在一起，中間的空間可以充分

利用。雙向棧的算法設(shè)計如下：

〃雙向棧的棧結(jié)構(gòu)類型與以前定義略有不同

#defineStackSize1001I假定分配了100個元素的向量空間

#definecharDataType

typedefstruct{

DataTypeData[StackSize]

inttopO;〃需設(shè)兩個指針

inttopi;

JDblStack

voidInitStack(DblStack*S)

{〃初始化雙向棧

S->topO=-1;

S->topl=StackSize;〃這里的top2也指出了向量空間，但由于是作為棧底，因此不會出錯

intEmptyStack(DblStack*S,inti)

{〃判棧空(棧號i)

return(i==0&&S->topO==-111i==1&&S->topl==StackSize);

intFullStack(DblStack*S)

{〃判棧滿，滿時肯定兩頭相遇

return(S->topO==S-top1-1);

voidPush(DblStack*S,inti,DataTypex)

{〃進棧(棧號i)

if(FullStack(S))

Error(nStackoverflow");〃上溢、退出運行

if(i==0)S->Data[++S->topO]=x;〃棧0入棧

if(i==1)S->Data[—S->topl]=x;//棧1入棧

DataTypePop(DblStack*S,inti)

{〃出棧(棧號i)

if(EmptyStack(S,i))

Error(nStackunderflow”);〃下溢退出

if(i==0)

return(S->Data[S->topO--]);〃返叵I棧頂元素，指針值減1

if(i==l)

retum(S->Data[S->topl++]);〃因為這個棧是以另一端為底的，所以指針值加1。

關(guān)閉

3.11Ackerman函數(shù)定義如下：請寫出遞歸算法。

「n+1當m=0時

AKM(m,n)=|AKM(m-1,1)當m/0,n=0時

LAKM(m-1,AKM(m,n-l))當m/),嚀0時

解：

算法如下

iniAKM(intm,intn)

|

if(m==0)returnn+1;

if(m<>0&&n==0)returnAKM(m-1,1);

if(m<>0&&noO)returnAKM(m-1,AKM(m,n-l));

關(guān)閉

3.12用第二種方法，即少用?個元素空間的方法來區(qū)別循環(huán)隊列的隊空和隊滿，試為其設(shè)計置空隊，判隊空，判隊滿、

出隊、入隊及取隊頭元素等六個基本操作的算法。

算法設(shè)計如下：

〃循環(huán)隊列的定義

#defineQueueSize100

typedefcharDatatype;〃設(shè)元素的類型為char型

typedefstruct{

intfront;

intrear;

DataTypeData[QueueSize];

JCirQueue;

⑴置空隊

voidInitQueue(CirQueue*Q)

{〃置空隊

Q->front=Q->rear=0;

(2)判隊空

intEmptyQueue(CirQueue*Q)

{〃判隊空

returnQ->front==Q->rear;

)

(3)判隊滿

intFullQueue(CirQueue*Q){//判隊滿//如果尾指針加1后等于頭指針，則認為滿

return(Q->rear+1)%QueueSize=Q->front;

)

(4)出隊

DataTypeDeQueue(CirQueue*Q)

{〃出隊

DataTypetemp;

if(EmptyQueue(Q))

Error("隊已空，無元素可以出隊)

temp=Q->Data[Q->front];〃保存元素值

Q->front=(Q->front+l)%QueueSize;〃循環(huán)意義上的加1

returntemp;〃返回元素值

)

⑸入隊

voidEnQueue(CirQueue*Q,DataTypex)

{〃入隊

if(FullQueue(Q))

Error("隊已滿，不可以入隊]

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

Q->rear=(Q->rear+l)%QueueSize;//rear指向下一個空元素位置

)

(6)取隊頭元素

DataTypeFrontQueue(CirQueue*Q)

{〃取隊頭元素

if(EmptyQueue(Q))

Error("隊空，無元素可取")；

returnQ->Data[Q->front];

)

關(guān)閉

3.13假設(shè)以帶頭結(jié)點的循環(huán)鏈表表示隊列，并且只設(shè)一個指針指向隊尾元素站點(注意不設(shè)頭指針)，試編寫相應(yīng)的置空

隊、判隊空、入隊和出隊等算法。

解：

算法如下：

〃先定義鏈隊結(jié)構(gòu)：

typedefstructqueuenode{

Datatypedata;

structqueuenode*next;

}QueueNode;〃以上是結(jié)點類型的定義

typedefstruct{

queuenode*rear;

JLinkQueue;〃只設(shè)一個指向隊尾元素的指針

(1)置空隊

voidInitQueue(LinkQueue*Q)

{〃置空隊：就是使頭結(jié)點成為隊尾元素

QueueNode*s;

Q->rear=Q->rear->next;〃將隊尾指針指向頭結(jié)點

while(Q->rear!=Q->rear?>next)〃當隊列非空，將隊中元素逐個出隊

{s=Q->rear->next;

Q->rear->next=s->next;

free(s);

}〃回收結(jié)點空間

)

(2)判隊空

intEmptyQueue(LinkQueue*Q)

{〃判隊空

〃當頭結(jié)點的next指針指向自己時為空隊

returnQ->rear->next->next==Q->rear->next;

)

⑶入隊

voidEnQueue(LinkQueue*Q,Datatypex)

{〃入隊

〃也就是在尾結(jié)點處插入元素

QueueNode*p=(QueueNode*)malloc(sizeof(QueueNode));〃申請新結(jié)點

p->data=x;p->next二Q-ArearonextJ/初始化新結(jié)點并鏈入

Q-rear->next=p;

Q?>rear=p;〃將尾指針移至新結(jié)點

)

(4)出隊

DatatypeDeQueue(LinkQueue*Q)

{〃出隊，把頭結(jié)點之后的元素摘下

Datatypet;

QueueNode*p;

if(EmptyQueue(Q))

Error("Queueunderflow1');

p=Q->rear?>next->next;〃p指向?qū)⒁碌慕Y(jié)點

x=p->data;〃保存結(jié)點中數(shù)據(jù)

if(p==Q->rear)

{〃當隊列中只有一個結(jié)點時，p結(jié)點出隊后，要將隊尾指針指向頭結(jié)點

Q->rear=Q->rear->next;Q->rear->next=p->next;}

else

Q->rear->next->next=p->next;〃摘下結(jié)點p

free(p);〃釋放被刪結(jié)點

returnx;

)

關(guān)閉

3.14對于循環(huán)向量中的循環(huán)隊列，寫出求隊列長度的公式。

解：

公式如下(設(shè)采用第二種方法，front指向真正的隊首元素，rear指向真正隊尾后一位置，向量空間大小：QueueSize

Queuelen=(QueueSize+rear-front)%QueueSize

關(guān)閉

3.15假設(shè)循環(huán)隊列中只設(shè)rear和quelen來分別指示隊尾元素的位置和隊中元素的個數(shù)，試給出判別此循環(huán)隊列的隊滿

條件，并寫出相應(yīng)的入隊和出隊算法，要求出隊時需返回隊頭元素。

解：

根據(jù)題意，可定義該循環(huán)隊列的存儲結(jié)構(gòu)：

#defineQueueSize100

typedefcharDatatype;〃設(shè)元素的類型為char型

typedefstruct{

intquelen;

intrear;

DatatypeData[QueueSize];

JCirQueue;

CirQueue*Q;

循環(huán)隊列的隊滿條件是：Q->quelen==QueueSize

知道了尾指針和元素個數(shù)，當然就能計算出隊頭元素的位置。算法如下：

(1)判斷隊滿

intFullQueue(CirQueue*Q)

{〃判隊滿,隊中元素個數(shù)等于空間大小

returnQ->quelen==QueueSize;

)

(2)入隊

voidEnQu