انتخاب گره تصادفی از لیست پیوندی — به زبان ساده

۱۷۴ بازدید
آخرین به‌روزرسانی: ۱۹ اردیبهشت ۱۴۰۲
زمان مطالعه: ۵ دقیقه
انتخاب گره تصادفی از لیست پیوندی — به زبان ساده

در این مطلب، روش انتخاب گره تصادفی از لیست پیوندی بیان شده است. یک لیست پیوندی داده شده و هدف انتخاب یک «گره» (Node) تصادفی از «لیست پیوندی» (Linked List) (احتمال انتخاب یک گره باید 1/N1/N باشد) است. یک «مولد اعداد تصادفی» (Random Number Generator) نیز داده شده است. راهکار ساده زیر برای حل این مساله قابل استفاده است.

997696
  1. تعداد گره‌ها را با پیمایش لیست بشمار.
  2. مجددا لیست را پیمایش و گره‌ای با احتمال 1/N1/N را انتخاب کن. انتخاب را می‌توان با تولید یک عدد تصادفی از صفر تا N-i برای iاُمین گره انجام داد. همچنین، iاُمین گره تنها در صورتی انتخاب شود که عدد تولید شده برابر با صفر باشد (یا هر ثابت دیگری از صفر تا N-i).

با طرح‌های بالا، احتمال‌های یکنواخت حاصل می‌شود.

i = 1, probability of selecting first node = 1/N
i = 2, probability of selecting second node =
[probability that first node is not selected] * 
[probability that second node is selected]
= ((N-1)/N)* 1/(N-1)
= 1/N

به طور مشابه، احتمال انتخاب دیگر گره‌ها 1/N1/N است. راهکار بالا نیازمند دو پیمایش لیست پیوندی است.

روش انتخاب یک گره تصادفی با تنها یک پیمایش

می‌توان از نمونه‌برداری «Reservoir» استفاده کرد. در ادامه، گام‌های لازم برای انتخاب تصادفی یک گره از لیست پیوندی با تنها یک پیمایش، بیان شده‌اند. این نسخه ساده‌تری از نمونه‌برداری Reservoir است؛ زیرا تنها نیاز به انتخاب یک کلید به جای k کلید دارد.

  1. نتیجه را با اولین گره مقداردهی اولیه کن (result = head->key)
  2. مقداردهی اولیه n = 2 را انجام بده.
  3. اکنون، یکی یکی همه گره‌ها از دومین گره به بعد را در نظر بگیر.
    1. یک عدد تصادفی از صفر تا n-1 تولید کن. عدد تصادفی تولید شده را در j قرار بده.
    2. اگر j برابر با صفر است (می‌توان دیگر اعداد ثابت بین ۰ تا N-1 را انتخاب کرد)، نتیجه را با گره کنونی جایگزین کن.
    3. n = n+1
    4. current = current->next

