数据结构
网络
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 次浏览
广告