チェーンテーブルデータ構造-力ブラシチェーンテーブル問題を知る必要がある(Python)

チェーンテーブルは前後順に並べられたデータ構造で、ここでは単一チェーンテーブルを例に、筆者が初めて力ボタンを塗ったとき、チェーンテーブルがどのように来たのか分からない.ここでは基礎的な知識を補充して紹介し、読者がチェーンテーブルの問題を理解するのを助ける必要がある.
チェーンテーブルノード
単一チェーンテーブルノードの定義式は非常に簡潔で、ここでは2つのインスタンス変数を持つクラスで定義します.

ノードの値(val)は、整数であってもよいし、他のデータ構造であってもよい.

このノードが指す次のノード(next)も、ノードである.

デュアルチェーンテーブルの場合、前のノードを指す前のノード(prev)もあります.

class ListNode:
    """
        
    """
    def __init__(self, x):          #       ，         
        self.val = x                #       
        self.next = None            #      ，     None

チェーンテーブルの作成
チェーンテーブルはノードからなり、チェーンテーブルはノードの結合であるため、チェーンテーブルの作成にはノードの作成とノードの接続の2つのステップが含まれます.

def create_linked_list(nums):
    """
        
    :param nums:             
    :return:             ，             
    """
    if not nums:                        #      
        return
    head = prev = ListNode(nums[0])     #      
    for num in nums[1:]:
        tmp = ListNode(num)             #       
        prev.next = tmp                 #             
        prev = prev.next                #     
    return head

チェーンテーブルコピー
チェーンテーブルのコピーは、チェーンテーブルを作成するときに別のチェーンテーブル制約で作成するプロセスに相当します.チェーンテーブルレプリケーションはチェーンテーブルの浅いコピーに相当し,チェーンテーブルのタイトルではチェーンテーブルが関数に入った後に修正されるなどの状況を避けることができる.

def copy_linked_list(head):
    """
           ，         
    :param head:
    :return:
    """
    new_head, cur = ListNode(0), head       #         ，         
    tmp = new_head                          #     
    while cur:                              #        
        new_cur = ListNode(cur.val)         #                  
        tmp.next = new_cur                  #               
        cur = cur.next                      #       
        tmp = tmp.next                      #        
    return new_head.next                    #      

チェーンテーブル印刷
チェーンテーブルの開始ノードが得られると、チェーンテーブル全体のすべてのノードが得られるすべての値に相当します.

def print_linked_list(head):
    """
        
    :param head:           
    :return:      
    """
    tmp = head              #     
    nums = []
    while tmp:
        nums.append(tmp.val)
        tmp = tmp.next
    print(nums)
    return nums

以上の方法ではチェーンテーブルがリングチェーンテーブルではない場合を判別するしかなく,チェーンテーブルにリング構造があればプログラムはデッドサイクルに陥り,ステップアップバージョンのプログラムを書き換え,リングチェーンテーブルを判別することができる.

def print_linked_list(head):
    """
        
    :param head:           
    :return:      
    """
    cur = head                              #        ，      
    nums = []                               #     
    nodes = []
    circle_flag = False                     #         flag
    circle_nums = []                        #        
    while cur:

        nodes.append(cur)
        if circle_flag:
            circle_nums.append(cur.val)     #          
        else:
            nums.append(cur.val)

        cur = cur.next
        if cur in nodes:
            if nodes.count(cur) == 2:        #         
                break
            else:                           #        ，    flag
                circle_flag = True

    if circle_flag:
        print("         ")
        print("       ：{}".format(nums))
        print("       ：{}".format(circle_nums))
        print("     ：{}".format(nums[len(nums)-len(circle_nums)]))
    else:
        print("       ：{}".format(nums))
    return nums

たとえば、次のコードを実行します.

if __name == '__main__':
   n1 = ListNode(1)
    n2 = ListNode(2)
    n3 = ListNode(3)
    n4 = ListNode(4)
    n1.next = n2
    n2.next = n3
    n3.next = n4
    print_linked_list(n1)

印刷結果が表示されます.

       ：[1, 2, 3, 4]

リングチェーンテーブルを構築する場合は、先ほどのコードに基づいて一言追加します.

if __name == '__main__':
    n1 = ListNode(1)
    n2 = ListNode(2)
    n3 = ListNode(3)
    n4 = ListNode(4)
    n1.next = n2
    n2.next = n3
    n3.next = n4
    n4.next = n2      #      
    print_linked_list(n1)

印刷結果が表示されます.

         
       ：[1, 2, 3, 4]
       ：[2, 3, 4]
     ：2

チェーンメーター判定等
チェーンテーブル判定等は、チェーンテーブルの該当要素の値が等しいか否かを判断すればよい.

def list_equal(head1, head2):
    """
              
    :param head1:
    :param head2:
    :return:
    """
    cur1, cur2 = head1, head2               #        ，       
    tmp = head1                             #         
    while cur1 and cur2:
        if cur1.val != cur2.val:
            return False
        cur1, cur2 = cur1.next, cur2.next
        if cur1 == tmp:
            return True
    return not cur1 and not cur2

チェーンゲージリング
チェーンテーブルにリング構造がある場合は、ループ時にループしたノードに必ず遭遇します.そうしないと、必ず最後のノードにループします.

def is_circle(head):
    """
               
    :param head:           
    :return:    ，    
    """
    if not head:
        return False
    tmp = head

    while head:
        head = head.next
        if not head:        #         
            return False    #         
        if head == tmp:     #             
            return True     #        

質問やアドバイスがあれば、コメントエリアへようこそ~