這個想法是找到第二個鏈表中與第一個鏈表相同的段，并將直接跟隨的節點添加到將回傳的串列中。所以，如果我的第一個鏈表是
h -> e -> y -> None
并且我的第二個是
h -> e -> y -> d -> u -> d -> e -> None
我的輸出應該是[d].
我已驗證鏈接串列已正確創建，但只會將其內容添加為注釋以保持簡單：
def find_sublist(list_start_node, corpus_start_node, output=[]):
if corpus_start_node is None:
return output
elif list_start_node is None:
output.append(corpus_start_node.item)
return find_sublist(myList.head, corpus_start_node)
elif list_start_node.item is corpus_start_node.item:
return find_sublist(list_start_node.next_node, corpus_start_node.next_node)
else:
return find_sublist(myList.head, corpus_start_node.next_node)
# myList: 3 -> 7 -> None
# myCorpus: 3 -> 7 -> 8 -> 2 -> 34 -> 77 -> 21 -> 3 -> 7 -> 9 -> 2 -> 34 -> 88 -> 9 -> None
print(find_sublist(myList.head, myCorpus.head))
底部列印功能列印輸出串列[8]，當我應該得到[8, 9]。有什么明顯的我忽略了嗎？
uj5u.com熱心網友回復：
您的主要問題是，當您在語料庫中找到與目標串列匹配的第一個值時，您需要進行兩次檢查。首先，您需要檢查目標串列的其余部分是否匹配。其次，您需要檢查整個主串列的其余語料庫。不幸的是，您并不想對兩者都使用相同的遞回函式，否則您將匹配目標串列的末尾出現的任何位置（無論它們是否遵循前面的部分）。也許您可以添加一個標志來阻止它，但是使用單獨的函式在概念上會更簡單。
def matcher(needle, haystack):
if haystack is None: # failure case #1, we've run out of haystack
return None
if needle is None: # success case, return the next haystack item
return haystack.item
if needle.item != haystack.item: # falure case #2, a mismatch
return None
return matcher(needle.next_node, haystack.next_node) # recurse
def searcher(needle, haystack, results=None):
if results is None: # avoid using a mutable default argument
results = []
if haystack is None: # base case, we've searched the whole haystack
return results
match = matcher(needle, haystack) # test current position in haystack
if match is not None:
results.append(match)
return searcher(needle, haystack.next_node, results) # recurse
請注意，由于這兩個函式都是尾遞回的，因此您可以輕松地將它們轉換為回圈，如果需要，可以將回圈嵌套在一個函式中：
def iterative_search_and_match(needle, haystack):
results = []
while needle and haystack: # search loop
match_needle = needle
match_haystack = haystack
while match_needle and match_haystack: # match loop
if match_needle.item != match_haystack.item:
break
match_needle = match_needle.next_node
match_haystack = match_haystack.next_node
else: # this doesn't run if the break was hit!
if match_haystack:
results.append(match_haystack.item)
needle = needle.next_node
haystack = haystack.next_node
return results
uj5u.com熱心網友回復：
我翻譯了你的功能，它似乎按預期作業。您的鏈表設定可能有問題嗎？
# Setup
start_corpus = None
for x in reversed([3, 7, 8, 2, 34, 77, 21,
3, 7, 9, 2, 34, 88, 9]):
start_corpus = (x, start_corpus)
start_word = (3, (7, None))
##################
def find_sublist(word, corpus):
if corpus is None:
return
elif word is None:
yield corpus[0]
yield from find_sublist(start_word, corpus)
elif word[0] == corpus[0]:
yield from find_sublist(word[1], corpus[1])
else:
yield from find_sublist(start_word, corpus[1])
print(list(find_sublist(start_word, start_corpus)))
# [8, 9]
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/411666.html
標籤：