링크 의 Python 실현 과 사례 분석
7010 단어 Python 데이터 구조 구현
저장 구조 에 순서대로 저 장 된 배열 (Array List) 이 있 는데 왜 링크 를 해 야 합 니까?어떤 경우 에는 링크 드 리스트 가 Array List 에 비해 우세 하기 때문이다.
4. 567917. 당신 의 응용 프로그램 은 데이터 에 무 작위 로 접근 하지 않 습 니 다.링크 드 리스트 의 n 번 째 요소 가 필요 할 때 첫 번 째 요소 순서 에서 n 번 째 데이터 까지 세 고 데 이 터 를 읽 어야 하기 때문이다.이때 의 복잡 도 는 O (n) 이 고 Array List 에 대해 서 는 O (1) 입 니 다
4. 567917. 당신 의 응용 은 요 소 를 더 많이 삽입 하고 삭제 하 며 색인 에 따라 데 이 터 를 더 적 게 읽 습 니 다 (옮 겨 다 니 기만 한다 면 차이 가 크 지 않 습 니 다).요 소 를 삽입 하고 삭제 하 는 것 은 재 배열 데이터 와 관련 이 없 기 때문에 복잡 도 는 O (1) 이 고 Array List 는 O (n) 입 니 다
파 이 썬 구현
Python 에 서 는 명시 적 포인터 가 없 지만 모든 변 수 는 기본 데이터 형식 (int, float 등) 을 제외 하고 '참조' 입 니 다.따라서 링크 는 노드 류 와 인용 을 정의 함으로써 이 루어 질 수 있다.
노드 클래스 에는 노드 데이터 와 다음 노드 주소, 즉 참조 가 포함 되 어 있 습 니 다.
체인 테이블 클래스 는 체인 테이블 의 각종 조작 입 니 다. 다음은 단일 체인 테이블 의 Python 실현 을 제시 하고 체인 테이블 에 노드 를 추가 하 는 동작 을 제공 합 니 다.
# @Author:
# @blog: http://blog.csdn.net/marksinoberg
class Node:
def __init__(self, data, next):
self.data = data
self.next = next
class LianBiao:
def __init__(self):
self.root = None
#
def addNode(self, data):
newNode = Node(data=data, next=None)
if self.root==None:
self.root = newNode
else:
# ， ，
cursor = self.root
while cursor.next!= None:
cursor = cursor.next
cursor.next = newNode주: 코드 는 블 로그 참조: Python 은 전면적 인 단일 체인 표를 실현 합 니 다. 이 블 로그 에는 더 많은 조작 이 있 습 니 다. 참고 하여 자신 이 실현 하려 고 시도 할 수 있 습 니 다.
응용 실례
조세 프 문제: n 명 이 한 바퀴 를 돌 고 각자 1, 2,..., n 으로 표시 되 어 있 으 며 1 번 부터 1 번 부터 숫자 를 보고 하고 k 에 도착 한 사람 에 게 원 을 내 라 고 요구 했다. 이 어 다음 사람 은 1 부터 숫자 를 보고 하기 시작 했다. 이렇게 순환 해서 마지막 사람 만 남 았 을 때 이 사람 이 승자 가 된다.
조세 프 문 제 를 푸 는 방법 중 하 나 는 이 과정 을 모 의 하 는 것 이다. 모 의 운반 체 는 대열 일 수도 있 고 링크 일 수도 있다.
칼럼 대기 열의 Python 구현 에서 대기 열 로 간단 한 인 스 턴 스 로 이 문 제 를 풀 었 습 니 다.
만약 에 링크 로 이 문 제 를 해결 하려 면 순환 링크, 즉 마지막 노드 의 연결 점 이 필요 하 다.대기 열 에 비해 순환 링크 의 차 이 는 자주 팀 에 들 어가 지 않 아 도 되 고 링크 를 계속 돌아 다 니 며 마지막 노드 를 남 길 때 까지 k 번 째 노드 를 삭제 하 는 것 입 니 다.
단일 체인 표를 바탕 으로 마지막 노드 를 상단 의 노드 로 연결 하면 순환 체인 표를 실현 할 수 있다.
#
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LoopLinkedList:
def __init__(self):
self.root = None
# ，
def addNode(self, data):
newNode = Node(data)
if self.root==None:
self.root = newNode
else:
cursor = self.root
while cursor.next!= self.root:
cursor = cursor.next
cursor.next = newNode
newNode.next=self.root #
#
def size(self):
if self.root == None:
return 0
cursor = self.root
i=1
while cursor.next != self.root:
i+=1
cursor = cursor.next
return i
#
def circle(num,nameList):
linkedList=LoopLinkedList()
for i in range(len(nameList)):
linkedList.addNode(nameList[i])
i=1
pre = linkedList.root
cursor = linkedList.root
while linkedList.size()!=1:
if i!=num:
pre=cursor
cursor=cursor.next
i+=1
else :
pre.next=cursor.next #
cursor=pre.next
linkedList.root=cursor #
i=1
return cursor.data
#
if __name__=='__main__':
nameList=["Bill","David","Susan","Jane","Kent","Brad"]
print(circle(7,nameList))
#
Kent좋은 웹페이지 즐겨찾기
