第二章線性表作業(yè)-答案課件

第二章線性表作業(yè)評(píng)講1可編輯課件PPT2.1試描述頭指針、頭結(jié)點(diǎn)、開始結(jié)點(diǎn)的區(qū)別、并說明頭指針和頭結(jié)點(diǎn)的作用。

2.2何時(shí)選用順序表、何時(shí)選用鏈表作為線性表的存儲(chǔ)結(jié)構(gòu)為宜?2.3在順序表中插入和刪除一個(gè)結(jié)點(diǎn)需平均移動(dòng)多少個(gè)結(jié)點(diǎn)?具體的移動(dòng)次數(shù)取決于哪兩個(gè)因素?2.4為什么在單循環(huán)鏈表中設(shè)置尾指針比設(shè)置頭指針更好?2.5在單鏈表、雙鏈表和單循環(huán)鏈表中，若僅知道指針p指向某結(jié)點(diǎn)，不知道頭指針，能否將結(jié)點(diǎn)*p從相應(yīng)的鏈表中刪去?若可以，其時(shí)間復(fù)雜度各為多少?作業(yè)：2.5、2.7、2.9、2.11做在作業(yè)本上，交，其余堂下練習(xí)2可編輯課件PPT2.6設(shè)有一個(gè)雙鏈表，每個(gè)結(jié)點(diǎn)中除有prior、data和next三個(gè)域外，還有一個(gè)訪問頻度域freq，在鏈表被起用之前，其值均初始化為零。每當(dāng)在鏈表進(jìn)行一次LocateNode(L,s)運(yùn)算時(shí)，令元素值為x的結(jié)點(diǎn)中freq域的值加1，并調(diào)整表中結(jié)點(diǎn)的次序，使其按訪問頻度的遞減序排列，以便使頻繁訪問的結(jié)點(diǎn)總是靠近表頭。試寫一符合上述要求的LocateNode運(yùn)算的算法。2.7寫一算法在單鏈表上實(shí)現(xiàn)線性表的ListLength(L)運(yùn)算。3可編輯課件PPT2.8已知由單鏈表表示的線性表中，含有三類字符的數(shù)據(jù)元素(如：字母字符、數(shù)字字符和其它字符)，試編寫算法構(gòu)造三個(gè)以循環(huán)鏈表表示的線性表，使每個(gè)表中只含同一類的字符，且利用原表中的結(jié)點(diǎn)空間作為這三個(gè)表的結(jié)點(diǎn)空間，頭結(jié)點(diǎn)可另辟空間。2.9假設(shè)在長(zhǎng)度大于1的單循環(huán)鏈表中，既無頭結(jié)點(diǎn)也無頭指針。s為指向鏈表中某個(gè)結(jié)點(diǎn)的指針，試編寫算法刪除結(jié)點(diǎn)*s的直接前趨結(jié)點(diǎn)。2.10設(shè)順序表L是一個(gè)遞增有序表，試寫一算法，將x插入L中，并使L仍是一個(gè)有序表。4可編輯課件PPT2.11寫出以下鏈表操作的算法1）創(chuàng)建一個(gè)空的雙向循環(huán)鏈表statusCreateList_Dul(DuLinkList&L);2）取得雙向循環(huán)鏈表中第i個(gè)數(shù)據(jù)元素的位置指針statusGetElemP_Dul(DuLinkListL,inti);3）將單鏈表置逆statusReverseList_L(LinkList&L);5可編輯課件PPT2.1試描述頭指針、頭結(jié)點(diǎn)、開始結(jié)點(diǎn)的區(qū)別、并說明頭指針和頭結(jié)點(diǎn)的作用。開始結(jié)點(diǎn)是指鏈表中的第一個(gè)結(jié)點(diǎn)，沒有直接前趨的那個(gè)結(jié)點(diǎn)。鏈表的頭指針是一指向鏈表開始結(jié)點(diǎn)的指針(沒有頭結(jié)點(diǎn)時(shí))，單鏈表由頭指針唯一確定，因此單鏈表可以用頭指針的名字來命名。頭結(jié)點(diǎn)在鏈表的開始結(jié)點(diǎn)之前附加的一個(gè)結(jié)點(diǎn)。有了頭結(jié)點(diǎn)之后，頭指針指向頭結(jié)點(diǎn)，不論鏈表否為空，頭指針總是非空。而且頭指針的設(shè)置使得對(duì)鏈表的第一個(gè)位置上的操作與在表其他位置上的操作一致(都是在某一結(jié)點(diǎn)之后)。6可編輯課件PPT2.2何時(shí)選用順序表、何時(shí)選用鏈表作為線性表的存儲(chǔ)結(jié)構(gòu)為宜?

