Python은 기본 선형 데이터 구조를 구현합니다.

어레이

어레이 설계

어레이 설계는 원래 형식적으로 메모리 할당에 의존하도록 설계되었으므로 사용하기 전에 미리 공간을 요청해야 합니다. 이는 배열에 다음과 같은 특징을 부여합니다.

1. 공간이 요청된 후에는 크기가 고정되며 변경할 수 없습니다(데이터 오버플로 문제).

2. 공간 연속성이 있습니다. 메모리에는 다른 프로그램이 중간에 호출해야 하는 데이터가 없습니다. 이는 이 배열의 전용 메모리 공간이며 배열의 작동에 대한 하한 판단이 이루어집니다. 범위를 벗어난 작업의 위험(예: 실행 중인 프로그램에서 호출해야 하는 핵심 부분의 메모리에 데이터가 기록됨)

간단한 배열은 컴퓨터 하드웨어의 메모리에 크게 의존하기 때문에 최신 프로그래밍에는 적합하지 않습니다. 가변 크기, 하드웨어 독립적 데이터 유형을 사용하려는 경우 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)은 직접적으로 스택이라고도 알려져 있으며 컴퓨터의 특수한 유형의 스택입니다. science 시리즈 형태의 데이터 구조의 특징은 연결된 시리즈 또는 배열의 한쪽 끝(맨 위라고 함)에서만 데이터 추가(영어: push) 및 출력 데이터(영어: top)를 허용한다는 것입니다. stack, 영어: top) 작업입니다. 또한, 1차원 배열이나 연결된 계열의 형태로도 적층이 완성될 수 있다. 스태킹의 반대 작업을 큐잉이라고 합니다.

Stacked 데이터 구조는 한쪽 끝에서만 연산이 가능하므로 LIFO(Last In First Out) 원리에 따라 동작합니다.

특징

1. 선입선출, 후입선출.

2. 헤드 노드와 테일 노드를 제외한 각 요소에는 선행 노드와 후행 노드가 있습니다.

연산

원리적으로 스택(Stack)에서 수행할 수 있는 연산은 다음과 같습니다.

1. top(): Get 스택의 최상위 객체

2. push(): 스택에 객체 추가

3. pop(): 스택에서 객체 푸시

Implement

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

Queue

큐란 무엇인가요?

유일한 차이점은 스택과 유사하다는 것입니다. 대기열은 대기열의 선두에서만 제거될 수 있습니다. 따라서 대기열은 선입선출(FIFO, First-In-First-Out)의 선형 테이블입니다.

특징

1. 선입선출, 후입선출

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(): 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 중국어 웹사이트를 주목하세요!