در ادامه، پیاده‌سازی روش بالا در زبان‌های برنامه‌نویسی گوناگون شامل «سی‌پلاس‌پلاس» (++C)، «زبان سی» (C)، «جاوا» (Java) و «سی‌شارپ» (#C) انجام شده است.

انتخاب گره تصادفی از لیست پیوندی در ++C

1// C++ program to del the node  
2// in which only a single pointer 
3// is known pointing to that node 
4#include <bits/stdc++.h> 
5#include<assert.h> 
6using namespace std; 
7  
8/* Link list node */
9class Node  
10{  
11    public: 
12    int data;  
13    Node* next;  
14};  
15  
16/* Given a reference (pointer to pointer) to the head  
17of a list and an int, push a new node on the front  
18of the list. */
19void push(Node** head_ref, int new_data)  
20{  
21    /* allocate node */
22    Node* new_node = new Node(); 
23      
24    /* put in the data */
25    new_node->data = new_data;  
26      
27    /* link the old list off the new node */
28    new_node->next = (*head_ref);  
29      
30    /* move the head to point to the new node */
31    (*head_ref) = new_node;  
32}  
33  
34void printList(Node *head)  
35{  
36    Node *temp = head;  
37    while(temp != NULL)  
38    {  
39        cout << temp->data << " ";  
40        temp = temp->next;  
41    }  
42}  
43  
44void deleteNode(Node *node_ptr)  
45{  
46    Node *temp = node_ptr->next;  
47    node_ptr->data = temp->data;  
48    node_ptr->next = temp->next;  
49    free(temp);  
50}  
51  
52/* Driver code*/
53int main()  
54{  
55    /* Start with the empty list */
56    Node* head = NULL;  
57  
58    /* Use push() to construct below list  
59    1->12->1->4->1 */
60    push(&head, 1);  
61    push(&head, 4);  
62    push(&head, 1);  
63    push(&head, 12);  
64    push(&head, 1);  
65  
66    cout << "Before deleting \n";  
67    printList(head);  
68  
69    /* I m deleting the head itself.  
70        You can check for more cases */
71    deleteNode(head);  
72      
73    cout << "\nAfter deleting \n";  
74    printList(head);  
75    return 0; 
76}  
77  
78// This code is contributed by rathbhupendra

انتخاب گره تصادفی از لیست پیوندی در C

1#include<stdio.h> 
2#include<assert.h> 
3#include<stdlib.h> 
4  
5/* Link list node */
6struct Node 
7{ 
8    int data; 
9    struct Node* next; 
10}; 
11  
12/* Given a reference (pointer to pointer) to the head 
13of a list and an int, push a new node on the front 
14of the list. */
15void push(struct Node** head_ref, int new_data) 
16{ 
17    /* allocate node */
18   struct Node* new_node = 
19             (struct Node*) malloc(sizeof(struct Node)); 
20  
21   /* put in the data  */
22   new_node->data  = new_data; 
23  
24   /* link the old list off the new node */
25   new_node->next = (*head_ref); 
26  
27   /* move the head to point to the new node */
28   (*head_ref)    = new_node; 
29} 
30  
31void printList(struct Node *head) 
32{ 
33   struct Node *temp = head; 
34   while(temp != NULL) 
35   { 
36      printf("%d  ", temp->data); 
37      temp = temp->next; 
38   } 
39} 
40  
41void deleteNode(struct Node *node_ptr) 
42{ 
43   struct Node *temp = node_ptr->next; 
44   node_ptr->data    = temp->data; 
45   node_ptr->next    = temp->next; 
46   free(temp); 
47} 
48  
49/* Drier program to test above function*/
50int main() 
51{ 
52    /* Start with the empty list */
53    struct Node* head = NULL; 
54  
55    /* Use push() to construct below list 
56    1->12->1->4->1  */
57    push(&head, 1); 
58    push(&head, 4); 
59    push(&head, 1); 
60    push(&head, 12); 
61    push(&head, 1); 
62  
63    printf("\n Before deleting \n"); 
64    printList(head); 
65  
66    /* I m deleting the head itself. 
67        You can check for more cases */
68   deleteNode(head); 
69  
70   printf("\n After deleting \n"); 
71   printList(head); 
72   getchar(); 
73}

انتخاب گره تصادفی از لیست پیوندی در جاوا

1// Java program to del the node in which only a single pointer 
2// is known pointing to that node 
3  
4class LinkedList { 
5  
6    static Node head; 
7  
8    static class Node { 
9  
10        int data; 
11        Node next; 
12  
13        Node(int d) { 
14            data = d; 
15            next = null; 
16        } 
17    } 
18  
19    void printList(Node node) { 
20        while (node != null) { 
21            System.out.print(node.data + " "); 
22            node = node.next; 
23        } 
24    } 
25  
26    void deleteNode(Node node) { 
27        Node temp = node.next; 
28        node.data = temp.data; 
29        node.next = temp.next; 
30        System.gc(); 
31  
32    } 
33  
34    // Driver program to test above functions 
35    public static void main(String[] args) { 
36        LinkedList list = new LinkedList(); 
37        list.head = new Node(1); 
38        list.head.next = new Node(12); 
39        list.head.next.next = new Node(1); 
40        list.head.next.next.next = new Node(4); 
41        list.head.next.next.next.next = new Node(1); 
42  
43        System.out.println("Before Deleting "); 
44        list.printList(head); 
45  
46        /* I m deleting the head itself. 
47         You can check for more cases */
48        list.deleteNode(head); 
49        System.out.println(""); 
50        System.out.println("After deleting "); 
51        list.printList(head); 
52    } 
53} 
54  
55// This code has been contributed by Mayank Jaiswal 

انتخاب گره تصادفی از لیست پیوندی در #C

1// C# program to del the node in 
2// which only a single pointer is 
3// known pointing to that node  
4using System; 
5  
6public class LinkedList 
7{  
8  
9    Node head;  
10  
11    public class Node 
12    {  
13  
14        public int data;  
15        public Node next;  
16  
17        public Node(int d)  
18        {  
19            data = d;  
20            next = null;  
21        }  
22    }  
23  
24    void printList(Node node) 
25    {  
26        while (node != null)  
27        {  
28            Console.Write(node.data + " ");  
29            node = node.next;  
30        }  
31    }  
32  
33    void deleteNode(Node node)  
34    {  
35        Node temp = node.next;  
36        node.data = temp.data;  
37        node.next = temp.next;  
38    }  
39  
40    // Driver code 
41    public static void Main()  
42    {  
43        LinkedList list = new LinkedList();  
44        list.head = new Node(1);  
45        list.head.next = new Node(12);  
46        list.head.next.next = new Node(1);  
47        list.head.next.next.next = new Node(4);  
48        list.head.next.next.next.next = new Node(1);  
49  
50        Console.WriteLine("Before Deleting ");  
51        list.printList(list.head);  
52  
53        /* I m deleting the head itself.  
54        You can check for more cases */
55        list.deleteNode(list.head);  
56        Console.WriteLine("");  
57        Console.WriteLine("After deleting ");  
58        list.printList(list.head);  
59    }  
60}  
61  
62/* This code contributed by PrinciRaj1992 */

خروجی قطعه کد بالا به صورت زیر است.

Before Deleting 
1 12 1 4 1 
After deleting 
12 1 4 1

این راهکار در صورتی که گره حذف شده آخرین گره در لیست باشد، کار نمی‌کند. برای اینکه راه حل کار کند، می‌توان گره پایانی را به عنوان گره مجازی علامت‌گذاری کرد. در این صورت، برنامه‌ها/تابع‌هایی که از این تابع استفاده می‌کنند نیز باید ویرایش شوند.

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

^^

بر اساس رای ۰ نفر
آیا این مطلب برای شما مفید بود؟
اگر بازخوردی درباره این مطلب دارید یا پرسشی دارید که بدون پاسخ مانده است، آن را از طریق بخش نظرات مطرح کنید.
منابع:
GeeksforGeeks
نظر شما چیست؟

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *