問題2.1

世界で闘うプログラミング力を鍛える150問

昨日、作りながら寝落ちしたので、昼休みに残り完成。
時間切れなので、発展問題は検討すらしてないです。

問題

ソートされていない連結リストから、重複する要素を削除するコードを書いてください。

発展問題

もし、一時的なバッファが使用できないとすれば、どうやってこの問題を解きますか？

pylist.py (短方向連結リスト)

#encoding: utf-8


class Cell:
    '''
    リストを構成するセルを表すクラス
    >>> cell = Cell(5)
    >>> print cell.get_data()
    5
    >>> print cell.get_next()
    None
    >>> cell.set_data('a')
    >>> print cell.get_data()
    a
    >>> cell.set_next(10)
    >>> print cell.get_next()
    10
    '''
    def __init__(self, data, next=None):
        self.data = data
        self.next = next

    # セルのデータ取得
    def get_data(self):
        return self.data

    # セルが指す次のセルのポインタ取得
    def get_next(self):
        return self.next

    # セルのデータを更新
    def set_data(self, data):
        self.data = data

    # セルが指す次のセルのポインタ更新
    def set_next(self, next):
        self.next = next


class LinkedList:
    '''
    連結リストクラス
    >>> linked_list = LinkedList()
    >>> linked_list.get_top()
    >>> linked_list.insert(0, 100)
    >>> print linked_list.index(100)
    0
    >>> linked_list.get_top().get_data()
    100
    >>> linked_list.insert(1, 200)
    >>> print linked_list.index(200)
    1
    >>> linked_list.insert(1, 150)
    >>> print linked_list.index(150)
    1
    >>> print linked_list.index(200)
    2
    >>> linked_list.delete(2)
    True
    >>> linked_list.index(200)
    -1
    >>> linked_list.index(150)
    1
    >>> linked_list.delete(0)
    True
    >>> linked_list.index(150)
    0
    >>> linked_list.delete(0)
    True
    >>> linked_list.delete(0)
    False
    '''
    def __init__(self):
        self.top = None

    # リストの先頭セルを取得
    def get_top(self):
        return self.top

    # dataに示すデータがリストの何番目かを取得
    def index(self, data):
        offset = 0
        cell = self.top
        while cell:
            if cell.get_data() == data:
                return offset
            offset += 1
            cell = cell.get_next()
        return -1

    # リストのoffset番目にdataを格納
    def insert(self, offset, data):
        # offsetが0もしくはリストが空の時
        if offset == 0 or not self.top:
            self.top = Cell(data, self.top)
        else:
            cell = self.top
            while cell.get_next():
                offset -= 1
                if offset == 0:
                    break
                cell = cell.get_next()
            # 新たにセルを作成し、リストに挿入する
            added_cell = Cell(data, cell.get_next())
            cell.set_next(added_cell)

    # リストのoffset番目を削除
    def delete(self, offset):
        # リストの先頭を削除
        if offset == 0:
            # リストにデータが1つ以上ある
            if self.top:
                self.top = self.top.get_next()
                return True
            else:
                return False
        else:
            cell = self.top
            while cell.get_next():
                offset -= 1
                if offset == 0:
                    # 対象のセルをリストから外す
                    cell.set_next(cell.get_next().get_next())
                    return True
                cell = cell.get_next()
            return False


def _test():
    import doctest
    doctest.testmod()


if __name__ == '__main__':
    _test()

2-1.py (重複の削除)

#encoding: utf-8
from pylist import Cell
from pylist import LinkedList


def erase_duplication(linked_list):
    '''
    リスト中の重複セルを削除
    >>> linked_list = LinkedList()
    >>> linked_list.insert(0, 100)
    >>> linked_list.insert(1, 200)
    >>> linked_list.insert(2, 300)
    >>> linked_list.insert(3, 200)
    >>> linked_list.insert(4, 100)
    >>> linked_list.insert(5, 500)
    >>> linked_list.index(500)
    5
    >>> erase_duplication(linked_list)
    >>> linked_list.index(500)
    3
    '''
    # 重複セルチェック用のハッシュテーブル
    hash_table = {}

    # 重複セルのチェック
    counter = 0
    cell = linked_list.get_top()
    while cell.get_next():
        # 重複セルは削除
        if cell.get_data() in hash_table:
            # 重複セルを削除する前に、次のセルを指定
            cell = cell.get_next()
            linked_list.delete(counter)
            counter -= 1
        else:
            hash_table[cell.get_data()] = True
            cell = cell.get_next()
        counter += 1
    # リストの最後のセルの処理
    if cell.get_data() in hash_table:
        linked_list.delete(counter + 1)


def _test():
    import doctest
    doctest.testmod()


if __name__ == '__main__':
    _test()