第2章線(xiàn)性表習(xí)題

第2章線(xiàn)性表習(xí)題本章要點(diǎn)回顧:1.了解線(xiàn)性表的邏輯結(jié)構(gòu)特性是數(shù)據(jù)元素之間存在著線(xiàn)性關(guān)系，在計(jì)算機(jī)中表示這種關(guān)系的兩類(lèi)不同的存儲(chǔ)結(jié)構(gòu)是順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。用前者表示的線(xiàn)性表簡(jiǎn)稱(chēng)為順序表，用后者表示的線(xiàn)性表簡(jiǎn)稱(chēng)為鏈表。2.熟練掌握這兩類(lèi)存儲(chǔ)結(jié)構(gòu)的描述方法，以及線(xiàn)性表的各種基本操作的實(shí)現(xiàn)。3.能夠從時(shí)間和空間復(fù)雜度的角度綜合比較線(xiàn)性表兩種存儲(chǔ)結(jié)構(gòu)的不同特點(diǎn)及其適用場(chǎng)合。線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)具有三個(gè)弱點(diǎn)：一在作插入或刪除操作時(shí)，需移動(dòng)大量元素；二由于難以估計(jì)大小，必須預(yù)先分配較大的空間，使存儲(chǔ)空間不能得到充分利用；三表的容量難以擴(kuò)充。

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)一般來(lái)說(shuō)克服了順序存儲(chǔ)結(jié)構(gòu)的三個(gè)弱點(diǎn)。(1)插入、刪除不需移動(dòng)元素，只修改指針，時(shí)間復(fù)雜度為O(1)；(2)不需要預(yù)先分配空間，可根據(jù)需要?jiǎng)討B(tài)申請(qǐng)空間；(3)表容量只受可用內(nèi)存空間的限制。其缺點(diǎn)是因?yàn)橹羔樤黾恿丝臻g開(kāi)銷(xiāo)，當(dāng)空間不允許時(shí)，就不能克服順序存儲(chǔ)的缺點(diǎn)。習(xí)題2.1

首元結(jié)點(diǎn)：指鏈表中存儲(chǔ)線(xiàn)性表中第一個(gè)數(shù)據(jù)元素a1的結(jié)點(diǎn)；

頭結(jié)點(diǎn)：為了操作方便，在鏈表的首元結(jié)點(diǎn)之前附設(shè)的一個(gè)結(jié)點(diǎn)，其作用是為了對(duì)鏈表進(jìn)行操作時(shí)，可以對(duì)空表、非空表的情況以及對(duì)首元結(jié)點(diǎn)進(jìn)行統(tǒng)一的處理；

頭指針：指向鏈表中第一個(gè)結(jié)點(diǎn)（或?yàn)槭自Y(jié)點(diǎn)或?yàn)轭^結(jié)點(diǎn)）的指針。習(xí)題2.2（1）表中一半該元素的位置（2）必定不一定（3）其直接前驅(qū)結(jié)點(diǎn)的鏈域的值（4）插入和刪除首元素時(shí)不必進(jìn)行特殊的處理習(xí)題2.3第1個(gè)FOR循環(huán)后:第2個(gè)FOR循環(huán)后:第3個(gè)FOR循環(huán)后:·1·3·5·7^8^L·1·2·3·4·L6·5·7·8^·2·L6·4·7·p注：Del_LinkList(L,i)中的i為第i個(gè)數(shù)據(jù)元素習(xí)題2.4將單鏈表的第二個(gè)元素改為表頭，第一個(gè)元素改為表尾。習(xí)題2.5算法2.9（P23）習(xí)題2.6//算法2.11（P25）voidinvert(Sqlist&A){n=A.length/2-1;for(k=0;k<=n;k++){w=A[k];A[k]=A[A.length-1-k];A[A.length-1-k]=w;}//for}//invertvoidinvert(Sqlist&L){inti,j;ElemTypee;for(i=0,j=L.length-1;i<j;i++,j--){e=L.elem[i];L.elem[i]=L.elem[j];L.elem[j]=e;

}//for}//invert習(xí)題2.7voidListConcat(LinkList&ha,LinkList&hb,LinkList&hc)

