其次章 部分習(xí)題參考答案

本文格式為Word版，下載可任意編輯——其次章部分習(xí)題參考答案2何時(shí)選用順序表，何時(shí)選用鏈表作為線性表的存儲(chǔ)結(jié)構(gòu)適合?各自的主要優(yōu)缺點(diǎn)是什么?

在實(shí)際應(yīng)用中，應(yīng)根據(jù)具體問題的要求和性質(zhì)來選擇順序表或鏈表作為線性表的存儲(chǔ)結(jié)構(gòu)，尋常有以下幾方面的考慮：

1.基于空間的考慮。當(dāng)要求存儲(chǔ)的線性表長度變化不大，易于事先確定其大小時(shí)，為了儉約存儲(chǔ)空間，宜采用順序表；反之，當(dāng)線性表長度變化大，難以估計(jì)其存儲(chǔ)規(guī)模時(shí)，采用動(dòng)態(tài)鏈表作為存儲(chǔ)結(jié)構(gòu)為好。

2.基于時(shí)間的考慮。若線性表的操作主要是進(jìn)行查找，很少做插入和刪除操作時(shí)，采用順序表做存儲(chǔ)結(jié)構(gòu)為宜；反之，若需要對線性表進(jìn)行頻繁地插入或刪除等的操作時(shí)，宜采用鏈表做存儲(chǔ)結(jié)構(gòu)。并且，若鏈表的插入和刪除主要發(fā)生在表的首尾兩端，則采用尾指針表示的單循環(huán)鏈表為宜。

順序表的主要優(yōu)點(diǎn):沒使用指針，不用花費(fèi)附加開銷;線性表元素的讀寫訪問十分簡單便利

鏈表的主要優(yōu)點(diǎn)：無需事先了解線性表的長度;能夠適應(yīng)經(jīng)常插入刪除內(nèi)部元素的狀況;允許線性表的長度有很大變化

3在順序表中插入和刪除一個(gè)結(jié)點(diǎn)平均需要移動(dòng)多少個(gè)結(jié)點(diǎn)?具體的移動(dòng)次數(shù)取決于哪兩個(gè)因素?

在等概率狀況下，順序表中插入一個(gè)結(jié)點(diǎn)需平均移動(dòng)n/2個(gè)結(jié)點(diǎn)。刪除一個(gè)結(jié)點(diǎn)需平均移動(dòng)(n-1)/2個(gè)結(jié)點(diǎn)。具體的移動(dòng)次數(shù)取決于順序表的長度n以及需插入或刪除的位置i。i越接近n則所需移動(dòng)的結(jié)點(diǎn)數(shù)越少。

4鏈表所表示的元素是否有序?如有序，則有序性表達(dá)于何處?鏈表所表示的元素是否一定要在物理上是相鄰的?順序表的有序性又如何理解?

有序。有序性表達(dá)在通過指針數(shù)據(jù)元素有序的相連。物理上不一定要相鄰。順序表的有序不僅表達(dá)在規(guī)律結(jié)構(gòu)上有序，而且在物理結(jié)構(gòu)（儲(chǔ)存結(jié)構(gòu)）也有序。

5設(shè)順序表L是遞增有序表，試寫一算法，將x插入到L中并使L仍是遞增有序表。因已知順序表L是遞增有序表，所以只要從順序表終端結(jié)點(diǎn)（設(shè)為i位置元素）開始向前尋覓到第一個(gè)小于或等于x的元素位置i后插入該位置即可。

在尋覓過程中，由于大于x的元素都應(yīng)放在x之后，所以可邊尋覓，邊后移元素，當(dāng)找到第一個(gè)小于或等于x的元素位置i時(shí)，該位置也空出來了。算法如下：

voidInsertIncreaseList(Seqlist*L,Datatypex){inti;

if(L->length>=ListSize)Error(“overflow\

for(i=L->length;i>0i--)L->data[i]=L->data[i];//比較并移動(dòng)元素L->data[i]=x;L->length++;}

6寫一求單鏈表的結(jié)點(diǎn)數(shù)目ListLength(L)的算法。

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

intListLength(LinkListL){

intlen=0;ListNode*p;

p=L;//設(shè)該表有頭結(jié)點(diǎn)while(p->next){

p=p->next;len++;}returnlen;}

7寫一算法將單鏈表中值重復(fù)的結(jié)點(diǎn)刪除，使所得的結(jié)果鏈表中所有結(jié)點(diǎn)的值均不一致。

此題可以這樣考慮，先取開始結(jié)點(diǎn)中的值，將它與其后的所有結(jié)點(diǎn)值一一比較，發(fā)現(xiàn)一致的就刪除掉，然后再取其次結(jié)點(diǎn)的值，重復(fù)上述過程直到最終一個(gè)結(jié)點(diǎn)。具體算法：

voidDeleteList(LinkListL){

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

while(p->next//由于要做刪除操作，所以q指針指向要?jiǎng)h除元素的直接前趨while(q->next)

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

{s=q->next;q->next=s->next;free(s);//刪除與*p的值一致的結(jié)點(diǎn)}

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

8寫一算法從一給定的向量A刪除值在x到y(tǒng)(x≤y)之間的所有元素(注意：x和y是給定的參數(shù)，可以和表中的元素一致，也可以不同)。

voidDeletElem(SqListA,intx,inty){

ElemType*p,*q;inti=0;intj;p=

for(i;i{if(p.data>=x||p.datanext;//pa指向A表開始結(jié)點(diǎn)

C=A;C->next=NULL;//取A表的表頭建立空的C表pb=B->next;//pb指向B表開始結(jié)點(diǎn)free(B);//回收B表的頭結(jié)點(diǎn)空間while(papa=pa->next;}

else

{//當(dāng)B中的元素大于A中當(dāng)前元素時(shí)，將pb表的開始結(jié)點(diǎn)摘下q=pb;pb=pb->next;}

q->next=C->next;C->next=q;//將摘下的結(jié)點(diǎn)q作為開始結(jié)點(diǎn)插入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;}return(C);}

該算法的時(shí)間繁雜度分析如下：

算