小白算法積累——順序查找1#“機率重心”前移

題目：線性表中各結點的檢索機率不等時，可用如下政策提高順序檢索的效率：機率重心前移（學霸往前坐）

即：若找到指定的結點，則将該結點和其前驅結點（若存在）交換，使得經常被檢索的結點盡量位于表的前端。

試設計在順序結構和鍊式結構的線性表上實作上述政策的順序檢索算法。

關鍵字： 線性表順序查找；機率重心前移；兩種存儲結構

思路：

檢索時可以從表頭開始向後順序掃描，若找到指定的結點，則将該結點和前驅節點（若存在）交換。

1.采用順序表存儲結構的算法實作：

代碼：

int SeqSrch(RcdType R[],ElemType k){//順序表查找線性表，找到後和前面的元素交換
  int i=0;
  while((R[i].key!=k)&&(i<n))
    i++;//從前向後順序查找指定結點
  if(i<n&&i>0){//若找到，則交換
    temp=R[i];
    R[i]=R[i-1];
    R[i-1]=temp;
    return --i;//交換成功，則傳回交換後的位置
  }
  else return -1;//交換失敗
 
}
           

2.鍊式存儲：略

注：為了保證交換結點順序時可以找到前驅結點，需要設立三個指針