Python 데이터 구조의 연결 목록에 대한 자세한 소개

이 글은 주로 Python 데이터 구조 연결 리스트 관련 정보를 자세하게 소개하고 있습니다. 관심 있는 친구들이 참고할 수 있습니다.

데이터 구조는 컴퓨터 과학에서 반드시 숙지해야 할 지식입니다. C에는 메모리를 쉽게 제어하고 연결 목록을 구현할 수 있는 포인터가 있기 때문에 C 언어를 사용하여 연결 목록을 구현합니다. 다른 언어에서는 시뮬레이션된 연결 목록을 사용하는 경우가 많지 않습니다. Python은 동적 언어이고 객체를 새 변수에 직접 할당할 수 있기 때문에 연결된 목록을 시뮬레이션합니다.

좋아, Python 구현에 대해 이야기하기 전에 연결 목록에 대해 간단히 이야기하겠습니다. 많은 양의 데이터를 저장할 때 배열을 사용하는 경우가 많은데, 삽입 연산을 수행할 때 매우 번거로운 작업이 있습니다. 아래의 예를 보면 1, 2, 3, 5, 6, 7번의 데이터가 있습니다. 3에 삽입하고 싶습니다. 5와 5 사이에 4를 삽입하세요. 배열을 사용하면 어떻게 되나요? 물론 5 이후의 데이터를 한 자리 뒤로 이동한 다음 4를 삽입하는 것은 매우 번거로운 일이지만 연결 리스트를 사용하면 3과 5 사이에 바로 4를 삽입하면 되기 때문에 매우 편리할 것 같습니다.

그럼 연결리스트의 구조는 어떻게 되나요? 이름에서 알 수 있듯이 연결 목록은 물론 노드가 서로 연결되어 데이터 체인을 형성하는 체인과 같습니다.

링크드 리스트 노드의 구조는 다음과 같습니다.

data는 맞춤 데이터이며, 다음은 다음 노드의 주소입니다.

연결된 목록의 구조는 head가 첫 번째 노드의 주소를 저장하는 것입니다.

다음으로 Python을 사용하여 연결 목록을 구현합니다

python으로 연결 목록을 구현합니다

먼저 node class Node:

class Node:
  '''
  data: 节点保存的数据
  _next: 保存下一个节点对象
  '''
  def __init__(self, data, pnext=None):
    self.data = data
    self._next = pnext

  def __repr__(self):
    '''
    用来定义Node的字符输出，
    print为输出data
    '''
    return str(self.data)

그런 다음 연결된 목록 클래스를 정의합니다.

연결된 목록에는 다음이 포함되어야 합니다.

속성:

List 헤더: head

연결된 목록의 길이: length

메서드:

비어 있는지 판단: isEmpty()

