什么是 LRU 算法

LRU 是一種緩存淘汰策略。計算機(jī)的緩存容量有限，如果緩存滿了就要刪除一些內(nèi)容，給新的內(nèi)容騰位置。但是要刪除哪些內(nèi)容呢？我們肯定希望刪掉那些沒有用的緩存，而把有用的數(shù)據(jù)繼續(xù)留在緩存中，方便之后繼續(xù)使用。

LRU 的全稱是 Least Recently Used，也就是說我們認(rèn)為最近使用過的數(shù)據(jù)應(yīng)該是有用的，很久都沒用過的數(shù)據(jù)應(yīng)該是無用的，緩存滿了就優(yōu)先刪除那些很久沒有用過的數(shù)據(jù)。

LRU 算法的特點

首先是緩存的大小是有限的。每次從緩存當(dāng)中獲取數(shù)據(jù)的時候，如果獲取成功會將數(shù)據(jù)移動到最頭部。同時新添加的元素也是在頭部。當(dāng)緩存大小達(dá)到上限之后，添加元素時會刪除最久未使用的元素，也就是鏈表的最后一個元素，然后將新的元素插入在鏈表頭。

LRU 的應(yīng)用場景

LRU 算法可以用來管理我們的緩存數(shù)據(jù)。控制我們的緩存大小，用較少的緩存空間達(dá)到更高的緩存數(shù)據(jù)。舉例來說我們可以將一些不容易發(fā)生變化的數(shù)據(jù)且頭部效應(yīng)表中的數(shù)據(jù)加入到緩存當(dāng)中。

編碼實現(xiàn)

結(jié)構(gòu)定義

#include?
#include?
#include?

//?默認(rèn)容量
#define?N?10

//?表示這個鏈表的長度信息
int?len?=?0;

//當(dāng)前鏈表的元素個數(shù)信息
int?count?=?0;

typedef?struct?Node
{
????/*?data?*/
????char?*key;
????char?*value;

????struct?Node?*next;
????struct?Node?*prev;
}?Node;

//?鏈表的頭節(jié)點和尾節(jié)點
struct?Node?*head;
struct?Node?*tail;

//?函數(shù)預(yù)聲明
//?創(chuàng)建節(jié)點
Node?*createNode(char?*key,?char?*value);
//?插入節(jié)點到頭部
void?insertHead(Node?*node);
//?移除尾部節(jié)點
void?removeTail();
//?添加節(jié)點操作
void?add(char?*key,?char?*value);
//?刪除鏈表中的一個節(jié)點
Node?*deleteNode(Node?*node);
//?獲取指定key的值
char?*get(char?*key);
//?銷毀數(shù)據(jù)
void?destory();

插入操作

//?獲取一個元素
void?add(char?*key,?char?*value){
????Node?*node?=?createNode(key,?value);
????//第一個元素
????if?(head?==?NULL)
????{
????????insertHead(node);
????????return;
????}

????//判斷整個鏈表中是否存在整個元素
????Node?*now?=?deleteNode(node);

????//?如果找到了元素?將元素移動至末尾?結(jié)束方法
????if?(now?!=?NULL)
????{
????????//?設(shè)置新的值
????????now->value?=?value;
????????insertHead(now);
????????return;
????}

????//?此時鏈表中是不存在這個元素
????//?判斷鏈表的長度
????if?(count?>=?len)
????{
????????removeTail();
????}

????//?將新元素添加至末尾
????insertHead(node);
????return;
}

獲取操作

char?*get(char?*key){
????if?(key?==?NULL)
????{
????????return?NULL;
????}

????//?尋找元素
????Node?*node?=?createNode(key,?NULL);
????Node?*now?=?deleteNode(node);

????//?釋放空間
????free(node);

????//?元素存在
????if?(now?!=?NULL)
????{
????????//將元素調(diào)整到末尾
????????insertHead(now);
????????return?now->value;
????}
????return?NULL;
}

基本操作函數(shù)

