Python implémente des structures de données linéaires de base

Tableau

Conception du tableau

La conception du tableau est à l'origine conçue pour s'appuyer formellement sur l'allocation de mémoire, l'espace doit donc être demandé à l'avance avant utilisation. Cela donne au tableau les caractéristiques suivantes :

1. La taille est fixe après la demande d'espace et ne peut pas être modifiée (problème de débordement de données

2. Il y a une continuité spatiale) ; dans la mémoire, il n'y aura aucune donnée que d'autres programmes devront appeler au milieu. Il s'agit d'un espace mémoire dédié à ce tableau. Un jugement inférieur sera porté sur le fonctionnement du tableau, et il y a un potentiel. risque d'opérations hors limites (par exemple, des données seront écrites dans la mémoire de la partie principale qui doit être appelée par le programme en cours d'exécution).

Étant donné que les tableaux simples dépendent fortement de la mémoire du matériel informatique, ils ne sont pas adaptés à la programmation moderne. Si vous souhaitez utiliser des types de données de taille variable et indépendants du matériel, les langages de programmation tels que Java fournissent des structures de données plus avancées : des tableaux dynamiques tels que ArrayList et Vector.

Tableaux Python

À proprement parler : il n'y a pas de tableau au sens strict en Python.

List peut être considéré comme un tableau en Python. Le code suivant est la structure de CPython qui implémente List :

Bien sûr, c'est un tableau en Python. .

Certaines des structures suivantes seront également implémentées à l'aide de List.

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;

Pile

Qu'est-ce qu'une pile

La pile (anglais : pile), également connue sous le nom de pile directement, est un type spécial de pile dans l'ordinateur science Structure de données sous forme de série. Sa particularité est qu'elle ne peut permettre d'ajouter des données (anglais : push) et de sortir des données (anglais : top) qu'à une extrémité de la série ou du tableau lié (appelé haut du). pile, anglais : top pop). De plus, l’empilement peut également être réalisé sous la forme d’un réseau unidimensionnel ou d’une série connectée. L’opération inverse de l’empilement est appelée mise en file d’attente.

La structure de données empilée ne permettant les opérations qu'à une seule extrémité, elle fonctionne selon le principe LIFO (Last In First Out).

Caractéristiques

1. Premier entré, premier sorti, dernier entré, premier sorti.

2. À l'exception des nœuds de tête et de queue, chaque élément a un prédécesseur et un successeur.

Opération

D'après le principe, les opérations pouvant être effectuées sur la pile (stack) sont :

1. top() : Get l'objet du haut de la pile

2. push() : Ajouter un objet à la pile

3. pop() : Pousser un objet de la pile

Mise en œuvre

File d'attente

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('已经是栈顶了')

Qu'est-ce qu'une file d'attente

Semblable à une pile, la seule différence est que la file d'attente ne peut être retirée de la file d'attente qu'en tête de l'opération de file d'attente, la file d'attente est donc un tableau linéaire du premier entré, premier sorti (FIFO, First-In-First-Out)

Caractéristiques

1. Premier entré, premier sorti, dernier entré-dernier sorti

2. À l'exception du nœud de queue, chaque nœud a un successeur

3. (Facultatif) À l'exception du nœud principal, chaque nœud a un prédécesseur

Opération

1. push() : rejoindre la file d'attente

2. pop() : quitter la file d'attente

Implémentation

File d'attente ordinaire

Liste chaînée

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)

Qu'est-ce qu'une liste chaînée

Une liste chaînée est une structure de données de base commune est un tableau linéaire, mais elle ne stocke pas les données dans un ordre linéaire. stocke un pointeur vers le nœud suivant dans chaque nœud. Puisqu'il n'est pas nécessaire de la stocker dans l'ordre, la liste chaînée peut atteindre une complexité O(1) lors de l'insertion, ce qui est beaucoup plus rapide qu'une autre liste linéaire, une liste séquentielle, mais trouver un nœud ou accéder à un nœud numéroté spécifique nécessite O(n ) temps, et la complexité temporelle correspondante de la table de séquence est respectivement O(logn) et O(1).

Caractéristiques

L'utilisation de la structure de liste chaînée peut surmonter l'inconvénient de la liste chaînée de tableau selon laquelle la taille des données doit être connue à l'avance. l'espace mémoire de l'ordinateur et obtenir une gestion dynamique et flexible de la mémoire. Cependant, la liste chaînée perd l'avantage de la lecture aléatoire du tableau. Dans le même temps, la liste chaînée a une surcharge d'espace relativement importante en raison de l'augmentation du champ de pointeur du nœud.

Opération

1. init() : initialisation

2. insert() : insert

3. trave() : traverser

4. delete() : supprimer

5. find() : trouver

pour implémenter

Seules les listes bidirectionnelles sont implémentées ici

Résumé

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

Ce qui précède concerne l'utilisation de Python pour implémenter des structures de données linéaires de base, j'espère. cet article sera utile à tous ceux qui apprennent Python peuvent aider. Si vous avez des questions, vous pouvez laisser un message pour en discuter.

Pour plus d'articles liés à l'implémentation par Python des structures de données linéaires de base, veuillez prêter attention au site Web PHP chinois !