체인 테이블이란 무엇입니까, 어떻게 Python에서 체인 테이블을 만듭니까?

| View Solution on GitHub |

(사진: iStock)
우선, 나는 내 문장을 단축해서 소화하기 쉽도록 하겠다고 발표했다.그들이 배불리 마시지 않고 추수감사절 식사에서 담백한 커피를 마실 수 있기를 바란다.
이번 주에 우리는 체인 시계를 토론할 것이다.그렇게 지도 모른다, 아마, 아마...아마도 당신은 데이터 구조에 관한 수업에서 그것들을 본 후에 "이것은 너무 까다롭게 들리는데, 왜 우리는 직접 수조를 사용하지 않습니까?"라고 생각했을 것이다.응, 체인 시계는 수조나 목록보다 장점이 있어.처음에는 복잡해 보일 수도 있지만, 걱정하지 마세요. 제가 당신의 손을 잡고 당신을 데리고 갈게요.
지금 당신은 우리가 손을 잡고 있는 화면을 보았습니다. 당신은 체인 테이블의 구조에 대해 잘 알고 있습니다. 링크로 연결된 하나의 노드, 즉 다른 노드에 대한 인용입니다.두 가지가 있는데, 단일 체인 테이블과 이중 체인 테이블:

(사진: Medium.com)
단일 체인 테이블에서는 각 노드에 앞쪽 화살표가 있고 이중 체인 테이블에는 뒤쪽 화살표가 있습니다.그러나 일반적으로 당신이 겪는 대부분의 문제는 단일 체인표로 가정됩니다.왜?목록을 뒤로 훑어볼 수 있는 특권은 없지만, 한 방향을 가리키는 화살표는 당신의 뇌를 추적하기에 충분하다고 말해 준다.
파이썬에서 체인 시계를 구현해 봅시다.class Linked_list부터 시작해서 노드 그룹을 만드는 것을 고려할 수 있지만, 그것보다 간단하다.상상해 보자. 우리는 클립 체인을 만들고 있다. 우리는 클립 한 묶음을 얻어 그것들을 한데 묶고 있다.

(사진: iStock)
이 사슬은 하나의 클립에 네가 그것들을 한데 묶었다는 사실로 이루어져 있다.우리는 Linked_list 클래스를 만드는 것이 아니라 Node 클래스를 간단하게 만들고 각 노드를 연결할 수 있도록 할 것이다.

class Node:

다음은 평소와 같이 Python에서 클래스를 만들 때 __init__ 방법을 만듭니다.이것은 새 Node 대상을 만들 때 클래스의 모든 필드 (즉 변수) 를 초기화하는 방법입니다.우리는 data라는 변수를 도입할 것이다. 이것은 우리가 노드에 저장해야 할 값이다.우리는 전통적으로 next 라고 불리는 전방향 체인도 정의해야 한다.우선, 노드는 아무것도 연결되지 않았기 때문에 우리는 그것을 None 로 설정했다.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

이것이 바로 우리가 필요로 하는 것이다.우리는 그것을 보존할 수 있지만, 해독 인코딩 접근은 appendToTail() 이라는 방법을 실현했다. 이 방법은 새로운 노드를 생성하고 목록의 끝에 추가해서 목록을 훑어보기 때문에 수동으로 실행할 필요가 없다.한번 봅시다.
먼저 Node 클래스에서 정의합니다.이것은 우리가 새 노드에 주고 싶은 값을 받아들일 것입니다. 파이썬에 대해서는 self 키워드입니다.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

    def append(self, val):
        pass

우리가 해야 할 첫 번째 일은 주어진 값으로 새 노드를 만드는 것이다.우리는 end라고 부른다.

  def append(self, val):
    end = Node(val)

이어서 우리는 지침을 하나 만들었다.이것은 약간 기술적으로 들릴 수 있지만, 본질적으로 말하자면, 우리가 언급한 것은 우리 명단의 첫 번째 인물이다.이것은 우리가 목록을 두루 훑어보고 싶어서 목록의 어떤 내용도 다시 분배하지 않기 때문이다.따라서 우리는 첫 번째 노드self를 인용하여 변수n와 함께 저장합니다.

  def append(self, val):
    end = Node(val)
    n = self

