LRU算法不用哈希表怎么实现？

可以使用双向链表来实现LRU算法，每次访问一个元素时，将其移动到链表头部，当链表满时，将链表尾部的元素删除即可。这样可以保证最近访问的元素总是在链表头部，最久未访问的元素总是在链表尾部。这种实现方式的时间复杂度为O(n)，空间复杂度为O(n)。

相关问题

利用哈希表来实现LRU页面置换算法C语言

好的，下面是一个利用哈希表和双向链表实现LRU页面置换算法的C语言代码示例：

#include <stdio.h>
#include <stdlib.h>

#define CACHE_CAPACITY 5 // 缓存容量为5

// 定义缓存节点
typedef struct CacheNode {
    int key; // 缓存键
    int value; // 缓存值
    struct CacheNode *prev; // 上一个节点指针
    struct CacheNode *next; // 下一个节点指针
} CacheNode;

// 定义哈希表节点
typedef struct HashNode {
    int key; // 哈希键
    CacheNode *value; // 哈希值，为指向缓存节点的指针
    struct HashNode *next; // 下一个节点指针
} HashNode;

// 初始化缓存节点
CacheNode *initCacheNode(int key, int value) {
    CacheNode *node = (CacheNode *)malloc(sizeof(CacheNode));
    node->key = key;
    node->value = value;
    node->prev = NULL;
    node->next = NULL;
    return node;
}

// 初始化哈希表
HashNode **initHashTable() {
    HashNode **hashTable = (HashNode **)malloc(CACHE_CAPACITY * sizeof(HashNode *));
    for (int i = 0; i < CACHE_CAPACITY; i++) {
        hashTable[i] = (HashNode *)malloc(sizeof(HashNode));
        hashTable[i]->key = -1; // 哈希键设为-1，表示无效节点
        hashTable[i]->value = NULL;
        hashTable[i]->next = NULL;
    }
    return hashTable;
}

// 计算哈希值
int hash(int key) {
    return key % CACHE_CAPACITY;
}

// 向哈希表中添加节点
void addHashNode(HashNode **hashTable, int key, CacheNode *node) {
    int index = hash(key);
    HashNode *hashNode = hashTable[index];
    while (hashNode->next != NULL) { // 找到哈希表尾部
        hashNode = hashNode->next;
    }
    HashNode *newNode = (HashNode *)malloc(sizeof(HashNode)); // 创建新节点
    newNode->key = key;
    newNode->value = node;
    newNode->next = NULL;
    hashNode->next = newNode; // 将新节点插入哈希表尾部
}

// 从哈希表中删除节点
void removeHashNode(HashNode **hashTable, int key) {
    int index = hash(key);
    HashNode *hashNode = hashTable[index];
    while (hashNode->next != NULL) {
        if (hashNode->next->key == key) { // 找到待删除节点
            HashNode *temp = hashNode->next;
            hashNode->next = temp->next; // 将待删除节点从哈希表中移除
            free(temp);
            break;
        }
        hashNode = hashNode->next;
    }
}

// 查找哈希表中是否存在指定键
CacheNode *findHashNode(HashNode **hashTable, int key) {
    int index = hash(key);
    HashNode *hashNode = hashTable[index];
    while (hashNode->next != NULL) {
        if (hashNode->next->key == key) { // 找到指定键的哈希节点
            return hashNode->next->value;
        }
        hashNode = hashNode->next;
    }
    return NULL;
}

// 将缓存节点移动到链表头部
void moveToHead(CacheNode *node) {
    CacheNode *prev = node->prev;
    CacheNode *next = node->next;
    prev->next = next;
    next->prev = prev;
    node->prev = NULL;
    node->next = NULL;
    prev = next = node;
}

// 利用LRU算法获取缓存中指定键的值
int getCacheValue(HashNode **hashTable, CacheNode **head, CacheNode **tail, int key, int value) {
    CacheNode *node = findHashNode(hashTable, key);
    if (node != NULL) { // 如果键已经在缓存中，将其移动到链表头部
        moveToHead(node);
        return node->value;
    } else { // 如果不在缓存中，将其添加到链表头部
        node = initCacheNode(key, value);
        addHashNode(hashTable, key, node);
        node->next = *head;
        (*head)->prev = node;
        *head = node;
        if (*tail == NULL) { // 如果链表为空，将尾指针指向头指针
            *tail = *head;
        }
        if (hashTable[key % CACHE_CAPACITY]->next->next != NULL) { // 如果缓存已经满了，将链表尾部的节点移除
            HashNode *lastNode = hashTable[(*tail)->key % CACHE_CAPACITY];
            removeHashNode(hashTable, (*tail)->key);
            *tail = (*tail)->prev;
            (*tail)->next = NULL;
            free(lastNode->next);
        }
        return -1;
    }
}

