資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++中計算排序雙向連結串列中和等於給定值x的三元組個數
給定一個包含整數值的排序雙向連結串列。目標是找到乘積等於給定值x的三元組。如果輸入連結串列是3-4-1-2，而x是6，則計數將為1（三元組(3,1,2)）
例如
輸入
linked list: [ 3−4−13−5−10−10−0 ] x=20
輸出
Count of triplets in a sorted doubly linked list whose product is equal to a given value x are: 2
解釋
Triplets will be: ( 3,4,13 ) and ( 10,10,0 )
輸入
linked list: [ 4−3−1−5−2−4−2 ] x=8
輸出
Count of triplets in a sorted doubly linked list whose product is equal to a given value x are: 6
解釋
Triplets will be: ( 4,3,1), (1,5,2), (3,1,4), (1,5,2), (4,2,2) and (2,4,2),
以下程式中使用的方案如下 −
在這個方案中。
我們將連結串列節點作為一個結構體，包含int資料部分以及自引用的next和previous指標。
函式insert_node(struct block** head, int data) 在連結串列頭部新增一個包含資料的節點。
函式Product_x(struct block* head, int x) 獲取雙向連結串列頭的指標和整數x，並返回資料部分乘積為x的節點三元組的個數。
將初始計數設為0。
取三個struct block型別的指標temp_1、temp_2和temp_3。
從temp_1指向連結串列頭開始，temp_2指向temp_1的下一個節點，temp_3指向temp_2的下一個節點，我們有三個指標指向前三個節點。
使用這些指標遍歷到最後一個節點。
如果上述所有指標的當前資料部分的乘積為x。((temp_1−>data * temp_2−>data * temp_3−>data) == x) 則遞增計數。
最後，我們計算了三元組的數量並將其儲存在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;
}輸出
如果我們執行上述程式碼，它將生成以下輸出：
Count of triplets in a sorted doubly linked list whose sum is equal to a given value x are: 1
更新於：2021年1月5日
208 次瀏覽
廣告