【正文】 Delete_Between(LinkList *L,int mink,int maxk){ p=*L。 　　free(hb)。 　++。 t=pdata。 pprior=q。第2章 　選擇題1．對于線性表最常用的操作是查找指定序號的元素和在末尾插入元素，則選擇（ ）最節(jié)省時間 A）順序表 B）帶頭結(jié)點的雙循環(huán)鏈表 C）單鏈表 D）帶尾結(jié)點的單循環(huán)鏈表 【答案】A 2．若長度為n的線性表采用順序存儲結(jié)構(gòu)，在其第i個位置插入一個新元素的算法時間復雜度為（　?。?1≤i≤n+1)。 qprior=pprior。 pnext=s。 　[i+1]=x。 　 pnext=hbnext。 【算法分析】 1）查找最后一個不大于mink的元素結(jié)點，由指針p指向； 2）如果還有比mink更大的元素，查找第一個不小于maxk的元素，由指針q指向； 3）pnext=q，即刪除表中所有值大于 mink且小于 maxk的元素。 　　　　　　　　　} 　　　　　　　　pnext=q。Lnext=s。 【算法分析】按從小到大的順序依次把A和B的元素插入新表的頭部pc處，最后處理A或B的剩余元素。 /*構(gòu)造新表頭*/}/*reverse_merge*/10．已知A，B和C為三個遞增有序的線性表，現(xiàn)要求對A表作如下操作：刪去那些既在B表中出現(xiàn)又在C表中出現(xiàn)的元素。 /*j和k后移到新的元素*/ while(i(*A).lengthamp。amp。pnextpre=ppre。 pc=Cnext。 pcdatapadata) pc=pcnext。 /*置A表表尾標記*/ while(pa!=NULL) /*刪除原A表剩余元素。p=s。} }/*結(jié)束奇數(shù)鏈結(jié)點*/ s=r。 /*暫存s的后繼*/ if(sdata%2==0) /*處理偶數(shù)*/ if (p==NULL) {p=s。}/*將新結(jié)點鏈入A表 */ pb=pbnext。 else if (pa amp。 【算法分析】留下三個鏈表中公共數(shù)據(jù)，首先查找兩表A和B中公共數(shù)據(jù)，再去C中找有無該數(shù)據(jù)。p!= (*L)) p=pnext。 /*p指向第一結(jié)點的后繼*/ lanextnext=NULL。 else if([j][k]) k++。pb=q。 qnext=s。 　　　q=s。 q=pnext?！next=new。試設計一個算法將這兩個鏈表連接在一起（即令其中一個表的首元結(jié)點連在另一個表的最后一個結(jié)點之后），假設指針hc指向連接后的鏈表的頭結(jié)點，并要求算法以盡可能短的時間完成連接運算。xamp。 【答案】（1）O(1) （2）O(n) 7. 對于雙向鏈表，在兩個結(jié)點之間插入一個新結(jié)點需修改的指針共_____________個，單鏈表為_____________個。 ppriornext=q。 qprior=pprior。 【答案】A 9．線性表采用鏈式存儲時，其元素地址（　?。?A）必須是連續(xù)的 B）一定是不連續(xù)的 C）部分地址是連續(xù)的 D）連續(xù)與否均可 【答案】D 　填空題1．線性表L=（a1，a2，…，an）用數(shù)組表示，假定刪除表中任一元素的概率相同，則刪除一個元素平均需要移動元素的個數(shù)是_____________。 【答案】144 11．帶頭結(jié)點的雙循環(huán)鏈表L中只有一個元素結(jié)點的條件是_____________。i=amp。 　new=(LinkList*)malloc(sizeof(LNode))。 /*q是第一個不小于maxk的元素*/ 　　　　pnext=q。 【算法源代碼】 void LinkList_reverse(LinkList L){ if(!Lnext||!Lnextnext) return?！　=Bnext。 　while(pa||pb) 　　{ if(padatapbdata||!pb) /*將A的元素插入新表*/ 　　　　{ pc=pa。 k=0。(*A).elem==same) i++。}12．設有一個雙向循環(huán)鏈表，每個結(jié)點中除有 prior，data和 next三個域外，還增設了一個訪問頻度域freq。 /*查找插入位置*/ if(q!=ppre) /*將x結(jié)點插入*/ { qnextpre=p。amp。pre=pa。編一函數(shù)，將 head鏈中結(jié)點分成一個奇數(shù)鏈和一個偶數(shù)鏈，分別由p，q指向，每個鏈中的數(shù)據(jù)按由小到大排列。qnext=NULL。 if (predatasdata) {snext=pre。 【算法分析】本題要求將一個鏈表分解成兩個鏈表，兩個鏈表都要有序，兩鏈表建立過程中不得使用malloc申請空間，這就是要利用原鏈表空間，隨著原鏈表的分解，新建鏈表隨之排序。pa=panext。amp。 qnext=p。試編寫符合上述要求的 LOCATE操作的算法。 /*A的剩余元素重新存儲*/