迭代链表时的无限循环 Python 3

Question

我正在尝试编写一个从链接列表中删除所有pdf文件的函数，但是运行此函数后，我很快意识到它变成了无限循环。我的第一个 while 循环应该捕获链接列表开头的所有 pdf 文件。我的第二个 while 循环应该迭代链接列表多次，以删除 pdf 文件。我想我的 while not 循环逻辑是不正确的。

def remove_all(lst):
    ptr = lst
    while ptr['data'][0] == 'pdf':
        ptr = ptr['next']
        lst = ptr
    all_removed = True
    while not all_removed:
        all_removed = False
        while ptr['next'] != None:
            if ptr['next']['data'][0] == 'pdf':
                ptr['next'] = ptr['next']['next']
                all_removed = True
            ptr = ptr['next']
    return lst

我收到错误，第二个 while 循环没有类型不可下标，这让我很困惑，因为当 ptr['next'] 为 None 时它应该停止。

我的链接列表如下所示：

{'data': ['pdf', 2, 4], 'next': {'data': ['csv', 1, 1], 'next': {'data': ['pdf', 234, 53], 'next': 
{'data': ['xml', 1, 2], 'next': {'data': ['pdf', 0, 1], 'next': None}}}}}

Answer 1

首先，尝试：

ptr['next'] = ptr['next']['next']

而不是：

ptr['next'] == ptr['next']['next']

其次，由于我们的结构中有一个

'next': 
{'data': ['xml', 1, 2]

（带有

xml

和

csv

- 而不是

pdf

），因此执行会进入嵌套的 while 循环：

while ptr['next'] != None:

并且由于 if 条件

if ptr['next']['data'][0] == 'pdf':

的计算结果为

False

它会无限地陷入循环中。

Answer 2

鉴于我不完全理解 while not、while true 循环，我求助于递归来回答我的问题。

def remove(lst):
    ptr=lst
    while ptr['data'][0]=='pdf':
        ptr=ptr['next']
        lst=ptr
    while ptr['next']!=None:
        if ptr['next']['data'][0]=='pdf':
            ptr['next']=ptr['next']['next']
            return remove(lst)
        ptr=ptr['next']
    return lst

如果列表开头有任何 pdf，它们将被删除，然后如果稍后遇到任何 pdf，它们将被删除，并且函数返回自身，以防存在相邻的 pdf。

Answer 3

6 年后，但你让我感兴趣。 在这里，我提出了一个简化复杂性的解决方案和一个用于测试目的的链表生成器。但我不讨论无限循环，因为我专注于 DrJessop 的第一个 while 循环：

在我看来，第一个 while 循环仅在开始时“擦除”连续的 pdf。但我认为它有更大的潜力，因为情况很清楚：

跟进你发现一些变化：

1. 向 while 循环引入一个新条件，让其运行到最后一个节点，即

   lst['next'] != None

   。请注意，如果最后一个节点链接到

   None

   类型并且循环错过了最后一个节点，则循环才会停止。
2. 条件

   ['data'][0] == 'pdf'

   被移入 while 循环作为 if 条件。这允许忽略所有 pdf，而不仅仅是开头的 pdf。
3. 初始化了一个最终链表

   final_ll

   和一个临时链表

   temp_ll

   作为字典，以存储迭代过程中的相关文档。这些用于其他情况：
4. 最后我添加最后一个节点。

def remove_all(lst):
    # initiating final ll and temporary LL for single nodes to be stored
    final_ll = {}
    temp_ll = final_ll # a link for temp_ll to store final results in final_ll
    
    while lst['next'] != None: # running through all but the last node
        
        if lst['data'][0] == 'pdf':  # ignoring all pdfs
            lst = lst['next']        # jump to next node
         
        else:                           # including desired nodes   
            temp_ll['data'] = lst['data'] # add node data
            temp_ll['next'] = {}          # add node link    
            temp_ll = temp_ll['next']     # update temp_ll
            lst = lst['next']             # jump to next node
    
    # catching the last node
    temp_ll['data'] = lst['data']
    temp_ll['next'] = None
    return final_ll

出于测试目的，这里是包含文档且采用您显示的格式的链接列表的随机生成器：

from random import randint as r_
documents = ['pdf', 'xml', 'csv', 'json', 'html']

def prod_doc_ll_list(size = 3):
    ll_docs = {}
    ll_doc = ll_docs
    for i in range(size):
        ll_doc['data'] = [documents[r_(0,4)], r_(0,250), r_(0,250)]
        if i < size-1:
            ll_doc['next'] = {}
            ll_doc = ll_doc['next']
        else:
            ll_doc['next'] = None
    return ll_docs
        
docs = prod_doc_ll_list(8)
docs