一次debug分析

背景描述：

实现LRU算法，在实现的过程中，遇到的输出如下,最开始的一部分输入是正常的，后来链表被破坏，长度依次减少了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
get 3 0
 -1 -1 -1  2  1  5  4  9 10  6  3
 -1 -1 -1 19 30  5 30  3 25 14  1
put 10 11
 -1 -1 -1  2  1  5  4  9 10
 -1 -1 -1 19 30  5 30  3 11
get 8 0
 -1 -1 -1  2  1  5  4  9 10
 -1 -1 -1 19 30  5 30  3 11
get 5 0
 -1 13 11  2  3 12  9  6  5
 -1 17 15 15 16 17  1 19 18
get 5 0
 -1 13 11  2  3 12  9  6  5
 -1 17 15 15 16 17  1 19 18
put 8 1
 -1 11  2  3 12  9  6  5  8
 -1 15 15 16 17  1 19 18  1
put 11 7
 -1  2  3 12  9  6  5  8 11
 -1 15 16 17  1 19 18  1  7
put 5 2
 -1  2  3 12  9  6  5
 -1 15 16 17  1 19  2
put 9 28
 -1  2  3 12  6  5  9
 -1 15 16 17 19  2 28
get 1 0
 -1  2  3 12  6  5  9
 -1 15 16 17 19  2 28
put 2 2
  • 在仔细分析输出的数据，每次都是在put 时候，出现问题，但是之前的多次put是没有问题的,只有再分析get了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
int get_Node(Node*ptr,int key){
    Node* head = ptr;
    Node* record = NULL;
    ptr = ptr->next;
    while(ptr){
        if(ptr->key == key){
            record = ptr;
            if(ptr->next != NULL){
                ptr->next->pre = ptr->pre;
                ptr->pre->next = ptr->next;
            }

        }
        if(ptr->next == NULL){
            if(record!=NULL){
                //if(ptr->next==NULL) return record->val;
                ptr->next = record;
                //bug 点 它的上一个指向了他自身，破坏了双向链表
                record->pre = ptr;
                record->next = NULL;
                return record->val;
            }
            return -1;
        }
        ptr = ptr->next;

    }
    return -1;
}