마지막으로, 우리는 목록을 두루 훑어보았다.우리 어떻게 해야 돼요?만약 다음 노드가 있다면, 우리는 단지 다음 노드로 이동하고 싶을 뿐이다. 만약 없다면, 우리는 우리가 이미 종점에 도착했다는 것을 안다.우리는 간단한 while 순환을 사용하여 꼴찌의 두 번째 노드까지 두루 돌아다닐 것이다.

  def append(self, val):
    end = Node(val)
    n = self
    while (n.next):
      n = n.next

마지막으로, 우리는 마지막 노드를 가리키는데, 그것은 다음 노드가 없다.우리는 단지 end 를 찾으면 된다. 이것은 우리의 새로운 노드이며, n.next 를 end 로 설정한다.

  def append(self, val):
    end = Node(val)
    n = self
    while (n.next):
      n = n.next
    n.next = end

그렇습니다!이것은 우리 반 전체이다.
list_노드회사 명

class Node:
  def __init__(self, data):
    self.next = None
    self.data = data

  def append(self, val):
    end = Node(val)
    n = self
    while (n.next):
      n = n.next
    n.next = end

링크 목록 테스트

한번 해볼게요.먼저 새로운 Node 대상을 만들기;나는 그것을 ll라고 명명하고 값을 1로 설정했다.

ll = Node(1)

현재, 우리는 sweet append() 방법을 추가했기 때문에, 목록에 새 노드를 추가할 수 있습니다.

ll.append(2)
ll.append(3)

우리는 우리의 목록을 어떻게 생각합니까?이론적으로 그것은 반드시 이렇다.

[1] --> [2] --> [3]

하지만 직접 출력할 수는 없습니다.우리는 목록을 두루 훑어보고 모든 값을 인쇄해야 한다.하지만 리스트를 훑어보는 방법을 기억하고 있죠?우리는 단지 하나를 했을 뿐이다.개요:

머리를 가리키는 변수 만들기

다음 노드가 있을 때 이 노드로 이동합니다.

그리고 우리는 각 노드에서 인쇄할 것이다 data.단계 #1부터 새 변수를 만들고 목록의 시작에 할당합니다.

node = ll

다음은 첫 번째 노드를 인쇄합니다.우리는 왜 while 순환을 시작하지 않습니까?while 순환은 두 개의 노드만 있기 때문에 next - 마지막 노드가 없습니다.컴퓨터 과학에서 우리는'울타리 문제'라고 부른다. 여기서 너는 X번을 하고 다시 한 번 해야 한다.너는 울타리를 상상할 수 있다. 거기에 기둥이 하나 있고, 그 다음에 울타리가 하나 있고, 그 다음에 기둥이 하나 있고, 또 울타리가 하나 있다.

(사진: 톱니목 제품)
하지만 마지막 울타리를 걸면 안 돼.너는 마지막으로 게시물이 하나 필요하다.따라서 말단에 다른 기둥을 추가하거나 CS에서 더 흔히 볼 수 있는 것처럼 첫 번째 기둥을 만들고 울타리의 나머지 부분을 구축할 수 있습니다.이것이 바로 우리가 해야 할 일이다.
우선, 우리는 첫 번째 노드를 인쇄한 다음, while 순환을 실행하여 아래의 모든 노드를 인쇄합니다.

node = ll
print(node.data)
while node.next:
    node = node.next
    print(node.data)

이전 목록에서 이 옵션을 실행하려면 다음과 같이 해야 합니다.

1
2
3

콘솔에 인쇄합니다.우리 갑니다!우리의 체인 시계는 유효하다.
이번 주는 여기까지!다음 주에 우리는 체인 시계 문제를 연구할 것입니다. 체인 시계를 어떻게 조작하는지에 대한 지식을 더 많이 배울 것입니다. 왜냐하면 그의 작업 원리는 일반적인Python 목록과 약간 다르기 때문입니다.여느 때와 마찬가지로 질문이 있거나 더 보고 싶으면 메시지를 남겨주세요!
| View Solution on GitHub |
Sheamus Heikkila는 예전에 시애틀 대회의 조교였다.이 블로그는 GA와 무관합니다.