1.基于空間的考慮。當(dāng)要求存儲(chǔ)的線性表長(zhǎng)度變化不大，易于事先確定其大小時(shí)，為了節(jié)約存儲(chǔ)空間，宜采用順序表；反之，當(dāng)線性表長(zhǎng)度變化大，難以估計(jì)其存儲(chǔ)規(guī)模時(shí)，采用動(dòng)態(tài)鏈表作為存儲(chǔ)結(jié)構(gòu)為好。2.基于時(shí)間的考慮。若線性表的操作主要是進(jìn)行查找，很少做插入和刪除操作時(shí)，采用順序表做存儲(chǔ)結(jié)構(gòu)為宜；反之，

若需要對(duì)線性表進(jìn)行頻繁地插入或刪除等的操作時(shí)，宜采用鏈表做存儲(chǔ)結(jié)構(gòu)。并且，若鏈表的插入和刪除主要發(fā)生在表的首尾兩端，則采用尾指針表示的單循環(huán)鏈表為宜。

7可編輯課件PPT2.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ù)取決于順序表的長(zhǎng)度n以及需插入或刪除的位置i。i越接近n則所需移動(dòng)的結(jié)點(diǎn)數(shù)越少。

8可編輯課件PPT2.4為什么在單循環(huán)鏈表中設(shè)置尾指針比設(shè)置頭指針更好?

尾指針是指向終端結(jié)點(diǎn)的指針，用它來表示單循環(huán)鏈表可以使得查找鏈表的開始結(jié)點(diǎn)和終端結(jié)點(diǎn)都很方便，設(shè)一帶頭結(jié)點(diǎn)的單循環(huán)鏈表，其尾指針為rear，則開始結(jié)點(diǎn)和終端結(jié)點(diǎn)的位置分別是rear->next->next和rear,查找時(shí)間都是O(1)。若用頭指針來表示該鏈表，則查找終端結(jié)點(diǎn)的時(shí)間為O(n)。

9可編輯課件PPT2.5在單鏈表、雙鏈表和單循環(huán)鏈表中，若僅知道指針p指向某結(jié)點(diǎn)，不知道頭指針，能否將結(jié)點(diǎn)*p從相應(yīng)的鏈表中刪去?若可以，其時(shí)間復(fù)雜度各為多少?

1.單鏈表。當(dāng)我們知道指針p指向某結(jié)點(diǎn)時(shí)，能夠根據(jù)該指針找到其直接后繼，但是由于不知道其頭指針，所以無法訪問到p指針指向的結(jié)點(diǎn)的直接前趨。因此無法刪去該結(jié)點(diǎn)。2.雙鏈表。由于這樣的鏈表提供雙向鏈接，因此根據(jù)已知結(jié)點(diǎn)可以查找到其直接前趨和直接后繼，從而可以刪除該結(jié)點(diǎn)。其時(shí)間復(fù)雜度為O(1)。3.單循環(huán)鏈表。根據(jù)已知結(jié)點(diǎn)位置，我們可以直接得到其后相鄰的結(jié)點(diǎn)位置(直接后繼)，又因?yàn)槭茄h(huán)鏈表，所以我們可以通過查找，得到p結(jié)點(diǎn)的直接前趨。因此可以刪去p所指結(jié)點(diǎn)。其時(shí)間復(fù)雜度應(yīng)為O(n)。