//把鏈表hb和ha連接起來(lái)形成鏈表hc，ha和hb的長(zhǎng)度//分別為m,n,要求算法在最短時(shí)間完成。{pa=ha->next;pb=hb->next;if(m<=n){while(pa)pa=pa->next;hc=ha;pa->next=pb;deletehb;}else{while(pb)pb=pb->next;hc=hb;pb->next=pa;deleteha;}//if}//ListConcatO(Min(m,n))習(xí)題2.8

voidmerge(LinkList&A,LinkList&B,LinkList&C)

//把鏈表A和B合并為C,A和B的元素間隔排列,且使用原存儲(chǔ)空間{LinkListp,q,s,t;p=A->next;q=B->next;C=A;while(p&&q){ s=p->next; p->next=q;//將B的元素插入 if(s) {t=q->next; q->next=s;//如A非空,將A的元素插入 } p=s;q=t;}//while}//merge習(xí)題2.9voidLinkList_Divide(LinkList&L,CLinkList&A,CLinkList&B,CLiNKList&C)//把單鏈表L的元素按類(lèi)型分為三個(gè)循環(huán)鏈表.設(shè)單鏈表L帶頭結(jié)點(diǎn)//CLNode為單循環(huán)鏈表的結(jié)點(diǎn)類(lèi)型；CLinkList為指向該類(lèi)結(jié)點(diǎn)的指針。

{

s=L->next;

A=newCLNode);p=A;

B=newCLNode);q=B;

C=newCLNode);r=C;//建立頭結(jié)點(diǎn)

while(s)

{

if(isalpha(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;A=p;q->next=B;B=q;r->next=C;C=r;//完成循環(huán)鏈表

deleteL;}//LinkList_Divide習(xí)題2.11voidDelMid(LinkList&L,intmink,intmaxk)//刪除表中所有值大于mink且小于mark的元素{LinkListp=L->next,q=L;if(p->data>maxk)

cout<<"不存在大于"<<mink<<"并且小于"<<mark<<"的元素"<<endl;else{while(p&&p->data<mink){q=p;p=p->next;}while(p&&p->data<maxk){q->next=p->next;deletep;p=q->next;}}}}//Delete_Between習(xí)題2.12voidreverse_merge(LinkList&A,LinkList&B,LinkList&C)

//把元素遞增排列的鏈表A和B合并為C,且C中元素遞減排列,使用原空間