//?創(chuàng)建一個節(jié)點
Node?*createNode(char?*key,?char?*value){
????Node?*node?=?(Node?*)malloc(sizeof(Node));
????node->key?=?key;
????node->value?=?value;
????node->prev?=?node->next?=?NULL;
????return?node;
}

//?將節(jié)點插入到頭節(jié)點部分
void?insertHead(Node?*node){
????//?元素為空時
????if?(head?==?NULL)
????{
????????tail?=?head?=?node;
????????count++;
????????return;
????}
????node->next?=?head;
????head->prev?=?node;
????//?移動鏈表的末尾指針
????head?=?node;
????//?計數(shù)
????count++;
}

//?移除
void?removeTail(){
????//移除最久未使用的那個元素
????Node?*now?=?tail;
????if?(now?!=?NULL)
????{
????????//?獲取前一個節(jié)點
????????Node?*p?=?now->prev;

????????if?(p?!=?NULL)
????????{
????????????//?斷開當(dāng)前節(jié)點?同時移動尾節(jié)點
????????????p->next?=?NULL;
????????????tail?=?p;
????????}
????????else
????????{
????????????head?=?tail?=?NULL;
????????}
????????//?當(dāng)前節(jié)點置空
????????now->prev?=?now->next?=?NULL;
????????//?元素減少
????????count--;
????????//?釋放空間
????????free(now);
????}
}

//?鏈表中刪除一個節(jié)點??刪除成功返回被刪除節(jié)點
Node?*deleteNode(Node?*node){
????Node?*now?=?head;
????while?(now?!=?NULL)
????{
????????//?存在節(jié)點
????????if?(strcmp(now->key,?node->key)?==?0)
????????{
????????????//?獲取前后節(jié)點
????????????Node?*p?=?now->prev;
????????????Node?*n?=?now->next;

????????????//?更新指向
????????????if?(n?!=?NULL)
????????????{
????????????????n->prev?=?p;
????????????}
????????????else
????????????{
????????????????tail?=?p;
????????????}

????????????if?(p?!=?NULL)
????????????{
????????????????p->next?=?n;
????????????}
????????????else
????????????{
????????????????head?=?n;
????????????}
????????????//當(dāng)前節(jié)點置空
????????????now->prev?=?NULL;
????????????now->next?=?NULL;
????????????count--;
????????????break;
????????}
????????now?=?now->next;
????}
????return?now;
}

//?銷毀數(shù)據(jù)
void?destory(){
????Node?*node?=?head;
????while?(node?!=?NULL)
????{
????????Node?*n?=?node;
????????free(n);
????????node?=?node->next;
????}
????len?=?0;
????count?=?0;
????head?=?tail?=?NULL;
}

//?從頭節(jié)點開始打印整個鏈表
void?printLink(){
????Node?*now?=?head;
????while?(now?!=?NULL)
????{
????????printf("[key=%s,value=%s]",?now->key,?now->value);
????????now?=?now->next;
????}
????printf("\n");
}

最后的測試函數(shù)

int?main(){
????init(5);
????add("1",?"1");
????add("2",?"2");
????printLink();
????char?*res?=?get("1");
????printLink();
????printf("value=%s\n",?res);
????add("3",?"3");
????add("4",?"4");
????add("5",?"5");
????add("6",?"6");
????printLink();
????res?=?get("1");
????printLink();
????destory();
????return?0;
}

//?輸出結(jié)果：
/*
[key=2,value=2][key=1,value=1]
[key=1,value=1][key=2,value=2]
value=1
[key=6,value=6][key=5,value=5][key=4,value=4][key=3,value=3][key=1,value=1]
[key=1,value=1][key=6,value=6][key=5,value=5][key=4,value=4][key=3,value=3]
*/

以上就是一個鏈表實現(xiàn) LRU 算法的大體代碼。

已將代碼上傳至https://gitlab.com/BitLegend/c-data-structure.git

感謝你能看到這里，歡迎關(guān)注我的公眾號：BitLegend,我們下期見！

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的c均值算法的设计与实现_如何使用C链表实现 LRU 算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。