自组织列表：转置法-yiteyi-C++库

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

null

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

在里面 转置法 ，被访问的节点将与其前一个节点交换。因此，如果任何节点被访问，它将与它前面的节点交换，除非它是列表中的第一个（头）节点。简单地说，被访问节点的优先级会缓慢增加，从而最终到达第一个位置。转置方法和其他方法的主要区别在于，需要多次访问才能将节点置于前端。

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

例如：

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

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

Explanation: In 1st case, 4 is swapped with its predecessor i.e. 3
             In 2nd case, 5 is swapped with its predecessor i.e. again 3

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

                     // CPP Program to implement self-organizing list                   
                     // using move to front method                   
                     #include <iostream>                   
                     using                               namespace                               std;                   
                             
                     // structure for self organizing list                   
                     struct                               self_list {                   
                                         int                               value;                   
                                         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->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;                   
                             
                                         // pointer to previous of previous                   
                                         self_list* prev_prev = NULL;                   
                             
                                         // searching for the key                   
                                         while                               (current != NULL) {                   
                             
                                         // if key found                   
                                         if                               (current->value == key) {                   
                             
                                         // if key is neither the first element                   
                                         // and nor the second element                   
                                         if                               (prev_prev != NULL) {                   
                             
                                         /* re-arranging the elements */                   
                                         prev_prev->next = current;                   
                                         prev->next = current->next;                   
                                         current->next = prev;                   
                                         }                   
                             
                                         // if key is second element                   
                                         else                               if                               (prev != NULL) {                   
                             
                                         /* re-arranging the elements */                   
                                         prev->next = current->next;                   
                                         current->next = prev;                   
                                         head = current;                   
                                         }                   
                                         return                               true                               ;                   
                                         }                   
                                         prev_prev = prev;                   
                                         prev = current;                   
                                         current = current->next;                   
                                         }                   
                             
                                         // key not found                   
                                         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;                   
                                         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);                   
                                         insert_self_list(6);                   
                             
                                         // Display the list                   
                                         display();                   
                             
                                         // search 4 and if found then re-arrange                   
                                         if                               (search_self_list(4))                   
                                         cout <<                               "Searched: 4"                               << endl;                   
                                         else                   
                                         cout <<                               "Not Found: 4"                               << endl;                   
                             
                                         // Display the list                   
                                         display();                   
                             
                                         // search 2 and if found then re-arrange                   
                                         if                               (search_self_list(5))                   
                                         cout <<                               "Searched: 5"                               << endl;                   
                                         else                   
                                         cout <<                               "Not Found: 5"                               << endl;                   
                                         display();                   
                             
                                         return                               0;                   
                     }                   

输出：

List: 1 --> 2 --> 3 --> 4 --> 5 --> 6

Searched: 4
List: 1 --> 2 --> 4 --> 3 --> 5 --> 6

Searched: 5
List: 1 --> 2 --> 4 --> 5 --> 3 --> 6

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

THE END

技术文章