{

pa=A->next;pb=B->next;C=A;//pa和pb分別指向A,B的當(dāng)前元素

while(pa&&pb)//不是用||

{

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

{

s=pa;pa=pa->next;s->next=C->next;C->next=s;}//將A的元素插入新表

else

{

t=pb;pb=pb->next;t->next=C->next;C->next=t;}//將B的元素插入新表

}//while

if(pa)while(pa){s=pa;pa=pa->next;s->next=C->next;C->next=s;}//將A的剩余元素插入if(pb)while(pb){t=pb;pb=pb->next;t->next=C->next;C->next=t;}//將B的剩余元素插入}//reverse_mergeO(m+n)補(bǔ)充習(xí)題:1.下列有關(guān)線(xiàn)性表的敘述中，正確的是（）。A）線(xiàn)性表中元素之間的關(guān)系是線(xiàn)性關(guān)系B）線(xiàn)性表中至少有一個(gè)元素C）線(xiàn)性表中的任一元素有且僅有一個(gè)直接前趨D）線(xiàn)性表中的任一元素有且僅有一個(gè)直接后繼2.下述哪一條是順序存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)？（）A）存儲(chǔ)密度大B）插入方便C）刪除方便D）可方便地用于各種邏輯結(jié)構(gòu)的存儲(chǔ)表示3.在一個(gè)長(zhǎng)度為n的順序表中，在第i個(gè)元素（1<=i<=n）之前插入一個(gè)新元素時(shí)需向后移動(dòng)（）個(gè)元素。A）1B）n-iC）n-i-1D）n-i+11.A2.A3.D補(bǔ)充習(xí)題:4.如果某線(xiàn)性表中最常用的操作是取第i個(gè)元素和找第i個(gè)元素的前驅(qū)，那么采用（）存儲(chǔ)方式最節(jié)省時(shí)間。A）順序表B）單鏈表C）雙鏈表D）循環(huán)鏈表5.對(duì)順序存儲(chǔ)的線(xiàn)性表，設(shè)其長(zhǎng)度為n，且在任何位置上插入或刪除操作都是等概率的。則插入一個(gè)元素時(shí)平均要移動(dòng)表中的（）個(gè)元素。A）n/2B）(n+1)/2C）(n-1)/2D）n6.下述哪一條是順序存儲(chǔ)結(jié)構(gòu)的缺點(diǎn)？（）A）存儲(chǔ)密度太大B）隨機(jī)存取C）一般要估計(jì)最大的需要空間D）只能應(yīng)用于少數(shù)幾種邏輯結(jié)構(gòu)的存儲(chǔ)表示4.A5.A6.C補(bǔ)充習(xí)題:7.在單鏈表中，增加頭結(jié)點(diǎn)的目的是（）。A）使單鏈表至少有一個(gè)結(jié)點(diǎn)B）標(biāo)志表中首結(jié)點(diǎn)的位置C）方便運(yùn)算的實(shí)現(xiàn)D）說(shuō)明單鏈表是線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)表示8.單鏈表不具有的特點(diǎn)是（）。A)可隨機(jī)訪(fǎng)問(wèn)任一元素B)插入和刪除不需要移動(dòng)元素C)不必事先估計(jì)存儲(chǔ)空間D)所需空間和線(xiàn)性表長(zhǎng)度成正比9.循環(huán)鏈表的主要優(yōu)點(diǎn)是（）。A）不再需要頭指針了B）已知某個(gè)結(jié)點(diǎn)的位置后，能夠容易找到他的直接前趨C）在進(jìn)行插入、刪除運(yùn)算時(shí)，能更好的保證鏈表不斷開(kāi)D）從表中的任意結(jié)點(diǎn)出發(fā)都能掃描到整個(gè)鏈表7.C8.A9.D補(bǔ)充習(xí)題:10.鏈表對(duì)于數(shù)據(jù)元素的插入與刪除是（）。A）不需移動(dòng)結(jié)點(diǎn)，不需改變結(jié)點(diǎn)指針B）不需移動(dòng)結(jié)點(diǎn)，只需改變結(jié)點(diǎn)指針C）只需移動(dòng)結(jié)點(diǎn)，不需改變結(jié)點(diǎn)指針D）既需移動(dòng)結(jié)點(diǎn)，又需改變結(jié)點(diǎn)指針11.在一個(gè)單鏈表中,已知q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn),若要在q和p所指結(jié)點(diǎn)之間插入s所指的結(jié)點(diǎn),則執(zhí)行（）。A）s->next=p->next;p->next=s;B）q->next=s;s->next=p;C）p->next=s;s->next=q;D）p->next=s->next;s->next=p;10.B11.B補(bǔ)充習(xí)題:12.向一個(gè)有115個(gè)元素的順序表中插入一個(gè)新元素并保持原來(lái)順序不變，平均要移動(dòng)（）個(gè)元素。A)115B)114C)58D)5713.帶頭結(jié)點(diǎn)的單鏈表Head為空表的判定條件是()。A)Head->next==HeadB)Head->next==NULLC)Head!=NULLD)Head==NULL14.若要求能快速地實(shí)現(xiàn)在鏈表的末尾插入結(jié)點(diǎn)和刪除第一個(gè)結(jié)點(diǎn)的運(yùn)算，則選擇()最合適。A)單鏈表B)帶尾指針的單循環(huán)鏈表C)雙鏈表D)雙循環(huán)鏈表12.C13.B14.B補(bǔ)充習(xí)題:15.給定有n個(gè)元素的向量，建立一個(gè)