データ構造スタックキュー順序テーブルチェーンテーブルツリー並べ替えツリー
アルゴリズム:問題を処理して解く1種の構想あるいは思想
時間の複雑さ:アルゴリズムの実行する操作の実行のステップの数量を量子化して、最も重要な項、大きいO記法を採用します
データ構造:基本データの組織方法
pythonデータ構造のパフォーマンス分析:
スタック
プロパティ:先進的なデータ構造
キュー
特性:先進先出
ケース:手やけ芋
游戏原名:6人の子供が1つの輪に囲まれ、順番を自分で指定し、最初の子供が手に芋を持っていて、タイマーが1秒後に次の子供に渡さなければならない.順番に類推する.ルールは、タイマーが7秒ごとに、手に芋を持っている子供がゲームを終了し、このゲームは1人の子供しか残っていないときに終了し、キューを使ってこのゲーム戦略を実現する.いくつかのポジションに並んで最終的に勝つ.
デュアルエンドキュー
プロパティ:両端でデータの挿入と削除が可能な2つのヘッダと末尾があり、単一のデータ構造におけるスタックとキューのプロパティを提供します.
ケース:レビューチェックの実装
面接問題:2つのキューでスタックを形成する方法
ちくじひょう
コレクションに格納される要素は順序があり、順序テーブルの構造は単一データ型とマルチデータ型に分けられます.
リストとメタグループがマルチデータ型に属するシーケンステーブル1つの整数占有メモリが4バイトを占める
単一データ型:メモリ領域が連続的に開き、データ型が統一される
マルチデータ型シーケンシャル・テーブル:メモリが非連続的に開かれ、非連続メモリ領域を格納するアドレスが個別に開かれます.
弊害:シーケンステーブルの構造は、連続的な記憶空間を申請するためにデータサイズを予め知る必要があり、拡張時にデータの移転を行う必要がある
チェーンテーブル
シーケンステーブルのようにデータを連続的に格納するのではなく、各ノード(データ記憶ユニット)に次のノードの情報(アドレス)を格納する一般的なリニアテーブル
シーケンステーブルに対して、チェーンテーブル構造はコンピュータのメモリ空間を十分に利用でき、柔軟なダイナミックメモリ管理を実現し、拡張時にデータの移転を必要としない
二叉木
ルートノード
リーフノード:左リーフノード右リーフノード
数のレベル/数の高さ
二叉木の遍歴
広さ優先ループ:ノードを1つずつループ
深度優先パス:
前序:根左右1 2 4 5 3 7
中序:左根右4 2 5 1 6 3
後序:左右根4 5 2 6 7 3 1
ツリーのソート
乱順データの挿入には、次のガイドラインに従う必要があります.
ツリーのルートノードとして挿入された最初の数値
ルートノードより小さい場合は、ルートノードの左側を挿入します.そうでない場合は、ルートノードの右側に挿入します.
時間の複雑さ:アルゴリズムの実行する操作の実行のステップの数量を量子化して、最も重要な項、大きいO記法を採用します
データ構造:基本データの組織方法
pythonデータ構造のパフォーマンス分析:
from timeit import Timer
def test01():
alist = []
for i in range(1000):
alist = [i]
return alist
def test02():
alist = []
for i in range(1000):
alist.appned(i)
return alist
def test03():
return [i for i in range(1000)]
def test04():
alist = list(range(1000))
return alist
if __name__=="__main__":
timer1 = Timer("test01()",'from __main__ import test01')
t1 = timer1.timeit(10000)
timer2 = Timer("test02",'from __main__ import test02')
t2 = timer2.timeit(10000)
timer3 = Timer("test03",'from __main__ import test03')
t3 = timer3.timeit(10000)
timer4 = Timer("test04",'from __main__ import test04')
t4 = timer4.timeit(10000)
print(t1,t2,t3,t4)
スタック
プロパティ:先進的なデータ構造
#
class Stack():
def __init__(self):
self.items = []
def enqueue(self,item): #
self.items.append(item)
def dequeue(self): #
return self.items.pop()
def peek(self): #
return len(self.items)-1
def isEmpty(self): #
return self.items == []
def size(self): #
return len(self.items)
キュー
特性:先進先出
ケース:手やけ芋
游戏原名:6人の子供が1つの輪に囲まれ、順番を自分で指定し、最初の子供が手に芋を持っていて、タイマーが1秒後に次の子供に渡さなければならない.順番に類推する.ルールは、タイマーが7秒ごとに、手に芋を持っている子供がゲームを終了し、このゲームは1人の子供しか残っていないときに終了し、キューを使ってこのゲーム戦略を実現する.いくつかのポジションに並んで最終的に勝つ.
#! -*- encode: utf-8 -*-
# ：
#
class Queue():
def __init__(self):
self.items = []
def enqueue(self,item): #
self.items.insert(0,item)
def dequeue(self): #
return self.items.pop()
def isEmpty(self): #
return self.items == []
def size(self): #
return len(self.items)
kids = ["A","B","C","D","E","F"]
queue = Queue()
for kid in kids:
queue.enqueue(kid) # A F
while queue.size() > 1:
for i in range(6): #
kid = queue.dequeue() #
queue.enqueue(kid) # ，
queue.dequeue() # ，
print(" ：",queue.dequeue())
デュアルエンドキュー
プロパティ:両端でデータの挿入と削除が可能な2つのヘッダと末尾があり、単一のデータ構造におけるスタックとキューのプロパティを提供します.
ケース:レビューチェックの実装
#! -*- encode: utf-8 -*-
#
class Deque():
def __init__(self):
self.items = []
def addFront(self,item): #
self.items.insert(0,item)
def addRear(self,item): #
self.items.append(item)
def removeFront(self): #
return self.items.pop()
def removeRear(self): #
return self.items.pop(0)
def isEmpty(self): #
return self.items == []
def size(self): #
return len(self.items)
def isHuiWen(s):
deque = Deque()
for i in str(s):
deque.addRear(i)
while deque.size() > 0:
if deque.removeFront() != deque.removeRear():
res = False
break
else:
res = True
return res
print(isHuiWen(12345321))
面接問題:2つのキューでスタックを形成する方法
#
class Queue():
def __init__(self):
self.items = []
def enqueue(self,item): #
self.items.insert(0,item)
def dequeue(self): #
return self.items.pop()
def isEmpty(self): #
return self.items == []
def size(self): #
return len(self.items)
def travel(self):
for item in self.items:
print(item)
alist = ["1","2","3","4","5"]
queue = Queue()
for i in alist:
queue.enqueue(i)
def toStack(queue):
queue2 = Queue()
while queue.size() > 0:
while True:
item = queue.dequeue()
if queue.size() == 0:
print(item)
break
queue2.enqueue(item)
if queue.size() <= 1:
print(queue.dequeue())
break
queue,queue2 = queue2,queue
toStack(queue)
ちくじひょう
コレクションに格納される要素は順序があり、順序テーブルの構造は単一データ型とマルチデータ型に分けられます.
リストとメタグループがマルチデータ型に属するシーケンステーブル1つの整数占有メモリが4バイトを占める
単一データ型:メモリ領域が連続的に開き、データ型が統一される
マルチデータ型シーケンシャル・テーブル:メモリが非連続的に開かれ、非連続メモリ領域を格納するアドレスが個別に開かれます.
弊害:シーケンステーブルの構造は、連続的な記憶空間を申請するためにデータサイズを予め知る必要があり、拡張時にデータの移転を行う必要がある
チェーンテーブル
シーケンステーブルのようにデータを連続的に格納するのではなく、各ノード(データ記憶ユニット)に次のノードの情報(アドレス)を格納する一般的なリニアテーブル
シーケンステーブルに対して、チェーンテーブル構造はコンピュータのメモリ空間を十分に利用でき、柔軟なダイナミックメモリ管理を実現し、拡張時にデータの移転を必要としない
class Node():
def __init__(self,item):
self.item = item
self.next = None
class Link():
def __init__(self):
#
# _head
self._head = None
#
def add(self,item):
#
node = Node(item)
# next
node.next = self._head
# _head ，
self._head = node
#
def travel(self):
# _head ， ，
cur = self._head
while cur: # cur None ，
print(cur.item)
cur = cur.next
#
def size(self):
cur = self._head
count = 0
while cur:
count += 1
cur = cur.next
return count
#
def append(self,item):
node = Node(item)
#
if self._head == None:
self._head = node
return
cur = self._head
# ，
while cur.next:
cur = cur.next
cur.next = node
#
def search(self,item):
cur = self._head
while cur:
if cur.item = item:
find = True
break
else:
cur = cur.next
find = False
return find
#
def insert(self,pos,item):
if pos == 0 or pos > self.size():
print(' ')
return
node = Node(item)
pre = None
cur = self._head
for i in range(pos):
pre = cur
cur = cur.next
pre.next = node
node.text = cur
#
def remove(self,item):
cur = self._head
pre = None
while cur :
if cur.item == item:
pre.next = cr.next
return
pre = cur
cur = cur.next
#
def reverse(self):
cur = self._head
pre = None
nex = cur.next
if cur == None:
print(' ')
while cur:
cur.next = pre
pre = cur
cur = nex
if cur:
nex = cur.next
self._head = pre
return
二叉木
ルートノード
リーフノード:左リーフノード右リーフノード
数のレベル/数の高さ
class Node():
def __init__(self,item):
self.item = item
self.left = None
self.right = None
class Tree():
def __init__(self):
self.root = None
def addNode(self,item):
node = Node(item)
#
if self.root == None:
self.root = node
return
cur = self.root
q = [cur] #
while q:
nd = q.pop(0)
if nd.left == None:
nd.left = node
return
else:
q.append(nd.left)
if nd.right == None:
nd.right = node
return
else:
q.append(nd.right)
def travel(self):
cur = self.root
q = [cur]
while q:
nd = q.pop(0)
print(nd.item)
if nd.left:
q.append(nd.left)
if nd.right:
q.append(nd.right)
# ：
def forward(self,root):
if root == None:
return
print(root.item)
self.forward(root.left)
self.forward(root.right)
# ：
def middle(self,root):
if root == None:
return
self.middle(root.left)
print(root.item)
self.middle(root.right)
# ：
def back(self,root):
if root == None:
return
self.back(root.left)
self.back(root.right)
print(root.item)
二叉木の遍歴
広さ優先ループ:ノードを1つずつループ
深度優先パス:
前序:根左右1 2 4 5 3 7
中序:左根右4 2 5 1 6 3
後序:左右根4 5 2 6 7 3 1
ツリーのソート
乱順データの挿入には、次のガイドラインに従う必要があります.
ツリーのルートノードとして挿入された最初の数値
ルートノードより小さい場合は、ルートノードの左側を挿入します.そうでない場合は、ルートノードの右側に挿入します.
#
class Node():
def __init__(self,item):
self.item = item
self.left = None
self.right = None
class SortTree():
def __init__(self):
self.root = None
def add(self,item):
node = Node(item)
cur = self.root
if self.root == None:
self.root = node
return
while cur:
#
if item > cur.item:
if cur.right == None:
cur.right = node
break
else:
cur = cur.right
else: #
if cur.left == None:
cur.left = node
break
else:
cur = cur.left
# ：
def middle(self,root):
if root == None:
return
self.middle(root.left)
print(root.item)
self.middle(root.right)