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

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

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

1. 사전 지식

"C로 배우는 알고리즘"^[각주:1]에 설명된 Linked List에 대한 주요 내용은 다음과 같습니다.

1. Linked List는 Node와 Link로 구성됨

2. Linked List는 Link의 개수와 연결 상태에 따라 "단순 연결 리스트", "환형 연결 리스트", "이중 연결 리스트", "이중 환형 연결 리스트"등이 있음

2. Simple Linked List

• Simple Linked List는 "정보를 저장하는 Node"와 "바로 다음 Node를 가리키는 Link" 하나로 구성됩니다.
• Linked List의 최대 장점은 재배열(rearrangement)이 쉽다는 것입니다.
• 관리를 위해서 Head Node와 Tail Node를 가집니다.

2. 동작 코드

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

Global로 head와 tail을 선언해서 작성해도 되겠지만, class 내에서 처리할 수 있도록 LinkedList라는 class를 작성했습니다. "C로 배우는 알고리즘"에 있듯이 head는 tail을, tail을 tail을 next로 지정하였습니다.

key 입력에 따라 정렬한 상태로 입력할 수 있도록 ordered_insert() 함수와 해당 key 값의 node를 지우고, 모든 node들을 print하는 함수를 작성하였습니다.

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

    def ordered_insert(self, key):
        newNode = Node(key)
        p = self.head
        s = p.next
        while s.key <= key and s != self.tail:
            p = p.next
            s = p.next
        p.next = newNode
        newNode.next = s

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

    def print_node(self):
        p = self.head
        p = p.next
        print("Start", end=" ")
        while p != self.tail:
            print(p.key, "->", end=" ")
            p = p.next
        print("End")

3. 실행 코드

Simple Linked List 함수들의 실행 코드는 아래와 같습니다. ("C로 배우는 알고리즘" 리스트 3-4 : LINKED1.C에 대응)

ordered_insert() 함수로 임의의 integer type의 key값을 갖는 node들을 생성한 후 print합니다. 그리고 하나의 node를 그리고 다시 print합니다.

#main() function
if __name__ == "__main__":
    list = LinkedList()
    list.ordered_insert(7)
    list.ordered_insert(8)
    list.ordered_insert(1)
    list.ordered_insert(9)
    list.print_node()

    list.delete_node(7)
    list.print_node()

5. 코드