[ppt模板]數(shù)據(jù)結(jié)構(gòu)線性表試題-閱讀頁
2025-01-30 06:15本頁面
【正文】 }/*while*/ while(i(*A).length) (*A).elem[m++]=(*A).elem[i++]。 }/* SqList_Intersect_Delete*/11．設(shè)L為單鏈表的頭結(jié)點地址，其數(shù)據(jù)結(jié)點的數(shù)據(jù)都是正整數(shù)且無相同的，試設(shè)計利用直接插入的原則把該鏈表整理成數(shù)據(jù)遞增的有序單鏈表的算法。這就要求從第二結(jié)點開始，將各結(jié)點依次插入到有序鏈表中。 /*p指向第一結(jié)點的后繼*/ lanextnext=NULL。/*暫存p的后繼*/ q=la。amp。/*查找插入位置*/ pnext=qnext。 p=r。在鏈表被起用之前，頻度域freq的值均初始化為零，而每當(dāng)對鏈表進行一次LOCATE（L，X）的操作后，被訪問的結(jié)點（元素值等于X的結(jié)點）中的頻度域freq的值便增1，同時調(diào)整鏈表中結(jié)點之間的次序，使其按訪問頻度非遞增的次序順序排列，以便始終保持被頻繁訪問的結(jié)點總是靠近表頭結(jié)點。 【算法分析】 1）在雙向鏈表中查找數(shù)據(jù)值為x的結(jié)點，由指針p指向，若找不到，直接返回，否則執(zhí)行第2步； 2）修改x結(jié)點的訪問頻度freq，并將結(jié)點從鏈表上摘下； 3）順結(jié)點的前驅(qū)鏈查找該結(jié)點的位置，即找到一個結(jié)點的訪問頻度大于x結(jié)點的訪問頻度，由指針q指向；若q和p不是相鄰結(jié)點，調(diào)整位置，把p插在q之后。 while(!=xamp。p!= (*L)) p=pnext。 /*沒找到x結(jié)點*/ pfreq++。pnextpre=ppre。 while(qfreq=pfreqamp。p!= (*L)) q=qpre。 pnext=qnext。ppreq。}/*Locate_DuList */13．已知三個帶頭結(jié)點的線性鏈表A、B和C中的結(jié)點均依元素值自小至大非遞減排列（可能存在兩個以上值相同的結(jié)點），編寫算法對A表進行如下操作：使操作后的鏈表A中僅留下三個表中均包含的數(shù)據(jù)元素的結(jié)點，且沒有值相同的結(jié)點，并釋放所有無用結(jié)點。 【算法分析】留下三個鏈表中公共數(shù)據(jù)，首先查找兩表A和B中公共數(shù)據(jù)，再去C中找有無該數(shù)據(jù)。 【算法源代碼】 LinkList Common(LinkList A, LinkList B, LinkList C){ pa=Anext。 pc=Cnext。 while(pa amp。 pb amp。 pc) /*當(dāng)三表均不空時，查找共同元素*/ { while(pa amp。 pb) if(padatapbdata) /*處理pa結(jié)點，后移指針*/ {u=pa。free(u)。 else if (pa amp。 pb) /*處理A和B表元素值相等的結(jié)點*/ { while(pc amp。 pcdatapadata) pc=pcnext。pa=panext。} else {if(pre==A) /*結(jié)果表中第一個結(jié)點*/ { prenext=pa。pa=panext} else if(predata==padata) /*重復(fù)結(jié)點不鏈入A表*/ {u=pa。free(u)。pre=pa。}/*將新結(jié)點鏈入A表 */ pb=pbnext。 /* 鏈表的工作指針后移*/ } } else if(pa==NULL)prenext=NULL。 /*置A表表尾標(biāo)記*/ while(pa!=NULL) /*刪除原A表剩余元素。pa=panext。} } }14．設(shè) head為一單鏈表的頭指針，單鏈表的每個結(jié)點由一個整數(shù)域data和指針域next組成，整數(shù)在單鏈表中是無序的。程序中不得使用malloc申請空間。 【算法源代碼】 discreat(LinkList p, LinkList q, LinkList head){ p=NULL。/*p和q鏈表初始化為空表*/ s=head。 /*暫存s的后繼*/ if(sdata%2==0) /*處理偶數(shù)*/ if (p==NULL) {p=s。} /*第一個偶數(shù)結(jié)點*/ else { pre=p。p=s。/*查找插入位置*/ snext=prenext。 } } else/*處理奇數(shù)鏈 if (q==NULL) {q=s。} /*第一奇數(shù)結(jié)點*/ else {pre=q。 q=s。 snext=prenext。} }/*結(jié)束奇數(shù)鏈結(jié)點*/
試題試卷相關(guān)推薦
鄂ICP備17016276號-1