배고픈 개발자 이야기
1.linked_list & queue & stack & hash (feat.PYTHON) 본문
728x90
1.linked_list
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
dummy = Node("dummy")
self.head = dummy
self.tail = dummy
self.current = None
self.before = None
self.num_of_data = 0
def append(self, data):
new_node = Node(data)
self.tail.next = new_node
self.tail = new_node
self.num_of_data += 1
def delete(self):
pop_data = self.current.data
if self.current is self.tail:
self.tail = self.before
self.before.next = self.current.next
self.current = self.before # 중요 : current가 next가 아닌 before로 변경된다.
self.num_of_data -= 1
return pop_data
def first(self):
if self.num_of_data == 0: # 데이터가 없는 경우 첫번째 노드도 없기 때문에 None 리턴
return None
self.before = self.head
self.current = self.head.next
return self.current.data
def next(self):
if self.current.next == None:
return None
self.before = self.current
self.current = self.current.next
return self.current.data
def search(self, data):
temp = self.head
found = False
while temp and found is False:
if temp.data == data :
found = True
else:
temp = temp.next
if found:
return "found " + str(temp.data)
else :
return "Not Found"
def size(self):
return self.num_of_data
if __name__ == '__main__':
l_list = LinkedList()
l_list.append(5)
l_list.append(2)
l_list.append(1)
l_list.append(2)
l_list.append(7)
l_list.append(2)
l_list.append(11)
print('first :', l_list.first()) # first : 5
print('next :', l_list.next()) # next : 2
print('size :', l_list.size()) # size : 7
print('delete :', l_list.delete()) # delete : 2
print('size :', l_list.size()) # size : 6
print('current:', l_list.current.data)# current: 5
print('tail:', l_list.tail.data) # tail: 11
print('first :', l_list.first()) # first : 5
print('next :', l_list.next()) # next : 1
print('next :', l_list.next()) # next : 2
print('next :', l_list.next()) # next : 7
print('search :', l_list.search(11))
# 전체 노드 data 표시하기
data = l_list.first()
if data:
print(data, end=' ')
while True:
data = l_list.next()
if data:
print(data, end= ' ')
else:
break
# 5 1 2 7 2 11
# 2만 삭제하기
data = l_list.first()
if data and data == 2:
l_list.delete()
print('deleted', end=' ')
else:
print(data, end= ' ')
while True:
data = l_list.next()
if data == 2:
l_list.delete()
print('deleted', end=' ')
elif data:
print(data, end=' ')
else:
break
# 5 1 deleted 7 deleted 11
2.queue
FIFO 구조 list로 구현함
node로 구현 : https://wayhome25.github.io/cs/2017/04/18/cs-21/
강의노트 20. 자료구조 - queue (큐) · 초보몽키의 개발공부로그
패스트캠퍼스 컴퓨터공학 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인공부 후 자료를 남기기 위한 목적임으로 내용 상에 오류가 있을 수 있습니다.
wayhome25.github.io
class Queue(list):
# enqueue == > insert 관용적인 이름
enqueue = list.append
# dequeue == > delete
def dequeue(self):
return self.pop(0)
def is_empty(self):
if not self:
return True
else:
return False
def peek(self):
return self[0]
if __name__ == '__main__':
q = Queue()
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
q.enqueue(4)
q.enqueue(5)
while not q.is_empty():
print(q.peek(), end= ' ')
print(q.dequeue()) # 1 2 3 4 5
3.stack
LIFO 구조 list로 구현함
node로 구현 : https://wayhome25.github.io/cs/2017/04/18/cs-20/
추상구조, 배열, linked list 구현 : https://github.com/keon/algorithms/blob/master/algorithms/stack/stack.py
class Stack(list):
push = list.append # Insert
# Delete - 내장 pop 메소드 활용
def is_empty(self): # 데이터가 없는지 확인
if not self:
return True
else:
return False
def peek(self): # 최상단 데이터 확인
return self[-1]
if __name__=="__main__":
s = Stack()
s.push(1)
s.push(2)
s.push(3)
while s:
data = s.pop()
print(data, end=' ') # 3 2 1
4.hash
class HashTable(object):
MINIMUM_BUCKETS = 4 # 최소 버킷 갯수
BUCKET_SIZE = 5 # 버킷당 값의 최대 갯수
def __init__(self, capacity=MINIMUM_BUCKETS*BUCKET_SIZE):
self.size = 0
self.threshold = capacity # 4*5
self.buckets = [[] for _ in range(capacity//self.BUCKET_SIZE)] # 이중 list, 버킷 수만큼 빈 버킷생성
def push(self, key, value): # key, value값
bucket = self.hash(key)
# print("push 버킷: ",bucket)
# hash code % 버킷수 나머지값 : 버킷 인덱스 번호
for n, element in enumerate(self.buckets[bucket]): # 버킷 탐색
if element['key'] == key: # 이미 동일한 key값이 있는지 확인
element['value'] = value # 해당 key의 value값 갱신
self.buckets[bucket][n] = element # 확인한 key, value를 해당 버킷의 인덱스에 저장
return
else:
self.buckets[bucket].append({'key': key, 'value': value}) # 동일한 key값이 없을 경우 key와 value값 버킷에 추가
self.size += 1 # 현제 크기 업데이트
if self.size == self.threshold: # 크기가 threshold와 같아질 경우 resize
self.resize()
def get(self, key):
bucket = self.hash(key)
for element in self.buckets[bucket]: # get할 key값을 찾아 value를 반환
if element['key'] == key:
return element['value']
raise KeyError("No such key '{0}'!".format(key))
def pop(self, key):
bucket = self.hash(key)
for n, element in enumerate(self.buckets[bucket]): # pop할 key값을 찾아 del 후 size -1
if element['key'] == key:
del self.buckets[bucket][n]
self.size -= 1
return
raise KeyError("No such key '{0}'!".format(key)) # 찾는 key값이 없을 경우 raise
def hash(self, key):
return hash(key) % len(self.buckets) # hash code를 버킷수로 나눈 나머지값 반환
def contains(self, key):
bucket = self.hash(key)
for element in self.buckets[bucket]: # 해당 key값이 있는지 boolean으로 반환
if element['key'] == key:
return True
return False
def __getitem__(self, key):
return self.get(key)
def __setitem__(self, key, value):
return self.push(key, value)
def __delitem__(self, key):
return self.pop(key)
def __len__(self):
return self.size
def is_empty(self):
return self.size == 0
def resize(self): # capacity 20, size = 20이 되었을 경우
# 버킷사이즈 5, 미니멈 버킷 4
capacity = self.size / self.BUCKET_SIZE * 2 # 20/5*2 = 8
if capacity >= self.MINIMUM_BUCKETS: # 8 >= 4
old = self.buckets # 이전 버킷 2중 list 값 저장
self.buckets = [[] for _ in range(capacity)] # resize한 크기 4->8로 버킷 재생성
for n in range(len(self.buckets)): # 새로 만든 버킷에 이전값 대입
self.buckets[n] = old[n]
self.rehash() # 대입 후 rehash
def rehash(self):
for n, bucket in enumerate(self.buckets):
for m, element in enumerate(bucket):
new_bucket = self.hash(element['key']) # hash code 재생성 후 나머지 값
self.buckets[new_bucket].append(element) # 다시 버킷에 저장
del self.buckets[n][m] # 기존값 제거
def main():
table = HashTable() # hash table 객체 생성
table.__setitem__("one", 1)
table.push("two", 2)
table.push("three", 3)
table.push("four", 4)
table["four"] = 4
table["five"] = 5
table.push("six", 6)
table.push("seven", 7)
table.push("eight", 8)
print(len(table))
print(table.is_empty())
print(table.__getitem__("two"))
table["one"] = 123
print(table["one"])
print(table["two"])
table.pop("three")
print(table["two"])
table.pop("four")
table.pop("five")
print(len(table))
print(table["two"])
table.__delitem__("one")
table.__delitem__("two")
table.__delitem__("six")
print(table.is_empty())
print(table["seven"])
table.pop("seven")
table.pop("eight")
print(len(table))
print(table.is_empty())
if __name__ == '__main__':
main()'전산학 > 자료구조' 카테고리의 다른 글
| 0.heap & priorityQ (feat.PYTHON) (0) | 2019.09.14 |
|---|
Comments