Python は基本的な線形データ構造を実装します

配列

配列の設計

配列の設計は本来フォームでのメモリ割り当てに基づいているため、使用前に事前に領域を要求する必要があります。これにより、配列に次の特性が与えられます:

1. スペースが要求された後はサイズが固定され、変更できません (データ オーバーフローの問題) 2. メモリ内に空間的な連続性があり、必要な他のプログラムが存在しません。データはこの配列専用のメモリ空間です

3. 古いプログラミング言語 (中間レベル言語としても知られる C など) では、プログラムは下限の判断を行いません。配列操作では、範囲外の操作が行われる可能性があります (たとえば、実行中のプログラムが呼び出す必要があるコア部分のメモリにデータが書き込まれるなど)。

単純な配列はコンピューター ハードウェアのメモリに大きく依存するため、最新のプログラミングには適していません。可変サイズでハードウェアに依存しないデータ型を使用する場合は、Java などのプログラミング言語が、より高度なデータ構造 (ArrayList や Vector などの動的配列) を提供します。

Python の配列

厳密に言うと、Python には厳密な意味での配列はありません。

List は Python の配列であると言えます。 次のコードは List を実装する CPython の構造です。

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;

もちろん、Python では配列です。

以下の構造の一部も List を使用して実装されます。

スタック

スタックとは

スタック（英語: stack ）は、直接スタックとも呼ばれ、コンピュータサイエンスにおける特別なシリアルデータ構造であり、その特徴は、プッシュおよびポップ操作のみを許可することです。リンクされたリストまたは配列の一端 (スタックの最上位と呼ばれる) で実行されます。さらに、一次元配列または連結されたシリーズの形で積み重ねを完了することもできます。スタッキングの逆の操作はキューイングと呼ばれます。

スタックされたデータ構造は一方の端でのみ操作を許可するため、LIFO (Last In First Out) の原則に従って動作します。

特徴

1. 先入れ、後出し、後入れ、先出し。

2. 先頭ノードと末尾ノードを除き、各要素には先行ノードと後続ノードがあります。

操作

原理から、スタック(stack)上で実行できる操作は以下の通りです:

1. top(): スタックの先頭にあるオブジェクトを取得します

2. Push() : スタックにオブジェクトを追加します

3. Pop(): スタックからオブジェクトをプッシュします

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

キューを実装します

キューとは

唯一の違いはスタックと似ています。つまり、キューはキューの先頭でのみデキューできるため、キューは先入れ先出し (FIFO、先入れ先出し) の線形テーブルになります

特徴

1. まず。 -in、first-out、last-in-last-out

2. 末尾ノードを除くすべてのノードには後続ノードがあります

3. (オプション) ヘッドノードを除き、各ノードには先行ノードがあります

操作

1.push(): enqueue

2.pop(): dequeue

実装

通常のキュー

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)

リンクリスト

リンクリストとは

リンクリストは共通の基本データ構造である線形テーブルですが、線形順序で格納されません。データは次のノードへのポインタとして各ノードに格納されます。順序どおりに格納する必要がないため、リンク リストは挿入時に O(1) の複雑さを実現できます。これは、別の線形リストや逐次リストよりもはるかに高速ですが、ノードの検索や特定の番号付きノードへのアクセスには O( n) 時間、シーケンス テーブルの対応する時間計算量はそれぞれ O(logn) と O(1) です。

特徴

リンクリスト構造を使用すると、データサイズを事前に知る必要があるという配列リンクリストの欠点を克服でき、コンピューターのメモリスペースを最大限に活用し、柔軟な動的メモリ管理を実現できます。ただし、リンク リストでは配列のランダム読み取りの利点が失われますが、同時に、ノードのポインタ フィールドが増加するため、比較的大きなスペース オーバーヘッドが発生します。

オペレーション

1. init(): 初期化

2. insert(): 挿入

3. trave(): トラバース

4. delete(): 削除

5. find( ) :

実装を見つけてください

ここでは双方向リストのみが実装されています

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

概要

上記はすべて、Python を使用して基本的な線形データ構造を実装する方法についてです。この記事が Python を学習するすべての人に役立つことを願っています。 。ご質問がある場合は、メッセージを残して話し合うことができます。

基本的な線形データ構造の Python の実装に関連するその他の記事については、PHP 中国語 Web サイトに注目してください。