數據結構考研分類復習真題 第二章 答案[55]

　　．[題目分析]首先在雙向鏈表中查找數據值為x的結點查到後將結點從鏈表上摘下然後再順結點的前驅鏈查找該結點的位置

　　DLinkList  locate(DLinkList LElemType x)∥L是帶頭結點的按訪問頻度遞減的雙向鏈表本算法先查找數據x查找成功時結點的訪問頻度域增最後將該結點按頻度遞減插入鏈表中適當位置
　　{ DLinkList p=L>nextq;∥p為L表的工作指針q為p的前驅用於查找插入位置
　　while (p && p>data !=x) p=p>next;∥查找值為x的結點
　　if (!p) {printf(不存在值為x的結點\n); exit();}
　　else { p>freq++;∥令元素值為x的結點的freq域加
　　p>next>pred=p>pred;∥將p結點從鏈表上摘下
　　p>pred>next=p>next;
　　q=p>pred;∥以下查找p結點的插入位置
　　while (q !=L && q>freq<p>freq) q=q>pred;
　　p>next=q>next; q>next>pred=p;∥將p結點插入
　　p>pred=q; q>next=p;
　　}
　　return(p);∥返回值為x的結點的指針
　　}∥算法結束

[]  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  

From:http://tw.wingwit.com/Article/program/sjjg/201311/23315.html