Python implementiert grundlegende lineare Datenstrukturen

Array

Design des Arrays

Array-Design ist ursprünglich so konzipiert, dass es formal auf der Speicherzuweisung basiert, daher muss vor der Verwendung Speicherplatz im Voraus angefordert werden. Dies verleiht dem Array die folgenden Eigenschaften:

1. Die Größe ist nach der Anforderung des Speicherplatzes festgelegt und kann nicht geändert werden (Datenüberlaufproblem);

2. Es besteht räumliche Kontinuität Im Speicher gibt es keine Daten, die andere Programme in der Mitte aufrufen müssen. Dies ist ein dedizierter Speicherbereich für dieses Array. Es wird eine Beurteilung der unteren Grenze vorgenommen, und es besteht ein Potenzial Risiko von Vorgängen außerhalb der Grenzen (z. B. werden Daten in den Speicher des Kernteils geschrieben, der vom laufenden Programm aufgerufen werden muss).

Da einfache Arrays stark auf den Speicher der Computerhardware angewiesen sind, sind sie für die moderne Programmierung nicht geeignet. Wenn Sie hardwareunabhängige Datentypen variabler Größe verwenden möchten, bieten Programmiersprachen wie Java erweiterte Datenstrukturen: dynamische Arrays wie ArrayList und Vector.

Python-Arrays

Genau genommen gibt es in Python kein Array im engeren Sinne.

Liste kann als Array in Python bezeichnet werden. Der folgende Code ist die Struktur von CPython, die List implementiert:

Natürlich ist es ein Array in Python .

Einige der folgenden Strukturen werden auch mit List implementiert.

typedef struct {
 PyObject_VAR_HEAD
 /* Vector of pointers to list elements. list[0] is ob_item[0], etc. */
 PyObject **ob_item;
 
 /* ob_item contains space for 'allocated' elements. The number
  * currently in use is ob_size.
  * Invariants:
  *  0 <= ob_size <= allocated
  *  len(list) == ob_size
  *  ob_item == NULL implies ob_size == allocated == 0
  * list.sort() temporarily sets allocated to -1 to detect mutations.
  *
  * Items must normally not be NULL, except during construction when
  * the list is not yet visible outside the function that builds it.
  */
 Py_ssize_t allocated;
} PyListObject;

Stapel

Was ist ein Stapel?

Stapel (englisch: Stack), auch direkt als Stapel bezeichnet, ist eine spezielle Art von Stapel im Computer Wissenschaft Eine Datenstruktur in Form einer Reihe. Ihre Besonderheit besteht darin, dass sie nur das Hinzufügen von Daten (englisch: push) und die Ausgabe von Daten (englisch: top) an einem Ende der verknüpften Reihe oder des Arrays (genannt oben) ermöglicht Stack, englisch: top). Darüber hinaus kann die Stapelung auch in Form eines eindimensionalen Arrays oder einer verbundenen Reihe erfolgen. Der umgekehrte Vorgang des Stapelns wird als Warteschlangen bezeichnet.

Da die gestapelte Datenstruktur nur Operationen an einem Ende zulässt, arbeitet sie nach dem Prinzip von LIFO (Last In First Out).

Funktionen

1. Zuerst rein, zuerst raus, zuletzt rein, zuerst raus.

2. Mit Ausnahme der Kopf- und Schwanzknoten hat jedes Element einen Vorgänger und einen Nachfolger.

Operation

Grundsätzlich sind die Operationen, die auf dem Stapel (Stack) ausgeführt werden können:

1. top(): Get das oberste Objekt des Stapels

2. push(): Füge ein Objekt zum Stapel hinzu

3. pop(): Schiebe ein Objekt vom Stapel

Implementierung

Warteschlange

class my_stack(object):
 def __init__(self, value):
  self.value = value
  # 前驱
  self.before = None
  # 后继
  self.behind = None
 
 def __str__(self):
  return str(self.value)
 
 
def top(stack):
 if isinstance(stack, my_stack):
  if stack.behind is not None:
   return top(stack.behind)
  else:
   return stack
 
 
def push(stack, ele):
 push_ele = my_stack(ele)
 if isinstance(stack, my_stack):
  stack_top = top(stack)
  push_ele.before = stack_top
  push_ele.before.behind = push_ele
 else:
  raise Exception('不要乱扔东西进来好么')
 
 
