必要なデータ構造
6895 ワード
二分検索を実現
ツリーを定義
ソートの選択
バブルソートの実現
キューの定義
スタックの定義
#
# : list
# :
def binarySearch(alist, item):
first = 0
last = len(alist) - 1
while first <= last:
mid = (first + last)//2
print(mid)
if alist[mid] > item:
last = mid - 1
elif alist[mid] < item:
first = mid + 1
else:
return mid+1
return -1
test = [0, 1, 2, 8, 13, 17, 19, 32, 42]
print(binarySearch(test, 3))
#4
#1
#2
#3
#-1
ツリーを定義
class BinaryTree:
def __init__(self, rootObj):
self.key = rootObj
self.leftChild = None
self.rightChild = None
def insertLeft(self, newNode):
if self.leftChild == None:
self.leftChild = BinaryTree(newNode)
else:
t = BinaryTree(newNode)
t.leftChild = self.leftChild
self.leftChild = t
def insertRight(self, newNode):
if self.rightChild == None:
self.rightChild = BinaryTree(newNode)
else:
t = BinaryTree(newNode)
t.rightChild = self.rightChild
self.rightChild = t
def getRightChild(self):
return self.rightChild
def getLeftChild(self):
return self.leftChild
def setRootVal(self, obj):
self.key = obj
def getRootVal(self):
return self.key
#
# ParseTree.py
def preorder(self):
print(self.key)
if self.leftChild:
self.leftChild.preorder()
if self.rightChild:
self.rightChild.preorder()
# r = BinaryTree('a')
# print(r.getRootVal())
# print(r.getLeftChild())
# r.insertLeft('b')
# print(r.getLeftChild())
# print(r.getLeftChild().getRootVal())
# r.insertRight('c')
# print(r.getRightChild())
# print(r.getRightChild().getRootVal())
# r.getRightChild().setRootVal('hello')
# print(r.getRightChild().getRootVal())
a
None
<__main__.binarytree object="" at="">
b
<__main__.binarytree object="" at="">
c
hello
ソートの選択
#
def selectionSort(alist):
for i in range(len(alist)-1):
min = i
for j in range(i+1, len(alist)):
if alist[j] < alist[min]:
min = j
alist[i], alist[min] = alist[min], alist[i]
return alist
alist = [54,26,93,17,77,31,44,55,20]
print(selectionSort(alist)) # [17, 20, 26, 31, 44, 54, 55, 77, 93]
バブルソートの実現
# Python
def bubbleSort(alist):
for passnum in range(len(alist)-1, 0, -1):
for i in range(passnum):
if alist[i] > alist[i+1]:
alist[i], alist[i+1] = alist[i+1], alist[i]
return alist
alist = [54,26,93,17,77,31,44,55,20]
print(bubbleSort(alist))
# , , ,
def modiBubbleSort(alist):
exchange = True
passnum = len(alist) - 1
while passnum >= 1 and exchange:
exchange = False
for i in range(passnum):
if alist[i] > alist[i+1]:
alist[i], alist[i+1] = alist[i+1], alist[i]
exchange = True
passnum -= 1
return alist
print(bubbleSort(alist))
[17, 20, 26, 31, 44, 54, 55, 77, 93]
[17, 20, 26, 31, 44, 54, 55, 77, 93]
キューの定義
class Queue:
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def enqueue(self, item):
self.items.insert(0, item)
def dequeue(self):
return self.items.pop()
def size(self):
return len(self.items)
q = Queue()
q.enqueue(4)
q.enqueue('god')
q.enqueue(True)
print(q.dequeue())
def hotPotato(namelist, num):
simqueue = Queue()
for name in namelist:
simqueue.enqueue(name)
while simqueue.size() > 1:
for i in range(num):
simqueue.enqueue(simqueue.dequeue())
simqueue.dequeue()
return simqueue.dequeue()
print(hotPotato(["Bill","David","Susan","Jane","Kent","Brad"],7))
# deque
class Deque:
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def addRear(self, item):
self.items.insert(0, item)
def addFront(self, item):
self.items.append(item)
def removeFront(self):
return self.items.pop()
def removeRear(self):
return self.items.pop(0)
def size(self):
return len(self.items)
# Deque
def palcheker(aString):
chardeque = Deque()
for ch in aString:
chardeque.addFront(ch)
stillEqual = True
while chardeque.size() > 1 and stillEqual:
first = chardeque.removeFront()
last = chardeque.removeRear()
if first != last:
stillEqual = False
return stillEqual
print(palcheker('lsdkjfskf'))
print(palcheker('radar'))
4
Susan
False
True
スタックの定義
#
class Stack():
#
def __init__(self):
self.items = []
# , True
def isEmpty(self):
return self.items ==[]
#
def push(self, item):
self.items.append(item)
#
def pop(self):
return self.items.pop()
#
def peek(self):
return self.items[len(self.items)-1]
#
def size(self):
return len(self.items)
#
s = Stack()
print(s.isEmpty())
s.push(4)
s.push('dog')
print(s.peek())
s.push(True)
print(s.isEmpty())
s.push(8.4)
print(s.pop())
print(s.pop())
print(s.size())
#
def revstring(mystr):
# your code here
s = Stack()
outputStr = ''
for c in mystr:
s.push(c)
while not s.isEmpty():
outputStr += s.pop()
return outputStr
print(revstring('apple'))
print(revstring('x'))
print(revstring('1234567890'))
# Balanced parentheses
def parChecker(symbolString):
s = Stack()
balanced = True
index = 0
while index < len(symbolString) and balanced:
symbol = symbolString[index]
if symbol in '([{':
s.push(symbol)
else:
if s.isEmpty():
balanced = False
else:
top = s.pop()
if not matches(top, symbol):
balanced = False
index += 1
if balanced and s.isEmpty():
return True
else:
return False
def matches(open, close):
opens = '([{'
closers = ')]}'
return opens.index(open) == closers.index(close)
print(parChecker('({([()])}){}'))
True
dog
False
8.4
True
2
elppa
x
0987654321
True