自组织列表：计数法-yiteyi-C++库

自组织列表是一个重新组织或重新安排自己以获得更好性能的列表。在一个简单的列表中，要搜索的项目是按顺序查找的，这使得时间复杂度为O（n）。但在真实场景中，并不是所有的项目都被频繁搜索，而且大多数情况下只有少数项目被多次搜索。

null

因此，自组织列表使用这个属性（也称为引用位置），将最常用的项置于列表的开头。这增加了在列表开头找到项目的可能性，并且那些很少使用的元素被推到列表的后面。

在里面 计数法 ，计算每个节点的搜索次数（即保持搜索频率）。因此，每个节点都有一个额外的存储空间，每次搜索节点时，存储空间都会增加。然后，节点按计数或搜索频率的非递增顺序排列。因此，这确保了访问频率最高的节点保持在列表的最前面。

图片[1]-自组织列表：计数法-yiteyi-C++库

例如：

Input : list : 1, 2, 3, 4, 5
        searched : 4 
Output : list : 4, 1, 2, 3, 5

Input : list : 4, 1, 2, 3, 5
        searched : 5
        searched : 5
        searched : 2
Output : list : 5, 2, 4, 1, 3
Explanation : 5 is searched 2 times (i.e. the 
most searched) 2 is searched 1 time and 4 is 
also searched 1 time (but since 2 is searched 
recently, it is kept ahead of 4) rest are not 
searched, so they maintained order in which
they were inserted.

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

                     // CPP Program to implement self-organizing list                   
                     // using count method                   
                     #include <iostream>                   
                     using                               namespace                               std;                   
                             
                     // structure for self organizing list                   
                     struct                               self_list {                   
                                         int                               value;                   
                                         int                               count;                   
                                         struct                               self_list* next;                   
                     };                   
                             
                     // head and rear pointing to start and end of list resp.                   
                     self_list *head = NULL, *rear = NULL;                   
                             
                     // function to insert an element                   
                     void                               insert_self_list(                               int                               number)                   
                     {                   
                                         // creating a node                   
                                         self_list* temp = (self_list*)                               malloc                               (                               sizeof                               (self_list));                   
                             
                                         // assigning value to the created node;                   
                                         temp->value = number;                   
                                         temp->count = 0;                   
                                         temp->next = NULL;                   
                             
                                         // first element of list                   
                                         if                               (head == NULL)                   
                                         head = rear = temp;                   
                             
                                         // rest elements of list                   
                                         else                               {                   
                                         rear->next = temp;                   
                                         rear = temp;                   
                                         }                   
                     }                   
                             
                     // function to search the key in list                   
                     // and re-arrange self-organizing list                   
                     bool                               search_self_list(                               int                               key)                   
                     {                   
                                         // pointer to current node                   
                                         self_list* current = head;                   
                             
                                         // pointer to previous node                   
                                         self_list* prev = NULL;                   
                             
                                         // searching for the key                   
                                         while                               (current != NULL) {                   
                             
                                         // if key is found                   
                                         if                               (current->value == key) {                   
                             
                                         // increment the count of node                   
                                         current->count = current->count + 1;                   
                             
                                         // if it is not the first element                   
                                         if                               (current != head) {                   
                                         self_list* temp = head;                   
                                         self_list* temp_prev = NULL;                   
                             
                                         // finding the place to arrange the searched node                   
                                         while                               (current->count < temp->count) {                   
                                         temp_prev = temp;                   
                                         temp = temp->next;                   
                                         }                   
                             
                                         // if the place is other than its own place                   
                                         if                               (current != temp) {                   
                                         prev->next = current->next;                   
                                         current->next = temp;                   
                             
                                         // if it is to be placed at beginning                   
                                         if                               (temp == head)                   
                                         head = current;                   
                                         else                   
                                         temp_prev->next = current;                   
                                         }                   
                                         }                   
                                         return                               true                               ;                   
                                         }                   
                                         prev = current;                   
                                         current = current->next;                   
                                         }                   
                                         return                               false                               ;                   
                     }                   
                             
                     // function to display the list                   
                     void                               display()                   
                     {                   
                                         if                               (head == NULL) {                   
                                         cout <<                               "List is empty"                               << endl;                   
                                         return                               ;                   
                                         }                   
                             
                                         // temporary pointer pointing to head                   
                                         self_list* temp = head;                   
                                         cout <<                               "List: "                               ;                   
                             
                                         // sequentially displaying nodes                   
                                         while                               (temp != NULL) {                   
                                         cout << temp->value <<                               "("                               << temp->count <<                               ")"                               ;                   
                                         if                               (temp->next != NULL)                   
                                         cout <<                               " --> "                               ;                   
                             
                                         // incrementing node pointer.                   
                                         temp = temp->next;                   
                                         }                   
                                         cout << endl                   
                                         << endl;                   
                     }                   
                             
                     // Driver Code                   
                     int                               main()                   
                     {                   
                                         /* inserting five values */                   
                                         insert_self_list(1);                   
                                         insert_self_list(2);                   
                                         insert_self_list(3);                   
                                         insert_self_list(4);                   
                                         insert_self_list(5);                   
                             
                                         // Display the list                   
                                         display();                   
                             
                                         search_self_list(4);                   
                                         search_self_list(2);                   
                                         display();                   
                             
                                         search_self_list(4);                   
                                         search_self_list(4);                   
                                         search_self_list(5);                   
                                         display();                   
                             
                                         search_self_list(5);                   
                                         search_self_list(2);                   
                                         search_self_list(2);                   
                                         search_self_list(2);                   
                                         display();                   
                                         return                               0;                   
                     }                   

输出：

List: 1(0) --> 2(0) --> 3(0) --> 4(0) --> 5(0)
List: 2(1) --> 4(1) --> 1(0) --> 3(0) --> 5(0)
List: 4(3) --> 5(1) --> 2(1) --> 1(0) --> 3(0)
List: 2(4) --> 4(3) --> 5(2) --> 1(0) --> 3(0)

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章