資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究在 C++ 中查詢排序雙向連結串列中具有給定乘積的數對
概念
對於給定的正的不同元素的排序雙向連結串列，我們的任務是在雙向連結串列中確定乘積等於給定值 x 的數對，並且不佔用任何額外的空間。
輸入
List = 1 <=> 2 <=> 4 <=> 5 <=> 6 <=> 8 <=> 9 x = 8
輸出
(1, 8), (2, 4)
輸入
List1 = 1 <=> 2 <=> 3 <=> 4 <=> 5 <=> 6 <=> 7 x = 6
輸出
(1, 4), (2,3)
方法
根據此問題的**簡單方法**，我們遍歷連結串列並實現兩個巢狀迴圈，確定所有數對並驗證乘積等於 x 的數對。在這裡，此問題的複雜度為 O(n^2)，其中 n 是雙向連結串列中節點的總數。
討論了此問題的**有效解決方案**。以下是演算法的步驟：
我們初始化兩個指標變數以確定排序雙向連結串列中的候選元素。
我們將 first1 初始化為雙向連結串列的開頭，即 first1=head，並將 second1 初始化為雙向連結串列的最後一個節點，即 second1=last_node。
現在我們將 first 和 second 指標初始化為第一個和最後一個節點。在這種情況下，我們沒有隨機訪問，因此要確定 second 指標，我們訪問列表以初始化 second1。
可以看出，如果 first1 和 second1 的當前和小於 x，則我們將 first1 向前移動。否則，如果 first1 和 second1 的當前和大於 x，則我們將 second1 向後移動。
最後，迴圈終止條件也與陣列不同。在這種情況下，當兩個指標中的任何一個變為 NULL，或者它們彼此交叉 (second1->next = first1)，或者它們變為相同 (first1 == second1) 時，迴圈結束。
示例
// C++ program to find a pair with
// given product x in sorted Doubly
// Linked List
#include <bits/stdc++.h>
using namespace std;
//Shows Doubly Linked List Node
struct Node1 {
int data1;
struct Node1 *next1, *prev1;
};
// Shows function to determine pair whose product
// equal to given value x
void pairProduct(struct Node1* head1, int x1){
// Now set two pointers,
// first to the beginning of DLL and second to the end of DLL.
struct Node1* first1 = head1;
struct Node1* second1 = head1;
while (second1->next1 != NULL)
second1 = second1->next1;
// Used to track if we find a pair or not
bool found1 = false;
// Now the loop terminates when either of two pointers
// become NULL, or they cross each other (second1->next1
// == first1), or they become same (first1 == second1)
while (first1 != NULL && second1 != NULL && first1 != second1 && second1->next1 != first1) {
// pair found
if ((first1->data1 * second1->data1) == x1) {
found1 = true;
cout << "(" << first1->data1 << ", " << second1->data1 << ")" << endl;
// Used to move first in forward direction
first1 = first1->next1;
// Used to move second in backward direction
second1 = second1->prev1;
} else {
if ((first1->data1 * second1->data1) < x1)
first1 = first1->next1;
else
second1 = second1->prev1;
}
}
// Now if pair is not present
if (found1 == false)
cout << "No pair found";
}
// Shows a utility function to insert a new node at the
// beginning of doubly linked list
void insert(struct Node1** head1, int data1){
struct Node1* temp1 = new Node1;
temp1->data1 = data1;
temp1->next1 = temp1->prev1 = NULL;
if (!(*head1))
(*head1) = temp1;
else {
temp1->next1 = *head1;
(*head1)->prev1 = temp1;
(*head1) = temp1;
}
}
// Driver Code
int main(){
// Create Doubly Linked List struct Node1* head1 = NULL;
/*insert(&head1, 9);
insert(&head1, 8);
insert(&head1, 6);
insert(&head1, 5);
insert(&head1, 4);
insert(&head1, 2);
insert(&head1, 1);
int x1 = 8; */
insert(&head1, 7);
insert(&head1, 6);
insert(&head1, 5);
insert(&head1, 4);
insert(&head1, 3);
insert(&head1, 2);
insert(&head1, 1);
int x1 = 6;
pairProduct(head1, x1);
return 0;
}輸出
(1, 6) (2, 3)
更新於: 2020年7月25日
201 次瀏覽
廣告