In diesem Artikel werden hauptsächlich die relevanten Informationen der verknüpften Liste der Python-Datenstruktur vorgestellt, die einen bestimmten Referenzwert haben.
Datenstruktur ist ein Muss in der Informatik In vielen früheren Lehrbüchern wurde die C-Sprache zum Implementieren verknüpfter Listen verwendet, sodass es nicht so einfach ist, den Speicher zu steuern und verknüpfte Listen zu implementieren. Diesmal habe ich dies jedoch getan Verwenden Sie zur Implementierung keine simulierte verknüpfte Liste, da Python eine dynamische Sprache ist und Objekte direkt neuen Variablen zuweisen kann.
Okay, bevor ich Python zur Implementierung verwende, möchte ich kurz über verknüpfte Listen sprechen. Wenn wir eine große Datenwelle speichern, verwenden wir häufig Arrays, aber es ist sehr mühsam, wenn wir das folgende Beispiel ansehen: Es gibt eine Reihe von Daten 1, 2, 3, 5, 6, 7. Wir Ich möchte es in 3 einfügen. 4 zwischen 5 und 5 einfügen. Was machen wir, wenn wir ein Array verwenden? Natürlich werden die Daten nach 5 um eine Position nach hinten verschoben und dann 4 eingefügt. Das ist sehr mühsam, aber wenn ich eine verknüpfte Liste verwende, kann ich 4 einfach direkt zwischen 3 und 5 einfügen, was sehr praktisch klingt.
Wie ist also die Struktur der verknüpften Liste? Wie der Name schon sagt, ist eine verknüpfte Liste natürlich wie eine Kette, bei der Knoten miteinander verbunden sind, um eine Datenkette zu bilden.
Die Knotenstruktur der verknüpften Liste ist wie folgt:
Daten sind benutzerdefinierte Daten, und als nächstes steht die Adresse des nächsten Knotens.
Die Struktur der verknüpften Liste ist: head speichert die Adresse des ersten Knotens:
Als nächstes verwenden wir Python, um die verknüpfte Liste zu implementieren
Python implementiert verknüpfte Listen
Definieren Sie zunächst die Knotenklasse 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)Definieren Sie dann die verknüpfte Liste Listenklasse:
Verknüpfte Liste zum Einschließen:
Attribute:
Listenkopf: Kopf
Listenlänge: Länge
Methode:
Bestimmen Sie, ob es leer ist: isEmpty()
def isEmpty(self): return (self.length == 0
Fügen Sie einen Knoten hinzu (fügen Sie ihn am Ende der verknüpften Liste hinzu): 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 += 1Einen Knoten löschen: delete()
#删除一个节点之后记得要把链表长度减一
def delete(self, index):
if self.isEmpty():
print "this chain table is empty."
return
if index < 0 or index >= self.length:
print 'error: out of index'
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 -= 1Einen Knoten ändern: update()
def update(self, index, data):
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
if j == index:
node.data = dataSuchen Sie einen Knoten: 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.dataSuchen Sie den Index eines Knotens: 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)
returnEinen Knoten einfügen: 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 += 1Löschen Sie die verknüpfte Liste : clear()
def clear(self): self.head = None self.length = 0
Das Obige ist die Methode, die in der verknüpften Listenklasse implementiert werden soll.
Ergebnis der Ausführung:
Das Folgende ist der vollständige Code:
# -*- 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 'error: out of index'
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 'error: out of index'
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 = ''
while node:
nlist += str(node.data) + ' '
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.lengthDas obige ist der detaillierte Inhalt vonDetaillierte Einführung in die verknüpfte Liste der Python-Datenstruktur. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
