[ppt模板]數(shù)據(jù)結(jié)構(gòu)線性表試題(參考版)
2025-01-18 06:15本頁面
【正文】 /*s指向新的待排序結(jié)點*/ }}。 /*鏈入結(jié)點*/ prenext=s。} /*修改頭指針*/ else {while (prenext!=NULL) /*查找插入位置*/ if (prenextdatasdata) pre=prenext。 if (predatasdata) {snext=pre。qnext=NULL。 /*鏈入結(jié)點*/ prenext=s。}/*插入當(dāng)前最小值結(jié)點*/ else {while (prenext!=NULL) if (prenextdatasdata) pre=prenext。 if(predatasdata) {snext=pre。pnext=NULL。 while (s!=NULL) { r=snext。 q=NULL。 【算法分析】本題要求將一個鏈表分解成兩個鏈表，兩個鏈表都要有序，兩鏈表建立過程中不得使用malloc申請空間，這就是要利用原鏈表空間，隨著原鏈表的分解，新建鏈表隨之排序。編一函數(shù)，將 head鏈中結(jié)點分成一個奇數(shù)鏈和一個偶數(shù)鏈，分別由p，q指向，每個鏈中的數(shù)據(jù)按由小到大排列。free(u)。*/ {u=pa。 /*若A表已結(jié)束，置A表表尾*/ else /*處理原A表未到尾而B或C到尾的情況*/ { prenext=NULL。pc=pcnext。pa=panext。} else {prenext=pa。pa=panext。pre=pa。free(u)。 if(pc) {if(pcdatapadata) /*處理pa結(jié)點，后移指針*/ {u=pa。amp。amp。} else if(padata pbdata)pb=pbnext。pa=panext。amp。amp。amp。 /*pa，pb和pc是工作指針*/ pre=A。pb=Bnext。要消除重復(fù)元素，應(yīng)記住前驅(qū)，要求時間復(fù)雜度O（m+n+p），在查找每個鏈表時，指針不能回溯。限定算法的時間復(fù)雜度為O（m+n+p），其中m、n和p分別為三個表的長度。 /*調(diào)整位置*/ } return p。 qnext=p。 /*查找插入位置*/ if(q!=ppre) /*將x結(jié)點插入*/ { qnextpre=p。amp。 /*將x結(jié)點從鏈表上摘下*/ q=ppre。 pprenext=pnext。 if(p==(*L)) return NULL。amp。 【算法源代碼】 DuLNode * Locate_DuList(DuLinkList *L,int x) { p=(*L)next。試編寫符合上述要求的 LOCATE操作的算法。}12．設(shè)有一個雙向循環(huán)鏈表，每個結(jié)點中除有 prior，data和 next三個域外，還增設(shè)了一個訪問頻度域freq。/*將p結(jié)點鏈入鏈表*/ qnext=p。qnextdatapdata) q=qnext。 while (qnext!=NULLamp。 /*直接插入原則認為第一元素有序，然后從第二元素起依次插入*/ while (p!=NULL) { r=pnext。 【算法源代碼】 void InsertSort (LinkList la){ if(lanext!=NULL) /*鏈表不為空表*/ { p=lanextnext。 【算法分析】本題明確指出單鏈表帶頭結(jié)點，其結(jié)點數(shù)據(jù)是正整數(shù)且不相同，要求利用直接插入原則把鏈表整理成遞增有序鏈表。 /*A的剩余元素重新存儲*/ (*A).length=m。(*A).elem==same) i++。 /*需保留的元素移動到新位置*/ while(i(*A).lengthamp。amp。 while([k]==same) k++。 else{ same=[j]。 k) { if ([j][k]) j++。jamp。 /*i指示A中元素原來的位置，m為移動后的位置*/ while(i(*A).lengthamp。 k=0。 【算法源代碼】 void SqLi
試題試卷相關(guān)推薦
鄂ICP備17016276號-1