นับทริปเล็ตใน Doubly Linked List เรียงลำดับที่ผลรวมเท่ากับ x ด้วย C++

ได้รับ Doubly Linked List ที่เรียงลำดับแล้วและมีค่าจำนวนเต็ม เป้าหมายคือหาทริปเล็ต (triplets) ที่ผลรวมเท่ากับค่า x ที่กำหนด ถ้าลิงค์ลิสต์คือ 3-4-13-5-10-10-0 และ x=20 จำนวนจะเป็น 2 (ทริปเล็ต (3,4,13) และ (10,10,0))

ตัวอย่าง

Input

linked list: [ 3-4-13-5-10-10-0 ] x=20

Output

Count of triplets in a sorted doubly linked list whose sum is equal to a given value x are: 2

Explanation

Triplets will be: ( 3,4,13 ) and ( 10,10,0 )

Input

linked list: [ 4-3-1-5-2-4-2 ] x=8

Output

Count of triplets in a sorted doubly linked list whose sum is equal to a given value x are: 6

Explanation

Triplets will be: ( 4,3,1), (1,5,2), (3,1,4), (1,5,2), (4,2,2) and (2,4,2),

วิธีการที่ใช้ในโปรแกรม

วิธีนี้ใช้โครงสร้างโหนด (struct) ที่มีส่วนข้อมูล int data และพอยน์เตอร์ next และ prev อ้างอิงตัวเอง

• ฟังก์ชัน insert_node(struct block** head, int data) เพิ่มโหนดที่หัวลิงค์ลิสต์
• ฟังก์ชัน sum_x(struct block* head, int x) รับพอยน์เตอร์หัวและ x คืนค่าจำนวนทริปเล็ตที่ผลรวมเท่ากับ x
• กำหนดจำนวนนับเริ่มต้นเป็น 0
• สร้างพอยน์เตอร์สามตัว temp_1, temp_2, temp_3 ชนิด struct block
• เริ่มจาก temp_1 ชี้หัว temp_2 ชี้ถัดจาก temp_1 และ temp_3 ชี้ถัดจาก temp_2 ได้สามพอยน์เตอร์ชี้โหนดแรกสามตัว
• วนลูปด้วยพอยน์เตอร์เหล่านี้จนถึงโหนดสุดท้าย
• ถ้าส่วนข้อมูลของพอยน์เตอร์ทั้งสามมีผลรวมเท่ากับ x ((temp_1->data + temp_2->data + temp_3->data) == x) เพิ่ม count
• เมื่อนับครบทริปเล็ตแล้ว เก็บไว้ใน count
• คืนค่า count เป็นผลลัพธ์

ตัวอย่างโค้ด

#include <iostream>
using namespace std;

struct block{
    int data;
    struct block *next, *prev;
};

void insert_node(struct block** head, int data){
    struct block* ptr = new block();
    ptr->data = data;
    ptr->next = NULL;
    ptr->prev = NULL;
    if ((*head) == NULL){
        (*head) = ptr;
    } else {
        ptr->next = *head;
        (*head)->prev = ptr;
        (*head) = ptr;
    }
}

int sum_x(struct block* head, int x){
    int count = 0;
    struct block *temp_1, *temp_2, *temp_3;
    for (temp_1 = head; temp_1 != NULL; temp_1 = temp_1->next){
        for (temp_2 = temp_1->next; temp_2 != NULL; temp_2 = temp_2->next){
            for (temp_3 = temp_2->next; temp_3 != NULL; temp_3 = temp_3->next){
                if ((temp_1->data + temp_2->data + temp_3->data) == x){
                    count++;
                }
            }
        }
    }
    return count;
}

int main(){
    struct block* head = NULL;
    insert_node(&head, 200);
    insert_node(&head, 100);
    insert_node(&head, 16);
    insert_node(&head, 14);
    insert_node(&head, 10);
    insert_node(&head, 10);
    insert_node(&head, 2);
    int x = 22;
    cout << "Count of triplets in a sorted doubly linked list whose sum is equal to a given value x are: " << sum_x(head, x);
    return 0;
}

Output

หากรันโค้ดข้างต้นจะได้ผลลัพธ์ดังนี้:

Count of triplets in a sorted doubly linked list whose sum is equal to a given value x are: 1