给定一个2D数组，只使用递归创建一个2D双链表。列表中的每个数字都必须有4个指针(上、下、右、左(，并且需要链接到旁边的每个数字(如果没有数字，则只有"无"(
import numpy as np
class Node:
""" Node class
up
|
left - data - right
|
down
"""
def __init__(self, data):
self.data = data
self.right = None
self.left = None
self.up = None
self.down = None
def constructDoublyLinkedListRecursion(arr):
""" Converts a 2D array into a 2D doubly linked list by calling
the recursee constructDLLRecursiveStep.
input:
arr: 2D array to turn into a 2D DLL
output:
head (top left node) of the 2D DLL of the input arr.
"""
return constructDLLRecursiveStep(arr, 0, 0, None)
def constructDLLRecursiveStep(arr, y, x, curr):
""" Recursively construct the 2D DLL from the given array.
This is the "recursee" of constructDoublyLinkedListRecursion.
input:
arr: The 2D array to construct the 2D DLL from.
y: y-coordinate of the array to get the value from.
x: x-coordinate of the array to get the value from.
curr: The current node to connect the new node from.
output:
new_node: The newly created node which connects to curr node.
"""
return new_node
这就是我目前所做的：
def constructDLLRecursiveStep(arr, y, x, curr):
arrDim = arr.shape[1]
if(y >= arrDim or x >= arrDim):
return None;
new_node = Node(arr[y,x])
if(x > 0):
new_node.left = curr
else:
new_node.left = None
if(y > 0):
new_node.up = curr
else:
new_node.up = None
new_node.right = constructDLLRecursiveStep(arr, y, x+1, new_node)
new_node.down = constructDLLRecursiveStep(arr, y+1, x, new_node)
return new_node
显示功能
def display(dll_ptr):
""" Prints the 2D dll according to their positions similar to
printing a 2D array.
input:
dll_ptr: the head (most upper left node) of a 2D dll.
output:
None
"""
right_ptr = None
down_ptr = dll_ptr
while down_ptr != None:
right_ptr = down_ptr
while right_ptr != None:
msg = f"{right_ptr.data} | "
for i, direction in enumerate([("up", right_ptr.up), ("right", right_ptr.right), ("down", right_ptr.down), ("left", right_ptr.left)]):
direction_str, direction_ptr = direction
if direction_ptr: msg += f"{direction_str}: {direction_ptr.data}"
else: msg += f"{direction_str}: None"
msg += ", "
print(msg)
right_ptr = right_ptr.right
print()
down_ptr = down_ptr.down
我得到的输出表明向上指针有问题：
"""
Input 2D array:
[[9 4 0 8 6]
[4 3 2 2 7]
[9 7 3 9 2]
[8 7 3 6 2]
[9 4 6 5 3]]
<class 'numpy.ndarray'>
constructDoublyLinkedListRecursion output:
9 4 0 8 6
4 3 2 2 7
9 7 3 9 2
8 7 3 6 2
9 4 6 5 3
constructDoublyLinkedListRecursion output:
9 | up: None, right: 4, down: 4, left: None,
4 | up: None, right: 0, down: 3, left: 9,
0 | up: None, right: 8, down: 2, left: 4,
8 | up: None, right: 6, down: 2, left: 0,
6 | up: None, right: None, down: 7, left: 8,
4 | up: 9, right: 3, down: 9, left: None,
3 | up: 4, right: 2, down: 7, left: 4,
2 | up: 3, right: 2, down: 3, left: 3,
2 | up: 2, right: 7, down: 9, left: 2,
7 | up: 2, right: None, down: 2, left: 2,
9 | up: 4, right: 7, down: 8, left: None,
7 | up: 9, right: 3, down: 7, left: 9,
3 | up: 7, right: 9, down: 3, left: 7,
9 | up: 3, right: 2, down: 6, left: 3,
2 | up: 9, right: None, down: 2, left: 9,
8 | up: 9, right: 7, down: 9, left: None,
7 | up: 8, right: 3, down: 4, left: 8,
3 | up: 7, right: 6, down: 6, left: 7,
6 | up: 3, right: 2, down: 5, left: 3,
2 | up: 6, right: None, down: 3, left: 6,
9 | up: 8, right: 4, down: None, left: None,
4 | up: 9, right: 6, down: None, left: 9,
6 | up: 4, right: 5, down: None, left: 4,
5 | up: 6, right: 3, down: None, left: 6,
3 | up: 5, right: None, down: None, left: 5,
"""
主要问题是您几乎无条件地在两个方向上重复出现。这意味着索引1，1处的节点将通过两个不同的递归路径创建：一次是先用x+1递归，然后用y+1递归，第二次是当调用y+1时，用x+1进行递归调用。递归调用的总数远远超过了您真正需要创建的节点数量，因为通过矩阵的所有可能的(Z字形(路径都在生成中。
一种解决方案是，当x为零时，只使用y+1进行递归调用。这将启动创建整行的过程(使用x+1递归(。唯一需要注意的是"；nit"；这些节点到它们正上方的对应节点。但这可以通过从左侧节点向上走，然后取其右侧的节点来实现。
这是更正后的代码：
def constructDLLRecursiveStep(arr, y, x, curr):
leny, lenx = arr.shape
if y >= leny or x >= lenx:
return None
new_node = Node(arr[y,x])
if x == 0: # Came from above
new_node.up = curr
else: # Came from the left
new_node.left = curr
if y > 0: # Link to row above, by walking "the block"
curr.up.right.down = new_node
new_node.up = curr.up.right
new_node.right = constructDLLRecursiveStep(arr, y, x + 1, new_node)
if x == 0: # Recur downwards
new_node.down = constructDLLRecursiveStep(arr, y + 1, 0, new_node)
return new_node