10可編輯課件PPT2.6設(shè)有一個(gè)雙鏈表，每個(gè)結(jié)點(diǎn)中除有prior、data和next三個(gè)域外，還有一個(gè)訪問頻度域freq，在鏈表被起用之前，其值均初始化為零。每當(dāng)在鏈表進(jìn)行一次LocateNode(L,s)運(yùn)算時(shí)，令元素值為x的結(jié)點(diǎn)中freq域的值加1，并調(diào)整表中結(jié)點(diǎn)的次序，使其按訪問頻度的遞減序排列，以便使頻繁訪問的結(jié)點(diǎn)總是靠近表頭。試寫一符合上述要求的LocateNode運(yùn)算的算法。

Statuslocatenode(dullinklist&L,elemtypex){dulnode*p,*q;p=q=L->next;while(p){if(p->data!=x)p=p->next;else{p->freq++;break;}}while(q){if(q->freq>p->freq)q=q->next;else{p->prior->next=p->next;p->next->prior=p->prior;p->next=q;p->prior=q->prior;q->prior->next=p;q->prior=p}}returnok;}11可編輯課件PPT2.7寫一算法在單鏈表上實(shí)現(xiàn)線性表的ListLength(L)運(yùn)算。

求單鏈表長(zhǎng)只能用遍歷的方法了，從頭數(shù)到尾。算法如下：intListLength(LinkListL)

{

intlen=0;

ListNode*p;

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

while(p->next)

{

p=p->next;

len++;

}

returnlen;

}

12可編輯課件PPT2.8已知由單鏈表表示的線性表中，含有三類字符的數(shù)據(jù)元素(如：字母字符、數(shù)字字符和其它字符)，試編寫算法構(gòu)造三個(gè)以循環(huán)鏈表表示的線性表，使每個(gè)表中只含同一類的字符，且利用原表中的結(jié)點(diǎn)空間作為這三個(gè)表的結(jié)點(diǎn)空間，頭結(jié)點(diǎn)可另辟空間。13可編輯課件PPT2.9假設(shè)在長(zhǎng)度大于1的單循環(huán)鏈表中，既無頭結(jié)點(diǎn)也無頭指針。s為指向鏈表中某個(gè)結(jié)點(diǎn)的指針，試編寫算法刪除結(jié)點(diǎn)*s的直接前趨結(jié)點(diǎn)。

statusDeleteNode(ListNode*s)

{

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

ListNode*p,*q;

p=s;

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

{

q=p;

p=p->next;

}

q->next=s;//刪除結(jié)點(diǎn)

free(p);//釋放空間

returnOK;}14可編輯課件PPT2.10設(shè)順序表L是一個(gè)遞增有序表，試寫一算法，將x插入L中，并使L仍是一個(gè)有序表。

voidInsertIncreaseList(Seqlist*L,Datatypex)

{

inti;

for(i=0;i<L->length&&L->data[i]<x;i++);//查找并比較ListInsert_sq(L，i,x);//調(diào)用順序表插入函數(shù)p24

}15可編輯課件PPT2.11寫出以下鏈表操作的算法

1）創(chuàng)建一個(gè)空的雙向循環(huán)鏈表statusCreateList_Dul(DuLinkList&L){L=(dulnode*)malloc(sizeof(dulnode));if(!L)exit(OVERFLOW);L->next=L;L->prior=L;return(OK);//見圖2.14(b)P36}16可編輯課件PPT2.11寫出以下鏈表操作的算法

2）取得雙向循環(huán)鏈表中第i個(gè)數(shù)據(jù)元素的位置指針statusGetElemP_Dul(DuLinkListL,inti){elemtype*p;inta=1;if(i<0)returnERROR;else{p=L;p=p->next;while(a<i||p!=NULL){p=p->next;a++;}}If(a==i)return(p);elsereturn(ERROR);}17可編輯課件PPT2.11寫出以下鏈表操作的算法

3）將單鏈表置逆statusReverseList_L(LinkList&L){Lnode*p1,*p2,*p3;If(L->next==NULL)returnOK;else{p1=L;p1->next=N