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

1、第二章 線性表,作業(yè)評講,2.1 試描述頭指針、頭結(jié)點(diǎn)、開始結(jié)點(diǎn)的區(qū)別、并說明頭指針和頭結(jié)點(diǎn)的作用。 2.2 何時選用順序表、何時選用鏈表作為線性表的存儲結(jié)構(gòu)為宜? 2.3 在順序表中插入和刪除一個結(jié)點(diǎn)需平均移動多少個結(jié)點(diǎn)?具體的移動次數(shù)取決于哪兩個因素? 2.4 為什么在單循環(huán)鏈表中設(shè)置尾指針比設(shè)置頭指針更好? 2.5 在單鏈表、雙鏈表和單循環(huán)鏈表中，若僅知道指針p指向某結(jié)點(diǎn)，不知道頭指針，能否將結(jié)點(diǎn)*p從相應(yīng)的鏈表中刪去?

2、若可以，其時間復(fù)雜度各為多少?,作業(yè)： 2.5、 2.7、2.9、2.11做在作業(yè)本上，交，其余堂下練習(xí),2.6 設(shè)有一個雙鏈表，每個結(jié)點(diǎn)中除有prior、data和next三個域外，還有一個訪問頻度域freq，在鏈表被起用之前，其值均初始化為零。每當(dāng)在鏈表進(jìn)行一次LocateNode(L,s)運(yùn)算時，令元素值為x的結(jié)點(diǎn)中freq域的值加1，并調(diào)整表中結(jié)點(diǎn)的次序，使其按訪問頻度的遞減序排列，以便使頻繁訪問的結(jié)點(diǎn)總是靠近表頭

3、。試寫一符合上述要求的LocateNode運(yùn)算的算法。 2.7 寫一算法在單鏈表上實(shí)現(xiàn)線性表的ListLength(L)運(yùn)算。,,2.8 已知由單鏈表表示的線性表中，含有三類字符的數(shù)據(jù)元素(如：字母字符、數(shù)字字符和其它字符)，試編寫算法構(gòu)造三個以循環(huán)鏈表表示的線性表，使每個表中只含同一類的字符，且利用原表中的結(jié)點(diǎn)空間作為這三個表的結(jié)點(diǎn)空間，頭結(jié)點(diǎn)可另辟空間。 2.9 假設(shè)在長度大于1的單循環(huán)鏈表中，既無頭結(jié)點(diǎn)也無頭指針。s為指向鏈

4、表中某個結(jié)點(diǎn)的指針，試編寫算法刪除結(jié)點(diǎn)*s的直接前趨結(jié)點(diǎn)。2.10設(shè)順序表L是一個遞增有序表，試寫一算法，將x插入L中，并使L仍是一個有序表。,2.11 寫出以下鏈表操作的算法1）創(chuàng)建一個空的雙向循環(huán)鏈表status CreateList_Dul(DuLinkList &L);2）取得雙向循環(huán)鏈表中第i個數(shù)據(jù)元素的位置指針status GetElemP_Dul(DuLinkList L, int i);3）將單鏈表置

5、逆status ReverseList_L(LinkList &L);,2.1 試描述頭指針、頭結(jié)點(diǎn)、開始結(jié)點(diǎn)的區(qū)別、并說明頭指針和頭結(jié)點(diǎn)的作用。,開始結(jié)點(diǎn)是指鏈表中的第一個結(jié)點(diǎn)，沒有直接前趨的那個結(jié)點(diǎn)。鏈表的頭指針是一指向鏈表開始結(jié)點(diǎn)的指針(沒有頭結(jié)點(diǎn)時)，單鏈表由頭指針唯一確定，因此單鏈表可以用頭指針的名字來命名。頭結(jié)點(diǎn)在鏈表的開始結(jié)點(diǎn)之前附加的一個結(jié)點(diǎn)。有了頭結(jié)點(diǎn)之后，頭指針指向頭結(jié)點(diǎn)，不論鏈表否為空，頭指針總是非空

6、。而且頭指針的設(shè)置使得對鏈表的第一個位置上的操作與在表其他位置上的操作一致(都是在某一結(jié)點(diǎn)之后)。,2.2 何時選用順序表、何時選用鏈表作為線性表的存儲結(jié)構(gòu)為宜?1.基于空間的考慮。當(dāng)要求存儲的線性表長度變化不大，易于事先確定其大小時，為了節(jié)約存儲空間，宜采用順序表；反之，當(dāng)線性表長度變化大，難以估計(jì)其存儲規(guī)模時，采用動態(tài)鏈表作為存儲結(jié)構(gòu)為好。2.基于時間的考慮。若線性表的操作主要是進(jìn)行查找，很少做插入和刪除操作時，采用順序表做

