더디지만... 꾸준히...

1. 개요 & 알고리즘

지금까지는 진행한 것들은 모두 선형적 자료 구조(Linear structure)"였지만, Tree는 비선형적 자료 구조(Non-linear structure)이며, 2차원적인 구조입니다. 뿌리(root)와 가지(link)로 구성되며, 잎(leaf)들이 달려 있는, 마치 나무의 모양을 거꾸로 뒤집어 놓은 모양입니다.^[각주:1] 

트리 구조는 뿌리 노드로부터 다른 노드에 이르는 경로(path)가 오직 하나 밖에 존재하지 않습니다. 이것은 트리 구조가 그래프 구조와 다른점입니다.

제일 마지막 레벨을 제외하고는 각 레벨의 노드가 꽉 차 있는 이진 트리를 완전한 이진 트리(complete binary tree)라고 하며, 모든 레벨이 꽉 차 있는 이진 나무를 꽉 차 있는 이진 나무(full binary tree)라고 합니다.

네 가지의 나무타기(Tree traverse) 방법이 있는데 이들은 각각 나무의 모든 노드들을 한 번씩 중복없이 순회하는 방법^[각주:2]을 제공합니다.

1. 뿌리를 먼저 타는 방법(전회순회, Preorder traverse)

2. 뿌리를 중간에 타는 방법(중위순회, Inorder traverse)

3. 뿌리를 나중에 타는 방법(후위순회, Postorder traverse)

4. 층별로 타는 방법(층별순회, Level order traverse)