int main() {
    HashNode **hashTable = initHashTable();
    CacheNode *head = NULL;
    CacheNode *tail = NULL;
    int cache[][2] = {{1, 10}, {2, 20}, {3, 30}, {4, 40}, {5, 50}, {6, 60}, {7, 70}, {8, 80}, {9, 90}, {1, 100}, {2, 200}, {3, 300}, {4, 400}}; // 测试数据
    for (int i = 0; i < sizeof(cache) / sizeof(cache[0]); i++) {
        int value = getCacheValue(hashTable, &head, &tail, cache[i][0], cache[i][1]);
        if (value != -1) {
            printf("hit: %d\n", value);
        } else {
            printf("miss: %d\n", cache[i][1]);
        }
    }
    return 0;
}

以上就是一个基于哈希表和双向链表实现的LRU页面置换算法的C语言代码示例。

lru算法用c语言的实现

LRU（Least Recently Used）算法是一种缓存淘汰算法，它的基本思想是根据数据的使用频率来淘汰最近最少使用的数据。以下是用C语言实现LRU算法的示例代码：

#include <stdio.h>
#include <stdlib.h>

// 定义LRU结点的结构体
typedef struct Node {
    int key;  // 结点的键
    int value;  // 结点的值
    struct Node* next;  // 指向下一个结点的指针
    struct Node* prev;  // 指向前一个结点的指针
} Node;

// 定义LRU缓存的结构体
typedef struct LRUCache {
    int capacity;  // 缓存的容量
    int size;  // 缓存的当前大小
    Node* head;  // 指向链表头节点的指针
    Node* tail;  // 指向链表尾节点的指针
    Node** hashmap;  // 哈希表，保存结点的指针
} LRUCache;

// 初始化LRU缓存
LRUCache* lRUCacheCreate(int capacity) {
    LRUCache* cache = (LRUCache*)malloc(sizeof(LRUCache));
    cache->capacity = capacity;
    cache->size = 0;
    cache->head = NULL;
    cache->tail = NULL;
    cache->hashmap = (Node**)calloc(capacity, sizeof(Node*));
    return cache;
}

// 获取LRU缓存中指定key对应的value
int lRUCacheGet(LRUCache* obj, int key) {
    if (obj->hashmap[key] == NULL) {
        return -1;
    }

    // 将访问的结点移到链表头部
    Node* node = obj->hashmap[key];
    if (node != obj->head) {
        if (node == obj->tail) {
            obj->tail = obj->tail->prev;
        } else {
            node->next->prev = node->prev;
            node->prev->next = node->next;
        }
        node->next = obj->head;
        node->prev = NULL;
        obj->head->prev = node;
        obj->head = node;
    }

    return node->value;
}

// 向LRU缓存中插入新的key-value对
void lRUCachePut(LRUCache* obj, int key, int value) {
    if (obj->hashmap[key] == NULL) {
        // 如果缓存已满，删除最近最少使用的结点
        if (obj->size == obj->capacity) {
            Node* tail = obj->tail;
            obj->hashmap[tail->key] = NULL;
            obj->tail = tail->prev;
            if (obj->tail != NULL) {
                obj->tail->next = NULL;
            } else {
                obj->head = NULL;
            }
            free(tail);
            obj->size--;
        }

        // 创建新的结点并加入链表头部
        Node* node = (Node*)malloc(sizeof(Node));
        node->key = key;
        node->value = value;
        node->next = obj->head;
        node->prev = NULL;
        if (obj->head != NULL) {
            obj->head->prev = node;
        } else {
            obj->tail = node;
        }
        obj->head = node;
        obj->hashmap[key] = node;
        obj->size++;
    } else {
        // 更新结点的值并移到链表头部
        Node* node = obj->hashmap[key];
        node->value = value;
        if (node != obj->head) {
            if (node == obj->tail) {
                obj->tail = obj->tail->prev;
            } else {
                node->next->prev = node->prev;
                node->prev->next = node->next;
            }
            node->next = obj->head;
            node->prev = NULL;
            obj->head->prev = node;
            obj->head = node;
        }
    }
}

// 释放LRU缓存的内存
void lRUCacheFree(LRUCache* obj) {
    Node* curr = obj->head;
    while (curr != NULL) {
        Node* tmp = curr->next;
        free(curr);
        curr = tmp;
    }
    free(obj->hashmap);
    free(obj);
}

int main() {
    LRUCache* cache = lRUCacheCreate(2);
    lRUCachePut(cache, 1, 1);
    lRUCachePut(cache, 2, 2);
    printf("%d\n", lRUCacheGet(cache, 1));  // 输出1
    lRUCachePut(cache, 3, 3);
    printf("%d\n", lRUCacheGet(cache, 2));  // 输出-1
    lRUCachePut(cache, 4, 4);
    printf("%d\n", lRUCacheGet(cache, 1));  // 输出-1
    printf("%d\n", lRUCacheGet(cache, 3));  // 输出3
    printf("%d\n", lRUCacheGet(cache, 4));  // 输出4
    lRUCacheFree(cache);
    return 0;
}

以上代码是用C语言实现LRU算法的简单示例，包括创建缓存、获取键对应的值、插入新的键值对以及释放内存的功能。代码中使用了双向链表和哈希表来实现LRU缓存，保证了缓存的快速查找和结点的插入/删除操作。在main函数中演示了LRU缓存的使用过程，并输出了一些操作的结果。