7、存儲結(jié)構(gòu)為宜；反之， 若需要對線性表進(jìn)行頻繁地插入或刪除等的操作時，宜采用鏈表做存儲結(jié)構(gòu)。并且，若鏈表的插入和刪除主要發(fā)生在表的首尾兩端，則采用尾指針表示的單循環(huán)鏈表為宜。,2.3 在順序表中插入和刪除一個結(jié)點(diǎn)需平均移動多少個結(jié)點(diǎn)?具體的移動次數(shù)取決于哪兩個因素? 在等概率情況下，順序表中插入一個結(jié)點(diǎn)需平均移動n/2個結(jié)點(diǎn)。 刪除一個結(jié)點(diǎn)需平均移動(n-1)/2個結(jié)點(diǎn)。 具體的移動次數(shù)取決于順序表的長度n以及

8、需插入或刪除的位置i。i越接近n則所需移動的結(jié)點(diǎn)數(shù)越少。,2.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, 查找時間都是O(1)。 若用頭指針來表示該鏈表，則查找終端結(jié)點(diǎn)的時間為

9、O(n)。,2.5 在單鏈表、雙鏈表和單循環(huán)鏈表中，若僅知道指針p指向某結(jié)點(diǎn)，不知道頭指針，能否將結(jié)點(diǎn)*p從相應(yīng)的鏈表中刪去?若可以，其時間復(fù)雜度各為多少?1. 單鏈表。當(dāng)我們知道指針p指向某結(jié)點(diǎn)時，能夠根據(jù)該指針找到其直接后繼，但是由于不知道其頭指針，所以無法訪問到p指針指向的結(jié)點(diǎn)的直接前趨。因此無法刪去該結(jié)點(diǎn)。2. 雙鏈表。由于這樣的鏈表提供雙向鏈接，因此根據(jù)已知結(jié)點(diǎn)可以查找到其直接前趨和直接后繼，從而可以刪除該結(jié)點(diǎn)。其時間復(fù)

10、雜度為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)。其時間復(fù)雜度應(yīng)為O(n)。,2.6設(shè)有一個雙鏈表，每個結(jié)點(diǎn)中除有prior、data和next三個域外，還有一個訪問頻度域freq，在鏈表被起用之前，其值均初始化為零。每當(dāng)在鏈表進(jìn)行一次LocateNode(L,s)運(yùn)算時，令元素值為x的結(jié)點(diǎn)中freq

11、域的值加1，并調(diào)整表中結(jié)點(diǎn)的次序，使其按訪問頻度的遞減序排列，以便使頻繁訪問的結(jié)點(diǎn)總是靠近表頭。試寫一符合上述要求的LocateNode運(yùn)算的算法。,Status locatenode(dullinklist &L,elemtype x){dulnode *p,*q; p=q=L->next; while(p) {if (p->data!=x) p=p->next; else {p->

12、;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-&

13、gt;prior->next=p; q->prior=p} } return ok;},2.7 寫一算法在單鏈表上實(shí)現(xiàn)線性表的ListLength(L)運(yùn)算。求單鏈表長只能用遍歷的方法了，從頭數(shù)到尾。算法如下：int ListLength ( LinkList L ){int len=0 ;ListNode *p;p=L; //設(shè)該表有頭結(jié)點(diǎn)while ( p->next ){p=p->

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

15、 DeleteNode( ListNode *s){//刪除單循環(huán)鏈表中指定結(jié)點(diǎn)的直接前趨結(jié)點(diǎn)ListNode *p, *q;p=s;while( p->next->next!=s) { p=p->next;}q=p->next;p->next=s; //刪除結(jié)點(diǎn)free(q); //釋放空間return OK;},2.10 設(shè)順序表L是一個遞增有序表，試寫一算法，將x插入L

16、中，并使L仍是一個有序表。void InsertIncreaseList( Seqlist *L , Datatype x ){int i;for ( i=0 ; i length && L->data[ i ] < x ; i++) ; // 查找并比較ListInsert_sq ( L ， i, x ); // 調(diào)用順序表插入函數(shù)p24 },2.11 寫出以下鏈表操作的算法1）創(chuàng)建一

17、個空的雙向循環(huán)鏈表,status CreateList_Dul(DuLinkList &L){ L=(dulnode *)malloc(sizeof(dulnode)); if(!L) exit(OVERFLOW); L->next=L; L->prior=L; return(OK);//見圖2.14(b) P36},2.11 寫出以下鏈表操作的算法2）取得雙向循環(huán)鏈

18、表中第i個數(shù)據(jù)元素的位置指針,elemtype * GetElemP_Dul(DuLinkList L, int i){elemtype *p; int a=1; if (inext; while(anext; a++;} }If (a==i)return(p); else return(ERROR);},2.11 寫出以下鏈表操作的算法3）將單鏈表置逆,status ReverseList_L(LinkList &a

19、mp;L){Lnode *p1,*p2,*p3; If(L->next==NULL) return OK; else { p1=L; P2=L->next; p1->next=NULL;P3=p2->next; While( p2!=NULL) {p2->next=p1; p1=p2;p2=p3; if(p2!=NULL) p3=p3->