Introduction détaillée à la liste chaînée de la structure de données Python

Cet article présente principalement en détail les informations pertinentes de la liste chaînée des structures de données Python, qui ont une certaine valeur de référence. Les amis intéressés peuvent s'y référer

La structure des données est une maîtrise incontournable en informatique. sujet, de nombreux manuels précédents utilisaient le langage C pour implémenter des listes chaînées. Parce que C a des pointeurs, il peut facilement contrôler la mémoire et implémenter des listes chaînées. Beaucoup utilisent des listes chaînées simulées, mais cette fois, je l'ai fait. n'utilisez pas de liste chaînée simulée pour l'implémenter, car python est un langage dynamique et peut directement attribuer des objets à de nouvelles variables.

D'accord, avant d'utiliser Python pour l'implémenter, permettez-moi de parler brièvement des listes chaînées. Lorsque nous stockons une grande vague de données, nous utilisons souvent des tableaux, mais c'est très gênant lorsque nous effectuons des opérations d'insertion. Regardez l'exemple ci-dessous. Il y a un tas de données 1, 2, 3, 5, 6, 7. nous voulons l'insérer dans 3 Insérez 4 entre 5 et 5. Que ferons-nous si nous utilisons un tableau ? Bien sûr, les données après 5 sont reculées d'une position, puis 4 est inséré, c'est très gênant, mais si j'utilise une liste chaînée, je peux simplement insérer 4 directement entre 3 et 5, ce qui semble très pratique.

Alors, quelle est la structure de la liste chaînée ? Comme son nom l’indique, une liste chaînée est bien entendu comme une chaîne, avec des nœuds connectés entre eux pour former une chaîne de données.

La structure des nœuds de la liste chaînée est la suivante :

les données sont des données personnalisées, et next est l'adresse du nœud suivant.

La structure de la liste chaînée est la suivante, head enregistre l'adresse du premier nœud :

Ensuite, nous utilisons python pour implémenter la liste chaînée

Python implémente la liste chaînée

Tout d'abord, définissez la classe de nœud 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)

Ensuite, définissez la classe liée classe de liste :

Liste chaînée À inclure :

Attributs :

Tête de liste : tête

Longueur de la liste : longueur

Méthode :

Déterminer s'il est vide : isEmpty()

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

Ajouter un nœud (ajouter à la fin de la liste chaînée) : 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

Supprimer un nœud : 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

Modifier un nœud : 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

Trouver un nœud : 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

Trouver l'index d'un nœud : 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

Insérer un nœud : 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

Effacer la liste chaînée : clear()

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

Ce qui précède est la méthode à implémenter dans la classe de liste chaînée.

Résultat de l'exécution :

Voici le code complet :

# -*- 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

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!