第二章線性表作業(yè)評講第1頁2.1試描述頭指針、頭結點、開始結點區(qū)分、并說明頭指針和頭結點作用。

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

1.基于空間考慮。當要求存放線性表長度改變不大，易于事先確定其大小時，為了節(jié)約存放空間，宜采取次序表；反之，當線性表長度改變大，難以預計其存放規(guī)模時，采取動態(tài)鏈表作為存放結構為好。2.基于時間考慮。若線性表操作主要是進行查找，極少做插入和刪除操作時，采取次序表做存放結構為宜；反之，

若需要對線性表進行頻繁地插入或刪除等操作時，宜采取鏈表做存放結構。而且，若鏈表插入和刪除主要發(fā)生在表首尾兩端，則采取尾指針表示單循環(huán)鏈表為宜。

第7頁2.3在次序表中插入和刪除一個結點需平均移動多少個結點?詳細移動次數(shù)取決于哪兩個原因?在等概率情況下，次序表中插入一個結點需平均移動n/2個結點。刪除一個結點需平均移動(n-1)/2個結點。詳細移動次數(shù)取決于次序表長度n以及需插入或刪除位置i。i越靠近n則所需移動結點數(shù)越少。

第8頁2.4為何在單循環(huán)鏈表中設置尾指針比設置頭指針更加好?

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

第9頁2.5在單鏈表、雙鏈表和單循環(huán)鏈表中，若僅知道指針p指向某結點，不知道頭指針，能否將結點*p從對應鏈表中刪去?若能夠，其時間復雜度各為多少?

1.單鏈表。當我們知道指針p指向某結點時，能夠依據(jù)該指針找到其直接后繼，不過因為不知道其頭指針，所以無法訪問到p指針指向結點直接前趨。所以無法刪去該結點。2.雙鏈表。因為這么鏈表提供雙向鏈接，所以依據(jù)已知結點能夠查找到其直接前趨和直接后繼，從而能夠刪除該結點。其時間復雜度為O(1)。3.單循環(huán)鏈表。依據(jù)已知結點位置，我們能夠直接得到其后相鄰結點位置(直接后繼)，又因為是循環(huán)鏈表，所以我們能夠經過查找，得到p結點直接前趨。所以能夠刪去p所指結點。其時間復雜度應為O(n)。

第10頁2.6設有一個雙鏈表，每個結點中除有prior、data和next三個域外，還有一個訪問頻度域freq，在鏈表被起用之前，其值均初始化為零。每當在鏈表進行一次LocateNode(L,s)運算時，令元素值為x結點中freq域值加1，并調整表中結點次序，使其按訪問頻度遞減序排列，方便使頻繁訪問結點總是靠近表頭。試寫一符合上述要求LocateNode運算算法。

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頁2.7寫一算法在單鏈表上實現(xiàn)線性表ListLength(L)運算。

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

{

intlen=0;

ListNode*p;

p=L;//設該表有頭結點

while(p->next)

{

p=p->next;

len++;

}

returnlen;

}

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

statusDeleteNode(ListNode*s)

{

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

ListNode*p,*q;

p=s;

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

{

q=p;

p=p->next;

}

q->next=s;//刪除結點

free(p);//釋放空間

returnOK;}第14頁2.10設次序表L是一個遞增有序表，試寫一算法，將x插入L中，并使L仍是一個有序表。

voidInsertIncreaseList(Seqlist*L,Datatypex)

{

inti;

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

}第15頁2.11寫出以下鏈表操作算法

1）創(chuàng)建一個空雙向循環(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頁2.11寫出以下鏈表操作算法

2）取得雙向循環(huán)鏈表中第i個數(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頁2.11寫出以下鏈表操作算法

3）將單鏈表置逆statusReverseList_L(LinkList&L){Lnode*p1,*p2,*p3;If(L->nex