Python 데이터 구조 및 알고리즘의 연결 목록 정의 사용에 대한 자세한 설명

이 글에서는 주로 Python 데이터 구조와 알고리즘에서 연결 목록의 정의와 사용법을 소개합니다. 단일 연결 목록, 순환 연결 목록 등의 정의, 사용 방법 및 관련 주의 사항을 구체적인 사례를 바탕으로 자세히 분석합니다. 참고하시면 됩니다

이 글의 예제는 Python 데이터 구조와 알고리즘에서 연결 리스트의 정의와 사용법을 설명합니다. 참고를 위해 모든 사람과 공유하세요. 세부 사항은 다음과 같습니다.

이 기사에서 설명할 내용은 다음과 같습니다.

(1) 연결 목록 노드의 정의부터 시작하여 클래스 및 객체 지향 형식으로 연결 목록을 설계합니다. 아이디어

(2) 연결리스트 클래스 삽입, 삭제,
prepend(헤드 삽입), pop(헤드 삭제), Append(테일 삽입), pop_last(테일 삭제) 등 멤버 함수 구현 시 고려해야 할 경계 조건

2.1 삽입:

빈 연결리스트
연결리스트의 길이는 1
끝까지 삽입

2.2 삭제

빈 연결리스트
연결리스트의 길이는 1
마지막 삭제 element

(3) 단일 연결 목록에서 단일 연결 목록으로의 다양한 변형:

꼬리 포함 노드의 단일 연결 목록
원형 단일 연결 목록
이중 연결 목록

1. 연결 목록 노드의 정의

class LNode:
 def __init__(self, elem, next_=None):
  self.elem = elem
  self.next = next_

2. 단일 연결 리스트 구현

삽입 및 삭제 구현과 고려해야 할 경계에 대한 이해에 중점을 둡니다. 조건:

class LinkedListUnderflow(ValueError):
 pass
class LList:
 def __init__(self):
  self._head = None
 def is_empty(self):
  return self._head is None
 def prepend(self, elem):
  self._head = LNode(elem, self._head)
 def pop(self):
  if self._head is None:
   raise LinkedListUnderflow('in pop')
  e = self._head.elem
  self._head = self._head.next
  return e
 def append(self, elem):
  if self._head is None:
   self._head = LNode(elem)
   return
  p = self._head
  while p.next is not None:
   p = p.next
  p.next = LNode(elem)
 def pop_last(self):
  if self._head is None:
   raise LinkedListUnderflow('in pop_last')
  p = self._head
  if p.next is None:
   e = p.elem
   self._head = None
   return e
  while p.next.next is not None:
   p = p.next
  e = p.next.elem
  p.next = None
  return e

간단한 요약:

(0) 전제 조건 p.next.next에 액세스할 수 있으려면 p.next가 비어 있지 않아야 합니다.
(1) 연결 목록이 비어 있지 않으면 꼬리 삽입이 필요합니다. 변경해야 할 것은 꼬리 노드의 포인터뿐입니다.
(2) 꼬리 삭제, 연결 리스트의 길이가 비어 있지 않은 경우 두 번째 노드의 포인터만 변경하면 됩니다.

단일 연결 리스트의 간단한 변환: 꼬리 노드가 있는 단일 연결 리스트

class LList1(LList):
 def __init__(self):
  LList.__init__(self)
  self._rear = None
 ...

다시 작성해야 할 것은: 머리 삽입, 꼬리 삽입, 꼬리 삭제

def prepend(self, elem):
 if self._head is None:
  self._head = LNode(elem)
  self._rear = self._head
 else:
  self._head = LNode(elem, self._head)
def append(self, elem):
 if self._head is None:
  self._head = LNode(elem)
  self._rear = self._head
 else:
  self._rear.next = LNode(elem)
  self._rear = self._rear.next
def pop_last(self):
 if self._head is None:
  raise LinkedListUnderflow('in pop_last')
 p = self._head
 if p.next is None:
  e = p.elem
  self._head = None
  return e
 while p.next.next is not None:
  p = p.next
 e = p.next.elem
 self._rear = p
 p.next = None
 return e

단일 연결 목록의 변형: 순환 단일 연결 목록

class LCList:
 def __init__(self):
  self._rear = None
 def prepend(self, elem):
  if self._rear is None:
   self._rear = LNode(elem)
   self._rear.next = self._rear
  else:
   self._rear.next = LNode(elem, self._rear.next)
 def append(self, elem):
  self.prepend(elem)
  self_rear = self._rear.next
 def pop(self):
  if self._rear is None:
   raise LinkedListUnderflow('in pop')
  p = self._rear.next
  if p is None:
   self._rear = None
  else:
   self._rear.next = p.next
  return p.elem
 def printall(self):
  if self._rear is None:
   raise ...
  p = self._rear.next
  while True:
   print(p.elem)
   if p is self._rear:
    break
   p = p.next

위 내용은 Python 데이터 구조 및 알고리즘의 연결 목록 정의 사용에 대한 자세한 설명의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!