(C로 배우는 알고리즘"^[각주:3])

기본적으로는 뿌리에서 시작해서 알고리즘에 맞는 방식에 따라서 원하는 위치를 찾아가고, 원하는 Node를 찾아서 처리하는 방식입니다.

트리 구조에 대해서는 계속 포스팅을 하게될 것입니다. 일단 수식 나무(Parse tree)^[각주:4]에 대해서 구현해봅니다. 수식 나무에서 외부 노드들은 모두 피연산자들이며, 내부 노드들은 모두 연산자들입니다.

후위 표기법을 입력으로 해서 수식 나무를 구성하는 알고리즘은 다음과 같습니다.

1. 피연산자를 만나면 node를 생성하여 stack에 push한다.

2. 연산자를 만나면 node를 생성하여

2.1 Stack에서 pop한 node를 오른쪽 자식으로 할당하고

2.2 Stack에서 또 pop한 node를 왼쪽 자식으로 할당한다.

2.3 그리고 연산자 node를 stack에 push한다.

3. Stack에서 마지막으로 남은 node가 뿌리 노드가 된다.

수식

((((A+B)*(C-D))/E) +(F*G))

을 후위 표기법으로 변환하면 아래와 같습니다.

A B + C D - * E / F G * +

이것을 위의 알고리즘에 맞춰 Tree로 구성하면 아래와 같습니다.^[각주:5]

2. 동작 코드

def is_legal(self, equation):
    num_of_operator = 0
    size = len(equation)
    step = 0
    while size != step:
        while equation[step] == ' ':
            step += 1
        if self.is_operator(equation[step]):
            num_of_operator -= 1
        else:
            num_of_operator += 1
        if num_of_operator < 1:
            break
        step += 1

    if num_of_operator == 1:
        return True
    else:
        return False

def make_parse_tree(self, equation):
    while len(equation) != 0:
        while equation[0] == ' ':
            del equation[0]
        node = Node()
        node.key = equation[0]
        node.left = self.tail
        node.right = self.tail
        if self.is_operator(equation[0]):
            node.right = self.stack.pop()
            node.left = self.stack.pop()
        self.stack.append(node)
        del equation[0]
    self.head.right = self.stack.pop()

3. 실행 코드

중위 표기법으로 수식을 입력 받아서 후위 표기법으로 변환한 후, 수식 나무를 구성하고, 네 가지의 나무타기 방법으로 수식 나무의 내용을 출력하는 프로그램입니다("C로 배우는 알고리즘" 리스트 3-14 : TREE1.C에 대응) 

중위 표기법을 후위 표기법으로 변경하는 프로그램은 앞선 포스팅^[각주:6]을 그대로 이용하였습니다.

후위 표기법으로 변환한 후에는 수식 나무로 구성한 후, 앞서 Tree를 순회하는 방법 4가지에 따라서 순회하도록 했습니다.

# main() function
if __name__ == "__main__":
    # Change infix notation to postfix notation
    source = "((((A+B)*(C-D))/E)+(F*G))"#input("Please input -> ")
    postfix = Postfix()
    contents = postfix.do_postfix(source)
    print(contents)
    #
    tree = Tree()
    if tree.is_legal(contents) is not True:
        print ("Expression is not legal")
    else:
        tree.make_parse_tree(contents)
        tree.preorder_traverse(tree.head.right)
        print()
        tree.inorder_traverse(tree.head.right)
        print()
        tree.postorder_traverse(tree.head.right)
        print()
        tree.levelorder_traverse(tree.head.right)
        print()

4. Tips

1. Python에서는 Node class와 같은 것도 append 함수로 List에 추가할 수 있었습니다.

@staticmethod
def visit(n):
    print(n.key, end=" ")

3. Queue는 따로 구현하지 않고, Python이 제공하는 Queue를 그대로 사용했습니다.^[각주:8]

5. 코드

1. 개요 & 알고리즘

Linked list로 Queue를 구현하는 경우, FIFO의 특성상 Doubly Linked List로 구현합니다. ("C로 배우는 알고리즘"^[각주:1])

2. 동작 코드

기존 포스팅에서 사용했던 Doubly linked list 코드^[각주:2]를 기본으로, put()과 get()등을 추가합니다. 추가한 put()은 다음과 같습니다.

def put(self, data):
    new_node = Node()
    new_node.key = data
    # Insert new_node in front of tail
    self.tail.prev.next = new_node
    new_node.prev = self.tail.prev
    self.tail.prev = new_node
    new_node.next = self.tail

    return data

get()은 아래와 같이 추가했습니다.

def get(self):
    t = self.head.next
    if t == self.tail:
        print("Queue underflow")
        return False
    data_temp = t.key
    # Remove node
    self.head.next = t.next
    t.next.prev = self.head

    return data_temp

3. 실행 코드

실행 코드는 앞선 포스팅^[각주:3]과 거의 같습니다 ("C로 배우는 알고리즘" 리스트 3-13 : QUEUE2.C에 대응)

# main() function
if __name__ == "__main__":
    queue = QueueWithDoubleLinkedList()

    print("Put 5, 4, 7, 8, 2, 1")
    queue.put(5)
    queue.put(4)
    queue.put(7)
    queue.put(8)
    queue.put(2)
    queue.put(1)
    queue.print_queue()

    print("Get")
    data = queue.get()
    queue.print_queue()
    print("Getting value is ", data)

    print("Put 3, 2, 5, 7")
    queue.put(3)
    queue.put(2)
    queue.put(5)
    queue.put(7)
    queue.print_queue()

    print("Initialize queue")
    queue.clear_queue()
    queue.print_queue()

    print("Now queue is empty, get")
    data = queue.get()
    queue.print_queue()
    print("Getting value is ", data)

5. 코드

1. 개요 & 알고리즘

Queue는 put과 get 동작을 수행하합니다. 자료는 뒤(rear)에 집어 넣고, 앞(front)에서 자료를 얻어내는 FIFO(First Input First Output) 동작을 하는 자료구조입니다.("C로 배우는 알고리즘"^[각주:1]) Python에서는 자체적으로 Queue를 제공^[각주:2]합니다만, 앞선 Stack에 대한 포스팅에서와 마찬가지로 List와 Linked list를 이용해서 Queue를 구현해 보겠습니다.

2. 동작 코드

Python에서 List를 이용해서 Queue를 구현한다면, 다음과 같이도 구현할 수 있어 보입니다.

* get()의 경우, List의 0번째 element를 읽고, del()을 사용해서 0번째 element를 지웁니다^[각주:3]. 이 경우 뒤에 있는 element들이 모두 앞으로 한칸씩 전진합니다.

* put()의 경우, List의 append()를 사용합니다.

* Python은 메모리 제약이 없기 때문에, empty 경우에 대해서만 예외처리하면 됩니다.

하지만, "C로 배우는 알고리즘"에서 구현한대로 List를 이용해서 Circular 동작을 하도록 구현하는 것은 알고리즘을 이해하는데 도움이 될 것으로 생각됩니다.

front와 rear가 같은 경우 empty로 생각하면 되고, front와 rear 사이에는 완충지대를 1개 둡니다. 따라서 front가 rear+1이면 full로 생각합니다.

put()은 아래와 같이 구현합니다.

def put(self, data):
    if (self.rear + 1) % self.max_num_of_list == self.front:
        print("Queue overflow")
        return False
    self.queue[self.rear] = data
    self.rear = (self.rear + 1) % self.max_num_of_list

    return data

get()은 아래와 같이 구현합니다.

def get(self):
    if self.front == self.rear:
        print("Queue underflow")
        return False
    data = self.queue[self.front]
    self.front = (self.front + 1) % self.max_num_of_list

    return data

3. 실행 코드

실행 코드는 아래와 같습니다("C로 배우는 알고리즘" 리스트 3-12 : QUEUE1에 대응) Full인 상황과 empty인 상황도 시험하도록 합니다.

# main() function
if __name__ == "__main__":
    queue = QueueWithArray()
    queue.init_queue()

    print("Put 5, 4, 7, 8, 2, 1")
    queue.put(5)
    queue.put(4)
    queue.put(7)
    queue.put(8)
    queue.put(2)
    queue.put(1)
    queue.print_queue()

    print("Get")
    data = queue.get()
    queue.print_queue()
    print("Getting value is ", data)

    print("Put 3, 2, 5, 7")
    queue.put(3)
    queue.put(2)
    queue.put(5)
    queue.put(7)
    queue.print_queue()

    print("Now queue is full, put 3")
    queue.put(3)
    queue.print_queue()

    print("Initialize queue")
    queue.clear_queue()
    queue.print_queue()

    print("Now queue is empty, get")
    data = queue.get()
    queue.print_queue()
    print("Getting value is ", data)

4. 코드

1. 개요 & 알고리즘

앞선 포스팅^[각주:1]에서 Stack을 이용해서 중위 표기법(Infix notation)으로 표현된 수식을 입력으로 받아서 후위 표기법(Postfix notation)으로 변경했습니다. 이번 포스팅에서는 후위 표기법으로 표시된 수식을 Stack을 이용해서 계산합니다. ("C로 배우는 알고리즘"^[각주:2])

알고리즘은 다음과 같습니다.

1. 숫자를 만나면 숫자는 Stack에 push한다.

2. 연산자를 만나면 Stack에서 pop을 두 번하여 그 두 데이터를 가지고 연산한 다음 그 결과를 Stack에 다시 push한다.

답은 마지막으로 Stack에 남아있는 값이 됩니다.

2. 동작 코드

10 이상의 숫자를 입력 받아서 연산을 할 수도 있습니다. 이에 앞선 포스팅^[각주:3]과 달리 이 부분을 보완했습니다. ("C로 배우는 알고리즘"^[각주:4]에는 이미 있는 내용이었습니다.) 입력된 값에서 숫자가 연속되는 경우 (아래 코드에서는 is_num이 1인 경우)를 처리하기 위한 코드입니다. 숫자의 구분은 space로 합니다.

def do_postfix(self, source):
    dst = []
    stack = []
    is_num = 0
    for i in source:
        # To handle not only single digit but also more than 10
        if '0' <= i <= '9':
            if is_num == 1:
                dst[-1] = i
            else:
                dst.append(i)
            dst.append(' ')
            is_num = 1
            continue

        is_num = 0
        # 이하 생략

후위 표기법으로 Stack에 저장된 값을 읽어서 계산하는 루틴입니다. 숫자가 연속되는 경우 앞의 숫자에 10을 곱한 후 현재 숫자를 더하는 계산을 수행합니다. "C로 배우는 알고리즘"^[각주:5]에 적혀 있듯이 "눈여겨 볼만한 기법"입니다.

def do_calc(self, src):
    stack = []
    i = 0
    while i < len(src):
        ch = src[i]
        if '0' <= ch <= '9':
            t = 0
            while True:
                t = t * 10 + int(ch)
                if '0' <= src[i+1] <= '9':
                    i += 1
                    ch = src[i]
                else:
                    break
            stack.append(t)
        elif ch == '+':
            t = stack.pop() + stack.pop()
            stack.append(t)
        elif ch == '*':
            t = stack.pop() * stack.pop()
            stack.append(t)
        elif ch == '-':
            t = stack.pop()
            t = stack.pop() - t
            stack.append(t)
        elif ch == '/':
            t = stack.pop()
            t = stack.pop() / t
            stack.append(t)
        i += 1

    # Return results which is in stack
    return (stack.pop())

3. 실행 코드

실행 루틴은 다음과 같습니다.

# main() function
if __name__ == "__main__":
    source = input("Please input -> ")
    postfix = Postfix()
    # Change infix notation to postfix notation
    contents = postfix.do_postfix(source)
    # Evaluate expression
    results = postfix.do_calc(contents)
    # Print results
    print(results)

4. 코드

"C로 배우는 알고리즘" 리스트 3-11 : CALC.C에 해당합니다.

https://github.com/steady08/python_beginner_algorithm/blob/master/Chapter_03/Ch_03_12.py

1. 개요 & 알고리즘

일반적으로 사용하는 중위 표기법(Infix notation)으로 표현된 수식을 입력으로 받아서 후위 표기법(Postfix notation)으로 바꾸고, 스택을 이용해서 값을 연산하여 화면에 출력하는 간단한 유틸리티인 CALC를 작성해 봅니다.("C로 배우는 알고리즘"^[각주:1])

후위 표기법으로의 변환은 책만 읽어서는 쉽게 이해되지 않습니다만, 인터넷에는 그림과 더불어 알기 쉽게 설명한 페이지^[각주:2]들이 많으니, 이를 참고하고 따로 설명은 하지 않겠습니다.

후위 표기법을 이용하면 괄호를 사용하지 않아도 되며, 스택의 push, pop 동작으로 수식을 evaluation할 수 있습니다.

이번 페이지에서는 스택을 이용해서 중위 표기법을 후위 표기법으로 변환하도록 하겠습니다. 우선 '(' 연산자는 제알 낮은 우선순위인 0을 주고, +와 - 연산자느 1의 우선순위를 *와 /는 2의 우선순위를 주겠습니다.

알고리즘은 다음과 같습니다.("C로 배우는 알고리즘"^[각주:3])

1. '('를 만나면 스택에 push한다.

2. ')'를 만나면 스택에서 '('가 나올 때까지 pop하여 출력하고 '('는 pop하여 버린다.

3. 연산자를 만나면 스택에서 그 연산자보다 낮은 우선순위의 연산자를 만날 때까지 팝하여 출력한 뒤에 자신을 push한다.

4. 피연산자는 그냥 출력한다.

5. 모든 입력이 끝나면 스택에 있는 연산자들을 모두 pop하여 출력한다.

2. 동작 코드

 기본적인 동작 코드는 다음과 같습니다.

def do_postfix(self, source):
    dst = []
    stack = []
    for i in source:
        if i == '(':
            stack.append(i)
        elif i == ')':
            while stack[-1] != '(':
                t = stack.pop()
                dst.append(t)
            stack.pop()
        elif self.is_operator(i):
            while len(stack) != 0 and self.precedence(stack[-1]) >= self.precedence(i):
                dst.append(stack.pop())
            stack.append(i)
        elif '0' <= i <= '9':
            dst.append(i)

    while len(stack) != 0:
        t = stack.pop()
        dst.append(t)

    return(dst)

3. 실행 코드

사용자로부터 중위 표기법으로 수식을 입력 받아서, 후위 표기법으로 출력하는 실행 코드입니다.

#main() function
if __name__ == "__main__":
    source = input("Please input -> ")
    postfix = Postfix()
    contents = postfix.do_postfix(source)
    print(contents)

4. Tips

1. Python에서 List를 Stack으로 사용하는 경우, 최 상위 element는 List의 맨 마지막 element에 해당하므로 따로 함수를 구현하지 않고, [-1]번째 element를 사용하는 것으로 대신할 수 있습니다. 아래 코드를 참고해 주십시오.

while stack[-1] != '(':

while len(stack) != 0:

5. 코드

https://github.com/steady08/python_beginner_algorithm/blob/master/Chapter_03/Ch_03_11.py

1. 개요 & 알고리즘

"C로 배우는 알고리즘"^[각주:1]에서는 Stack을 배열과 Linked list로 구현하는 방법을 설명하는데, 이번글에서는 Linked list로 Stack을 구현해 봅니다. Stack은 입/출구가 하나이므로 단순 연결 리스트를 사용합니다.

2. 동작 코드

앞서 단순 연결 리스트와 관련해서 사용한 코드를 기초로 진행합니다.^[각주:2]

새로운 Node를 생성해서 linked list의 head쪽에 연결하는 push()를 아래와 같이 구현합니다. Python을 사용하므로 메모리 제한과 관련해서 특별히 고려하지 않았습니다.

def push(self, i):
    new_node = Node(i)
    new_node.key = i
    # Input to head side
    new_node.next = self.head.next
    self.head.next = new_node

    return i

Linked list의 head쪽에서 Node를 빼내오도록 pop()을 아래와 같이 구현합니다. empty case에 대해서도 고려했습니다.

def pop(self):
    # Output to head side
    t = self.head.next
    # Stack empty case
    if t == self.tail:
        return -1

    output = t.key
    self.head.next = t.next

    return output

Python이 자체적으로 메모리를 관리하므로, Stack을 지우는 경우는 단순히 head와 tail을 연결했습니다. 

def clear_stack(self):
    # Python manage memory automatically
    self.head.next = self.tail

3. 실행 코드

구현한 Stack을 사용한 예제 코드는 다음과 같습니다("C로 배우는 알고리즘" 리스트 3-10 : STACK2.C에 대응).

#main() function
if __name__ == "__main__":
    stack = Stack()

    print("Push 5, 4, 7, 8, 2, 1")
    stack.push(5)
    stack.push(4)
    stack.push(7)
    stack.push(8)
    stack.push(2)
    stack.push(1)
    stack.print_stack()

    print("Pop")
    i = stack.pop()
    stack.print_stack()
    print("Poped value is : ", i)

    # Don't test for memory full case

    print("Initialize stack")
    stack.clear_stack()
    stack.print_stack()

    print("Now stack is empty, pop")
    i = stack.pop()
    stack.print_stack()
    print("Poped value is : ", i)

4. 코드

1. 개요 & 알고리즘

Stack은 LIFO(Last In First Out)의 자료 구조로, 자료를 Stack에 넣는 push 동작과 자료를 가져오는 pop 동작으로 구성됩니다.^[각주:1] "C로 배우는 알고리즘"^[각주:2]에서는 배열과 Linked list로 구현하는 방법을 설명하는데, 이번글에서는 배열 관련 내용을 정리합니다.

2. 동작 코드

Python에서는 List 자체가 Stack의 기능을 제공합니다. 즉, push 동작은 append()를 사용하면 되며, pop은 pop()을 사용하면 됩니다.^[각주:3]

>>> stack = [3, 4, 5]
>>> stack.append(6) #6을 push
>>> stack.append(7) #7을 push
>>> stack
[3, 4, 5, 6, 7]
>>> stack.pop()
7
>>> stack
[3, 4, 5, 6]
>>> stack.pop()
6
>>> stack.pop()
5
>>> stack
[3, 4]
>>> stack.pop()
4
>>> stack.pop()
3
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
IndexError: pop from empty list
>>>

3. 실행 코드

Python이 제공하는 기능을 그대로 사용해도 되겠지만, 조금 더 사용성을 고려해서 코드를 추가/구현할 수도 있겠습니다.^[각주:4]

1. 개요 & 알고리즘

간단한 텍스트뷰어를 이중 연결 리스트를 응용해서 작성해 봅니다. 이중 연결 리스트를 이용해서 텍스트 파일을 읽는 방법은 아래와 같습니다. ("C로 배우는 알고리즘"^[각주:1])

1. 파일을 연다.

2. 전체 라인 수를 0으로 초기화한다.

3. 파일의 끝에 도달할 때까지

3.1 파일에서 한 라인을 읽어서 buf에 저장한다.

3.2 buf에 저장된 문자의 길이가 80을 넘으면 자른다. (?)

3.3 새로운 노드를 생성하고 여기에 buf에 저장된 문자열을 복사한다.

3.4 새로 생성된 노드를 이중 연결 리스트의 제일 뒤에 삽입한다.

3.5 전체 라인 수를 증가시킨다.

3.6 3으로 돌아간다.

4. 파일을 닫고 끝낸다.

텍스트 파일을 보여 주는 동작은 PGUP, PGDN, ESC 키를 이용해서 동작합니다.

2. 동작 코드

텍스트 파일의 각 라인을 읽어서 double linked list를 구성하기 위한 기본적인 class는 다음과 같습니다.

class LineBufferNode:
    def __init__(self, line=""):
        self.line = line
        self.next = -1
        self.prev = -1

파일명을 인수로 받아서, 파일을 읽어서 double linked list를 구성하는 함수는 다음과 같습니다.

def load_file(self, file_name):
    fd = open(file_name, 'r')
    self.file_name = file_name
    self.total_line_num = 0

    print("File loading...")
    while (True):
        line_buffer = fd.readline()
        if not line_buffer:
            break

        new_line_buffer_node = LineBufferNode(line_buffer)
        new_line_buffer_node.prev = self.tail.prev
        new_line_buffer_node.next = self.tail
        self.tail.prev.next = new_line_buffer_node
        self.tail.prev = new_line_buffer_node

        self.total_line_num += 1

    fd.close()

파일에서 한 라인의 텍스트를 읽기 위해서 readline()함수를 사용했고, return 값이 없는 경우 EOF(End Of File)로 처리했습니다.^[각주:2], ^[각주:3]

Display하는 문자열을 반전하기 위해서 "curses.A_REVERSE"를 사용했습니다.

def show_header(self):
    string = " Text Viewer : " + self.file_name
    self.stdscr.addstr(0, 0, string, curses.A_REVERSE)
    self.stdscr.refresh()

하나의 페이지를 보이기 위해서 아래와 같은 함수를 작성했습니다. 윈도우의 command 창의 높이는 일정하지 않고 command 창을 변경하면 높이 값도 변경됩니다. 이에 command창의 라인수를 특정하지 않고 "try ... except"를 이용해서 error가 발생하기전까지는 계속 정상 출력하도록 했습니다.^[각주:4]

def show_page(self, line_node):
    # Clear screen
    self.stdscr.clear()
    # Show header
    self.show_header()

    line_num = 1
    # Can show total 29 lines (1 line for header and 28 lines for context
    while line_node != self.tail:
        try:
            self.stdscr.addstr(line_num, 0, line_node.line)
        except:
            break

        line_node = line_node.next
        line_num += 1

    self.stdscr.refresh()

    return line_num

키보드의 키 입력을 받아서 처리하도록 아래와 같이 작성했습니다. stdscr.getch()를 이용합니다. stdscr.getch()의 출력값은 integer입니다.print()를 이용해서 입력 받은 key 값을 출력하려면 chr(stdscr.getch()의 출력값)을 이용하면 됩니다.^[각주:5]

def key_proc(self):
    curses.noecho()
    self.stdscr.keypad(1)

    line_node = self.head.next
    line_num = self.show_page(line_node)

    while True:
        key = self.stdscr.getch()
        if key == curses.KEY_PPAGE: # Page Up
            line_node = self.move_line(-1*line_num, line_node)
            self.show_page(line_node)
        if key == curses.KEY_NPAGE: # Page Down
            line_node = self.move_line(line_num, line_node)
            self.show_page(line_node)
        if key == ord('q') or key == ord('Q'):
            break
        self.stdscr.refresh()

예를 들면 아래 코드를 사용해서 화면에 입력 받은 key를 출력할 수 있습니다.

self.stdscr.addstr(0, 0, chr(key))

3. 실행 코드

실행코드는 다음과 같습니다. ("C로 배우는 알고리즘" 리스트 3-8 : TVIEW.C에 대응)

# main() function
if __name__ == "__main__":
    # Get file name to read
    file_name = input("Please input file name to load -> ")

    # Initialize TextFileViewer class
    text_viewer = TextFileViewer()
    # Read file
    text_viewer.load_file(file_name)
    # Handle key input
    text_viewer.key_proc()

4. 코드

1. 개요 & 알고리즘

단순 연결 리스트를 이용하면 작은 데이터베이스를 구축할 수 있습니다. 여기서는 데이터베이스까지는 아니지만 명함을 입력하고, 삭제하고, 검색하고, 리스팅하고, 디스크에 저장하고, 디스크에서 읽어들이는 등의 기능을 가진 간단한 프로그램을 작성해 봅니다. ("C로 배우는 알고리즘"^[각주:1]) - 프린트 출력 기능은 제외하였다.

1. 저장 필드로 이름, 회사, 전화번호만 갖는다.

2. 메뉴는 다음과 같다.

   2.1. 명합을 입력 받는다.

   2.2. 이름으로 찾아서 명함을 삭제한다

   2.3. 이름으로 명함을 검색한다.

   2.4. 디스크에서 명함을 읽는다.

   2.5. 디스크에 명함을 저장한다.

   2.6. 명함들의 리스트를 화면에 보여준다.

   2.7. 프로그램을 끝낸다.

2. 동작 코드

기본적인 Node의 정의는 다음과 같습니다.

class NameCardNode:
    def __init__(self, name, corp, tel):
        self.name = name
        self.corp = corp
        self.tel = tel
        self.next = -1

실제 함수들을 포함하는 NameCardList classs의 초기화는 다음과 같습니다.

class NameCardList:
    def __init__ (self):
        self.head = NameCardNode("", "", -1)
        self.tail = NameCardNode("", "", -1)
        self.head .next = self.tail
        self.tail.next = self.tail

inputCard(name, corp, tel), deleteCard(name), deleteNodeAll(), searchCard(name), printCard(), printCardAll()함수들도 작성했습니다.

노드들을 파일로 저장하는 함수는 다음과 같이 작성했습니다.

def saveCard(self, fileName):
    fd = open(fileName, 'wb')
    t = self.head.next
    while t != self.tail:
        # Use pickle to save "object" itself
        pickle.dump(t.name, fd)
        pickle.dump(t.corp, fd)
        pickle.dump(t.tel, fd)
        t = t.next
    fd.close()

파일로부터 노드를 다시 읽어오는 함수는 다음과 같이 작성했습니다.

def loadCard(self, fileName):
    try:
        fd = open(fileName, 'rb')
    except FileNotFoundError:
        print("Error : \"%s\" file can't be found" % fileName)
        return False

    while True:
        # Use pickle to load "object" itself
        try:
            name = pickle.load(fd)
            corp = pickle.load(fd)
            tel = pickle.load(fd)
            self.inputCard(name, corp, tel)
        except EOFError:
            break
    fd.close()
    return True

마지막으로, 간단한 CLI(Command Line Interface) 명령을 수행하기 위한 메뉴는 selectMenu()로 다음과 같이 작성했습니다.

def selectMenu():
    print("")
    print("Namecard Manager")
    print("-------------------------------------")
    print("1. Input  Namecard")
    print("2. Delete Namecard")
    print("3. Search Namecard")
    print("4. Load   Namecard")
    print("5. Save   Namecard")
    print("6. List   Namecard")
    print("7. End    Program")
    while(True):
        print("")
        # Try to handle only integer
        try:
            i = int(input("Select operation -> "), 10)
        except ValueError:
            pass
        else:
            if i > 0 and i < 8:
                break
    return i

3. 실행 코드

selectMenu() 함수를 호출해서 명령을 입력 받는 실행 코드는 아래와 같이 작성했습니다. ("C로 배우는 알고리즘" 리스트 3-7 : NAMECARD.C에 대응)

# main() function
if __name__ == "__main__":
    fileName = "Namecard.dat"
    # Initialize namecard class
    nameCard = NameCardList()
    while(True):
        menuNum = selectMenu()
        # End program
        if menuNum == 7:
            break

        # Input namecard
        if menuNum == 1:
            print("Input namecard menu : ")
            name = input("     Input name : ")
            corp = input("     Input corporation : ")
            tel = input("     Input telephone number : ")
            if name == "":
                print("Name in mandatory. Please input name.")
                continue
            else:
                nameCard.inputCard(name, corp, tel)

        # Delete namecard
        elif menuNum == 2:
            name = input("Input name to delete ->")
            results = nameCard.deleteCard(name)
            if results is None:
                print("Can't find that name.")

        # Search namecard
        elif menuNum == 3:
            name = input("Input name to search ->")
            results = nameCard.searchCard(name)
            if results is None:
                print("Can't find that name.")
            else:
                nameCard.printCard(results)

        # Load namecard
        elif menuNum == 4:
            if nameCard.loadCard(fileName) == True:
                print("Load namecard done!!")

        # Save namecard
        elif menuNum == 5:
            nameCard.saveCard(fileName)
            print("Save namecard done!!")

        # List namecard
        elif menuNum == 6:
            nameCard.printCardAll()

4. Tips

1. saveCard()를 사용해서 파일에 데이터를 저장하거나, loadCard()를 사용해서 파일에서 데이터를 로드할 때, Python이 제공하는 pickle 모듈을 사용했습니다. 위 예제에서와 같이 각각 pickle.dump()와 pickle.load()를 사용해서 매우 손쉽게 처리할 수 있었습니다.(^[각주:2]), (^[각주:3]), ()

2. 실제 코드를 보면,  try ~ else 형식의 예외 처리 방법^[각주:4]이 정리되어 있습니다. Integer로 입력을 받을 때등등에 예외 처리를 추가했습니다. 가장 기본적인것에 대해서, 시험을 하면서 발생한 경우에 대해서만 추가했습니다.

예를 들면, while() 내에서 데이터를 load 하는 pickle.load()를 계속 실행하는 경우, save된 데이터를 모두 읽고 나서 아래와 같은 에러가 발생했습니다. 이때 EOFError에 대해서 예외 처리 코드(try...except...)를 추가하면 동작했습니다.

    name = pickle.load(fd)
EOFError: Ran out of input

5. 코드

1. 개요 & 알고리즘

단순 연결 리스트와 달리 이중 연결 리스트는 다음 노드를 가리키는 링크와 이전 노드를 가리키는 링크 두 가지를 가져서 바로 이전 노드에 접근할 수 있다는 차이점이 있습니다. ("C로 배우는 알고리즘"^[각주:1])

2. 동작 코드

지금까지는 Class에서 Node에 대한 정보를 return하지 않고, Class 내부적으로만 처리하도록 하였으나, 이번에는 Node 정보를 Class 외부에서 입력 받거나 출력할 수 있도록 진행합니다.

Doubly Linked List는 링크로 next 이외에 prev를 갖게 됩니다.

class Node:
    def __init__(self, key=-1):
        self.key = key
        self.prev = None
        self.next = None

최초 Class 생성시, head와 tail 노드를 생성하고, 각각이 prev와 next로 가리키도록 합니다.

# Class for doubly linked list
class LinkedList:
    def __init__(self):
        self.head = Node(-1)
        self.tail = Node(-1)
        self.head.next = self.tail
        self.head.prev = self.head
        self.tail.next = self.tail
        self.tail.prev = self.head

List에 포함된 노드 t 앞에 key 값을 갖는 새로운 노드를 삽입하는 함수는 다음과 같습니다.

# Insert new node ahead of tNode
def insert_dnode_ptr(self, key, tNode):
    if tNode == self.head:
        return None
    iNode = Node(key)
    tNode.prev.next = iNode
    iNode.prev = tNode.prev
    tNode.prev = iNode
    iNode.next = tNode

특정 노드 t를 지우는 함수는 다음과 같습니다.

def delete_dnode_ptr(self, tNode):
    # Can't remove head and tail
    if tNode == self.head or tNode == self.tail:
        return 0
    tNode.prev.next = tNode.next
    tNode.next.prev = tNode.prev

    return tNode

특정 Key 값을 갖는 노드를 찾는 함수는 다음과 같습니다. Key 값을 갖는 노드를 찾지 못하면 "False"를 return 합니다.

def find_node(self, key):
    s = self.head.next
    while s.key != key and s != self.tail:
        s = s.next
    if s == self.tail:
        return False
    else:
        return s

3. 실행 코드

Doubly Linked List 관련 실행 코드는 다음과 같습니다. ("C로 배우는 알고리즘" 리스트 3-6 : LINKED2.C에 대응)

#main() function
if __name__ == "__main__":
    list = LinkedList()
    list.ordered_insert(10)
    list.ordered_insert(5)
    list.ordered_insert(8)
    list.ordered_insert(3)
    list.ordered_insert(1)
    list.ordered_insert(7)
    list.ordered_insert(8)

    print("Initial linked list is")
    list.print_all()

    print()
    findNumber = 4
    if list.find_node(findNumber) != False:
        print("Finding %d is successful" % findNumber)
    else:
        print("Finding %d is unsuccessful" % findNumber)

    print()
    findNumber = 5
    t = list.find_node(findNumber)
    if t != False:
        print("Finding %d is successful" % findNumber)
    else:
        print("Finding %d is unsuccessful" % findNumber)

    print()
    print("Inserting 7 before 5")
    list.insert_dnode_ptr(7, t)
    list.print_all()

    print()
    findNumber = 3
    t = list.find_node(findNumber)
    if t != False:
        print("Finding %d is successful and Deleting" % findNumber)
        list.delete_dnode_ptr(t)
    else:
        print("Finding %d is unsuccessful" % findNumber)
    list.print_all()

    print()
    findNumber = 10
    t = list.find_node(findNumber)
    if t != False:
        print("Finding %d is successful" % findNumber)
        print("Inserting 2 before %d" % findNumber)
        list.insert_dnode_ptr(2, t)
    else:
        print("Finding %d is unsuccessful" % findNumber)
    list.print_all()

    print()
    findNumber = 2
    t = list.find_node(findNumber)
    if t != False:
        print("Finding %d is successful and Deleting" % findNumber)
        list.delete_dnode_ptr(t)
    else:
        print("Finding %d is unsuccessful" % findNumber)
    list.print_all()

    print()
    findNumber = 1
    t = list.find_node(findNumber)
    if t != False:
        print("Finding %d is successful and Deleting" % findNumber)
        list.delete_dnode_ptr(t)
    else:
        print("Finding %d is unsuccessful" % findNumber)
    list.print_all()

    print()
    print("Inserting 15 at last")
    list.insert_dnode_ptr(15, list.head.next)
    list.print_all()

    print()
    print("Delete all node")
    list.delete_all()
    list.print_all()

4. Tips

1. Python의 class는 특별히 public, private, protected등의 keyword를 제공하지 않으며, 일반적으로 class내에 선언된 변수들은 외부에서 access가 가능합니다^[각주:2]. 앞으로는 이를 그대로 사용하기로 합니다.

5. 코드