def pop(stack):
 if isinstance(stack, my_stack):
  stack_top = top(stack)
  if stack_top.before is not None:
   stack_top.before.behind = None
   stack_top.behind = None
   return stack_top
  else:
   print('已经是栈顶了')

Was ist eine Warteschlange

Ähnlich wie bei einem Stapel, der einzige Unterschied besteht darin Die Warteschlange kann nur an der Spitze der Warteschlangenoperation aus der Warteschlange entfernt werden, daher ist die Warteschlange eine lineare First-In-First-Out-Tabelle (FIFO, First-In-First-Out)

Funktionen

1. First-in-First-out, Last-in-Last-out

2. Mit Ausnahme des Endknotens hat jeder Knoten einen Nachfolger

3. (Optional) Mit Ausnahme des Kopfknotens hat jeder Knoten einen Vorgänger

Operation

1. push(): der Warteschlange beitreten

2. pop(): Warteschlange verlassen

Implementierung

Gewöhnliche Warteschlange

Verknüpfte Liste

class MyQueue():
 def __init__(self, value=None):
  self.value = value
  # 前驱
  # self.before = None
  # 后继
  self.behind = None
 
 def __str__(self):
  if self.value is not None:
   return str(self.value)
  else:
   return 'None'
 
 
def create_queue():
 """仅有队头"""
 return MyQueue()
 
 
def last(queue):
 if isinstance(queue, MyQueue):
  if queue.behind is not None:
   return last(queue.behind)
  else:
   return queue
 
 
def push(queue, ele):
 if isinstance(queue, MyQueue):
  last_queue = last(queue)
  new_queue = MyQueue(ele)
  last_queue.behind = new_queue
 
 
def pop(queue):
 if queue.behind is not None:
  get_queue = queue.behind
  queue.behind = queue.behind.behind
  return get_queue
 else:
  print('队列里已经没有元素了')
 
def print_queue(queue):
 print(queue)
 if queue.behind is not None:
  print_queue(queue.behind)

Was ist eine verknüpfte Liste?

Eine verknüpfte Liste ist eine übliche grundlegende Datenstruktur, die Daten jedoch nicht in linearer Reihenfolge speichert speichert in jedem Knoten einen Zeiger auf den nächsten Knoten. Da sie nicht in der richtigen Reihenfolge gespeichert werden muss, kann die verknüpfte Liste beim Einfügen eine O(1)-Komplexität erreichen, was viel schneller ist als eine andere lineare Liste oder eine sequentielle Liste, aber das Nachschlagen eines Knotens oder der Zugriff auf einen bestimmten nummerierten Knoten erfordert O( n) Zeit, und die entsprechende Zeitkomplexität der Sequenztabelle beträgt O(logn) bzw. O(1).

Funktionen

Die Verwendung der verknüpften Listenstruktur kann den Nachteil der verknüpften Array-Liste überwinden, dass die Datengröße im Voraus bekannt sein muss. Die verknüpfte Listenstruktur kann vollständig genutzt werden den Computerspeicherplatz und erreichen Sie eine flexible dynamische Speicherverwaltung. Allerdings verliert die verknüpfte Liste den Vorteil des zufälligen Lesens des Arrays. Gleichzeitig weist die verknüpfte Liste aufgrund der Vergrößerung des Zeigerfelds des Knotens einen relativ großen Speicherplatzaufwand auf.

Operation

1. init(): Initialisierung

2. insert(): insert

3. trave(): traverse

4. delete(): löschen

5. find():

finden, um

Hier werden nur Zwei-Wege-Listen implementiert

Zusammenfassung

class LinkedList():
 def __init__(self, value=None):
  self.value = value
  # 前驱
  self.before = None
  # 后继
  self.behind = None
 
 def __str__(self):
  if self.value is not None:
   return str(self.value)
  else:
   return 'None'
 
 
def init():
 return LinkedList('HEAD')
 
 
def delete(linked_list):
 if isinstance(linked_list, LinkedList):
  if linked_list.behind is not None:
   delete(linked_list.behind)
   linked_list.behind = None
   linked_list.before = None
  linked_list.value = None

Ich hoffe, dass es hier um die Verwendung von Python zur Implementierung grundlegender linearer Datenstrukturen geht Dieser Artikel wird für jeden hilfreich sein, der beim Erlernen von Python hilfreich sein kann. Wenn Sie Fragen haben, können Sie eine Nachricht zur Diskussion hinterlassen.

Weitere Artikel zur Python-Implementierung grundlegender linearer Datenstrukturen finden Sie auf der chinesischen PHP-Website!