## 問題描述 > 設頭指針為L的帶有表頭結點的非循環雙向鏈表，其每個結點中除有prior（前驅指針），data（數據），next（后繼指針）域外，還有一個訪問頻度域freq。在鏈表被啟用前，其值均初始化為零。每當在連表中進行一次Locate(L,x)運算時，令元素值為x的結點中freq域的值增1，并使此鏈表中結點保持按訪問頻度非遞增的順序排列，同時最近訪問的結點排在頻度相同的結點的前面，以便使頻繁訪問的結點總是靠近表頭。試編寫符合上述要求的Locate(L,x)運算的算法，該運算為函數過程，返回找到結點的地址，類型為指針型。 ## 算法思想 > 本題經過分析之后可以發現，主要考察了雙鏈表的查找，刪除，插入操作。 > - 首先在雙鏈表中查找數據域的值為x的結點； > - 找到后，將結點從鏈表上摘下，然后再從頭節點按照頻度遞減的次序向后查找，插入到同頻度出現的第一個位置 > - 這樣便完成了一次排序 ## 算法描述 ~~~ void Locate(DNode *head, ElemType x) { DNode *pre=head; DNode *p=head->next; while(p&&p->data!=x){ p=p->next; } if(!p){ printf("The %d isn't exist!\n",x); return; }else{ p->freq++; if(p->next){ p->next->prior=p->prior; } p->prior->next=p->next; pre=p->prior; while(pre!=head&&pre->freq<p->freq){ pre=pre->prior; } p->next=pre->next; pre->next->prior=p; p->prior=pre; pre->next=p; } } ~~~ 具體代碼見附件。 ## 附件 ~~~ #include<stdio.h> #include<stdlib.h> typedef int ElemType; typedef struct DNode{ int freq; ElemType data; struct DNode *prior,*next; }DNode,*DLinkList; DLinkList CreatList(DNode*); void Locate(DNode*,ElemType); void BackPrint(DNode*); int main(int argc,char* argv[]) { DNode *head; head=(DNode*)malloc(sizeof(DNode)); head->prior=NULL; head->next=NULL; head=CreatList(head); BackPrint(head); //模擬結點數據域的值出現的次數 for(ElemType x=1;x<=8;x++){ if(x%2==0){ Locate(head,x); if(x%3==0){ Locate(head,x); } } } BackPrint(head); return 0; } //頭插法建立非循環雙向鏈表 DLinkList CreatList(DNode *head) { DNode *L; int freq=0; ElemType x; scanf("%d",&x); while(x!=999){ L=(DNode*)malloc(sizeof(DNode)); L->freq=freq; L->data=x; L->next=head->next; if(head->next){ head->next->prior=L; } L->prior=head; head->next=L; scanf("%d",&x); } return head; } void Locate(DNode *head, ElemType x) { DNode *pre=head; DNode *p=head->next; while(p&&p->data!=x){ p=p->next; } if(!p){ printf("The %d isn't exist!\n",x); return; }else{ p->freq++; if(p->next){ p->next->prior=p->prior; } p->prior->next=p->next; pre=p->prior; while(pre!=head&&pre->freq<p->freq){ pre=pre->prior; } p->next=pre->next; pre->next->prior=p; p->prior=pre; pre->next=p; } } void BackPrint(DNode *head) { DNode *p=head; while(p->next){ p=p->next; printf("%4d|%d",p->data,p->freq); } printf("\n"); } ~~~