自组织列表：移动到前面方法-yiteyi-C++库

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

null

因此，自组织列表使用此属性（也称为 参考位置 )这使得最常用的物品排在榜首。这增加了在列表开头找到项目的可能性，并且那些很少使用的元素被推到列表的后面。

在里面 向前移动法 ，最近搜索的项目将移至列表的前面。因此，这种方法很容易实现，但它也会将频繁搜索的项目移到前面。这种将频繁搜索的项目移动到前端的做法是这种方法的一大缺点，因为它会影响访问时间。

图片[1]-自组织列表：移动到前面方法-yiteyi-C++库图片[2]-自组织列表：移动到前面方法-yiteyi-C++库

例如：

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

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

                     // 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;                   
                             
                                         // searching for the key                   
                                         while                               (current != NULL) {                   
                             
                                         // if key found                   
                                         if                               (current->value == key) {                   
                             
                                         // if key is not the first element                   
                                         if                               (prev != NULL) {                   
                             
                                         /* re-arranging the elements */                   
                                         prev->next = current->next;                   
                                         current->next = head;                   
                                         head = current;                   
                                         }                   
                                         return                               true                               ;                   
                                         }                   
                                         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);                   
                             
                                         // 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(2))                   
                                         cout <<                               "Searched: 2"                               << endl;                   
                                         else                   
                                         cout <<                               "Not Found: 2"                               << endl;                   
                                         display();                   
                             
                                         return                               0;                   
                     }                   

输出：

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

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

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

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

THE END

技术文章