01.25(12일차)
자료구조
컴퓨터에 처리할 자료를 효율적으로 관리하기위해 구조화
--리스트--
데이터에 순서를 매겨 늘어놓은 자료구조
--연결리스트--
데이터들이 각각의 공간을 할당 받고,데이터 사이의 연결 고리가 만들어지는 구조
① 1부터 5까지 데이터가 순서대로 나열되고 각 데이터가 화살표로 연결되어있다. -> 건너 뛰거나 되돌아가면 안 된다.
② 연결리스트의 각각의 원소(element)->클래스의 객체라고 보면된다. 노드와 원소는 같은말이다.
③ 노드는 데이터와 뒤쪽 노드를 가리키는(참조하는) 포인터를 가지고 있다.
④ 바로 앞의 노드를 앞쪽 노드(predecessor node), 바로 뒤에 있는 노드를 뒤쪽 노드(successor node)라고 한다
--연결리스트 추가--
추가하고 싶은 위치의 앞쪽 노드의 포인터가 추가 노드를 가리키도록 하고,
추가 노드의 포인터가 뒤쪽 노드를 가리키도록 한다
--스택--
데이터 구조의 하나로서 데이터를 1열로 나열하지만,
데이터가 입력되면 입력되는 순서대로 쌓고, 나중에 들어온 것부터 먼저 사용하는 자료구조.
이러한 구조를 후입선출(LIFO(last in first out))이라 한다
--스택-- 예시1
class Mystack:
def __init__(self):
self.li = []
def push(self, item):
self.li.append(item)
def pop(self):
if not self.is_empty():
return self.li.pop()
else:
return None # 스택이 비어있을 때 pop 시도시 None 반환
def peek(self):
if not self.is_empty():
return self.li[-1]
else:
return None # 스택이 비어있을 때 peek 시도시 None 반환
def is_empty(self):
return len(self.li) == 0
# Mystack 클래스의 인스턴스 생성
stack_instance = Mystack()
# 1부터 5까지의 값을 스택에 push
for i in range(1, 6):
stack_instance.push(i)
# 스택이 비어있지 않은 동안, 값을 출력하고 pop
while not stack_instance.is_empty():
print(stack_instance.peek())
stack_instance.pop()
--큐--
데이터 구조의 하나로서 데이터를 1열로 나열하고,데이터가 입력되면 입력되는 순서대로 쌓고,
먼저 들어온 것부터 먼저 사용하는 구조이다.
이러한 구조를 선입선출(FIFO(First In First Out))이라 한다.
--큐--예시1
class MyQueue:
def __init__(self):
self.queue = []
def enqueue(self, item):
self.queue.append(item)
def dequeue(self):
if not self.is_empty():
return self.queue.pop(0)
else:
return None # 큐가 비어있을 때 dequeue 시도시 None 반환
def front(self):
if not self.is_empty():
return self.queue[0]
else:
return None # 큐가 비어있을 때 front 시도시 None 반환
def is_empty(self):
return len(self.queue) == 0
# MyQueue 클래스의 인스턴스 생성
queue_instance = MyQueue()
# 1부터 5까지의 값을 큐에 enqueue
for i in range(1, 6):
queue_instance.enqueue(i)
# 큐가 비어있지 않은 동안, 값을 출력하고 dequeue
while not queue_instance.is_empty():
print(queue_instance.front())
queue_instance.dequeue()
--자료구조--예시1
# 연결 리스트를 구성하는 클래스는 데이터+다음 노드의 포인터
class Node:
def __init__(self, data, next = None) :
self.data = data
self.next = next
# 연결 리스트를 만든다. node1 ~ node5 그리고 연결포인터 구성
def init() :
global node1
node1 = Node(1)
node2 = Node(2)
node3 = Node(3)
node4 = Node(4)
node5 = Node(5)
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5
# 연결리스트의 데이터를 출력한다.
def print_list() :
global node1
node = node1
while node :
print(node.data)
node = node.next
print()
# 연결 리스트에 데이터를 추가한다.
def insert(ins_data) :
global node1
new_node = Node(ins_data)
new_node.next = node1
node1 = new_node
# 구성된 리스트에서 데이터를 지우고, 나머지를 연결한다.
def delete(del_data) :
global node1
pre_node = node1
next_node = pre_node.next
if pre_node.data == del_data :
node1 = next_dode
del pre_node
return
while next_node :
if next_node.data == del_data :
pre_node.next == next_node.next
del next_node
break
pre_node = next_node
next_node = next_node.next
# 연결 리스트에서 검색한다.
def search(data) :
global node1
node = node1
cnt = 1
while node :
if(node.data == data) :
print("%d번째 데이터" % cnt)
return 1
cnt += 1
node = node.next
return -1
n = 3
init()
delete(2)
insert(9)
print_list()
if 0 > search(n) :
print("검색하는 데이터가 존재하지 않습니다.")
알고리즘-
A에서 B까지 가는방법들 (효율적이여야한다.)