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

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. 코드

1. 개요 & 알고리즘

Circular linked list는 Simple linked list와 같은 노드 구조를 가지고 있지만, 제일 마지막 노드가 가장 처음의 노드를 가리키고 있다는 점이 다릅니다. 즉, Circular linked list에는 tail이라는 개념이 없습니다. ("C로 배우는 알고리즘"^[각주:1])

Circular linked list를 이용하는 문제는 "요셉의 문제"입니다. A에서 J까지 10명이 시계 방향으로 원모양을 만들어 순서대로 앉아 있다고 할 때, A부터 시작해서 4명 간격으로 사람을 그 원에서 뽑아낸다고 하면 그 순서는 어떻게 될까하는 문제입니다. 이 경우는 A, E, I, D, J, G, F, H, C, B의 순이됩니다.

2. 동작 코드

기본적인 코드는 Simple linked list와 거의 유사하지만, LinkedList class 초기화시 tail을 정의하지 않았습니다.

class LinkedList:
    def __init__(self, key):
        self.head = Node()
        self.head.key = key
        self.head.next = self.head

추가로 delete node 부분에서 header를 삭제하는 경우에 대해 보완을 했습니다.

def delete_node(self, key):
    p = self.head
    s = p.next
    # If we need to delete head
    if key == p.key:
        if s == self.head:
            return -1
        else:
            while True:
                if s.next == self.head:
                    s.next = self.head.next
                    self.head = s.next
                    return key
                else:
                    s = s.next
    # delete except head node
    while s.key != key and s != self.head:
        p = p.next
        s = p.next
    if s != self.head:
        p.next = s.next
        return key
    else:
        return -1

"요셉의 문제"도 LinkedList class내에서 수행하도록 했습니다.

def josephus(self, step):
    s = self.head
    while(True):
        print(s.key, "->", end=" ")
        self.delete_node(s.key)
        for i in range(step):
            s = s.next
        if s == self.head:
            print(s.key)
            break

3. 실행 코드

실행 코드는 LinkedList class를 정의하고, node를 입력 받은 수 만큼 생성한 후 "요셉의 문제"를 풀도록 하였습니다. ("C로 배우는 알고리즘" 리스트 3-5 : JOSEPH.C에 대응)

#main() function
if __name__ == "__main__":
    totalcount = int(input("Input total node's count : "))
    step = int(input("Input step for josephus's problem : "))

    list = LinkedList('A')
    # Already insert 'A' for header. So we only need to insert_node (totalcount-1)
    for i in range(totalcount-1):
        list.insert_node(chr(ord('B')+i))
    list.josephus(step)

4. Tips

1. LinkedList를 생성하면서 head node를 하나 생성하므로, 실제 insert_node()는 입력 받은 갯수-1만큼만 수행합니다.

5. 코드