def isEmpty(self):
  return (self.length == 0

노드 추가(연결된 목록 끝에 추가): append()

def append(self, dataOrNode):
  item = None
  if isinstance(dataOrNode, Node):
    item = dataOrNode
  else:
    item = Node(dataOrNode)

  if not self.head:
    self.head = item
    self.length += 1

  else:
    node = self.head
    while node._next:
      node = node._next
    node._next = item
    self.length += 1

노드 삭제: delete()

#删除一个节点之后记得要把链表长度减一
def delete(self, index):
  if self.isEmpty():
    print "this chain table is empty."
    return

  if index < 0 or index >= self.length:
    print &#39;error: out of index&#39;
    return
  #要注意删除第一个节点的情况
  #如果有空的头节点就不用这样
  #但是我不喜欢弄头节点
  if index == 0:
    self.head = self.head._next
    self.length -= 1
    return

  #prev为保存前导节点
  #node为保存当前节点
  #当j与index相等时就
  #相当于找到要删除的节点
  j = 0
  node = self.head
  prev = self.head
  while node._next and j < index:
    prev = node
    node = node._next
    j += 1

  if j == index:
    prev._next = node._next
    self.length -= 1

노드 수정: update()

def update(self, index, data):
  if self.isEmpty() or index < 0 or index >= self.length:
    print &#39;error: out of index&#39;
    return
  j = 0
  node = self.head
  while node._next and j < index:
    node = node._next
    j += 1

  if j == index:
    node.data = data

노드 찾기: getItem()

def getItem(self, index):
  if self.isEmpty() or index < 0 or index >= self.length:
    print "error: out of index"
    return
  j = 0
  node = self.head
  while node._next and j < index:
    node = node._next
    j += 1

  return node.data

노드의 인덱스 찾기: getIndex()

def getIndex(self, data):
  j = 0
  if self.isEmpty():
    print "this chain table is empty"
    return
  node = self.head
  while node:
    if node.data == data:
      return j
    node = node._next
    j += 1

  if j == self.length:
    print "%s not found" % str(data)
    return

노드 삽입: insert( )

def insert(self, index, dataOrNode):
  if self.isEmpty():
    print "this chain tabale is empty"
    return

  if index < 0 or index >= self.length:
    print "error: out of index"
    return

  item = None
  if isinstance(dataOrNode, Node):
    item = dataOrNode
  else:
    item = Node(dataOrNode)

  if index == 0:
    item._next = self.head
    self.head = item
    self.length += 1
    return

  j = 0
  node = self.head
  prev = self.head
  while node._next and j < index:
    prev = node
    node = node._next
    j += 1

  if j == index:
    item._next = node
    prev._next = item
    self.length += 1

연결리스트 지우기:clear()

def clear(self):
  self.head = None
  self.length = 0

위는 구현하려는 연결리스트 클래스 메소드이다.

실행 결과:

다음은 전체 코드입니다.

# -*- coding:utf8 -*-
#/usr/bin/env python

class Node(object):
 def __init__(self, data, pnext = None):
  self.data = data
  self._next = pnext

 def __repr__(self):
  return str(self.data)

class ChainTable(object):
 def __init__(self):
  self.head = None
  self.length = 0

 def isEmpty(self):
  return (self.length == 0)

 def append(self, dataOrNode):
  item = None
  if isinstance(dataOrNode, Node):
   item = dataOrNode
  else:
   item = Node(dataOrNode)

  if not self.head:
   self.head = item
   self.length += 1

  else:
   node = self.head
   while node._next:
    node = node._next
   node._next = item
   self.length += 1

 def delete(self, index):
  if self.isEmpty():
   print "this chain table is empty."
   return

  if index < 0 or index >= self.length:
   print &#39;error: out of index&#39;
   return

  if index == 0:
   self.head = self.head._next
   self.length -= 1
   return

  j = 0
  node = self.head
  prev = self.head
  while node._next and j < index:
   prev = node
   node = node._next
   j += 1

  if j == index:
   prev._next = node._next
   self.length -= 1

 def insert(self, index, dataOrNode):
  if self.isEmpty():
   print "this chain tabale is empty"
   return

  if index < 0 or index >= self.length:
   print "error: out of index"
   return

  item = None
  if isinstance(dataOrNode, Node):
   item = dataOrNode
  else:
   item = Node(dataOrNode)

  if index == 0:
   item._next = self.head
   self.head = item
   self.length += 1
   return

  j = 0
  node = self.head
  prev = self.head
  while node._next and j < index:
   prev = node
   node = node._next
   j += 1

  if j == index:
   item._next = node
   prev._next = item
   self.length += 1

 def update(self, index, data):
  if self.isEmpty() or index < 0 or index >= self.length:
   print &#39;error: out of index&#39;
   return
  j = 0
  node = self.head
  while node._next and j < index:
   node = node._next
   j += 1

  if j == index:
   node.data = data

 def getItem(self, index):
  if self.isEmpty() or index < 0 or index >= self.length:
   print "error: out of index"
   return
  j = 0
  node = self.head
  while node._next and j < index:
   node = node._next
   j += 1

  return node.data


 def getIndex(self, data):
  j = 0
  if self.isEmpty():
   print "this chain table is empty"
   return
  node = self.head
  while node:
   if node.data == data:
    return j
   node = node._next
   j += 1

  if j == self.length:
   print "%s not found" % str(data)
   return

 def clear(self):
  self.head = None
  self.length = 0

 def __repr__(self):
  if self.isEmpty():
   return "empty chain table"
  node = self.head
  nlist = &#39;&#39;
  while node:
   nlist += str(node.data) + &#39; &#39;
   node = node._next
  return nlist

 def __getitem__(self, ind):
  if self.isEmpty() or ind < 0 or ind >= self.length:
   print "error: out of index"
   return
  return self.getItem(ind)

 def __setitem__(self, ind, val):
  if self.isEmpty() or ind < 0 or ind >= self.length:
   print "error: out of index"
   return
  self.update(ind, val)

 def __len__(self):
  return self.length

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